Wondershare EdrawMind
Mindmap-Galerie Datenstruktur-Mindmap
Datenstruktur-Mindmap
Dies ist eine Mindmap zur Datenstruktur, einschließlich der Grundkonzepte von Datenstruktur, linearen Tabellen, Stapeln und Warteschlangen usw. Hoffe das hilft!
Bearbeitet um 2023-11-07 11:40:27
- Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells
Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells? EPC (Engineering, Procurement, Construction) bedeutet, dass der Generalunternehmer für den gesamten Prozess der Planung, Beschaffung, Konstruktion und Installation des Projekts verantwortlich ist und für die Testbetriebsdienste verantwortlich ist.
- Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen
Die Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen, werden ausführlich vorgestellt und das Wissen ist umfassend. Ich hoffe, es kann für alle hilfreich sein.
- Systemanalytiker – Software-Anforderungsentwicklung
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.
Datenstruktur-Mindmap
- Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells
Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells? EPC (Engineering, Procurement, Construction) bedeutet, dass der Generalunternehmer für den gesamten Prozess der Planung, Beschaffung, Konstruktion und Installation des Projekts verantwortlich ist und für die Testbetriebsdienste verantwortlich ist.
- Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen
Die Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen, werden ausführlich vorgestellt und das Wissen ist umfassend. Ich hoffe, es kann für alle hilfreich sein.
- Systemanalytiker – Software-Anforderungsentwicklung
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.
- Für Sie empfohlen
- Gliederung
![[Studiennotizen] Datenstrukturbaum](https://edrawcloudpublicus.s3.amazonaws.com/work/5635373/2024-5-15/1715741862/thumb.png?x-oss-process=image/resize,w_300,m_lfit)
Datenstruktur
Kapitel eins Einführung
1. Grundkonzepte der Datenstruktur
1. Grundkonzepte und Terminologie
1.Daten
Der Informationsträger ist eine Sammlung von Zahlen, Zeichen und allen von Computern erkennbaren und verarbeiteten Symbolen, die die Eigenschaften objektiver Dinge beschreiben.
2. Datenelemente
Die Grundeinheit der Daten, bestehend aus Datenelementen, der kleinsten unteilbaren Einheit
3. Datenobjekte
Eine Sammlung von Datenelementen mit denselben Eigenschaften, eine Teilmenge von Daten
4.Datentyp
Eine Sammlung von Werten und eine Reihe von Operationen, die für die Sammlung definiert sind.
Atomtyp
Der Wert kann nicht geteilt werden
Strukturtyp
Der Wert kann weiter aufgeteilt werden
abstrakter Datentyp
5. Abstrakte Datentypen
1. Definition: Ein mathematisches Modell und eine Reihe von Operationen, die auf dem Modell definiert sind
2. Merkmale: Die Definition hängt nur von ihren logischen Merkmalen ab und hat nichts damit zu tun, wie sie im Computer dargestellt und implementiert wird.
3. Darstellung: (Datenobjekte, Datenbeziehungen, Grundoperationssätze)
6. Datenstruktur
1. Struktur: die Beziehung zwischen Datenelementen
2. Definition: Eine Sammlung von Datenelementen, die eine oder mehrere spezifische Beziehungen zueinander haben.
3. Inhalt: Logische Struktur, Speicherstruktur, Datenoperationen
Logische Struktur: der Entwurf eines Algorithmus
Speicherstruktur: Implementierung eines Algorithmus
2. Drei Elemente der Datenstruktur
1. Logische Datenstruktur
1. Definition: Die logische Beziehung zwischen Datenelementen, die nichts mit der Speicherung zu tun hat und unabhängig vom Computer ist.
2. Klassifizierung
lineare Struktur
linearer Tisch
Eins zu eins
nichtlineare Struktur
versammeln
Gehören zum selben Set
Baum
eins zu viele
Figur/Netzwerk
viel zu viel
2. Datenspeicherstruktur
1. Definition: Darstellung der Datenstruktur im Computer (auch Bild-/physische Struktur genannt)
2. Einschließlich: Darstellung von Datenelementen und Darstellung von Beziehungen
3. Klassifizierung
sequentielle Speicherung
Vorteile: Direkter Zugriff, Elemente belegen den geringsten Speicherplatz
Nachteile: Es kann nur ein benachbarter Block von Speichereinheiten genutzt werden, was zu einer stärkeren externen Fragmentierung führt
Kettenspeicher
Vorteile: Keine Fragmentierung
Nachteile: Speicherzeiger belegen zusätzlichen Speicherplatz; der Zugriff ist nur sequentiell möglich
Indexspeicher
Definition: Erstellen Sie eine zusätzliche Indextabelle. Jedes Element wird als Indexelement (Schlüsselwort, Adresse) bezeichnet.
Vorteile: Schneller Abruf
Nachteile: Benötigt mehr Speicherplatz; das Hinzufügen und Löschen von Daten erfordert eine Änderung der Indextabelle, was mehr Zeit in Anspruch nimmt
Hash-Speicher
Definition: Berechnen Sie direkt die Speicheradresse des Elements (Hash-Speicher) basierend auf dem Schlüsselwort des Elements
Vorteile: Das Abrufen, Hinzufügen und Löschen von Knoten erfolgt schnell
Nachteile: Wenn die Hash-Funktion nicht gut ist, kommt es zu Konflikten zwischen Elementspeichereinheiten, was den Zeit- und Platzaufwand erhöht.
3. Datenoperationen
1. Definition der Operation: Zeigen Sie die Funktion der Operation gemäß der logischen Struktur auf
2. Implementierung des Betriebs: Weisen Sie auf die spezifischen Betriebsschritte des Betriebs gemäß der Speicherstruktur hin.
Zusammenfassung der Fragen
1. Fehleranfällig
1. Gehört zu einer logischen Struktur
Bestellliste
2. Eine kreisförmige Warteschlange ist eine Warteschlange, die durch eine Sequenztabelle dargestellt wird. Es handelt sich um eine Datenstruktur, nicht um eine abstrakte Datenstruktur.
3. Die Speicherplätze verschiedener Knoten können diskontinuierlich sein, die Speicherplätze innerhalb der Knoten müssen jedoch kontinuierlich sein.
4. Zwei unterschiedliche Datenstrukturen, die logische Struktur und die physische Struktur, können genau gleich sein, aber die Datenoperationen sind unterschiedlich.
Binärbäume und binäre Sortierbäume haben unterschiedliche Zeiten für die Suche nach Knoten.
2. Algorithmen und Algorithmenbewertung
1. Grundkonzepte von Algorithmen
1. Definition: Eine Beschreibung der Schritte zur Lösung eines bestimmten Problems, eine endliche Folge von Anweisungen
2.Eigenschaften
1. Endlichkeit
2. Gewissheit
3. Machbarkeit
4.Eingabe
5.Ausgabe
3. Guter Algorithmus
1. Korrektheit
2. Lesbarkeit
3. Robustheit
4. Effizienz und geringer Lagerbedarf
2. Messung der Algorithmuseffizienz
1. Zeitkomplexität O(n)
Definition: Misst, wie schnell die Ausführungszeit eines Algorithmus mit zunehmender Größe des Problems zunimmt.
2. Raumkomplexität S(n)
1. Definition: Misst, wie schnell der vom Algorithmus benötigte Platz mit zunehmender Größe des Problems zunimmt.
2. Der Algorithmus funktioniert an Ort und Stelle: Der vom Algorithmus benötigte Hilfsraum ist konstant, dh O (1).
Zusammenfassung der Fragen
1. Fehleranfällig
1. Führen Sie zwei aufsteigend verknüpfte Listen der Länge m, n zu einer absteigend verknüpften Liste von m n zusammen (nehmen Sie das kleinere Element, Kopfinterpolationsmethode).
1. Bester Fall: O(min(m,n))
Derjenige, der weniger erfordert
2. Schlimmster Fall: O(max(m,n)) =O(m n)
Beide verknüpften Listen wurden einmal durchlaufen
2. Berechnung der Zeitkomplexität
1.sum = i;
O(n^1/2)
k-ter Zeitpunkt: Summe = 1 2 3 ... k ≥n
2.i=i*2
O(log₂n)
3. Rekursiver Algorithmus
1.T(n)=2T(n/2) n (n>1) (wenn n=1: T(n)=1)
O(nlog₂n)
2. Angenommen, n = 2 ^ k, finden Sie zuerst die allgemeine Formel von T (2 ^ k) gemäß der Rekursionsbedingung und konvertieren Sie sie dann in n, dh erhalten Sie die Zeitkomplexität
3. Für denselben Algorithmus ist die Ausführungseffizienz umso geringer, je höher die Ebene der implementierten Sprache ist.
Kapitel 2 Lineare Tabelle
1. Definition und Grundoperationen linearer Tabellen
1.Definition der linearen Tabelle
1.Definition: Endliche Folge desselben Datentyps
2. Hinweis: Lineare Listen sind logische Strukturen, sequentielle Listen und verknüpfte Listen beziehen sich auf Speicherstrukturen.
2. Grundoperationen linearer Tabellen
1. Hinweis: & stellt eine Referenz in C dar. Wenn eine Zeigervariable übergeben wird und innerhalb des Funktionskörpers geändert werden muss, muss eine Referenz auf die Zeigervariable verwendet werden (in C kann auch ein Zeiger auf einen Zeiger verwendet werden). .
2. Hauptoperationen
2. Sequentielle Darstellung linearer Tabellen
1. Definition der Sequenztabelle
1. Die Sequenztabelle erfordert drei Teile
Die Ausgangsposition des Lagerraums
Maximaler Speicherplatz der Sequenztabelle
Die aktuelle Länge der Sequenztabelle
2. Statische Zuordnung
3. Dynamische Zuordnung
4. Dynamische Zuordnungsanweisung
C-Sprache: L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
C: L.data=new ElemType[InitSize];
5. Hinweis: Bei der dynamischen Zuweisung handelt es sich nicht um einen Kettenspeicher, sondern um eine sequentielle Speicherstruktur, und die physische Struktur ändert sich nicht: Es handelt sich um eine Direktzugriffsmethode, aber die Größe des zugewiesenen Speicherplatzes kann zur Laufzeit bestimmt werden.
6. Merkmale: Direktzugriff, hohe Speicherdichte, Einfügen und Löschen erfordern das Verschieben einer großen Anzahl von Elementen
2. Implementierung grundlegender Operationen in der Sequenztabelle
1. Einfügungsoperation O(n)
2. Operation O(n) löschen
3. Suche nach Wert (sequentielle Suche) O(n)
Zusammenfassung der Fragen
1. Fehleranfällig
1. Die lineare Tabelle muss eine endliche Folge sein
2. Fügen Sie eine Zahl an der i-ten Position der Sequenztabelle ein. Der zulässige Wert von i ist: 1≤i≤n 1
Das Einfügen an der ersten Position entspricht dem Anhängen an das Ende der Tabelle
2. Algorithmus
1. Kehren Sie alle Elemente der Sequenzliste um
1. Scannen Sie die erste Hälfte und tauschen Sie das i-te Element (0 ≤ i <n/2) durch das entsprechende Element (n-i-1) in der zweiten Hälfte aus
Leerzeichen O(1)
1.1 Im Array A[m n] gibt es zwei Sequenztabellen mit den Längen m und n, deren Positionen vertauscht sind.
1. Gedanken
1. Kehren Sie zunächst die Reihenfolge aller Elemente in A um (n,n-1,...,m,m-1,...,1)
2. Verwenden Sie dann den Algorithmus in umgekehrter Reihenfolge für die ersten n Elemente bzw. die letzten m Elemente.
2. Erkenne
1. Stellen Sie die Funktion Reverse() ein, um die umgekehrte Reihenfolge von jeder linken nach rechten Position zu implementieren
2. Stellen Sie die Funktion Exchange() ein, um den Positionsaustausch zweier Sequenztabellen mit den Längen m und n zu realisieren.
3.Reverse() hat drei Parameter. Der erste ist das Array, das umgekehrt werden muss. Tauschen Sie das linke Element mit dem entsprechenden (rechts-links-1) Element aus
4.Exchange() hat drei Parameter, der erste ist Array A und die restlichen Längen sind m und n.
5.Exchange() ruft Reverse() auf und übergibt zum ersten Mal Parameter (A,0,m n-1). Das zweite Mal (A,0,n-1), das dritte Mal (A,n,m n-1)
3. Ähnliche Beschreibungen
1. Verschieben Sie die Elemente in A an die linken p-Positionen
1. Behandeln Sie die ersten p Elemente als Array B
2. Behandeln Sie die letzten n-p-Elemente als Array C
3. Vervollständigen Sie den Austausch der Positionen B und C
Zeit O(n), Raum O(1)
2. Sequentielle Liste (nicht geordnet) löscht alle Datenelemente mit dem Wert x
1. Verwenden Sie k, um die Anzahl der Elemente aufzuzeichnen, die nicht gleich x sind (Anfangswert = 0). Dies ist die aktuelle Position, die eingefügt werden soll.
2. Scannen Sie die Sequenztabelle. Wenn es nicht x ist, platzieren Sie dieses Element an der k-ten Position, und k wird um 1 erhöht.
3. Die Länge der zuletzt geänderten Tabelle = k
Zeit O(n), Raum O(1)
2.1 Sequentielle Liste (nicht geordnet) löscht alle Elemente mit Werten zwischen s und t
1. Ändern Sie einfach k, um die Anzahl der Elemente aufzuzeichnen, die kleiner als s oder größer als t sind.
3. Die geordnete Sequenzliste löscht alle Elemente zwischen den angegebenen Werten s und t
1. Finden Sie zuerst das erste Element ≥ s (das erste gelöschte Element).
2. Suchen Sie das erste Element > t (das nächste Element nach dem letzten gelöschten Element).
3. Verschieben Sie die folgenden Elemente direkt nach vorne und ändern Sie schließlich die Tabellenlänge
4. Entfernen Sie alle Elemente mit doppelten Werten aus der geordneten Liste
1. Die Idee ähnelt der direkten Einfügungssortierung. Zunächst wird das erste Element als sich nicht wiederholende geordnete Liste betrachtet.
2. Bestimmen Sie nacheinander, ob die folgenden Elemente mit dem letzten Element der vorherigen sich nicht wiederholenden geordneten Liste identisch sind
3. Zwei Zeiger: i zeigt immer auf das letzte Element der geordneten Liste, j ist der Arbeitszeiger
4.1 Ändern Sie die geordnete Liste in eine ungeordnete Liste
1. Bei Verwendung einer Hash-Tabelle ist die Zeit O(n)
5. Führen Sie zwei geordnete Listen zu einer geordneten Liste zusammen und geben Sie das Ergebnis durch die Funktion zurück
1. Die Funktion verfügt über drei Parameter. Der letzte ist die verknüpfte Ergebnisliste und der Referenztyp
2. Vergleichen Sie die Kopfelemente der beiden verknüpften Listen der Reihe nach und fügen Sie das kleinere in die neue Liste ein.
3. Überprüfen Sie, welche Tabelle noch übrig ist, und fügen Sie den verbleibenden Teil am Ende der neuen Tabelle hinzu
6. Eine aufsteigende Folge S der Länge L, der Median ist ┍L/2┑ Finden Sie den Median zweier aufsteigender Folgen gleicher Länge A und B
1. Ermitteln Sie zunächst die Mediane a und b von A bzw. B und vergleichen Sie sie.
2. Wenn a=b, dann ist a der erforderliche Median
3. Wenn a<b, verwerfen Sie die kleinere Hälfte von A und verwerfen Sie die größere Hälfte von B. Die Längen der beiden Abwürfe müssen gleich sein.
4. Wenn a>b, verwerfen Sie die größere Hälfte von A und verwerfen Sie die kleinere Hälfte von B. Es ist erforderlich, dass die Länge der beiden Abwürfe gleich ist.
5. Wiederholen Sie die Schritte 2, 3 und 4, bis beide Sequenzen nur noch ein Element enthalten und das kleinere der erforderliche Median ist.
Hinweis: Um sicherzustellen, dass die verworfenen Längen jedes Mal gleich sind
1. Wenn die Sequenz eine ungerade Zahl ist, wird der Mittelpunkt beibehalten
2. Wenn die Sequenz eine gerade Zahl ist, weil die Position des Mittelpunkts relativ zuerst ist, Wenn Sie also den kleineren Teil wegwerfen, sollten Sie den Mittelpunkt zusammen wegwerfen. Um sicherzustellen, dass die verworfene Länge dem größeren Teil entspricht
3. Die beiden Fälle 3 und 4 müssen gesondert besprochen werden.
Zeit O(log₂n), Raum O(1)
7. Wenn die Anzahl der Elemente mit dem Wert x > n/2 ist, wird es als Hauptelement bezeichnet. Finden Sie das Hauptelement von A.
1. Wählen Sie die Hauptelemente der Kandidaten aus
1. Fügen Sie die erste Zahl a als Kandidatenhauptelement in c ein und notieren Sie die Anzahl der Vorkommen von a als 1
2. Wenn das nächste Element = a ist, zähle 1, andernfalls zähle -1
3. Wenn die Anzahl auf 0 sinkt, ersetzen Sie das Kandidaten-Hauptelement, geben Sie die nächste Zahl in c ein und zählen Sie erneut = 1
4. Wiederholen Sie den Vorgang bis zum Ende
2. Bestimmen Sie, ob das Element in c das eigentliche Hauptelement ist
1. Scannen Sie erneut, um die Anzahl der Vorkommen von c zu zählen. Wenn > n/2, handelt es sich um das Hauptelement.
Zeit O(n), Raum O(1)
Hinweis: Wenn Sie die Zählsortierung verwenden: Zeit O(n), Raum O(n)
8. Finden Sie in kürzerer Zeit die kleinste positive Ganzzahl, die nicht im Array erscheint
1. Tauschen Sie Raum gegen Zeit aus, weisen Sie ein Array B [n] zum Markieren zu, zeichnen Sie auf, ob eine positive Ganzzahl von 1-n erscheint, und der Anfangswert ist alles 0
2. Für Zahlen kleiner oder gleich 0 oder größer als n wird keine Aktion durchgeführt.
3. Wenn 0<A[i]≤n, sei B[A[i]-1]=1, andernfalls wird keine Operation ausgeführt
4. Durchlaufen Sie B, finden Sie das erste B[i]==0 und geben Sie i 1 zurück. Wenn nicht alle 0 sind, geben Sie i 1 zurück (i=n beim Verlassen der Schleife).
3. Verknüpfte Darstellung einer linearen Tabelle
1. Definition einer einfach verknüpften Liste
1.Beschreibung der Knotentypen
2. Merkmale: Platzverschwendung, nicht zufälliger Zugriff
3. Der Unterschied zwischen Kopfzeiger und Kopfknoten
1. Unabhängig davon, ob ein Kopfknoten vorhanden ist oder nicht, zeigt der Kopfzeiger immer auf den ersten Knoten der verknüpften Liste.
2. Der Kopfknoten ist der erste Knoten in der verknüpften Liste mit dem Kopfknoten und speichert normalerweise keine Informationen.
4. Vorteile der Einführung von Kopfknoten
1. Die Operation an der ersten Position der verknüpften Liste stimmt mit der Operation an anderen Positionen überein.
2. Unabhängig davon, ob die verknüpfte Liste leer ist oder nicht, zeigt der Kopfzeiger auf den Nicht-Null-Zeiger des Kopfknotens, und leere Listen und nicht leere Listen werden gleich behandelt
2. Implementierung grundlegender Operationen für einfach verknüpfte Listen
1. Kopfeinfügungsmethode zum Erstellen einer verknüpften Liste
2. Erstellen Sie eine verknüpfte Liste mit der Tail-Insertion-Methode
3. Suchen Sie den Knotenwert anhand der Seriennummer
4. Suchen Sie Tabellenknoten nach Wert
5. Knotenoperation einfügen
Vorwärtseinfügungsvorgang: Suchen Sie zuerst den vorherigen Knoten. Die zeitliche Komplexität beträgt O (n).
Erweiterung: Konvertieren Sie die Vorwärtseinfügeoperation in eine Rückwärtseinfügeoperation und tauschen Sie dann die Daten der beiden Knoten aus. Die Zeitkomplexität beträgt O (1).
6. Knotenoperation löschen
Suchen Sie zuerst den Vorgängerknoten und löschen Sie dann den Knoten O(n).
Erweiterung: Zuerst Daten mit dem Nachfolgeknoten austauschen und dann den Nachfolgeknoten löschen, O(1)
7. Finden Sie die Tabellenlängenoperation
Zählen Sie die Anzahl der Datenknoten
3. Doppelt verknüpfte Liste
1. Beschreibung der Knotentypen in doppelt verknüpften Listen
2. Operation einfügen
3. Vorgang löschen
4. Zirkuläre verknüpfte Liste
1. Zirkuläre einfach verknüpfte Liste
1. Nullbedingung: Ob der Zeiger des Kopfknotens auf den Kopfzeiger zeigt
2. Wenn Sie den Kopf und das Ende einer einfach verknüpften Liste bearbeiten: Setzen Sie nicht den Kopfzeiger, sondern nur den Schwanzzeiger, was effizienter ist.
3. Sie können die gesamte verknüpfte Liste ausgehend von jedem Knoten durchlaufen
2. Zirkuläre doppelt verknüpfte Liste
Nullbedingung: Das vorherige Feld und das nächste Feld des Kopfknotens zeigen beide auf den Kopfzeiger.
5. Statische verknüpfte Liste
1. Definition: Verwenden Sie ein Array, um eine verkettete Speicherstruktur zu beschreiben, die auch über ein Datenfeld und ein Zeigerfeld verfügt. Der Zeiger ist die relative Adresse des Knotens (Array-Index), auch Cursor genannt
2.Formular
3.End-Flag: next==-1
4. Achtung
1. Wie bei der Sequenztabelle muss im Voraus ein kontinuierlicher Speicherplatz zugewiesen werden
2. Das Einfügen und Löschen erfordert nur eine Änderung des Zeigers und erfordert keine Bewegung von Elementen.
3. Sehr clever in Hochsprachen (Basic), die keine Zeiger unterstützen
6. Vergleich zwischen Sequenzliste und verknüpfter Liste
1.Zugriffsmethode
Auf die Sequenzliste kann sequentiell oder zufällig zugegriffen werden. Auf die verknüpfte Liste kann nur sequentiell vom Kopf aus zugegriffen werden.
2. Logische Struktur und physische Struktur
3. Suchen, einfügen und löschen
1. Suche nach Wert
Wenn es außer Betrieb ist, ist es O(n)
Bei Bestellung kann die Sequenztabelle in zwei Hälften durchsucht werden, O(log₂n)
2. Suche nach Seriennummer
Die Sequenzliste ist O(1), die verknüpfte Liste ist O(n)
4. Platzzuweisung
5. So wählen Sie die Speicherstruktur aus
1. Überlegungen zur Lagerung
Verknüpfte Listen werden verwendet, wenn es schwierig ist, die Länge und Speichergröße abzuschätzen, die Speicherdichte verknüpfter Listen jedoch gering ist.
2. Überlegungen basierend auf dem Betrieb
Wir verwenden häufig Sequenztabellen, um auf Datenelemente anhand der Seriennummer zuzugreifen.
3. Umweltaspekte
Sequentielle Listen sind einfach zu implementieren, verknüpfte Listen basieren auf Zeigern
Wenn es stabiler ist, wählen Sie die Sequenzliste; wenn es dynamischer ist, wählen Sie die verknüpfte Liste.
Zusammenfassung der Fragen
1. Fehleranfällig
1. Die Kettenspeicherstruktur ist praktischer als die sequentielle Speicherstruktur, um verschiedene logische Strukturen darzustellen.
2. Sequentielle Speicherung kann nicht nur zum Speichern linearer Strukturen, sondern auch der Strukturen von Diagrammen und Bäumen (vollständiger Binärbaum) verwendet werden.
3. Statisch verknüpfte Listen müssen einen großen kontinuierlichen Speicherplatz zuweisen, und für das Einfügen und Löschen sind keine beweglichen Elemente erforderlich.
4. Wenn eine einfach verknüpfte Liste zur Darstellung der Warteschlange verwendet wird, sollte eine zirkulär verknüpfte Liste mit einem Endzeiger verwendet werden.
5. Bei einem eindimensionalen Array beträgt die Mindestzeit zum Erstellen einer geordneten einfach verknüpften Liste O(nlog₂n).
Sortieren Sie zuerst das Array und erstellen Sie dann eine einfach verknüpfte Liste
6. Häufig verwendete Operationen für verknüpfte Listen sind das Einfügen nach dem letzten Element und das Löschen des ersten Elements
1. Einzelne zirkulär verknüpfte Liste ohne Kopfknoten und Endzeiger
2. Auch wenn es sich um eine doppelt verknüpfte Liste handelt, muss der Endknoten gefunden werden, solange kein Endzeiger vorhanden ist, und die Zeit beträgt O(n).
Seien Sie vorsichtig
1. Beim Einfügen eines Knotens: Arbeiten Sie zuerst am Nachfolgerknoten des eingefügten Knotens und dann am ursprünglichen Knoten
Kapitel 3 Stapel und Warteschlange
1.Stapel
1. Grundkonzept des Stapels
1. Definition des Stapels: eine lineare Liste mit Einfügung und Löschung an einem Ende
2. Eigenschaften des Stapels: Letzter rein, zuerst raus
3. Grundlegende Operationen des Stapels: Keine Einschränkungen, kann direkt verwendet werden
2. Die sequentielle Speicherstruktur des Stapels
1. Implementierung eines sequentiellen Stapels
1. Stapeloberseitenzeiger: S.top Stapeloberseitenelement: S.data[S.top]
2. Auf den Stapel verschieben: Der Zeiger wird zuerst um 1 erhöht und dann wird der Wert an das oberste Element des Stapels gesendet.
3. Öffnen Sie den Stapel: Nehmen Sie zuerst den Wert des Elements oben auf dem Stapel und dekrementieren Sie dann den Zeiger oben auf dem Stapel um 1
4. Bedingungen für leeres Urteil und vollständiges Urteil: variieren aufgrund unterschiedlicher tatsächlich gegebener Bedingungen.
2. Grundoperationen des sequentiellen Stapels
3. Gemeinsamer Stapel
1. Definition: Platzieren Sie die Unterseite der beiden Stapel an beiden Enden des gemeinsamen Raums, und die Oberseite der beiden Stapel erstreckt sich zur Mitte hin.
2. Leeres Urteil: top0=-1 top1=MaxSize
3. Vollständiger Satz: top1-top0=1
Diese Formel gilt nur unter den oben genannten Bedingungen für ein Nullurteil. Wenn die Bedingungen unterschiedlich sind, wird auch die Formel unterschiedlich sein.
4. In den Stapel schieben: top0 addiert zuerst 1 und weist dann einen Wert zu, top1 dekrementiert zuerst 1 und weist dann einen Wert zu, und beim Herausspringen aus dem Stapel ist das Gegenteil der Fall.
Hinweis: Der obere Zeiger des Stapels zeigt auf die verschiedenen Operationen des obersten Elements des Stapels und des Elements neben dem obersten Element des Stapels (S.top=0).
1. Oberstes Element des Stapels
Push into stack:S.data[S.top]=x Pop from stack:x=S.data[S.top--]
2. Das nächste Element des obersten Elements auf dem Stapel
Push into stack:S.data[S.top]=x Pop from stack:x=S.data[--S.top]
3. Die Beurteilungsbedingungen für „Stapel leer“ und „Stapel voll“ ändern sich ebenfalls.
3. Stapelkettenspeicherstruktur
1. Vorteile: Es erleichtert die gemeinsame Nutzung von Speicherplatz durch mehrere Stapel, verbessert die Effizienz und verhindert einen Stapelüberlauf.
2. Merkmale: Alle Operationen werden am Kopf der Tabelle ausgeführt. Es gibt normalerweise keinen Kopfzeiger. Der Kopfzeiger wird als oberster Zeiger des Stapels verwendet, um das Einfügen/Löschen von Knoten zu erleichtern.
4. Stack-Pop-Sequenz
1. Nach jedem Element in der Pop-Sequenz bilden alle Elemente, die kleiner sind als dieses, eine absteigende Reihe.
Für zunehmende Sequenzen
2.f(n)=
f(2)=2, f(3)=5, f(4)=14
Zusammenfassung der Fragen
1. Fehleranfällig
1. Der Stapel und die Warteschlange haben dieselbe logische Struktur, keine Speicherstruktur
Lineare Listen, Stapel und Warteschlangen sind alle lineare Strukturen.
2. Die verknüpfte Liste hat keinen Kopfknoten und alle Operationen werden am Kopf der Liste ausgeführt. Dies ist der am wenigsten geeignete Link-Stack.
1. Eine einseitig zirkulär verknüpfte Liste mit nur Kopfknotenzeigern und keinen Schwanzknotenzeigern
2. Grund: Nach dem Einfügen des Knotens muss er noch in eine kreisförmige, einfach verknüpfte Liste umgewandelt werden und der Endknoten muss gefunden werden, was O (n) Zeit in Anspruch nimmt.
3.Lösung
1. Wenn der Kopfknoten verwendet wird: Die Oberseite des Stapels nimmt den ersten Knoten und der Stapelzeiger nimmt den Kopfknoten
2. Wenn kein führender Knoten vorhanden ist: Die Oberseite des Stapels nimmt den zweiten Knoten und der Stapelzeiger den ersten Knoten.
3. Beide behalten den ersten Knoten unverändert bei und müssen das Endelement der Tabelle nicht finden.
3. Fügen Sie einen x-Knoten in einen Kettenstapel ein (ohne den Kopfknoten), dessen oberer Zeiger oben ist
x->next=top; top=x
4. Die Push-Sequenz ist 1,2,...,n und die Pop-Sequenz ist P1, P2,...,Pn. Wenn P2=3, ist die Anzahl der möglichen Werte von P3 n-1.
1. Offensichtlich können 4, 5, ..., n nach 3 erhalten werden
2.P1 kann 1 sein und P3 kann 2 sein.
3.P1 kann 2 sein und P3 kann 1 sein
4.P1 kann 4 sein und P3 kann eine beliebige Zahl außer 1, 3 und 4 sein.
5. Beim Umschreiben eines rekursiven Programms auf nicht rekursive Weise ist der Stapel möglicherweise nicht anwendbar
1. Die Berechnung der Fibonacci-Folgeniteration erfordert nur eine Schleife
6. Die Definitionen der Zeiger am Anfang des Stapels, am Anfang der Warteschlange und am Ende der Warteschlange sind nicht eindeutig. Überprüfen Sie die Frage sorgfältig.
2. Algorithmus
1. Bestimmen Sie, ob eine verknüpfte Liste zentralsymmetrisch ist
1. Schieben Sie die erste Hälfte der Elemente nacheinander auf den Stapel. Wenn Sie auf ein verknüpftes Listenelement zugreifen, entfernen Sie ein Element aus dem Stapel, um festzustellen, ob sie gleich sind.
2. Beachten Sie, dass bei geraden Zahlen keine Anomalie vorliegt. Bei ungeraden Zahlen sollte zuerst der Mittelknoten übersprungen werden.
3. Es ist kein echter Stapel erforderlich. Verwenden Sie einfach das Array als Stapel und den Arbeitszeiger i als oberen Zeiger des Stapels.
2. Warteschlange
1. Grundkonzept der Warteschlange
1. Definition: Eine lineare Tabelle, die nur das Einfügen an einem Ende der Tabelle und das Löschen am anderen Ende zulässt.
2.Grundlegende Operationen
2. Sequentielle Speicherstruktur in der Warteschlange
1. Sequentielle Speicherung in der Warteschlange
1. Zwei Zeiger: Vorne zeigt auf das Kopfelement der Warteschlange und Hinten zeigt auf die nächste Position des Endelements der Warteschlange.
2. Ausgangszustand (Team leer): Q.front==Q.rear==0
3. Geben Sie die Warteschlange ein: Senden Sie zuerst den Wert an das letzte Element der Warteschlange und fügen Sie dann 1 zum letzten Zeiger der Warteschlange hinzu.
4. Aus der Warteschlange: Nehmen Sie zuerst den Wert des Kopfelements und addieren Sie dann 1 zum Kopfzeiger
5. Es liegt ein falscher Überlauf vor
6.Typbeschreibung
2. Kreisförmige Warteschlange
1. Ausgangszustand (Team leer): Q.front==Q.rear==0
2. Bewegen Sie den vorderen Zeiger weiter: Q.front=(Q.front 1)%MaxSize
3. Bewegen Sie den Warteschlangenendzeiger weiter: Q.rear=(Q.rear 1)%MaxSize
4. Warteschlangenlänge: (Q.rear MaxSize-Q.front)%MaxSize
5. Unterscheiden Sie zwischen leeren und vollen Teams
1. Opfern Sie eine Einheit und schließen Sie sich dem Team an, um eine Einheit weniger zu verwenden (häufig verwendet).
Volle Warteschlange: (Q.rear 1)%MaxSize==Q.front
Leeres Team: Q.vorn==Q.hinten
Anzahl der Elemente in der Warteschlange: (Q.rear MaxSize-Q.front)%MaxSize
2. Fügen Sie ein Datenelement hinzu, das die Anzahl der Elemente angibt: Q.size
3. Fügen Sie Tag-Datenmitglieder hinzu: Tag = 0 Löschvorgang: Die Warteschlange ist leer, Tag = 1 Einfügevorgang: Die Warteschlange ist voll
3. Betrieb der kreisförmigen Warteschlange
3. Speicherstruktur der Warteschlangenkette
1. Warteschlangenkettenspeicher
1. Typbeschreibung
2. Einzelne verknüpfte Liste mit Kopfknoten: einheitliche Einfüge- und Löschvorgänge
3. Geeignet für Situationen, in denen sich Datenelemente stark ändern. Es gibt keinen Warteschlangenüberlauf oder eine unangemessene Speicherzuweisung in mehreren Warteschlangen.
2. Grundlegende Operationen der Kettenwarteschlange
4. Doppelendige Warteschlange
1. Definition: Eine Warteschlange, die es beiden Enden (Front-End und Back-End) ermöglicht, in die Warteschlange einzutreten und sie zu verlassen.
2. Logische Struktur: lineare Struktur
3. Geben Sie eine eingeschränkte Deque ein
4. Ausgabebeschränkte Deque
Zusammenfassung der Fragen
1. Fehleranfällig
1. Wenn Sie eine verkettete Speicherwarteschlange zum Ausführen eines Löschvorgangs verwenden, können sowohl der Kopf- als auch der Endzeiger geändert werden.
Im Allgemeinen muss nur der Kopfzeiger der Warteschlange geändert werden. Wenn nur ein Element vorhanden ist, muss der Endzeiger geändert werden.
2. Führen Sie in der Kettenwarteschlange den Vorgang aus, wenn das Element, auf das x zeigt, in die Warteschlange gelangt
1.rear->next=x,x->next=null,rear=x;
2. Da x am Ende der Warteschlange eingefügt wird, muss es auf leer gesetzt werden (mittlerer Satz), was strenger ist
2. Fragetyp
1. Bestimmen Sie den Anfangs- und Vollstatus der Ringwarteschlange
1. Array A[0...n-1], vorne zeigt auf den Kopf des Teams, hinten zeigt auf den Schwanz des Teams Die erste wird in A[0] gespeichert und fragt nach der Ausgangssituation
1. Beim Betreten der Warteschlange bewegt sich die Vorderseite nicht und die Rückseite 1 zeigt schließlich auf A[0]. Also anfänglich vorne=0, hinten=n-1
Hinweis: Wenn Sie sich mit bestimmten Problemen befassen, können Sie einige spezielle Situationen verwenden (einfache Skizzen zeichnen), um die leeren und vollständigen Situationen zu beurteilen, was schneller ist als das direkte Denken.
2. Bestimmen Sie die Sequenz, die von der doppelendigen Eingabe-/Ausgabe-beschränkten Warteschlange nicht erhalten werden kann
1. Geben Sie die 4 Optionen nacheinander direkt ein und verwenden Sie dabei die Eliminierungsmethode
2. Allgemeine Fehlersituation: Die letzte Nummer in der Warteschlange kann nicht zwischen den beiden Nummern eingeklemmt werden, die vor ihr liegen (2,3,1).
3. Anwendung von Stapel und Warteschlange
1. Anwendung des Stack-in-Bracket-Matchings
1. Gedanken
1. Richten Sie einen leeren Stapel ein und lesen Sie die Klammern nacheinander
2. Wenn dies der Fall ist, wird es aus dem Stapel entfernt, wenn es mit der Oberseite des Stapels gepaart wird (oder es ist illegal).
3. Wenn es ( ist, schieben Sie es als neue, dringlichere Erwartung auf den Stapel
4. Der Algorithmus endet und der Stapel ist leer, andernfalls stimmt die Klammersequenz nicht überein
2. Anwendung des Stapels bei der Ausdrucksauswertung
1. Postfix-Ausdruck: Der Operator steht nach dem Operanden, ohne Klammern
2. Der Prozess der Konvertierung von Infix in Suffix
1. Fügen Sie allen Operatoren und ihren Operanden entsprechend der Operatorpriorität Klammern hinzu (es ist nicht erforderlich, Klammern hinzuzufügen, wenn sie ursprünglich vorhanden waren).
2. Verschieben Sie den Operator hinter die entsprechenden Klammern
3. Entfernen Sie die Halterungen
Hinweis: Der Präfixausdruck setzt den Operator vor die Klammern, die anderen sind gleich.
3. Idee des Infix-zu-Suffix-Algorithmus
1. Zahlen: direkt zum Suffixausdruck hinzugefügt
2. Wenn ja (: Zum Stapeln drücken
3. Wenn ja: Fügen Sie die Operatoren im Stapel nacheinander zum Postfix-Ausdruck hinzu, bis ( und löschen Sie ( im Stapel
4.Wenn - */
1. Der Stapel ist leer und wird in den Stapel geschoben
2. Die Oberseite des Stapels wird ( , auf den Stapel geschoben
3. Höher als die Priorität des Elements oben auf dem Stapel, schieben Sie es auf den Stapel [wenn es die gleiche Ebene hat, führen Sie auch 4 aus]
4. Andernfalls [niedriger oder gleich der Priorität des obersten Stapels] werden die Operatoren der Reihe nach platziert, bis der Operator darunter liegt, oder (oder der Stapel ist leer) und auf den Stapel geschoben
5. Der Durchlauf ist abgeschlossen. Wenn der Stapel nicht leer ist, werden alle Elemente nacheinander angezeigt.
4. Suffixberechnungsausdrucksprozess
1. Scannen Sie jeden Term des Ausdrucks nacheinander
2. Operand: Auf den Stapel schieben
3. Operator <op>: Verlassen Sie kontinuierlich zwei Operanden x und y vom Stapel, um eine Operationsanweisung x<op>y zu bilden, und verschieben Sie das Berechnungsergebnis zurück auf den Stapel
3. Anwendung des Stapels in der Rekursion
1. Zwei Bedingungen
1. Rekursiver Ausdruck (rekursiver Körper)
2. Randbedingungen (rekursiver Ausstieg)
2. Das Wesen der Rekursion: Kann das ursprüngliche Problem in ein kleineres Problem mit denselben Eigenschaften, aber kleinerem Maßstab umgewandelt werden?
3. Nachteile: Es gibt viele Rekursionen, die leicht zu einem Stapelüberlauf führen können. Sie enthalten viele wiederholte Berechnungen und sind nicht effizient.
4. Vorteile: Der Code ist einfach und leicht zu verstehen
5. Konvertierung: Muss mithilfe des Stapels erreicht werden
4. Anwendung der Warteschlange beim hierarchischen Durchlaufen
5. Anwendung von Warteschlangen in Computersystemen
1. Lösen Sie das Problem der Geschwindigkeitsinkongruenz zwischen dem Host und externen Geräten
1. Richten Sie einen Druckdatenpuffer ein, unterbrechen Sie die Ausgabe, wenn er voll ist, erledigen Sie andere Dinge und warten Sie, bis der Drucker eine Anfrage sendet
2. Lösen Sie Ressourcenwettbewerbsprobleme, die durch mehrere Benutzer verursacht werden
1. Ordnen Sie jede Anforderung entsprechend der zeitlichen Reihenfolge in einer Warteschlange an und weisen Sie die CPU jedes Mal dem ersten Benutzer in der Warteschlange zu.
Zusammenfassung der Fragen
Unterthema
4. Komprimierte Lagerung spezieller Matrizen
1. Definition des Arrays (logische Struktur)
2. Speicherstruktur des Arrays (sequentielle Speicherung)
1. Zwei Zuordnungsmethoden: Zeile zuerst, Spalte zuerst
3. Komprimierte Speicherung von Matrizen
1. Komprimierter Speicher: Mehrere Elemente mit demselben Wert weisen nur einen Speicherplatz zu, 0 weist keinen Speicherplatz zu
2. Spezielle Matrizen: viele identische Matrixelemente oder Nullelemente, regelmäßig verteilt
1. Symmetrische Matrix
2. Dreiecksmatrix
1. Untere Dreiecksmatrix
2. Obere Dreiecksmatrix
3. Tridiagonale Matrix
4. Sparse-Matrix
1. Speicherung: Konfigurieren Sie Nicht-Null-Elemente und entsprechende Zeilen und Spalten in einem Triplett (Zeilenbezeichnung, Spaltenbezeichnung, Wert).
2. Nachteile: Verlust der Direktzugriffseigenschaften
Kapitel 4 Bäume und Binärbäume
1. Grundkonzept des Baumes
1. Definition von Baum
2.Grundlegende Terminologie
1. Knotengrad
Die Anzahl der untergeordneten Knoten eines Knotens
2. Baumgrad
Der maximale Grad eines Knotens in einem Baum
3. Tiefe des Knotens
Beginnend beim Wurzelknoten und akkumulieren Schicht für Schicht von oben nach unten.
4.Höhe des Knotens
Beginnend bei den Blattknoten und akkumulieren Schicht für Schicht von unten nach oben.
5. Baumhöhe (Tiefe)
Die maximale Anzahl von Knotenebenen im Baum
6. Der Pfad zwischen zwei Knoten
Die Folge von Knoten, die zwischen zwei Knoten verlaufen
7. Pfadlänge
Die Anzahl der auf dem Pfad durchlaufenen Kanten
8. Achtung
Die Zweige im Baum sind gerichtet (Eltern zeigen auf Kinder), der Pfad verläuft von oben nach unten und es gibt keinen Pfad zwischen zwei Kindern.
3. Natur der Bäume
1. Anzahl der Knoten = Grad aller Knoten 1
2. Die i-te Ebene eines Baums mit Grad m hat höchstens m^(i-1) Knoten.
3. Ein m-ärer Baum mit der Höhe h hat höchstens (m^h-1)/(m-1) Knoten.
Summe geometrischer Reihen
2. Konzept des Binärbaums
1. Die Definition des Binärbaums und seine Hauptmerkmale
1. Definition des Binärbaums
1. Teilbäume können in links und rechts unterteilt werden, und die Reihenfolge kann nicht beliebig umgekehrt werden.
2. Der Unterschied zwischen einem Binärbaum und einem geordneten Baum vom Grad 2
1. Ein Baum mit Grad 2 hat mindestens 3 Knoten und ein Binärbaum kann leer sein.
2. Die linke und rechte Reihenfolge der Kinder eines geordneten Baums mit Grad 2 ist relativ zu einem anderen Kind. Ein Kind muss nicht zwischen links und rechts unterscheiden. Es wird die linke und rechte Reihenfolge eines Binärbaums bestimmt
2. Mehrere spezielle Binärbäume
1. Vollständiger Binärbaum
Jede Ebene im Baum enthält die meisten Knoten
2. Vollständiger Binärbaum
1. Definition: Jeder Knoten entspricht einem vollständigen Binärbaum, nicht unbedingt dem höchsten auf jeder Ebene.
2. Natur
1. Blattknoten befinden sich nur auf den beiden größten Schichten
2. Wenn es nur einen Knoten mit Grad 1 gibt, hat der Knoten nur noch ein Kind
3. Binärer Sortierbaum
1. Die Schlüssel aller Knoten im linken Teilbaum sind kleiner als die des Wurzelknotens
2. Die Schlüsselwörter aller Knoten im rechten Teilbaum sind größer als die des Wurzelknotens
3. Der linke und der rechte Teilbaum sind jeweils ein binärer Sortierbaum.
4.Binärer ausgeglichener Baum
Der Tiefenunterschied zwischen dem linken und dem rechten Teilbaum eines Knotens überschreitet nicht 1
3. Eigenschaften von Binärbäumen
1.n0=n₂ 1
Anzahl der Blattknoten = Anzahl der Knoten mit Grad 2 1 (n=n0 n₁ n₂=n₁ 2n₂ 1)
2. Die n-te Schicht hat höchstens 2^(n-1) Knoten
3. Ein Binärbaum mit der Höhe h hat höchstens 2^h-1 Knoten.
4. Für vollständige Binärbäume
1. Der übergeordnete Knoten i/2 des Knotens i (nimm die Grenze)
2. Das linke Kind des Knotens i ist 2i und das rechte Kind ist 2i 1
3. Die Ebene, auf der sich Knoten i befindet, ist ㏒₂i (nimm die Grenze) 1
5. Die Höhe eines vollständigen Binärbaums mit n Knoten beträgt ㏒₂n (von der Grenze abgezogen) 1
2. Speicherstruktur des Binärbaums
1. Sequentielle Speicherung
1. Geeignet für vollständige Binärbäume und vollständige Binärbäume
2. Im Allgemeinen werden dem Binärbaum einige leere Knoten hinzugefügt, die nicht vorhanden sind.
3. Hinweis: Nur wenn die Speicherung ab Array-Index 1 gestartet wird, können die oben genannten Eigenschaften erfüllt werden.
Beim Schreiben eines Programms kann man es leicht ignorieren
4. Unterscheiden Sie zwischen der sequentiellen Speicherung von Bäumen und binären Bäumen
1. Im Baum: Der Array-Index ist die Knotennummer, und der Inhalt über dem Index gibt die Beziehung zwischen den Knoten an.
2. In einem Binärbaum: Der Index repräsentiert sowohl die Knotennummer als auch die Beziehung zwischen Knoten.
2. Kettenlagerung
1. Die binär verknüpfte Liste hat drei Felder: data, lchild, rchild
2. Eine binär verknüpfte Liste mit n Knoten hat n 1 leere Linkfelder (der Wurzelknoten verwendet keinen Zeiger), um eine verknüpfte Hinweisliste zu bilden.
3. Durchquerung des Binärbaums und Hinweis auf den Binärbaum
1. Durchquerung des Binärbaums
1. Durchquerung vorbestellen
2. Durchquerung in der richtigen Reihenfolge
3. Postorder-Durchquerung
Die Reihenfolge bezieht sich darauf, wann der Wurzelknoten besucht wird
4. Konvertierung rekursiver Algorithmen und nicht rekursiver Algorithmen (mittlerer Ordnung)
1. Gedanken
1. Scannen Sie zunächst alle linken Knoten des (unbesuchten) Wurzelknotens und schieben Sie sie nacheinander auf den Stapel.
2. Entfernen Sie einen Knoten vom Stapel (kein untergeordnetes Element vorhanden oder bereits besucht) und greifen Sie darauf zu
3. Scannen Sie das rechte Kind und schieben Sie es auf den Stapel
4. Scannen Sie dann alle linken Knoten des rechten Kindes und schieben Sie sie nacheinander auf den Stapel.
5. Fahren Sie so fort, bis der Stapel leer ist
2. Algorithmusimplementierung
3. Die Ausführungseffizienz nicht rekursiver Algorithmen ist höher als die rekursiver Algorithmen
5. Leveldurchquerung (Warteschlange)
1. Gedanken
1. Stellen Sie zuerst den Root-Knoten in die Warteschlange, entfernen Sie ihn dann aus der Warteschlange und greifen Sie auf den Knoten zu.
2. Wenn ein linker Teilbaum vorhanden ist, fügen Sie den Wurzelknoten des linken Teilbaums zur Warteschlange hinzu
3. Wenn ein rechter Teilbaum vorhanden ist, fügen Sie den Wurzelknoten des rechten Teilbaums zur Warteschlange hinzu.
4. Entfernen Sie dann die Warteschlange und besuchen Sie den Dequeue-Knoten
5. Wiederholen Sie den Vorgang, bis die Warteschlange leer ist
2. Algorithmusimplementierung
6. Konstruieren Sie einen Binärbaum aus der Traversierungssequenz
1. Vorbestellung und Zwischenbestellung
1. In der Vorbestellung: Der erste ist der Wurzelknoten
2. In der richtigen Reihenfolge: Der Wurzelknoten ist in zwei Teilsequenzen unterteilt, den vorderen linken Teilbaum und den hinteren rechten Teilbaum.
3. In der Vorbestellung: Finden Sie zwei Teilsequenzen, und der erste Knoten jeder Teilsequenz ist auch der Wurzelknoten.
2. Nachbestellung und Zwischenbestellung
Der letzte Knoten in der Nachbestellung entspricht dem ersten Knoten in der Vorbestellung
3. Erstbestellung und letzte Bestellung sind nicht zulässig
2. Hinweis auf den Binärbaum
1. Grundkonzepte
1.Zweck: Beschleunigung der Suche nach Knotenvorgängern und -nachfolgern
2. Vorschriften
1. Wenn es keinen linken Teilbaum gibt, zeigen Sie lchild auf den Vorgängerknoten. Wenn es keinen rechten Teilbaum gibt, zeigen Sie rchild auf den Nachfolgerknoten.
Der Vorgänger und der Nachfolger werden durch die spezifische Traversierungsmethode bestimmt.
2. Fügen Sie zwei Flag-Felder hinzu, um anzugeben, ob der aktuelle Zeiger auf den Vorgänger (1) oder das linke Kind (0) verweist.
3.Hinweis: Hinweise auf Vorgänger und Nachfolger
4. Threading: Der Prozess des Durchlaufens eines Binärbaums in einer bestimmten Reihenfolge, um ihn in einen Thread-Binärbaum umzuwandeln.
2.Bau
1. Die Essenz des Hinweisens
1. Durchlaufen Sie den Binärbaum einmal und prüfen Sie, ob die linken und rechten Zeigerfelder des Knotens leer sind. Wenn sie leer sind, ändern Sie sie so, dass sie auf die Vorgänger- und Nachfolgerhinweise zeigen.
2. In der Durchlaufsequenz in der Reihenfolge: Der erste Knoten ist der Knoten ganz links und der letzte Knoten ist der Knoten ganz rechts.
3. Vorläuferknoten
1. Der linke Zeiger ist der Hinweis, und der Knoten, auf den gezeigt wird, ist der Vorgängerknoten.
2. Der linke Zeiger ist das linke Kind, und der Knoten ganz rechts in seinem linken Teilbaum ist der Vorgängerknoten.
4. Nachfolgerknoten
1. Der rechte Zeiger ist der Hinweis, und der Knoten, auf den gezeigt wird, ist der Nachfolgerknoten.
2. Der rechte Zeiger ist das rechte Kind, und der Knoten ganz links in seinem rechten Teilbaum ist der Nachfolgerknoten.
2. Implementierung der Thread-In-Order-Traversierung
3. Manchmal wird der verknüpften Hinweisliste auch ein Kopfknoten hinzugefügt, um eine bidirektionale verknüpfte Hinweisliste zu bilden.
1.lchild zeigt auf den Wurzelknoten, rchild zeigt auf den letzten Knoten des Durchlaufs in der Reihenfolge
2. Beim Durchlaufen der Reihenfolge zeigen der erste Knoten lchild und der letzte Knoten rchild auf den Kopfknoten
3. Traverse
1. Ein nicht rekursiver Algorithmus für die Durchquerung von Binärbäumen kann mithilfe von Clue-Binärbäumen implementiert werden.
1. Erster Knoten Firstnode (Knoten ganz links) in der Mitte
2. Der Nachfolgeknoten Nextnode in der mittleren Reihenfolge
2. Algorithmusimplementierung
4.Baum, Wald
1. Baumspeicherstruktur
1. Ausdruck der Eltern
1. Definition: Kontinuierliche Speicherplatzspeicherung. Jeder Knoten fügt einen Pseudozeiger hinzu, um die Position der Eltern im Array anzuzeigen. Der Index des Wurzelknotens ist 0 und sein Pseudozeiger ist -1
2. Merkmale: Eltern können schnell erreicht werden, aber das Kind muss die gesamte Struktur durchqueren.
2. Kindervertretung
1. Definition: Verbinden Sie die Kinder jedes Knotens mithilfe einer einzelnen verknüpften Liste zu einer linearen Struktur
2. Merkmale: Es ist bequem, nach Kindern zu fragen, aber unbequem, nach Eltern zu fragen.
3. Angabe der Brüder der Kinder (linkes Kind, rechter Bruder)
1. Definition: Der linke Zeiger zeigt auf das erste Kind, der rechte Zeiger zeigt auf den ersten Bruder und die binär verknüpfte Liste wird als Speicherstruktur verwendet
2. Vorteile: Bequeme Konvertierung des Baums in einen Binärbaum, leicht zu findende untergeordnete Elemente
3. Nachteile: Es ist mühsam, Eltern zu finden. Es ist praktisch, wenn Sie Eltern hinzufügen, um auf Eltern zu verweisen.
2. Umwandlung von Bäumen, Wäldern und Binärbäumen
1. Konvertieren Sie den Baum in einen Binärbaum
Der linke Zeiger zeigt auf das erste Kind, der rechte Zeiger zeigt auf den ersten Bruder, die Wurzel hat keine Brüder und der Binärbaum hat keinen rechten Teilbaum.
2. Wald in Binärbaum umwandeln
Die Wurzel jedes Binärbaums dient als rechter Teilbaum des vorherigen Binärbaums.
3. Binärbaum in Wald umwandeln (einzigartig)
1. Die Wurzel und der linke Teilbaum des Binärbaums werden als Binärbaumform des ersten Baums verwendet und dann in einen Baum umgewandelt (das rechte Kind wird zum Bruder).
2. Der rechte Teilbaum der Wurzel und sein linkes Kind dienen als zweiter Baum, und das rechte Kind dient als dritter Baum und so weiter.
3. Durchquerung von Bäumen und Wäldern
1. Erste Wurzeldurchquerung des Baumes
Besuchen Sie zuerst die Wurzel und durchlaufen Sie dann jeden Teilbaum von links nach rechts. Dies entspricht der Wurzel-zuerst-Durchquerung des entsprechenden Binärbaums.
2. Rückwurzeldurchquerung des Baumes
Durchlaufen Sie jeden Teilbaum von links nach rechts und besuchen Sie dann die Wurzel. Dies entspricht der Durchquerung der mittleren Wurzel des entsprechenden Binärbaums.
3. Durchquerung des Waldes vorbestellen
Identisch mit der Root-First-Traversierung eines Binärbaums
4. Durchqueren des Waldes in der richtigen Reihenfolge
Entspricht der Wurzeldurchquerung im Binärbaum
4. Anwendung von Bäumen – Gewerkschaftssuche
1,3 Operationen
1.Union(S,Root1,Root2): Zwei Untersammlungen zusammenführen und Root Root2 mit Root Root1 verbinden
S[Root2]=Root1
2.Find(S,x): Suchen Sie die Wurzel des Baums, der x enthält, bis eine negative Zahl gefunden wird
while(s[x]>=0) x=S[x]; x zurückgeben;
3. Initial(en): Jedes Element in der Menge S wird als Teilmenge mit nur einem einzigen Element initialisiert (allen Elementen wird der Wert -1 zugewiesen).
2. Speicherstruktur: Übergeordnete Darstellung des Baums, der Index des Wurzelknotens ist der Name der Teilmenge, der übergeordnete Knoten des Wurzelknotens ist eine negative Zahl und die Größe ist die Anzahl der Teilmengenknoten
5. Anwendung von Bäumen und Binärbäumen
1. Binärer Sortierbaum (binärer Suchbaum BST)
1.Definition
1. Die Schlüssel aller Knoten im linken Teilbaum sind kleiner als die des Wurzelknotens
2. Die Schlüsselwörter aller Knoten im rechten Teilbaum sind größer als die des Wurzelknotens
3. Der linke und der rechte Teilbaum sind jeweils ein binärer Sortierbaum.
Durch Inorder-Durchquerung kann eine zunehmend geordnete Reihenfolge erhalten werden
2. Finden
1. Nicht rekursive Implementierung, Rekursion ist einfach, aber ineffizient
3.Einfügen
1. Der neu eingefügte Knoten muss ein Blattknoten sein (er wird nur eingefügt, wenn der Baum leer ist).
4.Bau
1. Auch wenn die eingefügten Elemente gleich, aber in unterschiedlicher Reihenfolge sind, wird die konstruierte BST unterschiedlich sein.
5.Löschen
1. Blattknoten: direkt löschen
2.i hat nur einen linken/rechten Teilbaum: Lassen Sie den Teilbaum von i zum Teilbaum des übergeordneten Knotens von i werden und die Position von i ersetzen
3. i hat links und rechts zwei Teilbäume: Ersetzen Sie i durch seinen direkten Nachfolger/Vorgänger in der Reihenfolge, löschen Sie dann den direkten Nachfolger/Vorgänger und konvertieren Sie in Fall 1,2
6. Analyse der Sucheffizienz
1. Durchschnittliche Suchlänge ASL = (Anzahl jeder Schicht * Anzahl der entsprechenden Schichten) / Gesamtzahl
2. Schlimmster Fall: ähnlich der geordneten einfach verknüpften Liste O(n)
3. Bester Fall: ausgeglichener Binärbaum O(㏒₂n)
4. Suchprozess: Ähnlich der binären Suche, aber der Entscheidungsbaum der binären Suche ist eindeutig
2. Ausgeglichener Binärbaum (AVL-Baum)
1.Definition
1. Ausgeglichener Binärbaum: Der Absolutwert des Höhenunterschieds zwischen dem linken und dem rechten Teilbaum eines Knotens überschreitet nicht 1
2. Ausgleichsfaktor: Der Höhenunterschied zwischen dem linken und rechten Teilbaum des Knotens -1,0,1
2. Einfügen (zuerst einfügen und dann anpassen)
1. Das Ziel jeder Anpassung ist der minimale unausgeglichene Teilbaum
2.LL ausgewogene Rotation (rechte Einzelrotation)
0.A ist der Wurzelknoten des minimalen unausgeglichenen Teilbaums. Stellen Sie sicher, dass A eindeutig gefunden wird.
1. Grund: Ein neuer Knoten (kann links oder rechts sein) wird in den linken Teilbaum L von B, das linke Kind von A, eingefügt, und der Teilbaum mit A als Wurzel ist aus dem Gleichgewicht geraten.
2.Methode
1. Drehen Sie das linke untergeordnete Element B von A nach rechts oben und ersetzen Sie A als Wurzelknoten.
2.A dreht sich nach unten nach rechts und wird zum Wurzelknoten des rechten Teilbaums von B.
3. Der ursprüngliche rechte Teilbaum von B wird als linker Teilbaum von A verwendet
3.RR ausgewogene Rotation (linke Einzelrotation)
4.LR ausgewogene Drehung (doppelte Drehung zuerst nach links und dann nach rechts)
1. Grund: Ein neuer Knoten (kann links oder rechts sein) wird in den rechten Teilbaum c des linken Kindes B von A eingefügt, und der Teilbaum mit A als Wurzel ist aus dem Gleichgewicht geraten.
2.Methode
1. Drehen Sie den Wurzelknoten c des rechten Teilbaums von A's linkem Kind B nach links und nach oben bis zur Position des B-Knotens.
2. Drehen Sie dann den C-Knoten nach rechts oben und heben Sie ihn auf die Position des A-Knotens an.
5.RL ausgewogene Drehung (rechts und dann links doppelte Drehung)
3. Finden
1. Die maximale Tiefe eines ausgeglichenen Binärbaums mit n Knoten beträgt O(㏒₂n) und die ausgeglichene Suchlänge beträgt O(㏒₂n)
3. Huffman-Baum und Huffman-Codierung
1.Definition
1. Die gewichtete Pfadlänge (WPL) des Knotens
Das Produkt aus der Pfadlänge (Anzahl der Kanten) vom Wurzelknoten zu einem beliebigen Knoten und dem Gewicht des Knotens
2. Gewichtete Pfadlänge des Baums
Die Summe der gewichteten Pfadlängen aller Blattknoten
3. Huffman-Baum (optimaler Binärbaum)
Binärbaum mit minimaler gewichteter Pfadlänge
2.Bau
1.Bauprozess
1. Wählen Sie die beiden Knoten mit den kleinsten Gewichten aus, um einen neuen Knoten zu erstellen. Das Gewicht ist die Summe der beiden Knoten.
2. Wählen Sie dann den verbleibenden Knoten mit dem kleinsten Gewicht aus, konstruieren Sie ihn mit dem neuen Knoten und wiederholen Sie den Vorgang
2.Eigenschaften
1. Die Anfangsknoten sind alle Blattknoten. Je kleiner das Gewicht, desto größer die Pfadlänge zum Wurzelknoten.
2. Erstellen Sie n-1 neue Knoten, insgesamt 2n-1 Knoten
3. Es gibt keinen Knoten mit Grad 1
3. Huffman-Codierung
1. Kodierung mit fester Länge
Verwenden Sie für jedes Zeichen eine binäre Darstellung derselben Länge
2. Codierung mit variabler Länge
Verwenden Sie binäre Bits unterschiedlicher Länge, um unterschiedliche Zeichen darzustellen
3. Präfixkodierung
Keine Kodierung ist ein Präfix einer anderen Kodierung
4.Huffman-Codierungsprozess
Die auf dem Pfad vom Wurzelknoten zum Zeichen markierte Sequenz: 0 geht an das linke Kind, 1 geht an das rechte Kind
Kapitel 5 Bild
1. Grundkonzepte von Graphen
1. Definition des Diagramms
0.G=(V,E),V(G): Endliche nichtleere Menge von Eckpunkten E(G): Kantenmenge |V|: Anzahl der Eckpunkte (Reihenfolge des Graphen) |E|: Anzahl der Kanten
0,1 Hinweis: Die lineare Tabelle kann eine leere Tabelle sein und der Baum kann ein leerer Baum sein, aber das Diagramm kann kein leeres Diagramm sein: Die Scheitelpunktmenge darf nicht leer sein und die Kantenmenge kann leer sein.
1. Gerichteter Graph
<v,w>: Bogen von v nach w (v grenzt an w/w grenzt an v) v: Bogenende w: Bogenkopf
2. Ungerichteter Graph
(v,w)=(w,v)
3. Einfaches Diagramm
Es gibt keine doppelten Kanten und es gibt keine Kanten vom Scheitelpunkt zu sich selbst.
4.Mehrere Diagramme
Es gibt doppelte Kanten und Kanten von Scheitelpunkten zu sich selbst.
5. Vollständiges Diagramm (einfaches vollständiges Diagramm)
1. Ungerichteter vollständiger Graph: Es gibt n(n-1)/2 Kanten zwischen zwei beliebigen Eckpunkten.
2. Gerichteter vollständiger Graph: Zwei beliebige Scheitelpunkte haben zwei Bögen in entgegengesetzte Richtungen, n(n-1)
6. Unterbild
Untergraphen generieren: Untergraphen mit demselben Scheitelpunktsatz
7. Verbundener, verbundener Graph, verbundene Komponenten (ungerichteter Graph)
1. Maximal verbundener Teilgraph (zusammenhängende Komponente): Ein verbundener Teilgraph enthält alle Kanten, nicht unbedingt alle Eckpunkte (nicht unbedingt ein verbundener Graph).
2. Minimal verbundener Untergraph: Ein Untergraph, der die Graphkonnektivität beibehält und gleichzeitig die Anzahl der Kanten minimiert (kann ein einzelner Scheitelpunkt sein)
Minimum, Maximum relativ zur Seite
8. Stark verbundener Graph, stark verbundene Komponente (gerichteter Graph)
9. Spannender Baum, Spannender Wald
1. Spannender Baum eines verbundenen Graphen; ein minimal verbundener Teilgraph, der alle Eckpunkte enthält (n Eckpunkte haben n-1 Kanten)
2. In einem nicht verbundenen Diagramm bildet der Spannbaum verbundener Komponenten den Spannwald des nicht verbundenen Diagramms.
10. Scheitelpunktgrad, In-Grad, Out-Grad
1. Grad eines Scheitelpunkts: die Anzahl der Kanten mit dem Scheitelpunkt als Endpunkt
1. Knotengrad
Die Anzahl der untergeordneten Knoten eines Knotens
2. In einem ungerichteten Graphen: die Summe der Grade aller Eckpunkte = Anzahl der Kanten * 2
3. In einem gerichteten Graphen: der Grad eines Scheitelpunkts = Ein-Grad und Aus-Grad, die Summe der Ein-Grade aller Scheitelpunkte = die Summe der Aus-Grade = die Anzahl der Kanten
11. Rechte Seite, Netz
1. Gewichtetes Bild (netto): ein Bild mit Gewichten an der Seite
12. Dichtes Diagramm, spärliches Diagramm
13. Pfad, Pfadlänge, Schleife
1. Schleife/Schleife: Der Pfad, bei dem der erste Scheitelpunkt und der letzte Scheitelpunkt gleich sind
14. Einfacher Pfad, einfache Schleife
1. Einfacher Pfad: Ein Pfad, in dem Scheitelpunkte nicht wiederholt vorkommen
2. Einfache Schleife: Mit Ausnahme des ersten Scheitelpunkts und des letzten Scheitelpunkts erscheinen die anderen Scheitelpunkte nicht wiederholt.
15. Entfernung
1. Wenn der kürzeste Weg von v nach w existiert, ist er eine Entfernung. Wenn er nicht existiert, wird er als unendlich aufgezeichnet.
16. Gerichteter Baum
1. Ein gerichteter Graph, in dem der In-Grad eines Scheitelpunkts 0 und der In-Grad der anderen Scheitelpunkte 1 ist.
2. Bildspeicherung und Grundfunktionen
1. Adjazenzmatrixmethode (sequentiell)
1.Definition
1. Ein eindimensionales Array speichert Scheitelpunktinformationen und ein zweidimensionales Array speichert Kanteninformationen.
2.Eigenschaften
1. Ungerichteter Graph/gerichteter Graph: Die Anzahl der Nicht-Null-Elemente in der i-ten Zeile ist der Grad/Out-Grad des i-ten Scheitelpunkts
2. Es ist leicht zu bestimmen, ob es Kanten gibt, aber es ist schwierig zu bestimmen, wie viele Kanten es gibt.
3. Dichte Graphen eignen sich für die Verwendung von Adjazenzmatrizen
4.Aⁿ[i][j]: Die Anzahl der Pfade der Länge n vom Scheitelpunkt i zum Scheitelpunkt j
2. Adjazenzlistenmethode (Link)
1.Definition
1. Kombinieren Sie sequentiellen und verknüpften Speicher, um eine einfach verknüpfte Liste für jeden Scheitelpunkt i zu erstellen
2. Scheitelpunkttabelle: Zeiger des Scheitelpunktfelds (Daten) auf die erste Adjazenzliste (firstarc)
3. Kantentabelle: Adjazenzpunktfeld (adjvex) Zeigerfeld, das auf die nächste Adjazenzliste zeigt (nextarc)
2.Eigenschaften
1. Ungerichteter Graph: Speicherplatz O(|V| 2|E|) gerichteter Graph: O(|V| |E|)
2. Verwenden Sie die Adjazenzlistenmethode, um in Diagrammen mit geringer Dichte Platz zu sparen
3. Vernetzte Liste (gerichteter Graph)
1.Definition: Ein Kettenspeicher eines gerichteten Graphen
2. Struktur
1. ArcNode: 5 Domänen
1. Schwanzbereich (Tailvex), Kopfbereich (Headvex): Zeigt den Bogenschwanz und den Bogenkopf an
2. Kettendomäne hlink, tlink: Zeigt den nächsten Bogen mit demselben Bogenkopf/Bogenende an
<v,w>: Bogen von v nach w (v grenzt an w/w grenzt an v) v: Bogenende w: Bogenkopf
3.Info-Feld: bogenbezogene Informationen
2. Scheitelpunktzeiger (VNode): 3 Felder
1. Datenfeld: Scheitelpunktdateninformationen (Scheitelpunktname)
2. First-In-Domäne, First-Out-Domäne: Nehmen Sie diesen Scheitelpunkt als ersten Knoten des Bogenkopfes/Bogenendes
3. Hinweis: Scheitelpunktknoten werden sequentiell gespeichert
3.Eigenschaften
1. Es ist einfach, den Bogen mit vi als Schwanz und den Bogen mit vi als Kopf zu finden. Es ist einfach, den Außen-/Innengrad des Scheitelpunkts zu ermitteln.
2. Es bedeutet, dass es nicht eindeutig ist, aber ein Diagramm bestimmt.
4. Adjazenz-Mehrfachliste (ungerichteter Graph)
1.Definition: Ein weiterer Kettenspeicher eines ungerichteten Graphen
2. Struktur
1. Jede Kante wird durch einen Knoten dargestellt
1. Flag-Feld markieren: Ob diese Kante durchsucht wurde
2.ivex,jvex: Die Positionen der beiden an der Kante im Diagramm befestigten Scheitelpunkte
3.ilink,jlink: zeigt auf die nächste Kante, die an den Scheitelpunkt ivex/jvex angehängt ist
4.Info: Zeigerfeld für verschiedene Informationen
2. Der Scheitelpunkt wird durch einen Knoten dargestellt
1. Datenfeld: verwandte Informationen zu Scheitelpunkten
2. Firstedge-Domäne: Die erste Kante, die an den Scheitelpunkt angehängt ist
3.Eigenschaften
1. An denselben Scheitelpunkt angehängte Kanten werden in derselben verknüpften Liste verbunden, und jeder Kantenknoten ist gleichzeitig in zwei verknüpften Listen verknüpft.
2. Jede Kante hat nur einen Knoten
5. Grundlegende Operationen von Graphen
1. Unabhängig von der Speicherstruktur des Diagramms weisen verschiedene Speichermethoden unterschiedliche Leistungen auf
2. Spezifische Operationen
3. Graphdurchquerung
1. Breitensuche (BFS)
1.Definition
Ein hierarchischer Durchlaufalgorithmus ähnlich einem Binärbaum, der dem frühesten entdeckten Knoten Priorität einräumt.
2. Gedanken
1. Besuchen Sie zunächst den Startscheitelpunkt v
2. Besuchen Sie nacheinander alle nicht besuchten benachbarten Eckpunkte von v
3. Beginnen Sie dann mit diesen Scheitelpunkten und besuchen Sie alle ihre nicht besuchten Knoten.
3. Beschreibung des Algorithmus
1. Hierarchische Suche, der Vorwärtszugriff auf einen Knotenstapel ist im Gegensatz zur Tiefensuche, bei der eine Rückwärtssituation vorliegt, nicht rekursiv
2. Verwenden Sie das Hilfsmarkierungsarray der Warteschlange (unabhängig davon, ob der Scheitelpunkt besucht wird).
3. Algorithmusimplementierung
4.Leistungsanalyse
1. Raumkomplexität: O(|V|)
Mithilfe der Hilfswarteschlange werden Scheitelpunkte einmal in die Warteschlange gestellt
2. Zeitkomplexität
1. Adjazenzliste: O(|V| |E|)
2. Adjazenzmatrix: O(|V|²)
Die Essenz der Graphendurchquerung: der Prozess, die benachbarten Punkte für jeden Scheitelpunkt zu finden
5.BFS löst das Problem des kürzesten Pfades aus einer Hand
5. Breitenorientierter Spannbaum
1. Definition: Ein Traversierungsbaum, der während der Breitentraversierung erhalten wird
2. Merkmale: Eindeutig in der Adjazenzmatrix, nicht eindeutig in der Adjazenzliste
Das Gleiche gilt für DFS
2. Tiefensuche (DFS)
1.Definition
Ähnlich wie bei der Vorbestellungsdurchquerung eines Baums erhält der zuletzt entdeckte Knoten Priorität.
2. Gedanken
1. Besuchen Sie zunächst den Startscheitelpunkt v
2. Besuchen Sie einen beliebigen nicht besuchten benachbarten Scheitelpunkt w von v
3. Besuchen Sie dann einen beliebigen nicht besuchten benachbarten Scheitelpunkt w2 von w
4. Wiederholen Sie diesen Vorgang, bis Sie nicht mehr nach unten gelangen können, und kehren Sie der Reihe nach zu den zuletzt besuchten Eckpunkten zurück.
3. Beschreibung des Algorithmus
1. Ausgehend von einem Scheitelpunkt unter Verwendung einer rekursiven Form
2. Algorithmusimplementierung
4.Leistungsanalyse
1. Raumkomplexität: O(|V|)
Verwendung eines rekursiven Arbeitsstapels
2. Zeitkomplexität
1. Adjazenzliste: O(|V| |E|)
2. Adjazenzmatrix: O(|V|²)
5. Tiefenspannender Baum/Wald (nicht verbundener Graph)
3. Graphdurchquerung und Graphkonnektivität
1. Ungerichteter Graph
1. Verbunden: Besuchen Sie alle Scheitelpunkte in einer Durchquerung
2. Nicht verbunden: Besuchen Sie alle Eckpunkte verbundener Komponenten in einer Durchquerung
2. Gerichteter Graph
1. Wenn es einen Pfad vom Anfangsscheitelpunkt zu jedem Scheitelpunkt gibt, kann auf alle Scheitelpunkte zugegriffen werden, andernfalls nicht
3. Dem Algorithmus wird eine zweite for-Schleife hinzugefügt, und dann wird der Anfangspunkt ausgewählt.
Die erste for-Schleife initialisiert die Scheitelpunkte auf FLASE
4. Ungerichteter Graph: Die Anzahl der Aufrufe von BFS oder DFS = die Anzahl der verbundenen Komponenten des Graphen
4. Anwendung von Diagrammen
1. Minimaler Spanning Tree (MST)
1.Definition
Der Spannbaum mit der kleinsten Summe der Kantengewichte
2.Eigenschaften
1. Die Baumform ist nicht eindeutig, die Summe der Kantengewichte ist eindeutig
2. Anzahl der Kanten = Anzahl der Eckpunkte - 1
3. Allgemeine Gedanken
Wenn T keinen aufspannenden Baum bildet, suchen Sie nach einer Kante mit minimalen Kosten, und nach dem Hinzufügen von T wird keine Schleife generiert
4. Zwei Algorithmen
1.Prim-Algorithmus (Prim)
1. Gedanke (vom Scheitelpunkt ausgehend)
1. Initialisierung: Wählen Sie zunächst einen beliebigen Scheitelpunkt als Anfangsscheitelpunkt aus
2. Schleife (bis alle Scheitelpunkte enthalten sind): Wählen Sie dann die Kante mit dem geringsten Gewicht unter den benachbarten Kanten dieses Scheitelpunkts aus und bilden Sie keinen Kreis.
3. Wählen Sie dann unter den benachbarten Kanten der beiden Scheitelpunkte die Kante mit dem geringsten Gewicht aus, die keine Schleife bildet.
2.Eigenschaften
1. Zeitkomplexität: O(|V|²), hängt nicht von |E| ab, geeignet für Diagramme mit dichten Kanten
2.Kruskal-Algorithmus (Kruskal)
1. Gedanke (zunehmendes Gewicht)
1. Initialisierung: Schließen Sie zunächst alle Scheitelpunkte ein, keine Kanten
2. Schleife (bis daraus ein Baum wird): Wählen Sie Kanten in der Reihenfolge zunehmender Gewichtung aus, ohne einen Zyklus zu bilden, bis n-1 Kanten enthalten sind
2.Eigenschaften
1. Verwenden Sie einen Heap zum Speichern von Kantensätzen mit einer zeitlichen Komplexität von O(|E|log|E|), der für Diagramme mit spärlichen Kanten und vielen Eckpunkten geeignet ist.
2. Kürzester Weg
1.Dijkstras Algorithmus, um den kürzesten Weg aus einer einzigen Quelle zu finden
1. Hilfsvariablen
1. Set S: Zeichnet die Eckpunkte des kürzesten Pfades auf, die gefunden wurden, und der Anfangswert ist 0
2.dist[]: Zeichnen Sie die aktuelle (kontinuierlich aktualisierte) kürzeste Pfadlänge vom Quellpunkt v0 zu anderen Eckpunkten auf. Der Anfangswert ist arcs[v0][i].
3. Pfad []: Pfad [i] ist der Vorgängerknoten des kürzesten Pfads vom Quellpunkt zu i, und sein Wert kann auf den kürzesten Pfad von v0 nach vi zurückgeführt werden.
2. Gedanken
1. Initialisierung: Die Menge S ist {0}, dist[] ist der Abstand vom Anfangsscheitelpunkt 0 zu jedem Scheitelpunkt und es gibt keine Unendlichkeit. Der anfängliche Scheitelpunkt 0 in path[] ist -1 (immer unverändert), der Abstand von 0 zu anderen Punkten ist 0 und der Abstand von 0 zu anderen Punkten ist unendlich.
2. Wählen Sie den Punkt j mit dem kleinsten verbleibenden Wert in dist[]. Wenn dist[j] arcs[j][k]<dist[k] ist, aktualisieren Sie dist[k] Fügen Sie diesen Punkt zur Menge S hinzu. Wenn dist[k] aktualisiert wird, sei path[k]=j
3. Wiederholen Sie die Operation für die verbleibenden Punkte in der Menge S, bis S alle Punkte enthält
3.Eigenschaften
1. Die Zeitkomplexität einer einzelnen Quelle beträgt O(|V|²) und die aller Knotenpaare beträgt O(|V|³)
2. Der Algorithmus gilt nicht, wenn an den Kanten negative Gewichte vorhanden sind.
2. Floyds Algorithmus findet den kürzesten Weg zwischen Eckpunkten
1. Gedanken
1. Erzeugen Sie rekursiv eine quadratische Matrixfolge n-ter Ordnung, beginnend von A﹣¹ bis Aⁿ﹣¹
Hochgestellte Matrix plus Klammern
2.Anfangs: Wenn es eine Kante zwischen zwei beliebigen Scheitelpunkten gibt, wird das Gewicht als kürzester Weg betrachtet. Wenn es keine Kante gibt, ist es unendlich.
3. Fügen Sie später schrittweise den Scheitelpunkt k (k von 0 bis n-1) als Zwischenscheitelpunkt zum ursprünglichen Pfad hinzu. Wenn der Pfad abnimmt, ersetzen Sie den ursprünglichen Pfad.
4.A(k)[i][j]: Vom Scheitelpunkt i bis zum Scheitelpunkt j die Länge des kürzesten Pfades, dessen Zwischenknotennummer nicht größer als k ist
2.Eigenschaften
1. Zeitkomplexität: O(|V|³)
2. Kanten mit negativem Gewicht sind zulässig und Kanten mit negativem Gewicht dürfen keine Schleife bilden.
3. Gilt für gewichtete ungerichtete Graphen, die als gerichtete Graphen mit doppelten Kanten mit Rundlauf angesehen werden
3. Topologische Sortierung
1. Gerichteter azyklischer Graph (DAG-Graph)
In gerichteten Graphen gibt es keine Kreise
2. Der Scheitelpunkt repräsentiert das aktive Netzwerk (AOV-Netzwerk)
Das DAG-Diagramm stellt ein Projekt dar, die Scheitelpunkte stellen Aktivitäten dar und die gerichteten Kanten <vi, vj> stellen dar, dass Aktivität i vor Aktivität j vorausgehen muss
3. Topologische Sortierung (im DAG-Diagramm)
1.Definition
1. Jeder Scheitelpunkt kommt nur einmal vor
2. Wenn A vor B liegt, gibt es keinen Weg von B nach A.
2. Implementierungsmethode
1. Wählen Sie einen Scheitelpunkt ohne Vorgänger aus dem DAG-Diagramm aus und geben Sie ihn aus
2. Löschen Sie den Scheitelpunkt und alle von ihm ausgehenden gerichteten Kanten
3. Wiederholen Sie die Schritte 1 und 2, bis das Diagramm leer ist/es keinen Knoten ohne Vorgänger gibt (es muss ein Zyklus im Diagramm vorhanden sein).
3.Eigenschaften
1. Zeitkomplexität O(|V| |E|)
Scheitelpunkte ausgeben und Kanten entfernen
4. Achtung
1. Das Projekt kann von einem Scheitelpunkt mit Ingrad 0 beginnen
2. Ein Scheitelpunkt hat mehrere direkte Nachfolger und das Ergebnis ist normalerweise nicht eindeutig.
3. Die Adjazenzmatrix ist eine Dreiecksmatrix und es gibt eine topologische Sortierung, aber nicht unbedingt umgekehrt. Die Scheitelpunktzahlen können entsprechend den Sortierergebnissen neu angeordnet werden, und die Adjazenzmatrix ist eine Dreiecksmatrix.
4. Kritischer Pfad
1. Verwenden Sie Kanten, um aktive Netzwerke darzustellen (AOE-Netzwerk)
1.Definition
Scheitelpunkte stellen Ereignisse dar, gerichtete Kanten stellen Aktivitäten dar und Gewichte stellen Kosten (Zeit) dar.
2. Zwei Eigenschaften
1. Nachdem das durch den Scheitelpunkt dargestellte Ereignis eingetreten ist, können die Aktivitäten beginnen, die durch die gerichteten Kanten ausgehend vom Scheitelpunkt dargestellt werden.
2. Nur wenn alle Aktivitäten, die durch gerichtete Kanten dargestellt werden, die in einen bestimmten Scheitelpunkt eintreten, enden, kann das durch den Scheitelpunkt dargestellte Ereignis eintreten.
2. Mehrere Konzepte
1. Startscheitelpunkt (Quellpunkt): Es gibt nur einen Scheitelpunkt mit In-Grad 0, den Anfang des gesamten Projekts
2. Endscheitelpunkt (Senke): Es gibt nur einen Scheitelpunkt mit einem Out-Grad von 0, der das Ende des gesamten Projekts darstellt.
3. Kritischer Pfad: Der Pfad mit der maximalen Pfadlänge
4. Kritische Aktivitäten: Aktivitäten auf dem kritischen Pfad
5. Mindestzeit: Länge des kritischen Pfades
3. Mehrere Parameter
1. Der früheste Auftrittszeitpunkt Ve(k) des Ereignisses vk
1. Definition: Die längste Weglänge vom Scheitelpunkt V bis Vk bestimmt den frühesten Startzeitpunkt aller Aktivitäten ab Vk
2. Ermittlungsmethode: Addieren Sie Gewichte vom Quellpunkt rückwärts und nehmen Sie den Maximalwert verschiedener Pfade.
Alle Aktivitäten müssen abgeschlossen sein, bevor die Veranstaltung beginnen kann. Nehmen Sie den Maximalwert an.
2. Der späteste Auftrittszeitpunkt Vl(k) des Ereignisses vk
1. Definition: Der späteste Zeitpunkt, zu dem dieser Zeitpunkt erreicht wird, ohne dass sich die Fertigstellung des gesamten Projekts verzögert
2. So finden Sie es: Vl (Sinkpunkt) = Ve (Sinkpunkt), subtrahieren Sie die Gewichte vom Sinkpunkt nach vorne und nehmen Sie den Minimalwert verschiedener Pfade
Nehmen Sie den Mindestwert, um sicherzustellen, dass das gesamte Projekt nicht verzögert wird.
3. Der früheste Auftrittszeitpunkt e(i) der Aktivität ai
1. Definition: Der früheste Eintrittszeitpunkt des Ereignisses, dargestellt durch den Startpunkt der Aktivität
2. So finden Sie: <Vk, Vj> stellt die Aktivität ai dar, dann ist e(i)=Ve(k)
4. Der späteste Auftrittszeitpunkt l(i) der Aktivität ai
1. Definition: Die Differenz zwischen dem Zeitpunkt des letzten Auftretens des Ereignisses, das durch den Endpunkt der Aktivität dargestellt wird, und der für die Aktivität erforderlichen Zeit
2. So finden Sie: <Vk,Vj> repräsentiert die Aktivität ai,l(i)=Vl(j)-Weight(Vk,Vj)
5. Der Unterschied in den Aktivitäten d(i)=l(i)-e(i)
4. Kritischer Pfad
Die Aktivitäten mit der Differenz d()=0 unter allen Aktivitäten bilden den kritischen Pfad
Kapitel 6 Suche
1. Grundkonzepte der Suche
1. Nachschlagetabelle (Nachschlagestruktur): Datensammlung, die für die Suche verwendet wird
2. Geeignet für statische Nachschlagetabellen: sequentielle Suche, halbe Suche, Hash-Suche
3. Geeignet für dynamische Nachschlagetabellen: Binäre Sortierbäume, Hash-Suche, binäre ausgeglichene Bäume und B-Bäume sind alles Verbesserungen von binären Sortierbäumen.
4. Durchschnittliche Suchlänge (ASL)
2. Sequentielle Suche und binäre Suche
1. Sequentielle Suche (lineare Suche)
1. Sequentielle Suche nach allgemeinen linearen Tabellen
1. Eigenschaften des Algorithmus
1. Führen Sie den Sentinel (das erste Element des Arrays) ein und suchen Sie von hinten nach vorne. Es ist nicht erforderlich, zu beurteilen, ob das Array die Grenze überschreitet, was die Programmeffizienz verbessert.
2. Vor- und Nachteile
1. Nachteile: Wenn n groß ist, ist die Effizienz gering
2. Vorteile: Es gibt keine Anforderungen an die Speicherung von Datenelementen und keine Anforderungen an die Ordnung.
3. Leistung
1.ASL-Erfolg=(n 1)/2
2.ASL fehlgeschlagen=n 1
Füge einen Wachposten hinzu
2. Sequentielle Suche in geordneter Liste
1. Entscheidungsbaum: Kreisförmige Knoten sind Existenzknoten, rechteckige Knoten sind Fehlerknoten (Intervall), n Erfolge müssen n 1 Fehlerknoten haben
2. Die Suchlänge zum Erreichen des ausgefallenen Knotens = die Anzahl der Schichten eines darüber liegenden kreisförmigen Knotens
3. Nur ASL-Fehler sind unterschiedlich = (1 2 ... n n)/n 1
Die letzten beiden ausgefallenen Knoten liegen auf der gleichen Ebene, beide sind n
2. Halbsuche (binäre Suche)
1. Eigenschaften des Algorithmus
1. Schleifenbedingung: low≤high stellt sicher, dass am Ende alle auf denselben Wert zeigen, andernfalls muss eine Zahl weniger gesucht werden.
2.mid=(low high)/2 entspricht dem Entfernen der Grenzen
2.Leistung
1. Zeitkomplexität: O(log₂n)
2.ASL: Anzahl der Schichten pro Schicht * Anzahl der Knoten pro Schicht / Anzahl der Zusammenfassungspunkte, n Schicht hat 2ⁿ﹣¹ Knoten
3. Blocksuche (Suche nach Indexreihenfolge)
1. Eigenschaften des Algorithmus
1. Nutzen Sie die jeweiligen Vorteile der sequentiellen Suche und der binären Suche, haben Sie eine dynamische Struktur und sind für die schnelle Suche geeignet.
2. Gedanken
1. In mehrere Unterblöcke unterteilt, können die Blöcke ungeordnet und die Blöcke geordnet werden.
2. Das größte Schlüsselwort im ersten Block < alle Datensätze im zweiten Block usw
3. Erstellen Sie eine Indextabelle, die das größte Schlüsselwort jedes Blocks und die Adresse des ersten Elements jedes Blocks enthält, sortiert nach Schlüsselwörtern
3. Suchvorgang
1. Bestimmen Sie den Block in der Indextabelle und suchen Sie nacheinander/halbiert
2. Suchen Sie nacheinander innerhalb des Blocks
4. Leistung
ASL=Indextabellen-ASL Intrablock-ASL
Zusammenfassung der Fragen
1. Fehleranfällig
1. Die Geschwindigkeit der Halbwertsuche ist jetzt im Allgemeinen schneller. In besonderen Fällen kann die sequentielle Suche schneller sein.
2. Zeitleistung der binären Suche und des binären Sortierbaums
1. Die halbe Suche wird durch einen binären Entscheidungsbaum gemessen und ASL ist immer O(log₂n)
2. Der binäre Sortierbaum hängt mit der Eingabereihenfolge der Daten zusammen. Der schlimmste Fall ist O (n).
3. Bei der Suche nach der Hälfte ist der Mittelwert begrenzt
2.Formel
1. Die Höhe des binären Entscheidungsbaums: ┎log₂(n 1)┒ oder ┕log₂n┙ 1
1. Handelt es sich um einen ausgeglichenen Binärbaum mit Höhenunterschieden von höchstens 1 oder um einen binären Sortierbaum?
2. Die Anzahl der Vergleiche erfolgloser Knoten (die Differenz überschreitet nicht 1)/die maximale Anzahl der Vergleiche
3. Gesamtzahl der Knoten n=2^h-1
2. Die optimale Blocklänge der Indexsequenztabelle mit n Datensätzen:
Alle werden nacheinander durchsucht, die Blocklänge ist b, die Indextabelle ASL = (n/b 1)/2, die Intrablock-ASL = (b 1)/2 und die Grundungleichung wird für die Addition verwendet
3. Sequentielle Suche ASL=(n 1)/2, Indexsuche ASL=Indextabellen-ASL Intrablock-ASL
3. Fragetyp
1. Bestimmen Sie, ob es sich bei einem Baum um einen Entscheidungsbaum für die binäre Suche handelt
Nehmen Sie den letzten zu vergleichenden Knoten (die mittlere Position des Baums) und bestimmen Sie, ob die Ober- und Untergrenze konsistent ist (Sie können die Ober- und Untergrenze auch zuerst anhand des Wurzelknotens bestimmen).
2. Verwenden Sie eine Idee ähnlich der Satzsuche direkt in der geordneten Liste: W252
Die Suchlänge innerhalb eines Blocks ist für jedes Segment unterschiedlich
4.Wissenspunkte
1.k-Punkt-Suchmethode: Die zeitliche Komplexität von Erfolg und Misserfolg beträgt O(logk(n))
Die Tiefe eines k-ary-Baums mit n Knoten beträgt ┕logk(n)┙ 1
2. Wenn die Suchwahrscheinlichkeiten unterschiedlich sind, ist die sequentielle Suche am effektivsten
Sortieren Sie in absteigender Reihenfolge der Suchwahrscheinlichkeit
3.B-Baum und B-Baum
1.B-Baum und seine Grundoperationen
1.Definition
0.B-Baum (ein ausgeglichener Mehrpfad-Suchbaum mit einem Ausgleichsfaktor von 0 für alle Knoten), die maximale Anzahl untergeordneter Knoten entspricht der Reihenfolge des B-Baums (m).
1. Jeder Knoten hat höchstens m Teilbäume (höchstens m-1 Schlüsselwörter)
2. Wenn der Wurzelknoten kein Endknoten ist, gibt es mindestens zwei Teilbäume und 1 Schlüsselwort
3. Alle Nicht-Blattknoten außer dem Wurzelknoten haben mindestens ┎m/2┒ Teilbäume und mindestens ┎m/2┒-1 Schlüsselwörter.
4. Alle Nicht-Blattknotenstrukturen
1. Schlüsselwörter sind in aufsteigender Reihenfolge angeordnet
2. Alle Zahlen im linken Teilbaum <entsprechen dem Schlüsselwort, alle Zahlen im rechten Teilbaum> entsprechen dem Schlüsselwort
5. Alle Blattknoten befinden sich auf derselben Ebene, ohne Informationen (externe Knoten/Fehlerknoten).
2. Die Höhe von Baum B
1. Mindesthöhe
Jeder Knoten hat höchstens m Teilbäume und m-1 Schlüsselwörter
h≥logm(n 1) n≤(m-1)(1 m m² ... m^(h-1))=m^h-1
2. Maximale Höhe
Die erste Schicht hat mindestens einen Knoten, die zweite Schicht hat mindestens 2 Knoten, die dritte Schicht hat mindestens 2┎m/2┒,... und die erste Schicht hat mindestens 2┎m/2┒^ (h-1) Knoten
Die h1-te Schicht ist ein Blattknoten (Fehlerknoten), die Anzahl beträgt n 1 (Anzahl der Intervalle) und es gibt n-1 Fehlerknoten für n Schlüsselwörter.
n 1≥2┎m/2┒^(h-1)
3. B-Baum-Suche
Ähnlich einem binären Suchbaum
4.Einfügung in den B-Baum
1. Positionierung: Muss auf der untersten Ebene in einen Nicht-Blattknoten eingefügt werden
2.Einfügen
1. Die Anzahl der Schlüsselwörter für jeden nicht ausgefallenen Knoten liegt innerhalb von [┎m/2┒-1,m-1]
2. Wenn die Anzahl der Schlüsselwörter nach dem Einfügen <m ist, fügen Sie direkt> m-1 ein und teilen Sie den Knoten
3. Aufteilungsmethode
1. Teilen Sie den ursprünglichen Knoten nach dem Einsetzen des Schlüssels ab der Mittelposition ┎m/2┒ in zwei Teile
2. Der Knoten an der mittleren Position ┎m/2┒ wird in den übergeordneten Knoten eingefügt und der linke und rechte Teil werden als linker und rechter Teilbaum verwendet.
3. Wenn der übergeordnete Knoten ebenfalls die Obergrenze überschreitet, teilen Sie ihn weiter, bis er den Wurzelknoten erreicht. Die B-Baum-Höhe beträgt 1
5. Löschung des B-Baums
1. Am Endknoten
1. Schlüsselwörter direkt löschen
Anzahl der Schlüsselwörter>┎m/2┒-1
2. Brüder sind genug
1. Die Anzahl der Schlüsselwörter = ┎m/2┒-1 und die Schlüsselwörter der benachbarten rechten (linken) Geschwisterknoten sind >┎m/2┒
2. Eltern-Kind-Transpositionsmethode: Einer der Elternknoten tritt in den gelöschten Knoten ein, und einer der Geschwisterknoten tritt in den Elternknoten ein.
3. Nicht genügend Brüder zum Ausleihen (Fusionsmethode)
1. Die Anzahl der Schlüsselwörter = ┎m/2┒-1 und die Schlüsselwörter der benachbarten rechten (linken) Geschwisterknoten = ┎m/2┒-1
2. Zusammenführungsmethode: Führen Sie einen der übergeordneten Knoten mit einem der Geschwisterknoten zusammen, um den gelöschten Knoten zu ersetzen. Der übergeordnete Knoten hat ein Schlüsselwort weniger.
3. Wenn der übergeordnete Knoten der Wurzelknoten ist und auf 0 reduziert wird, löschen Sie den Wurzelknoten direkt und der neue Knoten wird nach dem Zusammenführen zur Wurzel.
4. Der übergeordnete Knoten ist nicht der Wurzelknoten und wird auf ┎m/2┒-2 reduziert und dann angepasst oder mit seinen Brüdern zusammengeführt (zuerst ausleihen, wenn genug verfügbar ist).
2. Nicht am Endknoten
1. Wenn die Anzahl der Schlüsselwörter im linken Teilbaum >┎m/2┒-1 ist, ersetzen Sie k durch den Vorgängerknoten von k (den Knoten ganz rechts im linken Teilbaum) und löschen Sie dann k rekursiv
2. Wenn die Anzahl der Schlüsselwörter im rechten Teilbaum >┎m/2┒-1 ist, ersetzen Sie k durch den Nachfolgeknoten von k (den Knoten ganz links im rechten Teilbaum) und löschen Sie dann k rekursiv
3. Wenn die Anzahl der Schlüsselwörter im linken und rechten Teilbaum = ┎m/2┒-1 ist, führen Sie die beiden Teilbäume direkt zusammen und löschen Sie k direkt
2. Grundkonzept des B-Baums
1.Definition
1. Jeder Zweigknoten hat höchstens m Teilbäume (Kindknoten)
2. Der Nicht-Blatt-Wurzelknoten hat mindestens zwei Teilbäume, und alle Nicht-Blattknoten außer dem Wurzelknoten haben mindestens ┎m/2┒ Teilbäume
3. Die Anzahl der Teilbäume eines Knotens = die Anzahl der Schlüsselwörter
Im B-Baum: Anzahl der Teilbäume eines Knotens = Anzahl Schlüsselwörter 1
4. Alle Blattknoten enthalten alle Schlüsselwörter (in der richtigen Reihenfolge angeordnet) und Zeiger auf entsprechende Datensätze, und benachbarte Blattknoten sind entsprechend ihrer Größe miteinander verknüpft.
5. Alle Verzweigungsknoten (Indizes, die als Indizes betrachtet werden können) enthalten nur den Maximalwert der Schlüsselwörter in jedem ihrer untergeordneten Knoten und Zeiger auf die untergeordneten Knoten.
2.Eigenschaften
1. Zwei Kopfzeiger: Einer zeigt auf den Wurzelknoten und der andere zeigt auf den Blattknoten mit dem kleinsten Schlüsselwort
2. Zwei Suchvorgänge: Suche anhand der minimalen Schlüsselwortreihenfolge/Mehrwegsuche vom Wurzelknoten aus
3. Hinweis: Bei der Suche endet die Suche nicht, wenn der Nicht-Blattknoten dem angegebenen Wert entspricht. Die Suche wird nach unten bis zum Blattknoten fortgesetzt. Unabhängig davon, ob die Suche erfolgreich ist oder nicht, handelt es sich um einen Pfad vom Wurzelknoten zum Blattknoten.
Zusammenfassung der Fragen
1. Fehleranfällig
1. Wenn die Anzahl der Schlüsselwörter in einem Knoten ≠ die Anzahl der Teilbäume ist, darf es sich nicht um einen B-Baum handeln
2. Alle Nicht-Blattknoten außer dem Wurzelknoten haben mindestens ┎m/2┒ Teilbäume und mindestens ┎m/2┒-1 Schlüsselwörter.
Achten Sie besonders auf den Wurzelknoten: Es gibt mindestens zwei Teilbäume und 1 Schlüsselwort
3. Wenn der B-Baum nach dem Einfügen geteilt wird, beträgt die Höhe nicht 1, solange der Wurzelknoten nicht geteilt wird
2.Formel
1. Mindesthöhe: h≥logm(n 1)
2. Maximale Höhe: n 1≥2┎m/2┒^(h-1)
3.Wissenspunkte
1. Für einen B-Baum dritter Ordnung: Wenn die Anzahl der Knoten am kleinsten ist, ähnelt er einem vollständigen Binärbaum. Wenn die Anzahl der Knoten am größten ist, ähnelt er einem vollständigen Ternärbaum.
Zusammenfassungspunkte=m^h-1
2.B-Baum wird für den Dateiindex/Datenbankindex verwendet
4.Hash-Tabelle
1. Grundkonzepte von Hash-Tabellen
1. Hash-Funktion
Die Funktion, die Schlüsselwörter den entsprechenden Adressen zuordnet, wird als Hash(key)=addr aufgezeichnet (kann Array-Index/Index/Speicheradresse sein)
2. Konflikt
Zwei oder mehr unterschiedliche Schlüsselwörter werden derselben Adresse zugeordnet
3. Synonyme
Kollision verschiedener Schlüsselwörter
4.Hash-Tabelle
Eine Datenstruktur, auf die direkt anhand von Schlüsselwörtern zugegriffen wird, idealerweise O(1)
2. Konstruktionsmethode der Hash-Funktion
0. Aufmerksamkeitspunkte
1. Die Definitionsdomäne muss alle Schlüsselwörter enthalten und der Wertebereich hängt von der Größe/dem Adressbereich der Hash-Tabelle ab
2. Adressen sollten gleich wahrscheinlich und gleichmäßig verteilt sein.
3. Machen Sie die Funktion so einfach wie möglich und berechnen Sie sie in kurzer Zeit
1. Direktadressierungsmethode
1. Funktion: H(Taste)=a*Taste b
2. Merkmale: Kein Konflikt, geeignet für die grundsätzlich kontinuierliche Verteilung von Schlüsselwörtern
2. Division mit Restmethode
1. Funktion: H(key)=key%p
2. Auswahl von P: Die Primzahl p, die nicht größer als m (Hash-Tabellenlänge) ist, aber am nächsten zu oder gleich m ist
3. Digitale Analysemethode
1. Wählen Sie als Hash-Adresse eine Anzahl von Bits mit einer relativ gleichmäßigen digitalen Verteilung
2. Funktionen: Geeignet für Sammlungen bekannter Schlüsselwörter
1. Die mittleren Ziffern des Quadratwerts werden als Hash-Adresse verwendet
2. Anwendbar auf Situationen, in denen die Werte jedes Bits nicht einheitlich genug sind/weniger als die Anzahl der für die Hash-Adresse erforderlichen Bits sind.
5. Faltmethode
1. Teilen Sie das Schlüsselwort in mehrere Teile mit der gleichen Anzahl von Ziffern und verwenden Sie die Überlagerungssumme als Hash-Adresse.
2. Geeignet für eine große Anzahl von Ziffern und die Ziffern auf jedem Bit sind ungefähr gleichmäßig verteilt.
3. Möglichkeiten, mit Konflikten umzugehen
1. Offenes Adressgesetz
0.Definition
1. Kostenlose Adressen stehen sowohl Synonymen als auch Nicht-Synonymen offen
2. Rekursionsformel: Hi=[H(key) di]%m, di: inkrementelle Sequenz
1. Lineare Erkennungsmethode
1.Definition: di=0,1,2,...,m-1
2. Merkmale: Bewirkt, dass sich eine große Anzahl von Elementen an benachbarten Hash-Adressen ansammelt, was die Sucheffizienz verringert.
2. Quadratische Erkennungsmethode (sekundäre Erkennungsmethode)
1. Definition: di=0²,1²,-1²,2²,-2²,...,k²,-k²
2.Eigenschaften
1. Vorteile: Kann Akkumulationsprobleme vermeiden
2. Nachteil: Nur die Hälfte der Zellen kann erkannt werden
3.Rehashing-Methode (Doppel-Hashing-Methode)
1. Definition: di=Hash₂(Schlüssel), Hi=[H(Schlüssel) i*Hash₂(Schlüssel)]%m
i ist die Anzahl der Konflikte
2.Eigenschaften
1. Verwenden Sie die zweite Hash-Funktion, um das Adressinkrement zu berechnen
2. Alle Positionen können bis zu m-1-mal erfasst werden
4. Pseudozufallssequenzmethode
1.Definition: di=Pseudozufallsfolge
5. Achtung
1. Sie können vorhandene Elemente nicht nach Belieben physisch löschen, da dadurch die Suchadressen anderer Elemente mit derselben Hash-Adresse abgeschnitten werden.
2. Kann zum Löschen und logischen Löschen markiert werden
3. Nebenwirkungen: Nach mehreren Löschungen scheint die Hash-Tabelle sehr voll zu sein, tatsächlich gibt es jedoch noch viele ungenutzte Speicherorte und erfordert regelmäßige Wartung.
2. Reißverschlussmethode (Link-Methode)
1. Definition: Alle Synonyme werden in einer linear verknüpften Liste gespeichert und durch eine Hash-Adresse eindeutig identifiziert
2. Geeignet für häufige Einfügungs- und Löschsituationen und kann direkt physisch gelöscht werden
4. Hash-Suche und Leistungsanalyse
1. Suchvorgang
0.Initialisierung: Addr=Hash(Schlüssel)
1. Prüfen Sie, ob auf Adr. ein Eintrag vorhanden ist
1. Kein Datensatz, Suche fehlgeschlagen
2. Es liegt ein Datensatz vor und die Gleichheitssuche ist erfolgreich. Warten Sie auf die Ausführung. 2
2. Berechnen Sie die „nächste Hash-Adresse“ mithilfe der angegebenen Konfliktbehandlungsmethode, setzen Sie Addr auf diese Adresse und übertragen Sie sie auf 1
2. Sucheffizienz
1. Hängt ab von: Hash-Funktion, Methode zur Kollisionsbehandlung, Ladefaktor
2. Füllfaktor (α): definiert, wie voll eine Tabelle ist
α=Anzahl der Datensätze in der Tabelle n/Hash-Tabellenlänge m
3. Die durchschnittliche Suchlänge hängt von α ab und hängt nicht direkt von n oder m ab.
Zusammenfassung der Fragen
1. Fehleranfällig
1. K Synonyme werden mithilfe der linearen Erkennung in die Hash-Tabelle gefüllt, was K (K 1)/2-fache Erkennung erfordert.
1 2...K
2. Die Konfliktwahrscheinlichkeit ist proportional zur Größe des Belastungsfaktors
Je voller es ist, desto wahrscheinlicher ist es, dass es zu Konflikten kommt.
3. Die Hash-Funktion kann nicht mit einer Zufallszahlenfunktion erstellt werden und normale Suchvorgänge können nicht durchgeführt werden.
2. Wissenspunkte
1. Ursachen der Akkumulation
Sondensequenzen für Synonymkonflikte und verschiedene Sondensequenzen für Nichtsynonyme sind miteinander verflochten
2. Durchschnittliche Anzahl von Erkennungen = durchschnittliche Suchlänge
3. Fragetyp
1. ASL-Erfolg
Anzahl der Suchen = Anzahl der Konflikte 1
2. ASL ist fehlgeschlagen
Bestimmen Sie die insgesamt erforderlichen Suchpositionen basierend auf der Hash-Funktion und suchen Sie nach jeder Position, bis sie leer ist. Verwenden Sie die entsprechende Konfliktbehandlungsmethode, um erneut zu suchen. Wenn sie leer ist, muss sie ebenfalls verglichen werden.
5. Spieße
1. Definition einer Zeichenfolge
1. Leerzeichenfolge: Besteht aus einem oder mehreren Leerzeichen, keine leere Zeichenfolge
2. Lineare Tabellen verwenden ein einzelnes Element als Operationsobjekt und Zeichenfolgen verwenden Teilzeichenfolgen als Operationsobjekt.
2. String-Speicherstruktur
1. Sequentielle Speicherdarstellung mit fester Länge
1. Ordnen Sie ähnlich wie bei der sequentiellen Speicherung linearer Tabellen Arrays mit fester Länge zu
2. Kürzung: Zeichenfolgenwerte, die die vordefinierte Länge überschreiten, werden verworfen.
2. Darstellung des Heap-Zuordnungsspeichers
1. Verwenden Sie malloc() und free() zum dynamischen Zuweisen und Löschen
3. Darstellung des Blockchain-Speichers
1. Verknüpfter Speicher, ähnlich einer linearen Liste, jeder Knoten kann ein oder mehrere Zeichen enthalten
3. Grundlegende Operationen von Strings
1. Minimale Teilmenge der Operationen (5): kann nicht mit anderen String-Operationen implementiert werden
1.String-Belegung: StrAssigh
2.String-Vergleich: StrCompare
3. String-Verbindung: Concat
4. Ermitteln Sie die Zeichenfolgenlänge: StrLength
5. Suchen Sie den Teilstring: SubString
4. String-Matching-Muster
1.Definition: Positionierungsvorgang eines Teilstrings
2. Gedanken
1. Beginnen Sie mit dem Pos-Zeichen der Hauptzeichenfolge und vergleichen Sie es mit dem ersten Zeichen der Musterzeichenfolge
2. Wenn sie gleich sind, vergleichen Sie die nachfolgenden Zeichen einzeln weiter.
3. Wenn die Werte nicht gleich sind, starten Sie den Vergleich erneut ab dem nächsten Zeichen der Hauptzeichenfolge.
3. Effizienz
Schlechteste Zeitkomplexität: O(mn)
5. Verbesserter Mustervergleichsalgorithmus-KMP-Algorithmus
1. Zeichenfolgenpräfixe und teilweise übereinstimmende Werte
1. Präfix: Alle Header-Teilzeichenfolgen außer dem letzten Zeichen (kann nur an der ersten Position beginnen)
2. Suffix: Alle nachfolgenden Teilzeichenfolgen außer dem ersten Zeichen (kann nur an der letzten Position beginnen)
3. Teilweiser Übereinstimmungswert: Die längsten Präfix- und Suffixlängen sind gleich
2. Effizienz
1. Zeitkomplexität: O(m n)
3. Lösen Sie das nächste Array (manuell)
1. Nächster Array-Wert = längste gleiche Präfix- und Suffixlänge 1
2. Die Zeichenfolge selbst kann nicht als Präfix oder Suffix verwendet werden.
3. Normalerweise next[1]=0 (abhängig von der spezifischen Frage, wenn es -1 ist, wird immer noch 0 für die Berechnung verwendet, und schließlich sind alle Zahlen -1)
4. Wenn das i-te Element in next[i] nicht übereinstimmt, beträgt die Zeichenfolgenlänge i-1, ohne das i-te Element.
5. Wenn die Zeichenfolge lang ist, können Sie nur die ersten paar zählen, um die Antwort zu erhalten.
Zusammenfassung der Fragen
1.Wissenspunkte
1.Der größte Vorteil des KMP-Algorithmus
Die Hauptzeichenfolge wird nicht zurückverfolgt, der i-Zeiger bewegt sich nicht, j=next[j]
2. Fragetyp
1. Eine schnelle Möglichkeit, next[] zu lösen, vorausgesetzt, dass next[n] gerade gelöst wird, next[n-1]=m
0.Standardmäßig next[1]=0, next[2]=1
Der Index kann auch bei 0 beginnen und der Zahlenwert kann auch bei -1 beginnen.
1. Die Zeichenfolge hat n-1 Zeichen und die letzten m Zeichen, dann ist next[n]=m 1, gehe zu 3
2. Wenn sich die ersten m Zahlen von den letzten m Zahlen unterscheiden, wenn m=1, dann next[n]=1, gehe zu 3. Andernfalls sei m = m-1 und vergleiche dann das erste m-1 und das letzte m-1. Wenn sie gleich sind, gehe zu 1, wenn sie unterschiedlich sind, gehe zu 2.
3. Beenden Sie den Vorgang
2.KMP-Matching-Prozess
Wenn der Wert von next[] bei 0 beginnt, beginnt die tiefgestellte Zahl bei 1. Wenn keine Übereinstimmung vorliegt, bewegt sich der i-Zeiger nicht, j=next[j]
3. Fehleranfällig
1. Während der Prüfung müssen Sie unterscheiden, ob der next[]-Wert bei 0 oder 1 beginnt
Kapitel 7 Sortieren
1. Grundkonzepte des Sortierens
1. Definition der Sortierung
1. Die Stabilität eines Algorithmus kann nicht die Qualität eines Algorithmus messen.
2. Interne Sortierung: Alle Elemente werden im Speicher abgelegt
3. Externe Sortierung: ständiger Wechsel zwischen Speicher und externem Speicher
Zusammenfassung der Fragen
1. Fehleranfällig
1. Der in der Sequenzliste implementierte Sortieralgorithmus ist möglicherweise nicht in der verknüpften Liste implementiert.
2. Wenn Sie zum Sortieren derselben linearen Tabelle unterschiedliche Sortiermethoden verwenden, können die erhaltenen Sortierergebnisse unterschiedlich sein.
2.Formel
1. Die Mindestanzahl an Vergleichen zum Sortieren beliebiger n Schlüsselwörter beträgt ┍log₂(n!)┑
2. Einfügungssortierung
1. Direkte Einfügungssortierung
1. Gedanken
1. Gehen Sie davon aus, dass das erste Element sortiert wurde
2. Beginnen Sie mit dem zweiten Element und vergleichen Sie es der Reihe nach mit dem vorherigen. Wenn der sofortige Austausch nicht ausreicht, sortieren Sie die bereits angeordneten Elemente an Ort und Stelle und verschieben Sie sie wiederholt nach hinten.
2.Eigenschaften
1. Kopieren Sie A[0] als Sentinel, um Indizes außerhalb der Grenzen zu vermeiden, die Zuweisung zu erleichtern und die Notwendigkeit zu beseitigen, temporäre Variablen zu beantragen.
2. Vergleichen und gleichzeitig verschieben
3.Leistungsanalyse
1. Zeiteffizienz
1. Bester Fall: O(n)
Muss jedes Mal nur einmal verglichen werden, kein Umzug erforderlich
2. Worst Case: O(n²)
2. Anwendbarkeit
Sowohl Sequenz als auch Kette sind geeignet. Die meisten Algorithmen sind nur für Sequenzen geeignet.
4. Algorithmusimplementierung
2. Sortierung nach halber Einfügung
1. Gedanken
1. Zuerst in der Mitte falten, um die Position zu finden, an der das Element eingefügt werden soll.
2. Verschieben Sie alle Elemente nach der einzufügenden Position einheitlich
2.Eigenschaften
1. Nur die Anzahl der Vergleichselemente wird reduziert und die Anzahl der Züge hat sich nicht geändert.
2. Die Anzahl der Vergleiche hat nichts mit dem Ausgangszustand zu tun, sondern nur n
3.Leistungsanalyse
1. Zeitkomplexität: O(n²)
Es bezieht sich nur auf die Anzahl der Bewegungen (zweistufige for-Schleife) und hat nichts mit der Anzahl der Vergleiche zu tun. Der Vergleich ist nur eine in der for-Schleife abgeschlossene Operation.
2. Stabil
4. Algorithmusimplementierung
3. Hill-Sortierung (Reduzierung der inkrementellen Sortierung)
1. Gedanken
1. Nehmen Sie zunächst die Schrittgröße als n/2, teilen Sie sie in mehrere Gruppen auf und verwenden Sie in jeder Gruppe die direkte Einfügungssortierung.
2. Reduzieren Sie die Schrittweite um die Hälfte und fahren Sie fort, bis die Schrittweite 1 beträgt
2.Eigenschaften
1. Die beste inkrementelle Sequenz wurde noch nicht gefunden und die zeitliche Komplexität kann nicht berechnet werden.
3.Leistungsanalyse
1. Zeiteffizienz
Schlimmster Fall: O(n²)
2. Instabil
Dieselben Schlüsselwörter können in verschiedene Untertabellen unterteilt werden
4. Algorithmusimplementierung
Zusammenfassung der Fragen
1. Fehleranfällig
1. Die zeitliche Komplexität der Halbeinfügungssortierung beträgt O(n²)
3. Börsensortierung
1. Blasensortierung
1. Gedanken
1. Vergleichen Sie ausgehend vom letzten Element die beiden benachbarten Elemente. Wenn sie in umgekehrter Reihenfolge sind, tauschen Sie sie aus.
2. Eine Blasenoperation führt dazu, dass das kleinste Element an die erste Position verlagert wird.
3. In der nächsten Blasenrunde nimmt das kleinste in der vorherigen Runde ermittelte Element nicht mehr teil und die zu sortierende Spalte wird um ein Element reduziert.
4. Das Ergebnis jeder Blase ist, dass das kleinste Element in der Sequenz an der Endposition platziert wird und bis zu n-1 abgeschlossen ist.
2.Eigenschaften
1. Die durch Blasensortierung erzeugte geordnete Teilsequenz muss global geordnet sein, was sich von der Direkteinfügungssortierung unterscheidet.
3.Leistungsanalyse
1. Zeiteffizienz
1. Bester Fall: O(n)
Nach dem Sprudeln ist das Flag immer noch False, es findet kein Elementaustausch statt und die Schleife wird direkt herausgesprungen.
4. Algorithmusimplementierung
2. Schnelle Sortierung (Teile-und-Herrsche-Methode)
1. Gedanken
1. Jedes Mal wird das erste Element in der aktuellen Tabelle als Basis-Pivot (Pivot-Wert) zum Teilen der Tabelle verwendet.
2.i zeigt auf das erste Element (Basis), j zeigt auf das letzte Element
3. Beginnen Sie mit j und suchen Sie von hinten nach vorne das erste Element, das kleiner als die Grundlinie ist, und ersetzen Sie das Element, auf das i zeigt, durch dieses Element.
4. Suchen Sie ausgehend von i das erste Element, das größer als die Grundlinie ist, und zeigen Sie von vorne nach hinten auf die Position dieses Elements. Ersetzen Sie das Element, auf das j zeigt, durch dieses Element.
5. Beginnen Sie erneut bei j und wiederholen Sie den Vorgang, bis der Kontakt zwischen i und j aufhört, und teilen Sie die Sequenz in zwei Teile. Die Vorderseite ist kleiner als der Referenzwert und letztere ist größer als der Referenzwert .
6. Nehmen Sie das erste Element der beiden Teilsequenzen als Referenzwert und wiederholen Sie den Vorgang.
2.Eigenschaften
1. Es wird keine geordnete Teilsequenz generiert, aber nach jedem Sortierdurchlauf wird ein Element an der endgültigen Position platziert
2. Je geordneter der Algorithmus ist, desto geringer ist die Effizienz, und je ungeordneter der Algorithmus ist, desto höher ist die Effizienz.
3.Leistungsanalyse
1. Raumeffizienz
Durchschnittsfall: O(㏒₂n)
Der Algorithmus ist rekursiv und erfordert einen rekursiven Arbeitsstapel, dessen Größe der Tiefe des rekursiven Baums entspricht.
Schlimmster Fall: O(n)
2. Zeiteffizienz
1. Worst Case: O(n²)
Die Reihenfolge ist grundsätzlich in der Reihenfolge oder umgekehrt
2. Bester Fall (Durchschnittsfall): O(n㏒₂n)
4. Instabil
Exchange-Schlüsselwort vorhanden
4. Möglichkeiten zur Effizienzsteigerung
1. Wenn die durch rekursive Division erhaltene Teilsequenz klein ist, ist keine Rekursion mehr erforderlich und für die nachfolgende Arbeit wird die direkte Einfügungssortierung verwendet.
2. Versuchen Sie, einen Benchmark zu wählen, der die Daten aufteilen kann.
1. Wählen Sie drei Elemente aus Kopf, Schwanz und Mitte aus und nehmen Sie dann den Mittelwert
2. Wählen Sie Benchmarks nach dem Zufallsprinzip aus, um sicherzustellen, dass das Worst-Case-Szenario nicht eintritt
5. Algorithmusimplementierung
Zusammenfassung der Fragen
1. Fehleranfällig
1. Die schnellste Situation, wenn eine Gruppe von Zahlen mithilfe der Schnellsortierung sortiert wird
Jeder ausgewählte Benchmark unterteilt die Tabelle in zwei Untertabellen ähnlicher Länge.
2. Bei der Suche nach möglichen Reihenfolgen müssen beide Ordnungen berücksichtigt werden (von groß nach klein, klein nach groß)
2. Wissenspunkte
1. Die schnelle Sortierung eignet sich am besten für die sequentielle Speicherung.
3.Algorithmisches Denken
1. Algorithmus, um alle ungeraden Zahlen vor alle geraden Zahlen zu verschieben (geringster Zeit-/Platzbedarf)
1. Finden Sie zuerst eine gerade Zahl L(i) von vorne nach hinten, dann eine ungerade Zahl L(j) von hinten nach vorne, tauschen Sie die beiden aus und wiederholen Sie den Vorgang, bis i>j
2. Basierend auf schneller Sortierung, einem Durchlauf, Zeit O(n), Raum O(1)
2. Niederländisches Flaggenproblem: Eine Folge von Blöcken, die nur aus Rot, Weiß und Blau besteht, sodass die Blöcke in der Reihenfolge Rot, Weiß und Blau angeordnet sind und die Zeit O(n) ist.
1. Scannen Sie nacheinander und tauschen Sie Rot nach vorne und Blau nach hinten aus
2. Drei Zeiger, ein Arbeitszeiger, einer zeigt auf den Kopf, einer zeigt auf den Schwanz, switch-Anweisung
Hinweis: Positive Zahlen, negative Zahlen und 0 werden auf die gleiche Weise sortiert.
3. Finden Sie das k-kleinste Element im Array L[1...n]
0. Sie können die direkte Sortierung verwenden, um k Elemente oder mehr O(nlog₂n) zu erhalten / einen kleinen oberen Heap O(n klog₂n) verwenden.
1. Spannender, basierend auf der schnellen Sortierung, ist die Zeit O(n)
2. Wählen Sie einen Benchmark aus und führen Sie die gleiche Divisionsoperation wie bei der Schnellsortierung durch, unterteilt in L[1...m-1] und L[m 1...n], L(m) ist der Benchmark
3. Besprechen Sie die Beziehung zwischen m und k
1.m=k, der Benchmark ist das gesuchte Element
2.m <k, das gesuchte Element befindet sich in der zweiten Hälfte. Suchen Sie weiterhin rekursiv das k-m-kleinste Element in der zweiten Hälfte
3.m>k, das gesuchte Element befindet sich in der ersten Hälfte. Suchen Sie weiterhin rekursiv das k-kleinste Element in der ersten Hälfte
4. n Zahlen bilden eine Menge A, die in zwei disjunkte Teilmengen A1 und A2 unterteilt ist. Die Zahlen sind n1 und n2, und die Summe der Elemente ist s1 und s2. Erfüllen Sie das Minimum von |n1-n2|
1. Platzieren Sie die kleinsten n/2 Elemente in A1 und den Rest in A2, imitieren Sie die schnelle Sortierung und verarbeiten Sie die Referenzposition i nach der Division separat
2. Wenn i=n/2, ist die Gruppierung abgeschlossen
3. Wenn i <n/2, setzen Sie die Basis und alle vorherigen Elemente in A1 ein und dividieren Sie die Elemente nach i weiter
4. Wenn i>n/2, setzen Sie die Basis und alle nachfolgenden Elemente in A2 und teilen Sie die Elemente vor i weiter
5. Es ist nicht erforderlich, alle Elemente zu sortieren, durchschnittliche Zeit O(n), Raum O(1)
4.Sortieren auswählen
1. Einfache Auswahlsortierung
1. Gedanken
1. Finden Sie im ersten Durchgang das kleinste Element und tauschen Sie dieses Element mit dem ersten Element aus
1. Suchen Sie im zweiten Durchgang das kleinste Element, tauschen Sie dieses Element durch das zweite Element aus und wiederholen Sie den Vorgang n-1 Mal
2.Eigenschaften
1. Jeder Sortierdurchlauf kann die endgültige Position eines Elements bestimmen.
3.Leistungsanalyse
1. Zeitkomplexität ist immer O(n²)
Die Anzahl der Elementbewegungen beträgt selten O(n), aber die Anzahl der Vergleiche hat nichts mit dem Anfangszustand zu tun und beträgt immer n(n-1)/2
2. Instabil
Der direkte Austausch nach dem Auffinden des kleinsten Elements zerstört die ursprüngliche Reihenfolge.
4. Algorithmusimplementierung
2. Heap-Sortierung
1. Gedanken
1. Definition von Heap
Großer Root-Heap (vollständiger Binärbaum): Das größte Element ist der Root-Knoten, und der Wert jedes Nicht-Root-Knotens ist kleiner oder gleich dem Wert seines übergeordneten Knotens
1.1 Heap-Operationen
1. Löschen Sie das oberste Element des Heaps
Tauschen Sie zunächst das letzte Element mit dem obersten Element des Heaps aus. Passen Sie nach dem Löschen das oberste Element des Heaps nach unten an, um ein Heap zu werden.
2. Operation einfügen
Platzieren Sie den neuen Knoten zunächst am Ende des Heaps und passen Sie ihn dann nach oben an den Heap an
2. Erstellen Sie den ersten Heap (großer Root-Heap).
1. Treffen Sie Ihre Beurteilung vom letzten Knoten auf der vorletzten Ebene nach vorne.
2. Schauen Sie sich nur den Teilbaum des Knotens an (nicht den übergeordneten Knoten). Wenn es einen Knoten im Teilbaum gibt, der größer als der Wurzelknoten ist, suchen Sie den größeren und tauschen Sie ihn gegen den Wurzelknoten aus.
3. Wenn der Heap der nächsten Ebene nach dem Austausch zerstört wird, verwenden Sie weiterhin die obige Methode, um den Heap der nächsten Ebene bis zum Wurzelknoten anzupassen.
3. Geben Sie das oberste Element (Maximalwert) des Heaps aus, platzieren Sie das letzte Element oben im Heap und passen Sie die Oberseite des Heaps nach unten an, um einen großen oberen Heap zu erhalten.
4. Wiederholen Sie den Vorgang, bis nur noch ein Element im Heap vorhanden ist
2.Leistungsanalyse
1. Die Zeitkomplexität ist immer O(n㏒₂n)
Die Heap-Erstellungszeit beträgt O(n), und dann gibt es jedes Mal n-1 Anpassungen nach unten, wenn O(h)
2. Instabil
Beim Aufbau eines Heaps wird die ursprüngliche Reihenfolge gestört.
3. Raumkomplexität: O(1)
Verwenden Sie nur eine konstante Anzahl an Nebenaggregaten
3. Algorithmusimplementierung
Die Auswahlsortierung ist instabil
Zusammenfassung der Fragen
1. Klassische Fragen
1. Jedes Element hat zwei Datenelemente k1 und k2. Sortieren Sie zuerst k1, wobei das kleinere zuerst ist; k1 hat dann den gleichen Wert, dann sehen Sie sich k2 an, wobei das kleinere zuerst ist.
1. Bestimmen Sie zuerst die Sortierreihenfolge, gefolgt von k1. Schauen Sie sich zuerst k1 an.
2. Für die k2-Sortierung gibt es keine Stabilitätsanforderungen. Versuchen Sie, einen Algorithmus mit hoher Effizienz zu wählen.
3. Zum Sortieren von k1 muss ein stabiler Algorithmus verwendet werden, da sonst die Sortierung von k2 gestört werden kann
2. Fragetyp
1. Anzahl der Vergleiche beim Einfügen/Löschen von Elementen aus dem Heap
2. Ich möchte nur die teilweise sortierte Sequenz vor dem k-ten (k≥5) kleinsten Element erhalten
1. Blasen-/einfache Auswahl/Haufensortierung verfügbar
2. Die ersten beiden Zeiten sind kn
3. Heap-Sortierung: Der anfängliche zu erstellende Heap überschreitet nicht 4n, die Zeit zum Erhalten von k Elementen beträgt klog₂n, insgesamt 4n klog₂n, optimal, wenn k≥5
3. Bestimmen Sie, ob eine Datensequenz ein kleiner Root-Heap ist
1. Zwei Situationen müssen geteilt werden, die Reihenfolge ist eine ungerade Zahl und eine gerade Zahl
2. Wenn es sich um eine ungerade Zahl handelt: Es gibt keinen einzelnen Zweigknoten, können Sie den übergeordneten Knoten direkt mit den beiden untergeordneten Knoten vergleichen
3. Wenn es sich um eine gerade Zahl handelt: Es gibt einen einzelnen Zweigknoten, der separat beurteilt werden kann, und die anderen Knoten sind normal.
5. Sortierung und Basissortierung zusammenführen
1. Sortierung zusammenführen
1. Gedanken
1. Teilen Sie es zunächst in n Untertabellen der Länge 1 auf und führen Sie diese paarweise zusammen.
2. Erhalten Sie die Unterlisten mit der Länge 2, führen Sie sie erneut zu zweit zusammen und wiederholen Sie den Vorgang
2.Leistungsanalyse
1. Raumkomplexität: O(n)
Die zusammengeführten Daten müssen in das Hilfsarray kopiert werden, die Länge beträgt n
2. Zeitkomplexität: O(n㏒₂n)
Jede Zusammenführung ist O(n) und wird insgesamt n-mal durchgeführt. Die geteilte Teilsequenz hat nichts mit dem Anfangszustand zu tun.
3. Algorithmusimplementierung
2. Radix-Sortierung
1. Gedanken
1. Least Significant First (LSD)
1. Ordnen Sie die Sequenz zunächst entsprechend der Größe der einzelnen Ziffern in 10 Warteschlangen (0–9, von oben nach innen und von unten nach außen) an.
2. Entfernen Sie alle Elemente der Reihe nach aus der ersten Warteschlange bis zur 10. Warteschlange
3. Wiederholen Sie dann den Vorgang des Betretens und Verlassens der Warteschlange entsprechend der Zehnerstelle, und führen Sie den gleichen Vorgang für die Hunderterstelle durch.
4. Wenn auch das höchste Bit aus der Warteschlange entfernt wird, ist die Reihenfolge in Ordnung.
2. Höchstwertiges Bit zuerst (MSD)
1. Platzieren Sie die Sequenz zunächst entsprechend der Größe des höchsten Bits in 10 Warteschlangen (0 bis 9, von oben nach innen und von unten nach unten).
2. Sortieren Sie die Warteschlangen, deren Nummer nicht 1 ist, rekursiv und ordnen Sie sie entsprechend der Größe der nächsthöheren Ziffer erneut in 10 Warteschlangen ein.
3. Bis in allen Warteschlangen nur noch eine Nummer vorhanden ist, endet die Rekursion. Sammeln Sie jede Warteschlange und kehren Sie zur vorherigen Ebene zurück
2.Eigenschaften
1. Übernehmen Sie die Idee der Sortierung nach mehreren Schlüsselwörtern, ohne auf Vergleichen zu basieren
3. Leistungsanalyse (LSD)
1. Raumkomplexität: O(r)
r ist die Basis der Zahl (welches Basissystem)
2. Zeitkomplexität: O(d(n r))
Führen Sie d-malige Zuteilung und Sammlung durch. Eine Zuteilung ist O(n) und eine Sammlung ist O(r).
3. Stabil
Sowohl die Zuteilung als auch die Sammlung erfolgen nacheinander
Zusammenfassung der Fragen
1. Fehleranfällig
1. Welche Methode sollte zum Sortieren von 10-TB-Datendateien verwendet werden?
Zusammenführungssortierung, die Datei ist zu groß, die interne Sortierung kann nicht verwendet werden, nur die externe Sortierung kann verwendet werden, normalerweise wird die Zusammenführungssortierung verwendet
2. Wissenspunkte
1. Füge zwei geordnete Listen mit jeweils n Elementen zu einer geordneten Liste zusammen
1. Die Mindestanzahl an Vergleichen beträgt: n
2. Die maximale Anzahl an Vergleichen beträgt: 2n-1
3. Fragetyp
1. Wie viele Sortiercodevergleiche werden bei der Basissortierung durchgeführt?
Habe mehrere Allokationen und Sammlungen durchgeführt
6. Vergleich und Anwendung verschiedener interner Sortieralgorithmen
1. Vergleich interner Sortieralgorithmen
2. Anwendung des internen Sortieralgorithmus (Zusammenfassung)
1. Auswahl des Algorithmus
1.n ist kleiner
1. Der Datensatz selbst ist klein
Direkteinfügung (weniger Vergleiche)/einfache Auswahl (weniger Austausche)
2. Der Datensatz selbst ist groß
Einfache Wahl
1.1 Mittlerer Maßstab (n<1000)
Hügelsortierung ist eine gute Wahl
2. n ist sehr groß (wählen Sie das mit der kürzeren Zeit)
1. Instabil
1. Schnelle Sortierung: Die beste Methode mit der kürzesten durchschnittlichen Zeit bei zufälliger Verteilung
2. Heap-Sortierung: Erfordert weniger Hilfsraum als die schnelle Sortierung
2. Stabil
Zusammenführungssortierung: weist jedoch die höchste räumliche Komplexität auf
3.n ist sehr groß, die Anzahl der Schlüsselwörter ist gering und kann zerlegt werden
Radix-Sortierung ist besser
4. Die Reihenfolge ist grundsätzlich in Ordnung
Direkteinfügungssortierung (höchste Effizienz/geringste Anzahl von Vergleichen)/Blasensortierung
Die Zeitkomplexität im besten Fall ist O(n)
5.Das Ergebnis nach mehreren Sortierungen
1. Platzieren Sie jeweils ein Element an der endgültigen Position
Einfache Auswahl/Heap-Sortierung, Blasensortierung/Schnellsortierung (Austausch)
Nur das schnell sortierte Element ist nicht das wertvollste Element, die anderen 3 sind alle die wertvollsten (erstes/letztes)
2. Die ersten paar Elemente sind in Ordnung, aber nicht die endgültige Position
direkt einfügen
3. Es ist möglich, dass sich vor Beginn der letzten Fahrt nicht alle Elemente in ihrer endgültigen Position befinden.
direkt einfügen
4. Es gibt keine Garantie dafür, dass sich an der endgültigen Position ein Element befindet
Direkteinfügung/Hill-Sortierung/Merge-Sortierung
6. Einige der meisten
1. Derzeit der beste interne Sortieralgorithmus in Bezug auf die durchschnittliche Leistung
Schnelle Sorte
2. Algorithmen, die den meisten Platz beanspruchen
Sortierung zusammenführen O(n)
Im schlimmsten Fall ist Quicksort O(n).
3. Was ist am schnellsten, wenn es grundsätzlich in Ordnung ist?
direkte Einfügungssortierung
4. Im besten Fall kann eine lineare Zeit erreicht werden
Direkteinfügung/Blasensortierung
7.0 Die Zeit des Algorithmus ist unabhängig von der Anfangssequenz
Auswahlsortierung (einfache Auswahl/Heap-Sortierung)/Zusammenführungssortierung/Radix-Sortierung
7.1 Die Anzahl der Sortierdurchgänge hat nichts mit der Ausgangsreihenfolge zu tun
Direktes Einfügen/einfache Auswahl erfolgt jeweils n-1-mal und die Basissortierung ist auf d-Zeiten festgelegt.
7.2 Die Anzahl der Züge hat nichts mit der Anfangssequenz zu tun
Radix-Sortierung
Die Radix-Sortierung hat nichts mit der Anfangssequenz zu tun
8. Finden Sie die am wenigsten effiziente Datenstruktur
Heap: Hauptsächlich zum Sortieren gedacht und bei der Suche ungeordnet.
9. Wenn die sequentielle Speicherung durch eine Kettenspeicherung ersetzt wird, verringert sich die Zeiteffizienz.
Hill-Sortierung/Heap-Sortierung (unter Ausnutzung der Direktzugriffseigenschaften sequentieller Tabellen)
2. Verbesserungen bei der Zusammenführungssortierung
Kombiniert mit der Sortierung durch direkte Einfügung: Verwenden Sie zuerst die direkte Einfügung, um längere geordnete Teilsequenzen zu erhalten, und führen Sie sie dann paarweise zusammen, immer noch stabil
3. Algorithmus basierend auf Vergleich
Der Vergleichsentscheidungsprozess kann durch einen Binärbaum beschrieben werden, sodass er mindestens O(n㏒₂n) Zeit benötigt
4. Der Datensatz selbst enthält eine große Menge an Informationen
Durch die Verwendung verknüpfter Listen als Speicherstrukturen kann ein hoher Zeitaufwand für das Verschieben von Datensätzen vermieden werden
7. Externe Sortierung
1. Grundkonzepte der externen Sortierung
1. Reduzieren Sie die Anzahl der Lese- und Schreibvorgänge im externen Speicher
Erhöhen Sie die Anzahl der Zusammenführungspfade/Reduzieren Sie die Anzahl der Zusammenführungssegmente
2. Erhöhen Sie die Anzahl der Zusammenführungspfade (m)
Verliererbaum
Nach der Verwendung hat die Anzahl der Vergleiche nichts mit m zu tun. Sie können m erhöhen, um die Höhe des Zusammenführungsbaums zu verringern.
3. Reduzieren Sie die Anzahl der zusammengeführten Segmente
Permutationsauswahlsortierung
Erhöhen Sie die Länge der Zusammenführungssegmente, um die Anzahl der Zusammenführungssegmente zu verringern
4. Organisieren Sie die Zusammenführungssequenz der zusammengeführten Segmente unterschiedlicher Länge
bester Zusammenführungsbaum
Huffman-Baum verallgemeinert zum m-ary-Baum
2. Externe Sortiermethode (Zusammenführungssortierung)
1. Zwei relativ unabhängige Phasen
1. Holen Sie sich die zusammengeführte Segment-/Serienzeichenfolge
Entsprechend der Größe des Speicherpuffers werden die n Datensätze in mehrere Datensätze aufgeteilt, die nacheinander in den Speicher eingelesen und durch interne Sortierung sortiert und anschließend in den externen Speicher zurückgeschrieben werden.
2. Führen Sie die zusammengeführten Segmente nacheinander zusammen, sodass die zusammengeführten Segmente von klein nach groß wachsen, bis sie vollständig sind.
2. Anzahl der Zusammenführungsdurchgänge S = Höhe des Baumes = ┌㏒mⁿ┐
n – die Anzahl der anfänglichen Zusammenführungssegmente m – die Anzahl der Zusammenführungspfade ┌┐ – aufgerundet
3. Mehrweg ausgewogener Zusammenführungs- und Verliererbaum
1. Die interne Verschmelzungszeit nimmt mit dem Wachstum von m zu
1. Macht die Vorteile zunichte, die sich aus der Reduzierung der Anzahl externer Speicherzugriffe aufgrund der Erhöhung von m ergeben.
2. Die normale interne Zusammenführungssortierung kann nicht verwendet werden
2. Verliererbaum (vollständiger Binärbaum)
1. Blattknoten
Datensätze, die derzeit am Vergleich teilnehmen
2. Interne Knoten
Merken Sie sich die Sequenznummer des Verlierers im linken und rechten Teilbaum und lassen Sie den Gewinner bis zum Wurzelknoten weiter vergleichen
3. Wurzelknoten
Die Seriennummer der aktuellen Mindest-/Höchstzahl, nicht der Wert selbst (Gewinner)
3. Nachdem Sie den Verliererbaum verwendet haben, um die Mindestwertsequenznummer zu erhalten, nehmen Sie die Mindestwertnummer heraus, fügen Sie das nächste Schlüsselwort an seiner Position hinzu, setzen Sie den Vergleich fort und erstellen Sie den Verliererbaum.
4. Nach Verwendung des Verliererbaums hat die Anzahl der Vergleiche nichts mit m zu tun. Sie können m erhöhen, um die Höhe des Zusammenführungsbaums zu verringern.
5.m bedeutet nicht, dass größer besser ist
Mit zunehmendem m nimmt der Eingabepuffer zu, seine Kapazität nimmt ab und die Anzahl der Datenaustausche zwischen internem und externem Speicher nimmt zu.
4. Ersetzungsauswahlsortierung (erzeugen Sie das längste anfängliche Zusammenführungssegment)
1. Gedanken
1. Nehmen Sie zunächst die kleinste Zahl a im Arbeitsbereich
2. Nehmen Sie dann die kleinste Zahl unter den Zahlen größer als a und fügen Sie sie in diesen Zusammenführungsabschnitt ein, und die Zahl kleiner als a wird in den nächsten Zusammenführungsabschnitt eingefügt.
5. Bester Zusammenführungsbaum
1. Definition (verallgemeinerter m-ary Huffman-Baum)
1. Blattknoten
Ein erstes Zusammenführungssegment, das an der Zusammenführung teilnimmt
2. Gewicht des Blattknotens
Die Anzahl der Datensätze im ersten Zusammenführungssegment
3. Pfadlänge vom Blattknoten zum Wurzelknoten
Anzahl der Zusammenführungsdurchgänge
4. Nicht-Blattknoten
Durch die Zusammenführung entstehen neue zusammengeführte Segmente
5. Gewichtete Pfadlänge des Zusammenführungsbaums
Gesamtzahl der gelesenen Datensätze
Anzahl der von allen Blattknoten übergebenen Kanten * Gewicht
2. Gedanken
Lassen Sie die Zusammenführungssegmente mit weniger Datensätzen zuerst und diejenigen mit mehr Datensätzen zuletzt zusammenführen.
3. Der optimale Zusammenführungsbaum ist ein strenger m-ary-Baum
1. Wenn das letzte fehlende Element nicht ausreicht, um einen strengen m-ary-Baum zu bilden, fügen Sie ein „virtuelles Segment“ mit einer Länge von 0 hinzu und führen Sie es zuerst zusammen.
2. Anzahl leerer Zusammenführungssegmente = m-u-1
u=(n0-1)%(m-1)
n0 – die Anzahl der Knoten mit Grad 0 (die Anzahl der anfänglich zusammengeführten Segmente) m-m-Baum
Zusammenfassung der Fragen
1. Fragetyp
1. Es gibt insgesamt n Datensätze, der Arbeitsbereich kann einen Datensatz aufnehmen und es wird eine m-Wege-balancierte Zusammenführung durchgeführt.
1. Die anfängliche Anzahl der Zusammenführungssegmente r=n/a, die Anzahl der Zusammenführungsdurchgänge s=┌㏒m(r)┐
2,5 anfängliche Zusammenführungssegmente mit jeweils 20 Datensätzen unter Verwendung einer ausgewogenen 5-Wege-Zusammenführung, Anzahl der Vergleiche ohne Verliererbaum und mit Verliererbaum
1. Es wird kein Verliererbaum verwendet: 5 Datensätze müssen viermal verglichen werden, um den kleinsten auszuwählen. Insgesamt sind 100 Datensätze erforderlich, um den kleinsten auszuwählen, 4*99=396
2. Verwenden Sie den Verliererbaum: Die Höhe des Verliererbaums beträgt h = 3, wählen Sie jedes Mal den kleinsten aus und die Anzahl der Vergleiche überschreitet h nicht, insgesamt 100 Mal, nicht mehr als 300 Mal
3. Führen Sie eine m-Wege-balancierte Zusammenführung durch und bestimmen Sie die Anzahl der Eingabe- und Ausgabepuffer
1. Normale Situation (serielle Operation): Es werden m Eingangspuffer und 1 Ausgangspuffer benötigt
2. Eingabe-/Ausgabe-Parallelbetrieb: 2 Mio. Eingabepuffer, 2 Ausgabepuffer
4. Die Gesamtzahl der gleichzeitig verfügbaren Ein-/Ausgabedateien überschreitet nicht 15
Es sind bis zu 14 Arten der Zusammenführung möglich