CS- Woche 5

Detaillierte Erläuterung der Datenstruktur: vom Array zum Baum und dann zur Hash -Tabelle

In diesem Artikel werden mehrere gemeinsame Datenstrukturen erörtert, darunter Arrays, verknüpfte Listen, binäre Suchbäume (BSTs) und Hash -Tabellen und erklärt ihre Organisation im Gedächtnis sowie deren Vor- und Nachteile.

Informationsstruktur und abstrakte Datenstruktur

Informationsstruktur bezieht sich auf die Art und Weise, wie Informationen im Gedächtnis organisiert werden, während abstrakte Datenstrukturen unser konzeptionelles Verständnis dieser Strukturen sind. Das Verständnis abstrakter Datenstrukturen hilft uns, verschiedene Datenstrukturen in der Praxis besser zu implementieren.

---

Stapel und Warteschlange

Warteschlangen sind eine abstrakte Datenstruktur, die dem FIFO -Prinzip (zuerst in, zuerst) folgt, ähnlich wie das Warten in der Linie. Zu den Hauptvorgängen gehören Enqueinging (Hinzufügen von Elementen zum Schwanz der Warteschlange) und Dequeuing (Entfernen der Kopfelemente der Warteschlange).

Der Stapel folgt dem LIFO -Prinzip (zuletzt in erster Out), genau wie das Stapeln eines Telleres. Zu den Vorgängen gehören das Schieben (Hinzufügen von Elementen an die Spitze des Stapels) und das Knallen (Topelemente des Stapels).

---

Array

Ein Array ist eine Struktur, die Daten kontinuierlich im Speicher speichert. Wie in der folgenden Abbildung gezeigt, belegen Arrays einen kontinuierlichen Speicherplatz im Speicher.

Andere Programme, Funktionen und Variablen können im Speicher sowie redundante Daten vorhanden sein, die zuvor verwendet wurden. Wenn Sie dem Array neue Elemente hinzufügen müssen, müssen Sie den Speicher neu zuweisen und das gesamte Array kopieren, was ineffizient sein kann.

Obwohl zu viel Speicher vorab, kann es den Kopiervorgang reduzieren, aber es wird Systemressourcen ab verschwenden. Daher ist es wichtig, Gedächtnis gemäß den tatsächlichen Bedürfnissen zuzuweisen.

---

Linkliste

Verbindete Listen sind leistungsstarke Datenstrukturen, die die Verkettung von Werten in verschiedenen Speicherregionen in eine Liste ermöglichen und die dynamische Expansion oder Reduzierung unterstützen.

Jeder CS- Woche 5 enthält zwei Werte: den Datenwert und ein Zeiger auf den nächsten CS- Woche 5. Der Zeigerwert des letzten CS- Woche 5s ist null, was das Ende der verknüpften Liste angibt.

In der C -Sprache können CS- Woche 5 wie folgt definiert werden:

 <code class="c">typedef struct node { int number; struct node *next; } node;</code>

Das folgende Beispiel zeigt den Prozess des Erstellens einer verknüpften Liste:

Zu den Nachteilen verknüpfter Listen gehören die Notwendigkeit zusätzlicher Speicherspeicherzeiger und die Unfähigkeit, über Indexe direkt auf Elemente zuzugreifen.

---

Binärer Suchbaum (BST)

Ein binärer Suchbaum ist eine Baumstruktur, die Daten effizient speichert, durchsucht und abruft.

Die Vorteile von BST sind dynamisch und die Suchseffizienz (O (log n)), und der Nachteil besteht darin, dass die Suchffizienz auf o (n) fällt, wenn der Baum nicht ausbalanciert ist und zusätzliche Speicherspeicherzeiger erfordert.

---

Hash -Tisch

Eine Hash-Tabelle ähnelt einem Wörterbuch und enthält Schlüsselwertpaare. Es verwendet eine Hash -Funktion, um Tasten an Array -Indizes zu kartieren und so die durchschnittliche Suchzeit von O (1) zu erreichen.

Hash -Konflikte (mehrere Schlüssel, die demselben Index zugeordnet sind) können durch verknüpfte Listen oder andere Methoden gelöst werden. Das Design von Hash -Funktionen ist entscheidend für die Leistung von Hash -Tabellen. Ein Beispiel für eine einfache Hash -Funktion ist wie folgt:

 <code class="c">#include <ctype.h> unsigned int hash(const char *word) { return toupper(word[0]) - 'A'; }</ctype.h></code>

Dieser Artikel wird basierend auf CS50X 2024 Quellcode zusammengestellt.

Das obige ist der detaillierte Inhalt vonCS- Woche 5. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!