// Die statische Zuweisung definiert die Sequenztabelle. Der Speicherplatz ist statisch und die Größe ist von Anfang an festgelegt. #define MaxSize 10//Definieren Sie die maximale Länge typedef struct{ ElemType data[MaxSize]; //Statisches „Array“ zum Speichern von Datenelementen verwenden int length; //Aktuelle Länge der Sequenztabelle }SqList; //Typdefinition der Sequenzliste (statische Zuordnungsmethode) ElemType bezieht sich auf den von Ihnen definierten Datentyp, z. B. int, double //Initialisierungssequenztabelle #include<stdio.h> #define MaxSize10 typedef struct{ int data[MaxSize]; int Länge; }SqList; void InitList(SqList &L){ for(int i=0;i<MaxSize;i) L.data[i]=0; //Alle Datenelemente auf Standardanfangswerte setzen L.length=0; //Setzen Sie die Anfangslänge der Sequenztabelle auf 0 } int main(){ SqList L; //Eine Sequenzliste deklarieren InitList(L): //Initialisierungssequenzliste ... 0 zurückgeben; } // Dynamische Zuordnungs-Implementierungssequenztabelle, die Größe kann geändert werden #include<stiod.h> #define InitSize 10 //Standardmäßige maximale Länge typedef struct{ int *data; //Zeiger, der das dynamisch zugewiesene Array anzeigt int MaxSize; //Maximale Kapazität der Sequenztabelle int length; //Aktuelle Länge der Sequenztabelle }SeqList; //Definition der Sequenzliste int main(){ SeqList L; //Eine Sequenzliste deklarieren InitList(L): //Mehrere Elemente zufällig in die Netzwerksequenztabelle einfügen Erhöhen Sie die Größe (L, 5); 0 zurückgeben; } void InitList(SeqList &L){ //Verwenden Sie die malloc-Funktion, um einen kontinuierlichen Speicherplatz zu beantragen L.data(int *)malloc(InitSize*sizeof(int)); L.length=0; L.MaxSize=InitSize; } //Erhöhen Sie die Länge des dynamischen Arrays void raiseSize(SeqList &L,int len){ int *p=L.data; L.data(int *)malloc((L.MaxSize len)*sizeof(int)): for(int i=0;i<L.length;i ){ L.data[i]=p[i]; //Daten in neuen Bereich kopieren } L.MaxSize=L.MaxSize len; //Die maximale Länge der Sequenztabelle erhöht sich um len free(p); //Den ursprünglichen Speicherplatz freigeben }

L.data=(ElemType *)malloc(sizeof ElemType *InitSize) Die malloc-Funktion gibt einen Zeiger zurück, der in einen Zeiger auf den von Ihnen definierten Datenelementtyp umgewandelt werden muss.

ListInsert(&L,I,e) fügt das angegebene Element e an der i-ten Position ein

// Sequentielles Einfügen von Tabellenelementen #define MaxSize 10 typedef struct{ ElemType-Daten[MaxSize]; int Länge; }SqList; void ListInsert(SqList &L,int I,int e){ for(int j=L.length;j>I;j--){ //Das i-te Element und die nachfolgenden Elemente nach hinten verschieben L.data[j]=L.data[j-1]; } L.data[i-1]=e; //Setze e an der i-ten Position L.length; //Länge 1 } int main(){ SqList L; InitList(L): // Wird hier weggelassen, Sie können eine Reihe von Elementen einfügen ListInsert(L,3,3); 0 zurückgeben; } //Um zu vermeiden, dass Elemente ohne Rückmeldung eingefügt werden, beispielsweise wenn der Speicher voll ist, muss die Funktion Einfügen so geändert werden, dass sie einen Rückgabewert hat. bool ListInsert(SqList &L,int I,int e){ if(i<1 || i>L.length 1) falsch zurückgeben; if(L.length>=MaxSize) falsch zurückgeben; for(int j=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L.Länge; falsch zurückgeben; }

ListDelete(SqList &L,int i,int &e) löscht das Element an Position i in Tabelle L und gibt den Wert des Elements zurück

//Sequenztabelle löschen bool ListDelete(SqList &L,int i,int &e){ if(i<1 || i>L.length 1) //Bestimmen Sie, ob der Bereich von i gültig ist falsch zurückgeben; e=L.data[i-1]; for(int j=1;j<L.length;j) L.data[j-1]=L.data[j]; L.Länge--; return true; } int main(){ SqList L; InitList(L); int e=-1; if(ListDelete(L,3,e)) printf("Das dritte Element löschen, der Wert des gelöschten Elements ist =%d/n",e); anders pprintf("Die Bitreihenfolge i ist illegal, das Löschen ist fehlgeschlagen "); 0 zurückgeben; }

GetElem(L,i) ruft den Wert des Elements an der i-ten Position in Tabelle L ab

//Suche nach Bit //Statische Zuordnung #MaxSize definieren typedef struct{ ElemType data[MaxSize]; //Statisches „Array“ zum Speichern von Datenelementen verwenden int length; //Aktuelle Länge der Sequenztabelle }SqList; //Typdefinition der Sequenzliste (statische Zuordnungsmethode) ElemType GetElem(SqList L,int i){ return L.data[i-1]; //Rufen Sie die Funktion GetElem() auf, um den Wert des i-ten Elements zurückzugeben } //Dynamische Zuordnung #defineInitSize typedef struct{ ElemType *data; int MaxSize; int Länge; }SeqList; ElemType GetElem(SeqList L,int i){ return L.data[i-1]; }

LocateElem(L,e) findet das Element mit dem angegebenen Schlüsselwortwert in Tabelle L

//Nach Wert suchen #defineInitSize 10 typedef struct{ ElemType *data; int MaxSize; int Länge; }SeqList; //Suchen Sie das Element, dessen erster Elementwert gleich e ist, in der Sequenzliste L und geben Sie seine Bitreihenfolge zurück int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.length,i) if(int i=0;o<L.length;i) return i 1; //Der Wert des mit i markierten Elements im Array ist gleich e und seine Bitreihenfolge wird mit i 1 zurückgegeben return 0; //Schleife verlassen, was darauf hinweist, dass die Suche fehlgeschlagen ist }

Zeitkomplexität: bestes O(1), schlechtestes O(n), durchschnittliches O(n)

Zusätzlich zum Speichern von Datenelementen speichert jeder Knoten auch einen Zeiger auf den nächsten Knoten.

struct LNode{ ElemType data; //Definieren Sie den Knotentyp einer einzelnen verknüpften Liste struct LNode *next;//Jeder Knoten speichert ein Datenelement } struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode)); //Jedes Mal, wenn ein neuer Knoten hinzugefügt wird, beantragen Sie einen Knotenplatz im Speicher und verwenden Sie den Zeiger p, um auf diesen Knoten zu zeigen Sie können auch typedef struct LNode LNode; anstelle von LNode *p=(LNode *)maloc(sizeof(LNode)); verwenden. In diesem Fall benötigen Sie struct LNode nicht, um Knoten hinzuzufügen.

//Lehrbuch, definiere eine einfach verknüpfte Liste typedef struct LNode{} //Definieren Sie den Knotentyp einer einzelnen verknüpften Liste ElemType-Daten; //Datenfeld struct LNode *next; //Zeigerfeld LNode,*LinkList; //LNode wird umbenannt, *LinkList ist der Zeiger auf diesen Knoten Verwenden Sie LNode *, um hervorzuheben, dass es sich um einen Knoten handelt Verwenden Sie LinkList, um hervorzuheben, dass es sich um eine einfach verknüpfte Liste handelt

Führender Knoten

Kein führender Knoten

einfügen

löschen

Bitweise Suche

Nach Wert suchen

Finden Sie die Länge der Tabelle

Schritt 1: Initialisieren Sie eine einfach verknüpfte Liste Schritt 2: Entfernen Sie jeweils ein Datenelement und fügen Sie es am Kopf/Fuß der Tabelle ein

Methode zum Einführen des Schwanzes

Methode zum Einsetzen des Kopfes

Einfach verknüpfte Liste: Eine einfach verknüpfte Liste kann nicht umgekehrt abgerufen werden, was manchmal unpraktisch ist. Doppelt verknüpfte Liste: kann vor- und zurückgehen, geringere Speicherdichte

//Initialisierung der doppelt verknüpften Liste (Lead-Knoten) bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); if(L==NULL) Rücklaufflamme; L->prior=NULL; L->next=NULL; return true; } void testDLinkList(){ //Doppelt verknüpfte Liste initialisieren DLinklist L; InitDLinkList(L); //...Folgender Code } typedef struct DNode{ ElemType-Daten; struct DNode *prior,*next; }DNode,*DLinklist; //Bestimmen Sie, ob die doppelt verknüpfte Liste leer ist (Hauptknoten) bool Empty(DLinklist L){ if(L->next==NULL) return true; anders falsch zurückgeben; }

//Einfügung in eine doppelt verknüpfte Liste bool InsertNextDNode(DNode *p,DNode *s){ s->next=p->next; //Knoten *s nach Knoten *p einfügen p->next->prior=s; s->prior=p; p->next=s; }

//Doppelt verknüpfte Liste löschen bool DeleteNextDNode(DNode *p){ if(p==NULL) return flase; DNode *q=p->next; //Nachfolgeknoten q von p finden if(q==NULL) return false; //p hat keinen Nachfolgeknoten p->next=q->next; if(q->next!=NULL) //Der q-Knoten ist nicht der letzte Knoten q->next->prior=p; free(q); //Knotenplatz freigeben return true; } void DestoryList(DLinklist &L){ //Schleife, um jeden Datenknoten freizugeben while(L->next!=NULL) DeleteNextDNode(L); free(L); //Den Kopfknoten freigeben L=NULL; //Kopfzeiger zeigt auf NULL }

//Durchlauf einer doppelt verknüpften Liste while(p!=NULL){ //Rückwärtsdurchlauf // Führen Sie die entsprechende Verarbeitung für Knoten p durch p=p->next; } while(p!=NULL){ //Vorwärtsdurchquerung p=p->prioe; } while(p->prioe!=NULL){ // Vorwärtsdurchquerung, Kopfknoten überspringen p=p->prior; }

Einfach verknüpfte Liste: Ausgehend von einem Knoten können nur nachfolgende Knoten gefunden werden, die vorherigen Knoten sind jedoch unbekannt. Zirkuläre einfach verknüpfte Liste: Ausgehend von einem Knoten können Sie jeden anderen Knoten finden.

//Definieren Sie eine kreisförmige einfach verknüpfte Liste typedef struct LNode{ //Definieren Sie den Knotentyp einer einzelnen verknüpften Liste ElemType data; //Jeder Knoten speichert ein Datenelement struct LNode *next; //data zeigt auf den nächsten Knoten }LNode,*LinkList; // Initialisieren Sie eine zirkuläre einfach verknüpfte Liste bool InitList(LinkList &L){ L=(LNode *)malloc(sizeof(LNode)); //Einen Kopfknoten zuweisen if(L==NULL) //Nicht genügend Speicher, Zuordnung fehlgeschlagen falsch zurückgeben; L->next = L; // Der nächste Kopfknoten zeigt auf den Kopfknoten return true; } //Bestimmen Sie, ob die zirkuläre einfach verknüpfte Liste leer ist bool Empty(LinkList L){ if(L->next==L) return true; anders Rücklaufflamme; } //Bestimmen Sie, ob Knoten p der Endknoten einer kreisförmigen einfach verknüpften Liste ist bool isTail(LinkList L,LNode *p){ if(p->next==L) return true; anders falsch zurückgeben; }

// Leere kreisförmige doppelt verknüpfte Liste initialisieren bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); //Einen Kopfknoten zuweisen if(L==NULL) //Nicht genügend Speicher, Zuordnung fehlgeschlagen falsch zurückgeben; L->prior=L; // Die Priorität des Kopfknotens zeigt auf den Kopfknoten L->next=L; //next des Kopfknotens zeigt auf den Kopfknoten return true; } void testDLinkList(){ //Zirkuläre doppelt verknüpfte Liste initialisieren DLinklist L; InitDLinkList(L); //...Folgender Code } //Bestimmen Sie, ob die kreisförmige doppelt verknüpfte Liste leer ist bool Empty(DLinklist){ if(L->next==L) return true; anders falsch zurückgeben; } //Bestimmen Sie, ob Knoten p der Endknoten der kreisförmigen doppelt verknüpften Liste ist bool isTail(DLinklist L,DNode *p){ if(p->next==L) return true; anders falsch zurückgeben; } typedef struct DNode{ ElemType-Daten; struct DNode *prior,*next; }DNode,*DLinklist;

Einfach verknüpfte Liste: Jeder Knoten wird zufällig im Speicher zugewiesen. Statische verknüpfte Liste: Weisen Sie einen ganzen Abschnitt kontinuierlichen Speicherplatzes zu und platzieren Sie jeden Knoten zentral.

//Statische verknüpfte Liste definieren #define MaxSize 10 typedef sreuct{} ElemType-Daten; int next; } void testSLinkList(){ struct Node a[MaxSize]; //...Folgender Code } //Sie können auch eine statische verknüpfte Liste mit dem folgenden Code erstellen #define MaxSize 10 //Maximale Länge der statisch verknüpften Liste typedef struct{ //Definition des Strukturtyps der statischen verknüpften Liste ElemType-Daten; //Speicherdatenelemente int next; //Array-Index des nächsten Elements } SLinkList[MaxSize]; void testSLinkLst(){} SLinkList a; //...Folgender Code }

Es sind alles lineare Tische und lineare Strukturen.

Vorteile von Sequenztabellen: Unterstützung von Direktzugriff und hoher Speicherdichte. Nachteile: Es ist unpraktisch, große Bereiche kontinuierlichen Raums zuzuweisen, und es ist unpraktisch, die Kapazität zu ändern. Vorteile verknüpfter Listen: Diskrete kleine Räume lassen sich leicht zuweisen und die Kapazität lässt sich leicht ändern. Nachteile: Kein wahlfreier Zugriff, geringe Speicherdichte.

Erstellung der Sequenztabelle: Es muss ein großer zusammenhängender Raum vorab reserviert werden. Wenn der zugewiesene Speicherplatz zu klein ist, ist eine spätere Erweiterung der Kapazität unpraktisch. Wenn der zugewiesene Speicherplatz zu groß ist, werden Speicherressourcen verschwendet. Statische Zuweisung: statisches Array, unveränderliche Kapazität Dynamische Zuordnung: Dynamisches Array (malloc, kostenlos), die Kapazität kann geändert werden, es ist jedoch das Verschieben einer großen Anzahl von Elementen erforderlich, was zeitaufwändig ist. Zerstörung: Länge = 0 ändern, statisch zugewiesener Speicherplatz wird automatisch zurückgefordert, dynamisch zugewiesene Malloc-Anwendungen müssen manuell freigegeben werden Das Einfügen/Löschen von Elementen erfordert das Vor- und Zurückschieben nachfolgender Elemente. Die Zeitkomplexität beträgt O(n) und der Zeitaufwand entsteht hauptsächlich durch das Verschieben von Elementen. Wenn das bewegliche Element groß ist, ist der Zeitaufwand für die Bewegung hoch. Suche: Bitweise Suche: O(1). Suche nach Wert: O(n). Wenn die Elemente in der Tabelle geordnet sind, können sie in O(log2n) Zeit gefunden werden.

Erstellung verknüpfter Listen: Sie müssen nur einen Kopfknoten zuweisen (Sie können den Kopfknoten auch weglassen und nur einen Kopfzeiger deklarieren), der später problemlos erweitert werden kann. Zerstören: Löschen Sie nacheinander jeden Knoten (kostenlos) Das Einfügen/Löschen von Elementen erfordert lediglich eine Änderung des Zeigers. Die zeitliche Komplexität beträgt O(n) und der Zeitaufwand entsteht hauptsächlich durch das Finden des Zielelements. Der Zeitaufwand für die Suche nach Elementen ist geringer. Suche: Bitweise Suche: O(n). Nach Wert suchen: O(n).

Verwenden Sie eine sequentielle Liste oder eine verknüpfte Liste: Die Länge der Liste ist schwer abzuschätzen und Elemente müssen häufig hinzugefügt, subtrahiert/gelöscht werden. Verwenden Sie daher eine verknüpfte Liste. Die Tabellenlänge kann geschätzt werden und es gibt viele Abfrage-(Such-)Vorgänge. Verwenden Sie daher eine sequentielle Tabelle. Frage: Bitte beschreiben Sie die Sequenzliste und die verknüpfte Liste ... Was ist besser, die Sequenzliste oder die verknüpfte Liste zu verwenden? Die logischen Strukturen von Sequenzlisten und verknüpften Listen sind lineare Ergebnisse und beide gehören zu linearen Listen. Die Speicherstrukturen der beiden sind jedoch unterschiedlich. Die Sequenztabelle verwendet sequentielle Speicherung ... (Merkmale, Vor- und Nachteile); Aufgrund der Verwendung unterschiedlicher Speichermethoden ist auch die Implementierungseffizienz grundlegender Vorgänge unterschiedlich. Beim Initialisieren...beim Einfügen eines Datenelements...beim Löschen eines Datenelements...beim Suchen eines Datenelements...

Implementiert mit „statischem Array“

Sobald die Größe festgelegt ist, kann sie nicht mehr geändert werden

Implementiert mit „dynamischem Array“

L.data=(ElemType *)malloc (sizeof(El;emType)* Größe)

Wenn die Sequenztabelle voll ist, kann malloc verwendet werden, um den maximalen Durchsatz der Sequenztabelle dynamisch zu erweitern.

Es ist notwendig, die Datenelemente in einen neuen Speicherbereich zu kopieren und den ursprünglichen Bereich mit der Free-Funktion freizugeben.

Kann das i-te Element in O(1)-Zeit finden

Definition (wie man es im Code implementiert)

Implementierung grundlegender Operationen

Einzelliste

Doppelt verknüpfte Liste

zirkuläre verknüpfte Liste

statische verknüpfte Liste

Fügen Sie das Element e an der i-ten Position von L ein

Bestes O(1), schlechtestes O(n), durchschnittliches O(n)

Löschen Sie das i-te Element von L und geben Sie es mit e zurück

Bestes O(1), schlechtestes O(n), durchschnittliches O(n)

Ermitteln Sie den Wert des Elements an Position i in Tabelle L

Verwenden Sie den Array-Index, um das i-te Element L.data[i-1] abzurufen

Die beste/schlechteste/durchschnittliche Zeitkomplexität ist O(1)

Suchen Sie in der Sequenzliste L das Element, dessen erster Elementwert gleich e ist, und geben Sie seine Bitreihenfolge zurück

Suche beginnend beim ersten Element und rückwärts

Die beste Zeitkomplexität ist O(1)

Schlechteste Zeitkomplexität O(n)

Durchschnittliche Zeitkomplexität O(n)

Beurteilung der leeren Tabelle: L==NULL

Einfach zu schreibender Code

Beurteilung der leeren Tabelle: L->next==NULL;

Das Schreiben von Code ist unbequem

Führender Knoten

Kein führender Knoten