Verknüpfte Speicherstruktur einer linearen Tabelle

Haben wir gute Lösungen für die Mängel der sequentiellen Struktur?

Die verknüpfte Speicherstruktur der linearen Liste, die wir heute vorstellen werden, kann die Mängel der sequentiellen Struktur sehr gut beheben.

Kettenspeicherstruktur, auch verknüpfte Speicherstruktur genannt. Im Computer wird ein Satz beliebiger Speichereinheiten verwendet, um die Datenelemente der linearen Tabelle zu speichern (dieser Satz Speichereinheiten kann kontinuierlich oder diskontinuierlich sein).

Grundlegende Einführung

Es ist nicht erforderlich, dass logisch benachbarte Elemente physisch benachbart sind. Daher weist es nicht die Schwächen der sequentiellen Speicherstruktur auf, verliert aber auch die Zufälligkeit der sequentiellen Liste des Zugriffs.

Merkmale

1. Die Speicherdichte ist kleiner als die sequentielle Speicherstruktur (jeder Knoten in der Kettenspeicherstruktur besteht aus einem Datenfeld und einem Zeiger Die Domäne besteht aus zwei Teilen, was den Speicherplatz im Vergleich zur sequentiellen Speicherstruktur erhöht.

2. Logisch benachbarte Knoten müssen nicht physisch benachbart sein.

3. Flexibles Einfügen und Löschen (kein Verschieben des Knotens erforderlich, einfach den Zeiger im Knoten ändern).

4. Verketteter Speicher ist bei der Suche nach Knoten langsamer als sequenzieller Speicher.

5. Jeder Knoten besteht aus einem Datenfeld und einem Zeigerfeld.

6. Da Cluster zufällig zugewiesen werden, verringert sich auch die Wahrscheinlichkeit eines Überschreibens nach dem Löschen der Daten und erhöht die Möglichkeit einer Wiederherstellung.

Empfohlener Kurs: C Language Tutorial.

Das letzte Element der linearen Liste hat keinen direkten Nachfolger, daher setzen wir im verknüpften Speicher das Zeigerfeld des letzten Knotens auf Null.

Machen wir das. Schauen wir uns das an Spezifische Code-Implementierung einer einfach verknüpften Liste

typedef struct LNode{     
    ElemType data;          //数据域    
    struct LNode *next;     //指针域，用来指向本节点的直接后继
 }LNode,*LinkList;           //定义节点，以及头指针

Viele Schüler können die Beziehung und den Unterschied zwischen dem Kopfzeiger, dem Kopfknoten und dem ersten Knoten nicht unterscheiden. Lassen Sie uns unten eine einfache Unterscheidung treffen .

Kopfzeiger: Es ist ein Zeiger auf die verknüpfte Liste. Wenn die verknüpfte Liste einen Kopfknoten hat, zeigt sie auf den Kopfknoten: Ein Hilfsknoten davor der erste Knoten. Der nächste Knoten zeigt auf den ersten Knoten

Der erste Knoten: Es ist ein Knoten, die Datenvariable speichert die ersten Daten und die nächste Zeigervariable zeigt auf den zweiten Knoten

Hier ist zu beachten, dass der Kopfzeiger ein notwendiges Element einer verknüpften Liste ist, der Kopfknoten jedoch nicht. Welche Bedeutung hat also die Existenz des Kopfknotens?

Mein persönliches Verständnis besteht darin, die Einfügungs- und Löschvorgänge des ersten Knotens mit den Vorgängen nachfolgender Knoten in Einklang zu bringen. Andernfalls müssen wir den Kopfzeiger ändern, wenn wir den ersten Knoten ändern.

Wenn kein Kopfknoten vorhanden ist, zeigt der Kopfzeiger direkt auf den ersten Knoten.

Das obige ist der detaillierte Inhalt vonVerknüpfte Speicherstruktur einer linearen Tabelle. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!