Zufällige Speicherung, aber das Einfügen und Löschen erfordert das Verschieben einer großen Datenmenge

statische verknüpfte Liste

zirkuläre verknüpfte Liste

Doppelt verknüpfte Liste

Einzelliste

Die Speicherverteilung kann diskontinuierlich sein Einfach einzufügen und zu löschen Die Suche muss an einem Ende beginnen

Zuerst rein, zuletzt raus, die Eingabe und Ausgabe von Elementen erfolgt am selben Ende

First in, first out, Eingabe am Ende der Warteschlange, Ausgabe am Anfang der Warteschlange

Sequentielle Speicherung und verkettete Speicherung

BF-Algorithmus

KMP-Algorithmus

Zeilenpriorität

Spalte zuerst

Triade

Angenommen, es gibt zwei Graphen. Die Eckpunkte und Kanten des einen Graphen sind eine Teilmenge der Eckpunkte und Kanten des anderen Graphen.

Ein ungerichteter Graph hat n(n-1)/2 Kanten und ein gerichteter Graph hat n(n-1) Bögen.

Sehr wenige Kanten oder Bögen

Es gibt viele Kanten oder Bögen

Aussagekräftige Werte an den Seiten. Das persönliche Verständnis kann mit dem Recht des Huffman-Baums verglichen werden

Zwei durch eine Kante verbundene Punkte sind zueinander benachbarte Punkte. Die Kante ist mit dem Scheitelpunkt verbunden und die Kante ist mit dem Scheitelpunkt verknüpft.

Bei gerichteten Graphen ist der Punkt der In-Grad und der Punkt der Out-Grad.

Ein Pfad mit denselben Start- und Endpunkten

Eine Matrix, die die Adjazenzbeziehung zwischen Scheitelpunkten darstellt

Eine verknüpfte Speicherstruktur eines Diagramms, die eine einzelne verknüpfte Liste für jeden Scheitelpunkt im Diagramm erstellt und benachbarte Scheitelpunkte in der verknüpften Liste platziert

Es handelt sich um eine weitere Kettenspeicherstruktur eines gerichteten Graphen

Es handelt sich um eine weitere Kettenspeicherstruktur eines ungerichteten Graphen

Zugriff von einem Scheitelpunkt aus Suchen Sie den ersten nicht besuchten Nachbarpunkt des gerade besuchten Scheitelpunkts und wiederholen Sie die Ausführung Gibt den zuvor besuchten Scheitelpunkt zurück, der noch nicht besuchte benachbarte Scheitelpunkte hat, und findet den nächsten nicht besuchten benachbarten Scheitelpunkt.

Zugriff von einem Scheitelpunkt aus Besuchen Sie nacheinander jeden nicht besuchten benachbarten Scheitelpunkt dieses Scheitelpunkts Besuchen Sie ausgehend von diesen benachbarten Punkten nacheinander deren benachbarte Punkte.

Prims Algorithmus

Kruskals Algorithmus

Dijkstras Algorithmus

Freuds Algorithmus

Besuchen Sie in einem gerichteten Graphen einen Scheitelpunkt ohne Vorgänger und geben Sie ihn aus Löschen Sie diesen Scheitelpunkt. Wiederholen Sie die oben genannten Vorgänge

Der längste gewichtete Pfad von einem Punkt mit Grad 0 (Quellenpunkt) zum Senkenpunkt

eine unabhängige Einheit im Baum

Die Anzahl der Teilbäume, die ein Knoten hat, wird als Grad des Knotens bezeichnet

Knoten mit dem Grad 0 werden Blätter oder Endknoten genannt

Die maximale Knotenebene im Baum wird als Tiefe oder Höhe des Baums bezeichnet

Der Grad eines Baums ist der maximale Wert des Grades jedes Knotens im Baum

Ein binärer Baum der Tiefe k, der 2∧k-1 Knoten enthält

Merkmale

Binärbaum mit Tiefe k und n Knoten Ein vollständiger Binärbaum wird genau dann als vollständiger Binärbaum bezeichnet, wenn jeder Knoten einem von 1 bis n nummerierten Knoten in einem vollständigen Binärbaum der Tiefe k entspricht.

Merkmale

Die aus dieser Knotenstruktur zusammengesetzte binäre verknüpfte Liste wird als Speicherstruktur des Binärbaums verwendet und als verknüpfte Hinweisliste bezeichnet. Die Zeiger, die auf den Vorgänger und Nachfolger des Knotens zeigen, werden als Hinweise bezeichnet ein Hinweis-Binärbaum.

Durchquerung vorbestellen

Inorder-Durchquerung

Postorder-Durchquerung

Die sogenannten ersten, mittleren und letzten beziehen sich auf den Zeitpunkt des Zugriffs auf den Wurzelknoten. Beim Durchlaufen eines Binärbaums müssen die linken und rechten Teilbäume und Wurzelknoten in einer bestimmten Reihenfolge aufgerufen werden.

Weg

Pfadlänge

Baumpfadlänge

Rechts

Die Struktur des Huffman-Baums

Huffman-Codierung

Berechnung des WPL-Wertes

Eine Sammlung von Datenelementen desselben Typs

Der Wert eines Datenelements in einem Datenelement

Bestimmen Sie anhand eines bestimmten Werts einen Datensatz oder ein Datenelement in der Nachschlagetabelle, dessen Schlüssel dem angegebenen Wert entspricht

Vergleichen Sie sie beginnend an einem Ende der Tabelle der Reihe nach

Beginnen Sie den Vergleich in der Mitte der Tabelle, führen Sie einen Halbierungsvergleich mit der größeren Hälfte durch. Wenn er kleiner ist, führen Sie einen Halbierungsvergleich mit der Hälfte durch, die kleiner als die Tabelle ist, bis die Suche erfolgreich ist es gibt kein Ergebnis.

Erstellen Sie eine Indextabelle und führen Sie sequentielle Suchvorgänge in den Blöcken entsprechend den Blöcken durch, auf die die Indextabelle verweist.

Wenn der linke Teilbaum nicht leer ist, muss er kleiner als sein Wurzelknoten sein.

Wenn der rechte Teilbaum nicht leer ist, muss er größer als sein Wurzelknoten sein.

Der linke und der rechte Teilbaum sind beide binär sortierte Bäume.

Aufgrund des binären Sortierbaums gibt es eine zusätzliche Einschränkung, d. h. der absolute Wert der Tiefendifferenz zwischen dem linken und rechten Teilbaum darf 1 nicht überschreiten.

Ist die Neuordnung einer Reihe von Datensätzen in nicht absteigender oder nicht aufsteigender Reihenfolge der Schlüsselwörter

Wenn die Sortierschlüssel unterschiedlich sind, ist das durch Sortieren der ungeordneten Reihenfolge eines Datensatzes erhaltene Ergebnis eindeutig, andernfalls ist es nicht eindeutig.

Interne Sortierung

externe Sortierung

Beim Einfügen des i-ten (i >= 1) wurden die vorherigen V[0], V[1],..., V[i-1] sortiert. Verwenden Sie zu diesem Zeitpunkt den Sortiercode von V [I], um die Reihenfolge der Sortiercodes von V [i-1], V [i-2], ... zu vergleichen, die Einfügeposition zu finden und V [i] einzufügen. , und das Element an der ursprünglichen Position wird in „Rückwärts bewegen“ eingefügt

Verwenden Sie „low“, „mid“ und „high“, um es in zwei Bereiche zu unterteilen [low, mid-1] und [mid 1, high] Wenn der Schlüsselwert kleiner als der Mittelwert in der Mitte der Sequenz ist, bedeutet dies, dass der Schlüsselwert in den linken Bereich [niedrig, mittel-1] eingefügt werden sollte und der Bereich dann wiederholt durch [niedrig, mittel-1] geteilt werden sollte. bis niedrig> hoch, und die endgültige Einfügung sollte hoch sein 1. Verschieben Sie die Daten an der Position nach hoch nach hinten als Ganzes und weisen Sie dann den Schlüssel [Mitte 1] zu.

Im Wesentlichen handelt es sich um eine Gruppeneinfügemethode, die durch kontinuierliche Verkürzung der Stofflänge sortiert.

Finden Sie nacheinander kleine oder große Elemente, indem Sie die Positionen benachbarter Elemente vergleichen und austauschen.

Dies ist eine Verbesserung gegenüber der Blasensortierung. Wählen Sie den Teilungswert aus, um ihn in zwei Teile zu teilen. Die linke Seite ist kleiner als die rechte Seite und die rechte Seite ist größer.

Suchen Sie zunächst das kleinste (große) Element in der unsortierten Sequenz und speichern Sie es am Anfang der sortierten Sequenz. Suchen Sie dann weiterhin das kleinste (große) Element aus den verbleibenden unsortierten Elementen und fügen Sie es dann am Ende ein sortierte Reihenfolge. Und so weiter, bis alle Elemente sortiert sind.

Vergleichen Sie die n zu sortierenden Elemente paarweise, nehmen Sie die kleineren heraus, vergleichen Sie dann die n/2 kleineren paarweise, nehmen Sie die kleineren heraus und wiederholen Sie die obigen Schritte, bis die minimalen Elemente herausgenommen werden.

Konstruieren Sie die Sequenz, die in einen Big-Top-Heap sortiert werden soll. Gemäß den Eigenschaften des Big-Top-Heaps ist der Wurzelknoten des aktuellen Heaps das größte Element in der Sequenz. Tauschen Sie das oberste Element des Heaps mit dem letzten Element aus und rekonstruieren Sie dann die verbleibenden Knoten in einen Big-Top-Heap usw. Ab dem ersten Mal, wenn wir den Big-Top-Heap erstellen, können wir jeweils den Maximalwert einer Sequenz ermitteln Mal bauen wir es und legen es dann ans Ende des Big Top-Stapels. Schließlich wird eine geordnete Sequenz erhalten.

Methode mit der höchsten Priorität

Methode mit der niedrigsten Priorität