Eine verknüpfte Liste ist eine lineare Liste, die in welcher Speicherstruktur gespeichert ist

Eine verknüpfte Liste ist eine lineare Liste, die in einer „verketteten“ Speicherstruktur gespeichert ist. Die von den Datenelementen der verknüpften Liste belegten Speichereinheitsadressen können kontinuierlich oder diskontinuierlich sein. Der entsprechende Speicherplatz kann je nach Bedarf vorübergehend und dynamisch zugewiesen werden. Die logische Beziehung zwischen den Datenelementen kann durch „Kette“ ausgedrückt werden.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

Um die Mängel der sequentiellen Tabellenspeicherstruktur zu überwinden, den Speicherplatz voll auszunutzen und die Betriebseffizienz zu verbessern, können lineare Tabellen eine andere Speicherstruktur verwenden – Verkettete Speicherstruktur. Die verknüpfte Speicherstruktur der linearen Liste wird als „Linkliste“ bezeichnet

1. Übersicht über die verknüpfte Liste

Die von den Datenelementen der verknüpften Liste belegten Speichereinheitsadressen können je nach Bedarf kontinuierlich oder diskontinuierlich sein Beantragen Sie vorübergehend und dynamisch die Zuweisung des entsprechenden Speicherplatzes, und die logische Beziehung zwischen Datenelementen kann als „Kette“ ausgedrückt werden.

Das Einfügen und Löschen verknüpfter Listen erfordert keine Verschiebung von Datenelementen, lediglich die Kette muss geändert werden.

Klassifizierung verknüpfter Listen:

1. Klassifizierung nach Speicherzuordnung für verknüpfte Listen

① Dynamische verknüpfte Liste

② Statische verknüpfte Liste

2. Klassifizierung nach Verknüpfungsmethode

① Einzelne verknüpfte Liste

② Zirkular verknüpfte Liste

③ Doppelt verknüpfte Liste

(Alles sind dynamisch verknüpfte Listen)

2. Definition einer einfach verknüpften Liste

1. Definition

Um die logische Beziehung zwischen jedem Datenelement ai und seinem direkten Nachfolger darzustellen Datenelement ai+1, für jedes Datenelement Zusätzlich zum Speichern seiner eigenen Informationen muss ai auch Informationen speichern , die seinen direkten Nachfolger angeben (Speicherort des Nachfolgers – Adresse).

Das Feld, in dem Datenelementinformationen gespeichert werden, heißt Datenfeld, und das Feld, in dem direkte Nachfolgerpositionen gespeichert werden, heißt Zeigerfeld Die im Zeigerfeld gespeicherten Informationen werden Zeiger oder Kette genannt.

Diese beiden Informationsteile bilden das Speicherbild des Datenelements ai, das Knoten genannt wird.

n Knoten sind zu einer verknüpften Liste verknüpft, die die verknüpfte Speicherstruktur der linearen Liste darstellt (a1, a2, a3, ..., an), da jeder Knoten der verknüpften Liste nur ein Zeigerfeld enthält genannt Es handelt sich um eine einzelne verknüpfte Liste.

Bei linearen Listen gibt es immer einen Kopf und einen Schwanz, und verknüpfte Listen bilden da keine Ausnahme. Der Zeiger auf den ersten Knoten der einfach verknüpften Liste in der verknüpften Liste wird als Kopfzeiger bezeichnet. Der Zugriff auf die gesamte verknüpfte Liste muss vom Kopfzeiger aus beginnen, und auf jeden nachfolgenden Knoten wird vom Nachfolger verwiesen Zeiger des vorherigen Knotens. Der Zeiger des letzten Knotens der verknüpften Liste ist „null (normalerweise dargestellt durch NULL)“ – ein Nullzeiger.

Um die Implementierung verschiedener Operationen in der verknüpften Liste zu erleichtern, wird ein Knoten desselben Typs vor den ersten Datenknoten der einfach verknüpften Liste gesetzt. Dieser Knoten wird als Kopfknoten bezeichnet.

Das Datenfeld des Hauptknotens kann spezielle Flag-Informationen wie die Länge der verknüpften Liste speichern oder keine Daten speichern.

Der erste Datenknoten und der letzte Knoten der verknüpften Liste werden auch Kopfknoten und Endknoten genannt.

2. Die Ähnlichkeiten und Unterschiede zwischen dem Kopfzeiger und dem Kopfknoten

Kopfzeiger:

• Der Kopfzeiger bezieht sich auf den Zeiger, der auf den ersten Knoten in der verknüpften Liste zeigt Der Kopfknoten zeigt auf den Kopfzeiger auf den Knoten.
• Der Kopfzeiger hat eine Identifikationsfunktion und wird häufig als Name der verknüpften Liste verwendet.
• Egal ob die verknüpfte Liste leer ist oder nicht, der Kopfzeiger ist nicht leer. Der Kopfzeiger ist ein notwendiges Element der verknüpften Liste.

Kopfknoten:

• Der Kopfknoten wird zur Vereinheitlichung und Vereinfachung von Operationen eingerichtet. Er wird vor dem Knoten des ersten Elements platziert und sein Datenfeld ist im Allgemeinen unbeabsichtigt.
• Mit dem Kopfknoten werden die Vorgänge des Einfügens eines Knotens vor dem ersten Elementknoten und des Löschens des ersten Knotens mit denen anderer Knoten vereinheitlicht.
• Der Kopfknoten ist nicht unbedingt ein notwendiges Element der verknüpften Liste.

3. Code-Demonstration

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

3. Operationen einer einfach verknüpften Liste

1) Einfügungssimulation

Angenommen, der Knoten, der das Element e speichert, ist s und fügt s hinter dem ai-Knoten ein.

Denken: Können die beiden Sätze des Einfügungscodes ausgetauscht werden?

Nein, wenn man es umschaltet, können nachfolgende Elemente wie ai+1 nicht gefunden werden, da das Zeigerfeld von s nicht auf die Adresse von ai+1 zeigt.

2) Algorithmusidee zum Einfügen der i-ten Daten in den Knoten einer einfach verknüpften Liste

Deklarieren Sie einen Knoten p, der auf den ersten Knoten der verknüpften Liste zeigt, und initialisieren Sie j=1;

• Wenn j
• Wenn p am Ende der verknüpften Liste leer ist, bedeutet dies, dass das i-te Element nicht existiert Die Suche ist erfolgreich, ein leerer Knoten s wird generiert (mithilfe der Malloc-Funktion)
• Weisen Sie das Datenelement e zu s->data zu, d. h. fügen Sie die Standardanweisung für s->data=e;
• ein: s->next=p->next; p->next=s;
• Rückkehr erfolgreich.
• 2. Löschvorgang

1) Löschsimulation

Angenommen, der Knoten, der das Element ai speichert, ist q und der Vorgang zum Löschen des Knotens q aus einer einfach verknüpften Liste soll implementiert werden.

2) Algorithmusidee zum Löschen des i-ten Datenknotens in einer einfach verknüpften Liste

Deklarieren Sie einen Knoten p, der auf den ersten Knoten der verknüpften Liste zeigt, und initialisieren Sie j=1;

• Wenn j< ;i, traverse Lassen Sie in der verknüpften Liste den Zeiger von p rückwärts bewegen und kontinuierlich auf den nächsten Knoten j++ zeigen;
• Wenn p am Ende der verknüpften Liste leer ist, bedeutet dies, dass das i-te Element dies nicht tut Wenn die Suche erfolgreich ist, wird der Knoten p-> neben q zugewiesen. Fügen Sie die Standardanweisung ein: p->next=q->next; q->data;
• Q-Knoten freigeben
• Erfolg zurückgeben.
• 4. Vergleich zwischen einfach verknüpfter Listenstruktur und sequentieller Listenstruktur
• Speichermethode:

Sequentielle Tabelle verwendet eine kontinuierliche Speichereinheit, um die Datenelemente in der linearen Liste der Reihe nach zu speichern.

Einfach verknüpfte Liste verwendet einen verknüpften Speicher Struktur unter Verwendung einer Gruppe beliebiger Speichereinheiten zum Speichern linearer Tabellenelemente Tabelle O(n)

Einfach verknüpfte Liste O(1)

• Speicherplatzleistung:

Die Sequenztabelle erfordert vorab zugewiesenen Speicherplatz, wenn sie in eine große Größe unterteilt wird In eine kleine Größe ist es anfällig für Überlauf.

Einfach verknüpfte Liste erfordert keinen vorab zugewiesenen Speicherplatz. Sie können so viel zuweisen, wie Sie benötigen, und die Anzahl der Elemente ist nicht begrenzt.

Für weitere verwandte Informationen Bitte besuchen Sie die
• FAQ
-Kolumne!

Das obige ist der detaillierte Inhalt vonEine verknüpfte Liste ist eine lineare Liste, die in welcher Speicherstruktur gespeichert ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!