Eine lineare Tabelle ist eine endliche Folge von n Datenelementen desselben Datentyps

Die Anzahl der Elemente in der Tabelle ist begrenzt

Die Elemente in der Tabelle haben eine logische Reihenfolge. Die Elemente in der Tabelle haben ihre Reihenfolge.

Die Elemente in der Tabelle sind alle Datenelemente und jedes Element ist ein einzelnes Element

Die Datentypen der Elemente in der Tabelle sind alle gleich, was bedeutet, dass jedes Element den gleichen Speicherplatz belegt

Die Elemente in der Tabelle sind abstrakt, das heißt, es wird nur die logische Beziehung zwischen den Elementen diskutiert, ohne zu berücksichtigen, was die Elemente tatsächlich darstellen.

InitList(&): Initialisierungsliste. Konstruieren Sie eine leere lineare Tabelle

Länge (L): Ermitteln Sie die Länge der Tabelle. Gibt die Länge der linearen Tabelle L zurück, also die Anzahl der Datenelemente in L

LocateElem(L,e): Operation nach Wert suchen. Suchen Sie in Tabelle L nach Elementen mit dem angegebenen Schlüsselwert

GetElem(L,i): Bitweise Suchoperation. Ermitteln Sie den Wert des Elements an Position i in der Tabelle

ListInsert (&L,i,e): Einfügevorgang. Fügen Sie das angegebene Element e an der i-ten Position in Tabelle L ein

ListDelete(&L,i,&e): Löschvorgang. Löschen Sie das Element an der i-ten Position in der Tabelle und geben Sie mit e den Wert des gelöschten Elements zurück

PrintList(L): Ausgabevorgang. Geben Sie alle Elementwerte der linearen Tabelle in sequentieller Reihenfolge aus

Leer (L): Leerer Vorgang. Wenn der Job eine leere Tabelle ist, geben Sie „true“ zurück, andernfalls geben Sie „false“ zurück

DestroyList(&L): Zerstörungsvorgang. Zerstören Sie die lineare Tabelle und geben Sie den von der linearen Tabelle L belegten Speicherplatz frei

Die sequentielle Speicherung einer linearen Tabelle verwendet eine Reihe von Speichereinheiten mit aufeinanderfolgenden Adressen, um die Datenelemente in der linearen Tabelle sequentiell zu speichern, sodass zwei logisch benachbarte Elemente auch physisch benachbart sind.

Merkmale

（1） einfügen

（2） löschen

（3） Nach Wert suchen (sequentielle Suche)

Speichern Sie Datenelemente in einer linearen Tabelle über einen beliebigen Satz von Speichereinheiten

Für jeden verknüpften Listenknoten muss zusätzlich zur Speicherung der Elementinformationen auch ein Zeiger auf seinen Nachfolger gespeichert werden.

Fügen Sie vor dem ersten Knoten der einfach verknüpften Liste einen Knoten hinzu, der als Kopfknoten bezeichnet wird. Sein Datenfeld enthält keine Informationen und der Zeiger zeigt auf den ersten Elementknoten der linearen Liste.

Erstellen Sie eine einfach verknüpfte Liste mit der Kopfeinfügungsmethode

Erstellen Sie eine einfach verknüpfte Liste mit der Tail-Insertion-Methode

Finden Sie den Knotenwert anhand der Seriennummer

Suchen Sie Tabellenknoten nach Wert

Knotenoperation einfügen

Knoten löschen

Operation zum Ermitteln der Tabellenlänge

Die zeitliche Komplexität des Zugriffs auf den Vorgängerknoten einer einzelnen verknüpften Liste beträgt O(n). Aus diesem Grund wird eine doppelt verknüpfte Liste eingeführt. Jeder Knoten verfügt über zwei Zeiger, den Vorgänger und den Nachfolger.

Einfügevorgang

Vorgang löschen

Zirkuläre einfach verknüpfte Liste

Zirkuläre doppelt verkettete Liste

Verwenden Sie Arrays, um die verknüpfte Speicherstruktur linearer Listen zu beschreiben

Der Zeiger ist die relative Adresse des Knotens (Array-Index), auch Cursor genannt

Verwenden Sie next==-1 als Endmarke

Zugriffsmethoden (Lesen und Schreiben).

Logische Struktur und physische Struktur

Suchen, Einfügen und Löschen von Elementoperationen

Raumaufteilung