1.Daten

2. Datenelemente

3. Datenobjekte

4.Datentyp

Datenstruktur

Drei Elemente

Zeitkomplexität

Raumkomplexität

einfügen

löschen

Suche nach Wert (sequentiell suchen)

Erstellen Sie eine einfach verknüpfte Liste

Finden Sie Knoten anhand der Seriennummer

Knotentabellenknoten nach Wert suchen

Knoten einfügen

Knoten löschen

Fragen Sie nach der Tischlänge

Knoten einfügen

Knoten löschen

Zirkuläre einfach verknüpfte Liste

Zirkuläre doppelt verkettete Liste

Initialisierung void InitStack(SqStack &S){ oben = -1; }

Der Stapel ist leer bool StackEmpty(SqStack S){ if(S.top == -1) return true; sonst gibt false zurück; }

in den Stapel schieben bool Push(SqStack &S,ElemType x){ if(S.top == MaxSize-1) return false; S.data[ S.top] = x; //top wird auf -1 initialisiert return true; }

Pop bool Pop(SqStack &S,ElemType &x){ if(S.top == -1) return false; x = S.data[S.top- -]; return true; }

Lesen Sie das oberste Element des Stapels bool GetTop(SqStack S,ElemType &x){ if(S.top == -1) return false; x = S.data[S.top]; return true; }

Anfänglich: top0 = -1 top1 = MaxSize; Stapel voll: nur, wenn zwei Stapelzeiger benachbart sind top1 - top0 = 1

sequentielle Warteschlange

kreisförmige Warteschlange Die Warteschlangenentfernungs-, Verbindungs- und Volloperationen der zirkulären Warteschlange müssen % haben; die leere Bedingung ist nur Q.rear == Q.front

Initialisierung void InitQueue(LinkQueue &Q){ Q.front = Q.rear = (LinkQueue*)malloc(sizeof(LinkQueue)); //Erstelle den Kopfknoten Q.front ->next = NULL; }

Das Team ist leer bool IsEmpty(LinkQueue&Q){ if(Q.front == Q.rear) return true;//Mit Kopfknoten sonst gibt false zurück; }

Tritt dem Team bei void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = x; s->next = NULL;//Erstelle einen neuen Knoten und füge ihn am Ende der Kette ein Q.rear->next = s; Q.rear = s; }

Aus der Warteschlange entfernen bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.rear == Q.front) return false; LinkNode *p = Q.front->next; x = p->Daten; Q.front->next = p->next; if(Q.rear == p) Q.rear = Q.front;//Die ursprüngliche Warteschlange hat nur einen Knoten frei(p); return true; }

Eingabebeschränkte Deque

Ausgabebeschränkte Deque

[]()([][]()) ist das richtige Format; (] [) ist das falsche Format

Infix-Ausdrücke: hängen von der Operatorpriorität ab, behandeln aber auch Klammern Postfix-Ausdrücke: Operatorpriorität bereits berücksichtigt, keine Klammern (Post-Order-Durchlauf des Ausdrucksbaums) Konvertieren Sie den Infix-Ausdruck in den Postfix-Ausdruck

Der Wurzelknoten tritt in die Warteschlange ein. Wenn die Warteschlange leer ist (alle Knoten wurden verarbeitet), wird der nächste Schritt wiederholt. Wenn ein linker Knoten vorhanden ist, wird der nächste Schritt in der Warteschlange wiederholt. Das linke Kind tritt dem Team bei. Wenn es ein rechtes Kind hat, fügen Sie das rechte Kind dem Team hinzu und kehren Sie zum vorherigen Schritt zurück

1. Lösen Sie das Problem der Geschwindigkeitsinkongruenz zwischen dem Host und externen Geräten. 2. Lösen Sie Ressourcenwettbewerbsprobleme, die durch mehrere Benutzer verursacht werden

Array-Speicherstruktur Zeilen-Major; Spalten-Major

Symmetrische Matrix

Dreiecksmatrix

tridiagonale Matrix

Verwenden Sie die Triplett-Methode (Zeilenbeschriftung, Spaltenbeschriftung, Wert) oder die Methode der vernetzten Liste

Sequentielle Speicherung mit fester Länge #define MaxLen 255 typedef struct{ char ch[MaxLen]; int Länge; }SString; Sie können die Länge auch nicht aufzeichnen und „\0“ verwenden, das nicht in der Zeichenfolgenlänge enthalten ist, um die Zeichenfolgenlänge anzugeben.

Heap-zugewiesene Speicherdarstellung (dynamische Zuweisung) typedef struct{ char*ch; int Länge; }HString; In der C-Sprache wird dynamisch zugewiesener Speicherplatz im Heap gespeichert und von malloc() free() verwaltet. Wenn die Zuweisung fehlschlägt, wird NULL zurückgegeben.

Darstellung der Blockkettenspeicherung: Jeder Knoten wird als Block bezeichnet, und ein Block kann ein Zeichen oder mehrere Zeichen speichern. Die gesamte verknüpfte Liste wird als Blockkettenstruktur bezeichnet. Wenn der letzte Knoten weniger als einen Block einnimmt, wird er normalerweise mit „#“ gefüllt.

String-Zuweisung StrAssign(&T,chars) weist chars den Wert von T zu

String-Vergleich StrCompare(S,T) wenn S>T,return>0;S=T,return 0;S<T,return<0

Ermitteln Sie die Stringlänge. StrLength(S) gibt die Anzahl der S-Elemente zurück

Reihenverkettung Concat(&T,S1,S2) verwendet T, um eine neue Zeichenfolge zurückzugeben, die durch die Verkettung von S1 und S2 gebildet wird

Suchen Sie die Teilzeichenfolge SubString(&Sub,S,pos,len). Verwenden Sie Sub, um die Teilzeichenfolge zurückzugeben, beginnend mit dem pos-Zeichen der S-Zeichenfolge und weiter mit der Länge von len

int index(SString S,SString T){ int i=1,j=1; while(i<=S.length && j<=T.length){ if(S.ch[i] == T.ch[j]){ ich ;j ; } anders{ i = i-j 1 1;j = 1; } if(j > T.length) return i - T.length; sonst 0 zurückgeben; } Schlechteste Zeitkomplexität O(mn)

Verwandte konzepte: Präfix: Alle Header-Teilzeichenfolgen der Zeichenfolge mit Ausnahme des letzten Zeichens; Suffix: Alle nachfolgenden Teilzeichenfolgen der Zeichenfolge außer dem ersten Zeichen; Teilweise Übereinstimmung (PM): Die längste gleiche Präfix- und Suffixlänge der Zeichenfolge. Beispiel: 'ababa' Achtung! ! Beginnen Sie mit dem ersten Zeichen der Hauptzeichenfolge, teilen Sie alle Teilzeichenfolgen auf und analysieren Sie dann die Länge des Präfixes und Suffixes bzw. des längsten gleichen Suffixes und Suffixes. Das Präfix und Suffix „a“ ist eine leere Menge, und die längste gleiche Präfix- und Suffixlänge ist 0 „ab“ Präfix „a“ Suffix „b“ Die längste gleiche Übereinstimmungslänge ist 0 'aba' Präfix 'a' 'ab' Suffix 'a' 'ba' {'a' 'ab'} ^ {'a' 'ba'} = 'a', die längste gleiche Suffixlänge ist 1 „abab“ Präfix „a“ „ab“ „aba“ Suffix „b“ „ab“ „bab“, die längste gleiche Präfix- und Suffixlänge beträgt 2 'ababa' Präfix 'a' 'ab' 'aba' 'abab' Suffix 'a' 'ba' 'aba' 'baba' ,{ } ^ { } = {'a' 'aba'}, die längste gleiche Suffixlänge 3 Der teilweise übereinstimmende Wert der endgültigen Zeichenfolge ist also 00123

Wenn Sie den KMP-Algorithmus verwenden, schreiben Sie zuerst die PM-Tabelle der Musterzeichenfolge (Teilzeichenfolge); wenn die Teilzeichenfolge nicht mit der Hauptzeichenfolge übereinstimmt, suchen Sie den PM-Wert des letzten übereinstimmenden Elements der Teilzeichenfolge in der PM-Tabelle und lassen Sie ihn dann Teilzeichenfolge Die zurückgelegte Distanz (Anzahl der übereinstimmenden Zeichen – PM-Wert des letzten übereinstimmenden Zeichens); wenn bei einer bestimmten Fahrt eine Nichtübereinstimmung auftritt und der Teilübereinstimmungswert des entsprechenden Teils 0 ist, bedeutet dies, dass es keine gleichen Suffixe gibt Suffixe in der übereinstimmenden Sequenz sind am größten (übereinstimmende Länge - 0) und werden für den nächsten Vergleich direkt an die Position verschoben, auf die die Hauptzeichenfolge zu diesem Zeitpunkt zeigt. Move = (j-1) - PM[j-1];

Generierung und Änderung des nächsten Arrays: Um die Nichtübereinstimmung zu erleichtern, überprüfen Sie, anstatt sich auf ein Zeichen zu freuen, direkt den PM-Wert der aktuellen nicht übereinstimmenden Zeichenposition, sodass alle Elemente in der PM um 1 Position nach rechts verschoben werden und die erste Position mit -1 gefüllt wird , und die letzte Position wird ignoriert; Wird als nächstes Array bezeichnet, Move = (j-1)-next[j] Zu diesem Zeitpunkt kehrt j zu j = j-Move = next[j] 1; Addiere dann 1 zu allen next und aktualisiere das nächste Array, sodass j = next[j] (Zu diesem Zeitpunkt ist die erste Position des nächsten Arrays 0) Die Bedeutung des letzten nächsten Arrays: Wenn das j-te Zeichen der Teilzeichenfolge nicht übereinstimmt, springen Sie zur nächsten [j]-Position der Teilzeichenfolge für die nächste Übereinstimmungsrunde! ! !

Ein Baum ist eine endliche Menge von n (n>0) Knoten. Wenn n = 0 ist, wird er als leerer Baum bezeichnet. Er hat nur einen Wurzelknoten und die verbleibenden Knoten können in disjunkte endliche Mengen, sogenannte Teilbäume, unterteilt werden. 1. Der Wurzelknoten des Baums hat keinen Vorgänger und die Knoten außer dem Wurzelknoten haben nur einen Vorgänger. 2. Alle Knoten im Baum können null oder mehr Nachfolger haben. Der Baum ist für die Darstellung von Daten mit a geeignet hierarchische Struktur; 3. Terminologie: 1. Vorfahr-Nachkomme (kann mehrere Ebenen umfassen, solange eine Top-Down-Beziehung besteht (mit demselben Elternknoten); 2. Die Anzahl der Kinder eines Knotens im Baum wird als Grad des Knotens bezeichnet. Der maximale Grad eines Knotens im Baum ist der Grad des Baums. 3. Knoten mit einem Grad > 0 werden als Verzweigungsknoten (nicht terminale Knoten) bezeichnet; die Anzahl der Zweige eines Verzweigungsknotens ist der Grad des Verzweigungsknotens; 4. Die Knotenebene wird ausgehend von der Wurzel des Baums definiert, wobei der Wurzelknoten die Knoten der ersten Ebene ist, deren übergeordnete Knoten sich auf derselben Ebene befinden und Cousinen voneinander sind. Die Tiefe eines Knotens wird Schicht für Schicht akkumuliert, beginnend beim Wurzelknoten und von oben nach unten (stellen Sie sich vor, die Wurzeln des Baums werden nach unten tiefer). Die Höhe des Knotens wird Schicht für Schicht akkumuliert, beginnend am Blattknoten und von unten nach oben (von unten nach oben sieht es sehr hoch aus). Die Höhe oder Tiefe eines Baums ist die maximale Anzahl der Knotenebenen im Baum; 4. Geordnete Bäume und ungeordnete Bäume, geordnete Bäume sind nicht austauschbar 5. Pfad und Pfadlänge: Der Pfad besteht aus der Folge von Knoten, die zwischen den beiden Knoten durchlaufen werden, und die Pfadlänge ist die Anzahl der durchlaufenen Kanten! 6. Wald: eine Sammlung von m disjunkten Bäumen. Solange der Wurzelknoten gelöscht wird, wird der Baum zu einem Wald. Wenn umgekehrt ein Wurzelknoten zu m Bäumen hinzugefügt wird, wird der Wald zu einem Baum.

Natur: 1. Die Anzahl der Knoten des Baums ist gleich der Summe der Grade aller Knoten (Gesamtzahl der Zweige) 1 (Wurzelknoten) 2. Die i-te Ebene eines Baums vom Grad m hat höchstens m^i-1 Knoten (i>1) 3. Ein m-ärer Baum mit der Höhe h hat höchstens (m^i - 1)/(m-1) Knoten. 4. Die minimale Höhe eines m-ären Baums mit n Knoten beträgt

1. Sequentielle Speicherung: Übergeordnete Notation: Eine große Struktur legt eine kleine Struktur fest, und die kleine Struktur besteht aus Daten und übergeordneten Zeigern. Die große Struktur ist ein Array, das aus mehreren kleinen Strukturen und der Anzahl der Knoten besteht. #define Max_Tree_SIze 100 typedef struct{ ElemType-Daten; int parent; }PTNode; typedef struct{ PTNode-Knoten[Max_Tree_Size]; int n; }PTree; Diese Struktur nutzt die Tatsache aus, dass jeder Knoten (mit Ausnahme des Wurzelknotens) nur einen übergeordneten Knoten hat und den übergeordneten Knoten jedes Knotens schnell erhalten kann, erfordert jedoch das Durchlaufen des gesamten Baums, um die untergeordneten Knoten des Knotens zu finden.

2. In der untergeordneten Darstellung: Verbinden Sie die untergeordneten Knoten jedes Knotens mit einer einzelnen verknüpften Liste, um eine lineare Struktur zu bilden. Es gibt n verknüpfte Listen für n Knoten (die untergeordnete verknüpfte Liste eines Blattknotens ist eine leere verknüpfte Liste). Diese Methode ist sehr einfach, um Kinder zu finden, aber um Eltern zu finden, müssen die n untergeordneten verknüpften Listen durchlaufen werden, auf die die Zeiger der untergeordneten verknüpften Listen in n Knoten zeigen. Ähnlich wie eine kritische Tabelle

3. Darstellung des Kindesbruders: Auch als binäre Baumdarstellung bekannt. typedef struct CSNode{ ElemType-Daten; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree; Implementieren Sie den Vorgang der Konvertierung eines Baums in einen Binärbaum bequem Das linke Kind hat einen Bruder

Konvertierung zwischen Bäumen und Binärbäumen; sowohl Bäume als auch Binärbäume können durch binär verknüpfte Listen dargestellt werden. Die physikalische Struktur ist dieselbe, aber die Regeln für die Konvertierung eines Baums in einen Binärbaum sind unterschiedlich. Da der Wurzelknoten keine Brüder hat, gibt es für den Wurzelknoten keine rechten Handschriftkonvertierungsschritte: 1. Verbinden Sie eine Linie zwischen Geschwisterknoten. 2. Behalten Sie nur die Verbindung zwischen jedem Knoten und seinem ersten untergeordneten Knoten bei und verwenden Sie andere. Löschen Sie alle Verbindungen der untergeordneten Knoten 3. Nehmen Sie die Wurzel des Baumes als Achse und drehen Sie sie um 45 Grad im Uhrzeigersinn

Konvertierung von Wald in Binärbaum 1. Konvertieren Sie zunächst jeden Baum im Wald in einen Binärbaum 2. Die Wurzel jedes Baums wird als Geschwisterbeziehung betrachtet, und die nachfolgenden Bäume werden nacheinander als rechte Knoten des vorherigen Baums betrachtet. 3. Drehen Sie die Wurzel des ersten Baumes um 45 Grad im Uhrzeigersinn

Konvertieren Sie einen Binärbaum in eine Gesamtstruktur: 1. Trennen Sie nacheinander den rechten Teilbaum des Wurzelknotens, bis nur noch ein Wurzelknoten ohne rechten Teilbaum vorhanden ist. 2. Konvertieren Sie alle getrennten Binärbäume in Bäume, um den ursprünglichen Wald zu erhalten Das Konvertieren eines Binärbaums in einen Baum oder eine Gesamtstruktur ist einzigartig

Konvertieren Sie einen Binärbaum in einen Baum 1. Entfernen Sie alle rechten Knoten, rechten Knoten und rechten Knoten des linken Teilbaums des Wurzelknotens. . . alle als Kinder der Wurzel 2. Nacheinander anpassen

Baumdurchquerung

Unterwegs durch den Wald

Union-Find ist eine einfache Mengendarstellung, die drei Operationen unterstützt Die Strukturdefinition des Union-Suchsatzes: #define GRÖSSE 100 int UFSets[SIZE]; Eine Menge in der Union-Suche ist ein Baum, und mehrere Mengen bilden einen Wald.

Hinweis-Binärbaum (unbekannt, daher speziell erweitert) typedef struct TreadNode{ ElemType-Daten; struct TreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; Eine binär verknüpfte Liste, die aus einer Knotenstruktur als Speicherstruktur des Binärbaums besteht, wird als verknüpfte Hinweisliste bezeichnet. Die Zeiger, die auf den Vorgänger und Nachfolger des Knotens zeigen, werden als Hinweise bezeichnet. Ein Binärbaum mit Hinweisen wird als Hinweis-Binärbaum bezeichnet

Traverse

Binärer Sortierbaum BST (binärer Suchbaum)

ausgeglichener Binärbaum

roter schwarzer Baum

Huffman-Bäume und Huffman-Codierung

gerichteter Graph, ungerichteter Graph Gerichteter Graph: E ist eine gerichtete Kante (Bogen) und ein Bogen ist ein geordnetes Eckpunktpaar, bezeichnet als <v,w> Ungerichteter Graph: E ist eine ungerichtete Kante (Kante) und eine Kante ist ein ungeordnetes Scheitelpunktpaar, aufgezeichnet als (v, w)

Einfaches Diagramm, mehrere Diagramme Einfaches Diagramm: 1. Es gibt keine doppelten Kanten (Kanten, die zwischen zwei benachbarten Knoten in einem gerichteten Diagramm aufeinander zeigen, werden nicht als doppelte Kanten gezählt) 2. Es gibt keine Kante vom Scheitelpunkt zu sich selbst. Mehrere Grundstücke: 1. Die Anzahl der Kanten zwischen zwei Eckpunkten ist größer als 1 2. Erlauben Sie, dass Scheitelpunkte durch eine Kante mit sich selbst in Beziehung gesetzt werden Die Definitionen mehrerer Diagramme und einfacher Diagramme sind relativ. In der Datenstruktur werden nur einfache Diagramme erläutert.

Vollständiges Diagramm (einfaches vollständiges Diagramm) Für ungerichtete Graphen beträgt der Wertebereich von |E| 0-n(n-1)/2, Ein ungerichteter Graph mit n(n-1)/2 Kanten wird als vollständiger Graph bezeichnet, und es gibt eine Kante zwischen zwei beliebigen Eckpunkten; Für gerichtete Graphen beträgt der Wertebereich von |E| 0-n(n-1), Ein gerichteter Graph mit n(n-1) Bögen wird als gerichteter vollständiger Graph bezeichnet, und zwischen zwei beliebigen Eckpunkten gibt es einen entgegengesetzten Bogen.

Nebenhandlung G=(V,E),G'=(V',E'); Wenn V‘ eine Teilmenge von V und E‘ eine Teilmenge von E ist, dann heißt G‘ ein Teilgraph von G. Wenn V(G')=V(G) erfüllt ist, dann wird G' der erzeugte Teilgraph von G genannt; Nicht jede Teilmenge von V und E kann einen G-Teilgraphen bilden, da die Eckpunkte, die einigen Kanten in der Teilmenge von E zugeordnet sind, möglicherweise nicht in dieser Teilmenge von V enthalten sind.

Konnektivität, verbundene Diagramme und verbundene Komponenten Wenn es einen Weg vom Scheitelpunkt v zum Scheitelpunkt w gibt, dann werden v und w als verbunden bezeichnet. Wenn zwei beliebige Knoten in G verbunden sind, handelt es sich um einen verbundenen Graphen, andernfalls handelt es sich um einen nicht zusammenhängenden Graphen. Der maximal zusammenhängende Teilgraph in einem ungerichteten Graphen wird als Zusammenhangskomponente bezeichnet. Ein zusammenhängender Graph hat mindestens n-1 Kanten. Wenn die Anzahl der Kanten kleiner als n-1 ist, muss es sich um einen nicht zusammenhängenden Graphen handeln. Wie viele Kanten kann ein unzusammenhängender Graph maximal haben? : Der kritische Zustand von n-1 Eckpunkten, die einen vollständigen Graphen bilden (es kann jederzeit eine Kante hinzugefügt werden, um einen verbundenen Graphen zu bilden)

Stark zusammenhängender Graph, stark zusammenhängende Komponenten Wenn in einem gerichteten Graphen ein Paar von Eckpunkten v nach w und w nach v Pfade haben, dann nennt man die beiden Eckpunkte stark verbunden. Wenn ein Knotenpaar im Graphen stark verbunden ist, wird der Graph als stark verbundener Graph bezeichnet. Der maximal stark verbundene Teilgraph in einem gerichteten Graphen wird als stark verbundene Komponente des gerichteten Graphen bezeichnet; Die Situation mit den wenigsten Kanten, wenn ein gerichteter Graph stark zusammenhängend ist: Es werden mindestens n Kanten benötigt, um einen Kreis zu bilden

Spannender Baum, Spannender Wald Der Spannbaum eines verbundenen Graphen ist ein minimal verbundener Teilgraph, der alle Eckpunkte im Diagramm enthält. Wenn die Anzahl der festen Eckpunkte n ist, hat der Spannbaum n-1 Kanten. Wenn eine Kante vom aufspannenden Baum abgeschnitten wird, wird er zu einem nicht zusammenhängenden Teilgraphen. Wenn eine Kante hinzugefügt wird, wird ein Zyklus gebildet. In einem nicht verbundenen Diagramm bildet der Spanning Tree verbundener Komponenten den Spanning Forest des nicht verbundenen Diagramms.

Scheitelpunktgrad, In-Grad und Out-Grad Ungerichteter Graph: TD(v), die Summe der Grade aller Eckpunkte eines ungerichteten Graphen ist gleich dem Zweifachen der Anzahl der Kanten Gerichteter Graph: Der Grad des Scheitelpunkts v wird in In-Grad-ID(v) und Out-Grad-OD(v) unterteilt. Der Grad des Scheitelpunkts v ist gleich der Summe aus In-Grad und Out-Grad: TD(v). =ID(v) OD(v) , der In-Grad aller Eckpunkte eines gerichteten Graphen ist gleich dem Out-Grad, der der Anzahl der Kanten entspricht

Bians Quanhe.com Jede Kante kann mit einem numerischen Wert markiert werden, der eine bestimmte Bedeutung hat, die als Gewicht der Kante bezeichnet wird. Der Graph mit gewichteten Kanten wird als gewichteter Graph bezeichnet, der auch als Netzwerk bezeichnet wird.

Dichtes Diagramm, spärliches Diagramm Ein Graph mit wenigen Kanten wird als dünn besetzter Graph bezeichnet, das Gegenteil als dichter Graph. Wenn G |E|<|V|log|V| erfüllt, wird G im Allgemeinen als dünn besetzter Graph betrachtet.

Wege, Weglängen und Schleifen Pfad: Ein Pfad vom Scheitelpunkt vp nach vq bezieht sich auf die Scheitelpunktsequenz vp,vi1...vim,vq, Die Anzahl der Kanten auf einem Pfad wird Pfadlänge genannt Ein Pfad, dessen erster und letzter Scheitelpunkt gleich sind, wird Zyklus oder Kreis genannt Wenn ein Graph n Eckpunkte und mehr als n-1 Kanten hat, muss der Graph einen Kreis haben.

Einfacher Weg, einfache Schleife In einer Pfadsequenz wird ein Pfad, dessen Scheitelpunkte nicht wiederholt vorkommen, als einfacher Pfad bezeichnet. Mit Ausnahme des ersten Scheitelpunkts und des letzten Scheitelpunkts wird der Zyklus, in dem die verbleibenden Scheitelpunkte nicht in diesem Diagramm enden, als einfacher Zyklus bezeichnet.

Distanz Wenn der kürzeste Weg vom Scheitelpunkt u zum Scheitelpunkt v existiert, dann ist die Länge dieses Weges der Abstand von u nach v; Gibt es überhaupt keinen Weg von u nach v, dann wird die Entfernung als ∞ aufgezeichnet

gerichteter Baum Ein gerichteter Graph, in dem der In-Grad eines Knotens 0 und der Out-Grad der übrigen Knoten 1 ist, wird als gerichteter Baum bezeichnet.

Es bezieht sich auf die Verwendung eines eindimensionalen Arrays zum Speichern der Beziehung zwischen Scheitelpunkten im Diagramm und auf die Verwendung eines zweidimensionalen Arrays zum Speichern der Kanteninformationen im Diagramm (die Adjazenzbeziehung zwischen Scheitelpunkten). Die Adjazenzbeziehung zwischen Eckpunkten wird als Adjazenzmatrix bezeichnet. Die Speicherstruktur des gesamten Graphen G: #define MaxVertexNum 100 typedef char VertexType; typedef int EdgeType; typedef struct{ VertexType Vex[MaxVertexNum]; //Vertex-Tabelle EdgeType Edge[MaxVertexNum][MaxVertexNum];//Adjazenzmatrix, Kantentabelle int vexnum,arcnum; }MGraph;

Wenn es sich bei einem Diagramm um ein Diagramm mit geringer Dichte handelt, spart die Verwendung der Adjazenzlistenmethode viel Platz. Die Adjazenzlistenmethode des Diagramms kombiniert sequentielle Speicher- und Kettenspeichermethoden Erstellen Sie für jeden Scheitelpunkt im Diagramm eine einfach verknüpfte Liste. Der Knoten in der i-ten einfach verknüpften Liste ist an die Kante vi des Scheitelpunkts gebunden ausgehende Kantenliste) (Die Kantenliste ist „Edge“ ist wirklich erstaunlich) Jeder Knoten in der Kantentabelle stellt eine Kante dar, speichert jedoch eine Scheitelpunktnummer und lässt eine andere Scheitelpunktnummer (in der Scheitelpunkttabelle) weg. Der Kopfzeiger der Kantentabelle und die Scheitelpunktdateninformationen des Diagramms G werden nacheinander gespeichert (sogenannte Scheitelpunkttabelle). #define MaxVertexNum 100 typedef struct ArcNode{//edge Tabellenknoten int adjvex;//Die Position des Scheitelpunkts, auf den der Bogen zeigt struct ArcNode *next; //Info Typeinfo; //Das Kantengewicht des Netzwerks }ArcNode; typedef struct VNode{ VertexType-Daten; // Vertex-Informationen struct VNode *first;//Zeiger auf den ersten Bogen, der an den Scheitelpunkt angehängt ist }VNode, AdjList[MaxVertexNum]; typedef struct{ AdjList vertices;//Adjazenzliste int vexnum, arcnum;//Die Anzahl der Eckpunkte und Bögen des Diagramms }ALGraph

Eine vernetzte Liste ist eine verknüpfte Speicherstruktur eines gerichteten Graphen. Jeder Bogen im Graphen hat einen Knoten. Der Bogenknoten hat 5 Felder: (tailvex, headvex, hlink, tlink, info) tailvex und headvex sind jeweils die Ursprungs- und Einfügescheitelpunkte der Kante; hlink und tlink verbinden jeweils die Kantenknoten derselben Ursprungs- und Einfügungsscheitelpunkte. Der Scheitelpunktknoten hat 3 Felder: (Daten, Firstin, Firstout) Die vernetzte Liste ist nicht eindeutig, aber eine vernetzte Liste repräsentiert ein bestimmtes Diagramm In der vernetzten Liste ist es einfach, den In-Grad von V und den Out-Grad von V zu finden.

Adjazenz-Mehrfachliste ist eine Kettenspeicherstruktur eines ungerichteten Graphen Kantenknoten (mark,ivex,ilink,jvex,jlink,info) mark ist ein Flag-Feld, das markieren kann, ob diese Kante durchsucht wurde; ivex und jvex sind die Positionen der beiden an der Kante angehängten Eckpunkte im Diagramm; An den Scheitelpunkt JVEX Edge ist ein Zeigerfeld angehängt, das auf verschiedene Informationen im Zusammenhang mit der Kante verweist vertex(data,firstedge)

BFS löst das Single-Source-Shortest-Path-Problem void BFS_MIN_Distance(Graph G,int u){ for(i=0;i<G.vexnum;i) //d[i] stellt den kürzesten Weg von u nach i dar d[i]=∞;//Pfadlänge initialisieren besuchte[u]=TRUE; d[u]=0; EnQueue(Q,u); while(!isEmpty(Q)){ DeQueue(Q,u); for(w=FirstNeighbor(G,u);w>=0;w=NextN eighbor(G,u,w)) if(visited[w]){ besuchte[w]=TRUE; d[w]=d[u] 1;//Pfadlänge 1 EnQueue(Q,w); } } }

Breitenspannender Baum Die Adjazenzmatrix wird eindeutig gespeichert – ihr Spannbaum in der Breitenrichtung ist eindeutig Der Adjazenzlistenspeicher ist nicht eindeutig – sein Breiten-Spannungsbaum ist nicht eindeutig

Ähnlich wie bei der Vorbestellungsdurchquerung eines Baums bool besucht[MAX_VERTEX_NUM]; void DFSTraverse(Graph G){ for(v=0;v<G.vexnum;v) besucht[v] = FALSCH; for(v=0,v<G.vexnum;v) if(!visited[v]) DFS(G,v); } void DFS(Graph G,int v){ Besuch(v); besuchte[v] = TRUE; for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) if(!visited[w]){ DFS(G,w); } }

Graph-Traversal-Algorithmen können verwendet werden, um die Konnektivität des Graphen zu bestimmen. Wenn ein ungerichteter Graph ausgehend von einem beliebigen Scheitelpunkt verbunden ist, kann auf alle Scheitelpunkte im Graphen mit nur einem Durchlauf zugegriffen werden; Wenn ein gerichteter Graph verbunden ist und es einen Pfad vom Anfangspunkt zu jedem Scheitelpunkt im Diagramm gibt, kann auf alle Scheitelpunkte im Diagramm zugegriffen werden.

Prim-Algorithmus (BFS) Wählen Sie ähnlich wie bei Dijkstra zunächst einen Scheitelpunkt aus dem Diagramm aus und fügen Sie ihn dem Baum T hinzu. Wählen Sie dann einen Scheitelpunkt aus, der dem aktuellen Satz von Scheitelpunkten in T am nächsten liegt, und fügen Sie den Scheitelpunkt und die Kante zum Baum T hinzu Nach jeder Operation wird die Anzahl der Kanten um 1 erhöht, bis alle Scheitelpunkte im Diagramm zum Baum T hinzugefügt werden. T ist der minimale Spannbaum. Es müssen n-1 Kanten in T vorhanden sein voidPrim(G,T){ T=leere Menge; U={W}; while((V-U)!=empty set){//Wenn der Baum nicht alle Eckpunkte enthält Sei (u, v) die Kante, die u∈U und v∈(V-U) ergibt und das kleinste Gewicht hat; T=T∪{(u,v)};//Kanten werden in Bäume klassifiziert U=U∪{v};//Scheitelpunkte werden in Bäume klassifiziert } } Die zeitliche Komplexität des Prim-Algorithmus beträgt O(|V^2|) und hängt nicht von |E| ab. Daher eignet er sich zum Lösen des minimalen Spannbaums von Graphen mit dichten Kanten.

Kruskal-Algorithmus Im Gegensatz zum Prim-Algorithmus, der von den Eckpunkten aus expandiert, um einen minimalen Spannbaum zu erzeugen, wählt der Kruskal-Algorithmus geeignete Kanten in aufsteigender Reihenfolge der Gewichte aus, um einen minimalen Spannbaum zu erstellen. Zunächst bildet jeder Scheitelpunkt eine verbundene Komponente. Anschließend wird in der Reihenfolge der Kantengewichte von klein nach groß die Kante ausgewählt, die noch nicht ausgewählt wurde und das kleinste Gewicht aufweist, wenn der an der Kante befestigte Scheitelpunkt auf eine andere verbundene Komponente fällt Komponente der T-Komponente, fügen Sie diese Kante zu T hinzu, andernfalls verwerfen Sie diese Kante, bis alle Eckpunkte in T auf einer verbundenen Komponente liegen void Kruskal(V,T){ T=V; // T initialisieren, nur Scheitelpunkte numS=n;//Anzahl der verbundenen Komponenten while(numS>1){//Wenn die Anzahl der verbundenen Komponenten größer als 1 ist Nehmen Sie die Kante (v, u) mit dem kleinsten Gewicht aus E if (v und u gehören zu verschiedenen Zusammenhangskomponenten in T) T=T∪{(v,u)}; numS--; } } } Kruskals Algorithmus verwendet einen Heap zum Speichern der Kantenmenge, sodass jedes Mal nur O(log|E|) Zeit benötigt wird, um die Kante mit dem kleinsten Gewicht auszuwählen. Das Hinzufügen einer neuen Kante ähnelt dem Prozess der Lösung einer Äquivalenz Klasse und die Union-Suchmethode können verwendet werden. Datenstruktur zur Beschreibung von T, die Zeitkomplexität beträgt O(|E|log|E|), sodass Kruskal für Diagramme mit spärlichen Kanten und vielen Scheitelpunkten geeignet ist.

Dijkstra-Algorithmus (BFS) Kürzester Weg aus einer Hand; Der Dijkstra-Algorithmus legt eine Menge S fest, um die Eckpunkte des kürzesten Pfades aufzuzeichnen, der erhalten wurde. Zunächst wird der Quellpunkt v0 in S platziert. Jedes Mal, wenn ein neuer Eckpunkt vi in ​​die Menge S aufgenommen wird, muss der Quellpunkt v0 geändert werden zum aktuell kürzesten Scheitelpunkt im eingestellten V-S-Längenwert; negative Gewichtswerte an Kanten sind nicht zulässig Richten Sie zwei Hilfsarrays ein: dist[]: Zeichnen Sie die aktuell kürzeste Pfadlänge vom Quellpunkt v0 zu anderen Eckpunkten auf. Ausgangszustand: Wenn es einen Bogen von v0 nach vi gibt, ist dist[i] das Gewicht des Bogens, andernfalls wird dist[i] festgelegt ] zu ∞. (dist[] geht jeweils nur einen Schritt zurück – BFS-Idee) Pfad[]: Pfad[i] repräsentiert den Vorgängerknoten des kürzesten Pfades vom Quellpunkt zum Scheitelpunkt i. Am Ende des Algorithmus kann der kürzeste Weg vom Quellpunkt v0 zum Scheitelpunkt vi verfolgt werden. Zeichnen Sie beim manuellen Lösen ein Diktat-Array. Das Wichtigste ist, den Scheitelpunkt bei jeder Auswahl zum Satz S hinzuzufügen, den Pfadabstand jedes Punkts zu aktualisieren und dann den nächsten Schritt ausgehend vom letzten Scheitelpunkt des Satzes auszuführen S. Zeitkomplexität O(|V|^2)

Floyd-Algorithmus Der kürzeste Weg zwischen jedem Scheitelpunktpaar Die Rekursion erzeugt eine quadratische Matrixfolge n-ter Ordnung: A^-1,A^0,..A^N; wobei A^k[i][j] die Länge vom Scheitelpunkt i bis j darstellt und der k-te Scheitelpunkt verwendet wird als Entspannen Sie die mittleren Eckpunkte Die Zeitkomplexität beträgt O(|V|^3) (entspricht der einmaligen Ausführung des Dijkstra-Algorithmus für jeden Scheitelpunkt O(|V^2|)*|V|), Kanten mit negativen Gewichten sind nicht zulässig und können auf gerichtete Graphen/ungerichtete Graphen wirken (umgewandelt in gerichtete Graphen mit denselben bilateralen Seiten).

AOV-Netzwerk (Aktivität im Vertex-Netzwerk) Wenn ein DAG zur Darstellung eines Projekts verwendet wird, seine Scheitelpunkte Aktivitäten darstellen und die gerichtete Kante <Vi, Vj> eine Beziehung darstellt, in der Vi vor Vj stehen muss, wird diese Art von Diagramm als Netzwerk mit Scheitelpunkten bezeichnet, die Aktivitäten darstellen. Es gibt viele Algorithmen zur topologischen Sortierung von AOV-Netzwerken. Einer der am häufigsten verwendeten Algorithmen ist: 1. Wählen Sie einen Scheitelpunkt ohne Vorgänger aus dem AOV-Netzwerk aus und geben Sie ihn aus 2. Löschen Sie den Scheitelpunkt und alle von ihm ausgehenden gerichteten Kanten aus dem Netzwerk 3. Wiederholen Sie Schritt 1.2, bis das AOV-Netzwerk leer ist oder im aktuellen Netzwerk keine Scheitelpunkte ohne Vorgänger vorhanden sind (was anzeigt, dass im Diagramm ein Zyklus vorhanden sein muss). Da die Ausgabe jedes Scheitelpunkts das Löschen seiner Startkante erfordert, beträgt die zeitliche Komplexität der topologischen Sortierung O(|V| |E|) Darüber hinaus kann die topologische Sortierung auch mit DFS implementiert werden (beginnend mit den Scheitelpunkten mit einem Eingangsgrad von 0 und einem Ausgangsgrad von ungleich 0 nacheinander), und sie schlägt fehl, solange eine Rückverfolgung erfolgt, bis ein Strich abgeschlossen ist ) umgekehrte topologische Sortierung Beginnen Sie am Scheitelpunkt mit Out-Grad 0 Das AOV-Netzwerk verwendet Adjazenzmatrixspeicher. Wenn es sich um eine Dreiecksmatrix handelt, muss eine topologische Sequenz vorhanden sein und umgekehrt.

AOE-Netzwerk (Aktivität im Edge-Netzwerk) Ereignisse werden durch Scheitelpunkte dargestellt, Aktivitäten werden durch gerichtete Kanten dargestellt und die Kosten für den Abschluss der Aktivität werden durch das Gewicht auf der Kante dargestellt (z. B. die für den Abschluss der Aktivität erforderliche Zeit). Zwei Eigenschaften des AOE-Netzwerks: 1. Erst nachdem das durch einen Scheitelpunkt dargestellte Ereignis eintritt, können die Aktivitäten beginnen, die durch die gerichteten Kanten ausgehend vom Scheitelpunkt dargestellt werden. 2. Das Ereignis an einem Scheitelpunkt kann erst auftreten, nachdem die durch die eingehenden Kanten eines Scheitelpunkts dargestellten Aktivitäten abgeschlossen sind. Es gibt nur einen Scheitelpunkt mit einem In-Grad von 0 im AOE-Netzwerk, der als Start-Scheitelpunkt (Quellpunkt) bezeichnet wird und den Anfang des gesamten Projekts darstellt. Das AOE-Netzwerk hat auch nur einen Scheitelpunkt mit einem Out-Grad von 0 , genannt Endscheitelpunkt (Senke). Stellt das Ende des gesamten Projekts dar. Einige Aktivitäten im AOE-Netzwerk können parallel ausgeführt werden, aber alle Aktivitäten auf allen Pfaden können nicht enden, bis sie abgeschlossen sind. Daher wird unter allen Pfaden von der Quelle bis zur Senke der Pfad mit der größten Pfadlänge als kritischer Pfad bezeichnet Die Aktivitäten auf dem Pfad werden als kritische Aktivitäten bezeichnet (das Finden der kritischen Aktivitäten ist gleichbedeutend mit dem Finden des kritischen Pfads). Die kürzeste Zeit zum Abschluss des gesamten Projekts ist die Länge des kritischen Pfads.

Üben Sie ASL bei der Suche nach Erfolg und Misserfolg

Sequentielle Suche nach allgemeinen linearen Tabellen typedef struct{//Datenstruktur der Nachschlagetabelle ElemType *elem; //Basisadresse des Elementspeicherplatzes int TableLen;//Die Länge der Tabelle }SSTable; int Search_Seq(SSTable ST,ElemType key){ ST.elem[0] = key;//Sentinel for(i=ST.TableLen;ST.elem[i]!=key;--i);//Blick von hinten nach vorne gib i zurück; } Im obigen Algorithmus wird ST.elem[0] als Sentinel bezeichnet, sodass die interne Schleife von Search_Seq nicht beurteilen muss, ob das Array außerhalb der Grenzen liegt, da die Schleife definitiv herausspringt, wenn i==0 ist befriedigt. Durch die Einführung von Sentinels können viele unnötige Beurteilungen vermieden und dadurch die Programmeffizienz verbessert werden.

Sequentielle Suche in geordneter Liste Wenn vor der Suche bekannt ist, dass die Schlüsselwörter in der Tabelle in Ordnung sind, ist nach einem fehlgeschlagenen Vergleich kein Vergleich mit dem anderen Ende der Tabelle erforderlich, um den Suchfehler zurückzugeben, wodurch sich die durchschnittliche Suchlänge verringert Suchfehler. Ein Entscheidungsbaum kann verwendet werden, um den Suchprozess einer geordneten linearen Liste zu beschreiben. Die kreisförmigen Knoten stellen die Elemente dar, die in der geordneten linearen Liste vorhanden sind. Die rechteckigen Knoten sind Ihre eigenen fiktiven leeren Knoten , dann Entsprechend gibt es n 1 Knoten, bei denen die Suche fehlgeschlagen ist. Die durchschnittliche Suchlänge (ASL) einer fehlgeschlagenen Suche beträgt (1 2 .. n n)/(n 1); die Wahrscheinlichkeit, jeden „fehlgeschlagenen Knoten“ zu finden, beträgt 1/n 1

ASL-Erfolg=(n 1)/2

int Binary_Search(SeqList L,ElemType key){ int low=0,high=L.TableLen-1,mid; while(low<=high){ mittel = (niedrig hoch)/2; if(L.elem[mid]==key) return mid; sonst if(L.elem[mid]<key){ niedrig = mittel 1; // mid = (low high)/2; } anders{ hoch = mittel-1; // mid = (low high)/2; } } return -1; }

B Baumhöhe Die Anzahl der Festplattenzugriffe, die für die meisten Vorgänge in einem B-Baum erforderlich sind, ist proportional zur Höhe des B-Baums. Jeder Knoten im Baum hat höchstens m Teilbäume und m-1 Schlüsselwörter, und die Anzahl der Schlüsselwörter sollte n≤m^h-1 erfüllen; Die h1-te Schicht hat mindestens 2(m/2 Obergrenze)^(h-1) Knoten, und die h1-te Schicht ist ein Blattknoten, der keine Informationen enthält; Für einen B-Baum mit n Schlüsselwörtern ist der Knoten, an dem die Blattknotensuche fehlschlägt, n 1, also ist n 1>=2 (m/2 übernimmt die Obergrenze)^(h-1), d. h. h≤log ( m/2 übernimmt die Obergrenze)((n 1)/2 1)

B-Tree-Suche 1. Knoten im B-Baum finden 2. Suchen Sie nach Schlüsselwörtern innerhalb des Knotens Der Suchvorgang von 1. wird auf der Festplatte ausgeführt, und der Suchvorgang von 2. wird im Speicher ausgeführt; Nachdem Sie den Zielknoten gefunden haben, lesen Sie ihn in den Speicher ein und verwenden Sie dann die sequentielle Suchmethode oder die binäre Suchmethode innerhalb des Knotens.

Einfügen in den B-Baum Wenn Sie den Standort direkt einfügen, nachdem Sie ihn nicht gefunden haben, werden die Anforderungen in der B-Baum-Definition zerstört. 1. Positionierung: Suchen Sie den Nicht-Blattknoten in der untersten Ebene (finden Sie den Blattknoten und nehmen Sie den Nicht-Blattknoten der vorherigen Ebene). 2. Einfügung: Die Anzahl der Schlüsselwörter in jedem nicht fehlgeschlagenen Knoten liegt innerhalb des Intervalls [m/2 nimmt die Obergrenze -1, m-1] an und kann direkt eingefügt werden; Wenn die Anzahl der eingefügten Knotenschlüsselwörter größer als m-1 ist, wird der Knoten geteilt. Aufteilungsmethode: Nehmen Sie die Obergrenze von der mittleren Position m/2 und teilen Sie das Schlüsselwort in zwei Teile. Der linke Teil wird im ursprünglichen Knoten enthalten und der rechte Teil wird im neuen Knoten an der mittleren Position platziert. m/2 nimmt den oberen Grenzpunkt, um den übergeordneten Knoten des ursprünglichen Knotens einzufügen;

Löschung des B-Baums Wenn sich das gelöschte Schlüsselwort k nicht im Endknoten (dem niedrigsten Nicht-Blattknoten) befindet, kann k durch k's Vorgänger (Nachfolger) k' ersetzt werden, und dann wird k' im entsprechenden Knoten gelöscht und in ein Schlüsselwort umgewandelt im Endknoten; Wenn sich das gelöschte Schlüsselwort am Endknoten (dem niedrigsten Nicht-Blattknoten) befindet, gibt es drei Situationen: 1. Schlüsselwörter direkt löschen: Die Anzahl der Schlüsselwörter ≥ m/2 hat die Obergrenze -1 2. Brüder sind genug: Die Anzahl der Schlüsselwörter = m/2, die Obergrenze beträgt -1, und die Anzahl der linken und rechten (benachbarten) Geschwisterschlüsselwörter ist größer oder gleich m/2, die Obergrenze beträgt. Dann verwenden seine Brüder, Eltern und er selbst die Vater-Sohn-Transpositionsmethode, um ein Gleichgewicht zu erreichen 3. Es sind nicht genügend Brüder vorhanden: Die Anzahl der gelöschten Schlüsselwörter ist = m/2 und die Obergrenze beträgt -1. Zu diesem Zeitpunkt sind die Knoten seiner linken und rechten (benachbarten) Brüder ebenfalls = m/2 und die Obergrenze ist 1. Dann werden die Schlüsselwörter nach dem Löschen mit den Schlüsselwörtern im linken (rechten) Geschwisterknoten zusammengeführt und die Anzahl der Schlüsselwörter im übergeordneten Knoten wird um eins reduziert Der Wurzelknoten kann direkt auf 0 reduziert werden (Wurzelknoten löschen). Der neue Knoten wird als Wurzel bezeichnet.

B-Baum-bezogene Eigenschaften Es ist notwendig, die Beziehung zwischen der Anzahl der Schlüsselwörter und der Anzahl der Teilbäume zu verstehen: Die Anzahl der Schlüsselwörter ist 1 kleiner als die Anzahl der Teilbäume. Alle nichtterminalen Knoten außer dem Wurzelknoten haben mindestens m/2 Obergrenze-Teilbäume (m/2 Obergrenze – 1 Schlüsselwort) Schlüsselwörter in Knoten werden in aufsteigender Reihenfolge von links nach rechts sortiert. Das heißt, m/2 nimmt die Obergrenze -1 ≤ n ≤ m-1 an, das heißt, [m/2 nimmt die Obergrenze -1, m-1] an.

B-Baum ist ein deformierter B-Baum, der als Reaktion auf die Anforderungen der Datenbank erscheint. Ein B-Baum m-Ordnung erfüllt die folgenden Bedingungen: 1. Jeder Zweigknoten hat höchstens m Teilbäume 2. Der Nicht-Blatt-Wurzelknoten hat mindestens zwei Teilbäume 3. Die Anzahl der Teilbäume eines Knotens entspricht der Anzahl der Schlüsselwörter 4. Alle Blattknoten enthalten alle Schlüsselwörter und Zeiger auf entsprechende Datensätze. Die Schlüsselwörter sind in der Reihenfolge ihrer Größe in den Blattknoten angeordnet, und benachbarte Blattknoten sind in der Reihenfolge ihrer Größe miteinander verbunden.

Hauptunterschiede zu B-Bäumen: 1. Ein Knoten mit n Schlüsselwörtern im B-Baum hat n Teilbäume, und jedes Schlüsselwort entspricht einem Teilbaum; n Schlüsselwortknoten im B-Baum enthalten n-1 Teilbäume. 2. Der Bereich der Anzahl n von Schlüsselwörtern für jeden Knoten im B-Baum beträgt [m/2 nimmt die Obergrenze, m] (relativ zur Ober- und Untergrenze der Anzahl n von Knotenschlüsselwörtern im B-Baum plus 1). ); Wurzelknoten B: [1,m],B:[1,m-1] 3. In Baum B enthalten Blattknoten Informationen (alle Schlüsselwörter), und Nicht-Blattknoten dienen nur als Indizes. 4. Jede Suche im B-Baum, ob erfolgreich oder nicht, ist ein Pfad vom Wurzelknoten zum Blattknoten.

Aufgrund der bisherigen linearen Tabellen- und Baumsuche gibt es keinen eindeutigen Zusammenhang zwischen der Position des Datensatzes in der Tabelle und dem Schlüssel des Datensatzes. Daher muss bei der Suche nach Datensätzen in diesen Tabellen eine Reihe von Schlüsselwörtern verglichen werden. Diese Suchmethode basiert auf Vergleichen, und die Effizienz der Suche hängt von der Anzahl der Vergleiche ab. Hash-Funktion: Die Funktion Hash(key)=Addr, die die Schlüsselwörter in der Nachschlagetabelle der Adresse zuordnet, die dem Schlüsselwort entspricht, d. h. unter Verwendung der Eigenschaften des Schlüsselworts selbst und mit möglichst wenig „Vergleichs“-Suchen. Die Hash-Funktion kann mehrere verschiedene Schlüsselwörter derselben Adresse zuordnen, was als „Kollision“ bezeichnet wird. Diese verschiedenen Schlüsselwörter, die kollidieren, werden Synonyme genannt. Einerseits minimiert eine gut gestaltete Hash-Funktion Konflikte; andererseits sind Konflikte unvermeidlich und es müssen Methoden für den Umgang mit ihnen entwickelt werden. Hash-Tabelle: Eine Datenstruktur, auf die basierend auf Schlüsselwörtern direkt zugegriffen wird. Mit anderen Worten: Die Hash-Tabelle stellt eine direkte Zuordnungsbeziehung zwischen Schlüsselwörtern und Speicheradressen her. Im Idealfall beträgt die zeitliche Komplexität der Suche in einer Hash-Tabelle O(1), was bedeutet, dass sie nichts mit der Anzahl der Elemente zu tun hat.

1. Der Definitionsbereich der Hash-Funktion muss alle Speicherschlüssel umfassen, und der Wertebereich hängt von der Größe oder dem Adressbereich der Hash-Tabelle ab. 2. Die von der Hash-Funktion berechneten Adressen sollten mit gleicher Wahrscheinlichkeit gleichmäßig im gesamten Adressraum verteilt sein, wodurch das Auftreten von Konflikten verringert wird. 3. Die Hash-Funktion sollte so einfach wie möglich sein und in kurzer Zeit den Hash für jedes Schlüsselwort berechnen können.

Geordnete Folge L[1..i-1]L(i) Ungeordnete Folge L[i 1…n] void InsertSort(ELemType A[],int n){ int i,j; for(i=2;i<=n;i){//Fügen Sie die folgenden n-1 Zahlen vorne ein if(A[i]<A[i-1]){ A[0] = A[i];//Als Sentinel kopieren, A[0] speichert keine Elemente for(j=i-1;A[0]<A[j];j--){//Finden Sie die Einfügeposition von hinten nach vorne A[j 1] = A[j]; A[j 1] = A[0]; } } Raumkomplexität O(1), Raumkomplexität O(n^2) Bester Fall: Die Elemente in der Tabelle sind bereits sortiert, Zeit O(n) Schlimmster Fall: Die Reihenfolge der Elemente in der Tabelle ist umgekehrt, Zeit O(n^2) Da jeder Vergleich von hinten nach vorne erfolgt, ist er stabil. Geeignet für sequentielle Listen und verknüpfte Listen (Sie können die angegebene Elementposition von vorne nach hinten finden) Geeignet für grundsätzlich geordnete Sortiertabellen mit kleinen Datenmengen

void InsertSort(ElemType A[],int n){ int i,j,low,high,mid; for(i=2;i<=n;i ){ A[0] =A[i]; niedrig=1;hoch=i-1; while(low<=high){ mittel = (niedrig hoch)/2; if(A[mid]>A[0])high=mid-1; sonst niedrig=mittel 1; } for(j=i-1;j>=high 1;j--) A[j 1] = A[j]; A[hoch 1]=A[0]; } } Zeitkomplexität O(n^2) Die Anzahl der Vergleiche hat nichts mit dem Ausgangszustand der zu sortierenden Liste zu tun, sondern hängt nur von der Anzahl n der Elemente in der Liste ab; Die Anzahl der Verschiebungen hängt vom Ausgangszustand der zu sortierenden Liste ab

Teilen Sie die Sortiertabelle zunächst in mehrere Untertabellen auf (Datensätze mit demselben Inkrement bilden eine Untertabelle di 1 = di / 2, und das letzte Inkrement ist gleich 1) und führen Sie eine direkte Einfügungssortierung für jede Untertabelle durch die gesamte Tabelle. Wenn die Elemente grundsätzlich in der richtigen Reihenfolge sind, wird für alle Datensätze eine Direkteinfügungssortierung durchgeführt. void ShellSort(ELemType A[],int n){ //A[0] ist eine temporäre Speichereinheit, kein Wächter. Wenn j<=0, ist die Einfügeposition erreicht for(dk=n/2;dk>=1;dk/=2)//Schrittgrößenänderung for(i=di 1;i<=n;i) if(A[i]<A[i-dk]){//A[i] muss in die geordnete inkrementelle Untertabelle eingefügt werden A[0]=A[j];//vorübergehend in A[0] gespeichert for(j=i-dk;j>0&&A[0]<A[j];j-=dk) A[j dk]=A[j]; } } Es gibt keine eindeutige Schlussfolgerung zur Zeitkomplexität, es wird jedoch angenommen, dass sie O(n^2) ist. Sortierinstabilität Geeignet für Sequenztabelle

Vergleichen Sie die Werte benachbarter Elemente von hinten nach vorne (von vorne nach hinten) und tauschen Sie sie aus, wenn sie in umgekehrter Reihenfolge vorliegen. Schlüsselwörter schweben nach und nach wie Blasen an der Oberfläche void BubbleSort(ELemType A[],int n){ for(int i=0;i<n-1;i){//n-1 mal Flag = false; for(j=n-1;j>i;j--) if(A[j-1]>A[j]){//Wenn die Reihenfolge umgekehrt ist swap(A[j-1],A[j]); Flag = wahr; } if(flag==false)//Die Flagge des Endes der Blasensortierung: kein einziger Austausch zurückkehren; } } Raum O(1), Zeit O(n^2) Stabilität: Elemente werden nicht ausgetauscht, wenn sie gleich und stabil sind Die durch die Blasensortierung erzeugte Reihenfolge ist global geordnet, was nicht der lokalen Reihenfolge der Einfügungssortierung entspricht.

Wählen Sie ein beliebiges Element in der Liste aus, das als Pivot sortiert werden soll (normalerweise das erste Element), und teilen Sie die sortierte Sequenz in zwei unabhängige Teile L[1..k-1] L(k) L[k 1, ...n] , sodass die erste Hälfte kleiner als der Pivot und die zweite Hälfte größer als der Pivot ist und der Pivot an der Endposition L(k) platziert wird. Dieser Vorgang wird als One-Pass-Schnellsortierung (One-Pass-Division) bezeichnet. void QuickSort(ELemType A[],int low,int high){ if(low<high){//Bedingung für rekursives Herausspringen int Pivotpos = Partition(A,low,high);//Partition QuickSort(A,low,pivotpos-1); QuickSort(A,pivotpos 1,high); } } Die Leistung und der Schlüssel des Schnellsortierungsalgorithmus ergeben sich aus der Partitionsoperation. Es gibt viele Versionen der Partitionsoperation. Hier wird das erste Element als Pivot-Pivot für die Partitionierung verwendet. int Partition(ElemType A[],int low,int high){ ElemType-Pivot=A[niedrig]; while(low<high){//Schleifenunterbrechungsbedingung while(low<high ​​​​&& A[high]>=pivot) --high; A[niedrig]=A[hoch]; whilie(low<high ​​​​&& A[low]<=pivot) low; A[hoch] = A[niedrig]; } A[low] = Pivot; Rückkehr niedrig; } Platz: Erfordert einen rekursiven Arbeitsstapel, vorzugsweise O(log2n), durchschnittlich O(log2n) (so weit wie möglich in zwei Hälften geteilt, wie ein vollständiger Binärbaum), Im schlimmsten Fall ist O(n) (die Anzahl der Elemente in den beiden geteilten Bereichen beträgt n-1 und 0, es sind n-1 rekursive Aufrufe erforderlich und die Stapeltiefe beträgt O(n)). Zeit: Die Laufzeit der Schnellsortierung hängt davon ab, ob die Division symmetrisch ist. Der schlimmste Fall ist halb n-1 und halb 0. Die maximale Asymmetrie tritt auf jeder Rekursionsebene auf, die der anfänglichen geordneten Sequenz entspricht (sequentiell oder umgekehrt). Ordnung), ist O(n^2) Stabilität: Instabil, die gleichen Elemente werden auf verschiedene Teile übertragen und die relativen Positionen werden geändert. Hinweis: Die schnelle Sortierung erzeugt keine geordnete Teilsequenz, aber das Pivot-Element wird in jedem Durchgang an der endgültigen Position platziert. Verbessern Sie die Effizienz: 1. Wählen Sie Pivot-Elemente aus, die die Sequenz so weit wie möglich unterteilen können. 2. Wählen Sie Pivot-Elemente zufällig aus Die idealste Unterteilung: Beide Textaufgaben sind kleiner als n/2, die Zeit beträgt O(nlog2n) und die Laufzeit der schnellen Sortierung liegt im Durchschnitt sehr nahe am besten Fall. Quicksort ist der Sortieralgorithmus mit der besten Durchschnittsleistung unter allen internen Sortieralgorithmen.

void SelectSort(ElemType A[],int n){ for(i=0;i<n-1;i)//Insgesamt n-1 Mal min=i;//Notieren Sie die minimale Elementposition for(j=i 1;j<n;j) if(A[j]<A[min]) min = j; if(min!=i) swap(A[i],A[min]); } } Raum O(1), Zeit O(n^2) Stabilität: Es kann dazu führen, dass sich die relative Position von Schlüsselwörtern, die dieselben Elemente enthalten, ändert, was instabil ist.

Der Heap ist ein Array-Objekt eines Baums. Ein eindimensionales Array kann als vollständiger Binärbaum betrachtet werden, der die Eigenschaften erfüllt 1.L(i)>=L(2i) und L(i)>=L(2i 1) oder 2.L(i)<=L(2i) und L(i)<=L(2i 1) ( 1<=i<=n/2 (nimm die Grenze); Diejenigen, die 1. erfüllen, werden als große Root-Heaps (große Top-Heaps) betrachtet, und diejenigen, die 2. erfüllen, werden als kleine Root-Heaps (kleine Top-Heaps) betrachtet. Heap-Sortierung: Zuerst werden n Elemente im Array in einen anfänglichen Heap eingebaut; nach der Ausgabe des oberen Elements des Heaps wird das untere Element des Heaps zu diesem Zeitpunkt nicht mehr an die Spitze des Heaps gesendet erfüllt die Eigenschaften eines großen Wurzelhaufens und der Heap wird an die Spitze des Heaps verschoben, sodass er weiterhin die Natur eines großen oberen Heaps beibehalten kann. Geben Sie dann das oberste Element des Turms aus und wiederholen Sie den Vorgang, bis nur noch ein Element im Heap übrig ist. Heap-Sortieralgorithmus: void HeapSort(ElemType A[],int len){ BuildMaxHeap(A,len); for(i=len;i>1;i--){ Swap(A[i],A[1]);//Gib das obere Element des Heaps aus und tausche es mit dem unteren Element des Heaps aus HeadAdjust(A,1,i-1);//Ordnen Sie die verbleibenden i-1-Elemente in einem Stapel an } } Die Heap-Sortierung eignet sich für Situationen, in denen es viele Schlüsselwörter gibt (in der Größenordnung von Hunderten von Millionen). Beispiel: Um die 100 höchsten Maximalwerte unter 100 Millionen Zahlen auszuwählen, verwenden Sie zunächst ein Array von 100, lesen Sie die ersten 100 Zahlen, erstellen Sie einen kleinen oberen Heap und lesen Sie dann die verbleibenden Zahlen nacheinander den oberen Teil des Heaps, verwerfen Sie sie andernfalls ersetzen Sie den oberen Teil des Heaps durch diese Zahl und ändern Sie die Größe des Heaps. Nachdem die Daten gelesen wurden, sind die 100 Zahlen im Heap die erforderlichen. Raumeffizienz O(1), Zeiteffizienz O(nlog2n) instabil

Unter der Annahme, dass die zu sortierende Tabelle n Datensätze enthält, kann sie als n geordnete Untertabellen mit einer Länge von jeweils 1 betrachtet und dann paarweise zusammengeführt werden, um n/2 nach oben begrenzte Datensätze mit einer Länge von 2 oder 1 zu erhalten. Sequenzliste; weiterhin zwei nacheinander zusammenführen, bis sie zu einer geordneten Liste der Länge n zusammengeführt wird. Diese Methode wird als 2-Wege-Zusammenführungssortierung bezeichnet. ElemType *B=(ElemType*)malloc((n 1)*sizeof(ElemType));//Hilfsarray B void Merge(ElemType A[],int low,int mid,int high){ //Tabelle A[low..mid]A[mid 1..high] werden jeweils geordnet, füge sie zu einer geordneten Liste zusammen for(int k=low;k<=high;k) B[k]=A[k]; for(i=low;j=mid 1;k=i,i<=mid&&j<=high;k ){ if(B[i]<=B[j]) A[k]=B[i ]; sonst A[k]=B[j]; } while(i<=mid) A[k ]=B[i ]; while(j<=high) A[k ]=B[j ]; } void MergeSort(ELemType A[],int low,int high){ if(low<high){ int mid=(low high)/2; MergeSort(A,low,mid); MergeSort(A,mid 1,high); Merge(A,low,mid,high); } } Raumeffizienz: n Einheiten Hilfsraum, Raumkomplexität O(n) Zeiteffizienz: Jede Zusammenführung ist O(n), und die Zusammenführung der oberen Log2n-Grenze ist erforderlich. Die Zeitkomplexität des Algorithmus beträgt O(nlog2n). Stabilität: Die Operation Merge() ändert nicht die relative Reihenfolge von Datensätzen mit denselben Schlüsselwörtern, stabil

Sortieren Sie nach der Keyword-Größe. Das Schlüsselwort jedes Knotens aj besteht aus d Tupeln, kd-1j ist das primäre Schlüsselwort und kj0 ist das sekundäre Schlüsselwort. Um eine Sortierung nach mehreren Schlüsselwörtern zu erreichen, gibt es normalerweise zwei Methoden: 1. Das höchstwertige Bit zuerst (MSD), mehrere kleinere Teilsequenzen Schicht für Schicht entsprechend der abnehmenden Gewichtung der Schlüsselwörter aufteilen und schließlich alle Teilsequenzen zu einer geordneten Sequenz verbinden. 2. Niedrigste Ziffer zuerst (LSD), sortieren Sie in aufsteigender Reihenfolge der Schlüsselwortgewichtung, um eine geordnete Reihenfolge zu bilden. arbeiten: 1. Verteilung: Leeren Sie die Warteschlange Q0 ... Qr-1 und fügen Sie sie dann entsprechend dem entsprechenden Bit jedes Knotens der entsprechenden Warteschlange hinzu. 2. Sammlung: Verbinden Sie die Warteschlangenknoten von Q0..Qr-1 Ende an Ende, um eine neue Knotensequenz zu erhalten und eine neue lineare Tabelle zu bilden. Beispiel: Um Sequenzen unter 1000 zu sortieren, bestimmen Sie zunächst die Basis r (kann als r-Basis betrachtet werden). Die Basis von 1000 ist 10, daher sind während des Sortiervorgangs 10 Kettenwarteschlangen erforderlich. Zahlen unter 1000 sind dreistellig, daher sind drei „Verteilungs“- und „Sammel“-Vorgänge erforderlich. Alle Datensätze mit demselben Schlüsselwort mit der niedrigsten Ziffer (Einerziffer) werden einer Warteschlange zugewiesen, und dann wird der „Sammel“-Vorgang ausgeführt. Platzeffizienz: Der für eine Sortierfahrt erforderliche Hilfsspeicherplatz beträgt r (r Warteschlangen: r Warteschlangenkopfzeiger, r Warteschlangenendzeiger), O(r) Zeiteffizienz: d Durchläufe der Zuweisung und Sammlung, ein Durchgang der Zuweisung erfordert O(n), ein Durchgang der Sammlung erfordert O(r), die zeitliche Komplexität beträgt O(d(n r)), unabhängig vom Anfangszustand der Sequenz . Stabilität: Die Radix-Sortierung selbst erfordert, dass die bitweise Sortierung stabil sein muss, also ist sie stabil!

1. Wenn n klein ist, kann eine direkte Einfügungssortierung oder eine einfache Auswahlsortierung verwendet werden. Da die direkte Einfügungssortierung mehr Datensatzverschiebungen erfordert als die einfache Auswahlsortierung, ist die einfache Auswahlsortierung besser, wenn der Datensatz selbst eine große Menge an Informationen enthält. 2. Wenn der Anfangszustand der Datei grundsätzlich nach Schlüsselwörtern geordnet ist, empfiehlt es sich, Direkteinfügung oder Blasensortierung zu verwenden. 3. Wenn n groß ist, verwenden Sie die Sortiermethode O(nlog2n): Schnellsortierung, Heap-Sortierung oder Zusammenführungssortierung. Die Schnellsortierung gilt derzeit als die beste Methode der vergleichsbasierten internen Sortierung. Wenn die zu sortierenden Schlüsselwörter zufällig verteilt sind, erfordert die Schnellsortierung im Durchschnitt weniger Zeit als die Schnellsortierung nicht eintreten. Aber beide Sortierungen sind instabil. Wenn ein stabiler O(nlog2n)-Algorithmus erforderlich ist, wird die Zusammenführungssortierung verwendet, das Zusammenführen von Paaren aus einem einzelnen Datensatz wird jedoch nicht empfohlen. Sie können normalerweise in Kombination mit der direkten Einfügungssortierung verwendet werden: Verwenden Sie zunächst die direkte Einfügungssortierung, um längere geordnete Unterteilungen zu erhalten. Dateien und fügen Sie sie dann einzeln zusammen. Die Direkteinfügungssortierung ist stabil, und die verbesserte Zusammenführungssortierung ist ebenfalls stabil. 4. Bei der vergleichsbasierten Sortiermethode treten nach jedem Vergleich zweier Schlüsselwortgrößen nur zwei mögliche Übergänge auf. Daher kann ein Binärbaum verwendet werden, um den Vergleichsentscheidungsprozess zu beschreiben. Es kann bewiesen werden, dass: wenn es n Dateien gibt Wenn Schlüsselwörter zufällig verteilt sind, benötigt jeder Sortieralgorithmus, der auf „Vergleich“ basiert, mindestens O(nlog2n) Zeit. 5. Wenn n sehr groß ist und die Anzahl der aufgezeichneten Schlüsselwörter klein ist und zerlegt werden kann, ist es besser, die Basissortierung zu verwenden. 6. Wenn der Datensatz selbst eine große Menge an Informationen enthält, kann eine verknüpfte Liste als Speicherstruktur verwendet werden, um zu vermeiden, dass viel Zeit mit dem Verschieben des Datensatzes verschwendet wird.

Die im Speicher durchgeführte Sortierung wird als interne Sortierung bezeichnet. In vielen Anwendungen müssen große Dateien sortiert werden, und die gesamte Datei kann zum Sortieren nicht in den Speicher kopiert werden. Daher müssen die zu sortierenden Datensätze im externen Speicher abgelegt werden. Beim Sortieren werden die Daten Teil für Teil zum Sortieren übertragen. Während des Sortiervorgangs ist ein mehrfacher Austausch zwischen Speicher und externem Speicher erforderlich. Diese Sortierung wird als externe Sortierung bezeichnet

Der Zeitaufwand während des externen Sortiervorgangs berücksichtigt hauptsächlich die Anzahl der Festplattenzugriffe, also die Anzahl der IOs Bei der externen Sortierung wird normalerweise die Zusammenführungssortierung verwendet: 1. Teilen Sie die Dateien im externen Speicher entsprechend der Größe des Speicherpuffers in Unterdateien der Länge l auf, lesen Sie sie nacheinander in den Speicher ein, sortieren Sie sie mithilfe der internen Sortiermethode und schreiben Sie die geordneten Unterdateien Diese geordneten Unterdateien werden nach dem Zurücksortieren in den externen Speicher als zusammengeführte Segmente oder sequentielle Zeichenfolgen bezeichnet. 2. Führen Sie diese zusammengeführten Segmente nacheinander zusammen, sodass die zusammengeführten Segmente allmählich von klein nach groß zunehmen, bis die gesamte geordnete Datei erhalten wird. Beim Zusammenführen in einem Durchgang werden alle Segmente derselben aktuellen Ebene zu einem zusammengeführt Gesamte externe Sortierzeit = Zeit, die für die interne Sortierung benötigt wird, Zeit für das Lesen und Schreiben externer Informationen, Zeit, die für die interne Zusammenführung benötigt wird Die Zeit zum Lesen und Schreiben externer Speicherinformationen ist viel länger als die Zeit zum internen Sortieren und internen Zusammenführen. Das Lesen und Schreiben externer Speicherinformationen basiert auf „Festplattenblöcken“. Daher beträgt die Gesamtzahl der erforderlichen Lese- und Schreibvorgänge: 2*Gesamtzahl der Datensätze/Anzahl der Datensätze in einem Festplattenblock*n (Anzahl der Male) Gesamtzahl der Datensätze/Anzahl der Datensätze in einem Plattenblock (interne Sortierung erfordert auch ein vollständiges Lesen und Schreiben) Führen Sie für r anfängliche Zusammenführungssegmente eine k-Wege-balancierte Zusammenführung durch. Die Höhe des Baums (invertierter k-ary-Baum) = logkr und die Obergrenze = die Anzahl der Zusammenführungsdurchgänge S Es ist ersichtlich, dass durch Erhöhen der Anzahl der Zusammenführungspfade k oder durch Verringern der Anzahl der anfänglichen Zusammenführungssegmente r die Anzahl der Zusammenführungsdurchgänge S verringert werden kann, wodurch die Anzahl der Festplatten-E/As verringert und die Geschwindigkeit der externen Sortierung verbessert wird.

Eine Erhöhung der Anzahl der Zusammenführungspfade k kann die Anzahl der Zusammenführungsdurchgänge S verringern, erhöht jedoch die interne Zusammenführungszeit. Bei der internen Zusammenführung sind für die Auswahl des kleinsten Schlüsselworts unter k Elementen k-1 Vergleiche erforderlich, und für jede Zusammenführung von n Elementen sind (n-1)(k-1) Vergleiche erforderlich Anzahl der für die Zusammenführung erforderlichen Vergleiche beträgt S(n-1)(k-1)=log2r nimmt die Obergrenze an (n-1)(k-1)/log2k nimmt die Obergrenze an, wobei (k-1)/log2k die Obergrenze annimmt und mit wächst Wachstum von k. Daher kann der gewöhnliche interne Zusammenführungssortierungsalgorithmus nicht verwendet werden.

Um r zu reduzieren, benötigt r=n/l eine Obergrenze, daher müssen wir einen Weg finden, ein längeres anfängliches Zusammenführungssegment l zu erzeugen. Angenommen, die zu sortierende Anfangsdatei ist FI, die anfängliche Zusammenführungssegment-Ausgabedatei ist FO, der Speicherarbeitsbereich ist WA, FO und WA sind anfänglich leer und WA kann w Datensätze aufnehmen. Die Schritte des Ersetzungsauswahlalgorithmus sind wie folgt: 1. Geben Sie w Datensätze von FI in den Arbeitsbereich WA ein 2. Wählen Sie den Datensatz mit dem minimalen Schlüsselwortwert aus WA aus und zeichnen Sie ihn als MINIMAX auf 3. MINIMAX auf FO aufzeichnen 4. Wenn FI nicht leer ist, geben Sie den nächsten Datensatz von FI an WA aus 5. Wählen Sie aus allen Datensätzen in WA den kleinsten Schlüsselwortdatensatz aus, dessen Schlüsselwörter größer als die Schlüsselwörter des MINIMAX-Datensatzes sind, als neuen MINIMAX-Datensatz. 6. Wiederholen Sie die Schritte 3–5, bis kein neues MINIMAX in WA ausgewählt werden kann, erhalten Sie ein anfängliches Zusammenführungssegment und geben Sie ein Endflag des Zusammenführungssegments an FO aus. 7. Wiederholen Sie die Schritte 2–6, bis WA leer ist und alle anfänglichen zusammengeführten Segmente erhalten sind. Der Prozess der Auswahl der MINIMAX-Aufzeichnung in WA erfordert die Verwendung von Verliererbäumen.

Nachdem die Datei durch Substitutionsauswahl sortiert wurde, werden zunächst zusammengeführte Segmente unterschiedlicher Länge erhalten. Wie kann die Zusammenführungsreihenfolge der anfänglichen Zusammenführungssegmente mit unterschiedlichen Längen organisiert werden, um die Anzahl der E/As zu minimieren? Zeichnen Sie den entsprechenden Zusammenführungsbaum. Die gewichtete Pfadlänge WPL des Baums ist die Gesamtzahl der während des rekursiven Prozesses gelesenen Datensätze. Erweitern Sie die Idee des Huffman-Baums auf den Fall des k-ary-Baums. Lassen Sie im Zusammenführungsbaum zuerst das anfängliche Zusammenführungssegment mit einer kleinen Anzahl von Datensätzen und das anfängliche Zusammenführungssegment mit einer großen Anzahl von Datensätzen zusammenführen zuletzt zusammengeführt Die gesamte IO kann mit der geringsten Anzahl von Malen erstellt werden Der beste Zusammenführungsbaum. Methode zum Erstellen des besten Zusammenführungsbaums: Wenn das anfängliche Zusammenführungssegment nicht ausreicht, um einen strengen k-ary-Baum zu bilden, muss ein „virtuelles Segment“ mit einer Länge von 0 hinzugefügt werden. Wie bestimme ich die Anzahl der hinzuzufügenden virtuellen Segmente? Ein strenger k-ary-Baum hat n0=(k-1)nk 1. Wenn (n0-1)%(k-1)=0, dann kann ein k-Fork-Mergebuch mit nk internen Knoten erstellt werden. Wenn (n0-1)%(k-1)=u!=0, können k-u-1 leere Zusammenführungssegmente hinzugefügt werden, um einen Zusammenführungsbaum zu erstellen