Dynamische Datenstrukturen und lineare Listen erklärt

Dynamische und statische Datenstrukturen

Dynamische Strukturen: Dynamische Datenstrukturen sind Strukturen, die während der Programmlaufzeit wachsen können. Eine dynamische Datenstruktur ist eine Sammlung von Knoten (gelegentlich auch als Produkte bezeichnet), normalerweise Datensätze. Im Gegensatz zu einem Array, das festen Platz für eine Reihe von Elementen reserviert, werden dynamische Strukturen für die Speicherung von realen Daten verwendet, die sich ständig ändern.

Ein typisches Beispiel für eine statische Datenstruktur ist die Liste der Fahrgäste einer Fluggesellschaft. Wenn diese Liste in alphabetischer Reihenfolge in einem Array gespeichert wird, wäre es notwendig, Platz zu schaffen, um einen neuen Passagier in alphabetischer Reihenfolge einzufügen. Dazu bedarf es einer Schleife, um die Datensätze aller nachfolgenden Fluggäste in das jeweils nächste Array-Element zu kopieren.

Unterschied zwischen statisch und dynamisch

Eine statische Struktur besteht aus Daten, deren Struktur zum Zeitpunkt der Erstellung des Programms festgelegt wird und vom Programm nicht geändert werden kann. Die Werte der Elemente können variieren, aber nicht die Struktur selbst, da sie fixiert ist. Eine dynamische Datenstruktur hingegen kann ihre Struktur durch das Programm verändern. Sie können ihre Größe während des laufenden Programms erweitern oder begrenzen.

Definition der linearen Liste

Linear-Liste: Dies ist ein Satz von Elementen eines bestimmten Typs, deren Anzahl variieren kann. Jedes Element hat einen eindeutigen Vorgänger und Nachfolger (bzw. ein nächstes Element), mit Ausnahme des ersten und des letzten Elements der Liste. Dies ist eine sehr weit gefasste Definition, die auch Dateien und Vektoren einschließt.

Die linearen Listenelemente werden in der Regel benachbart gespeichert, ein Element nach dem anderen, in aufeinanderfolgenden Speicherorten. Eine lineare Liste befindet sich im Hauptspeicher eines Computers in aufeinanderfolgenden Positionen. Wenn sie auf einem Magnetband gespeichert wird, werden die Elemente ebenfalls aufeinanderfolgend auf dem Band präsentiert.

Operationen auf linearen Listen

Die folgenden Operationen können mit benachbarten linearen Listen durchgeführt werden:

• Einfügen, Löschen oder Suchen eines Elements.
• Bestimmen der Größe (Anzahl der Elemente) in der Liste.
• Blättern in der Liste, um ein bestimmtes Produkt zu finden.
• Sortieren der Elemente in der Liste (auf- oder absteigend).
• Zusammenfügen von zwei oder mehr Listen zu einer einzigen Liste (Sola).
• Teilen einer Liste in mehrere Teillisten oder Kopieren der Liste sowie Löschen der Liste.

Eine lineare Liste wird im zusammenhängenden Speicher des Computers in aufeinanderfolgenden, benachbarten Positionen gespeichert und als eindimensionales Array verarbeitet.

Beispiel 12.1: Zugriff auf ein Element

Sie wollen das j-te Element einer Liste P lesen. Der Algorithmus erfordert die Kenntnis der Anzahl der Elemente in der Liste (die Länge L). Die durchzuführenden Schritte sind:

1. Kenntnis der Länge der Liste L.
2. Wenn L = 0, zeige die Fehlermeldung 'Fehler: leere Liste' an.
3. Ansonsten prüfen, ob das j-te Element im zulässigen Bereich der Elemente (1 ≤ j ≤ L) liegt. In diesem Fall weisen Sie den Wert des Elements P(j) einer Variablen B zu.
4. Falls das j-te Element nicht im Bereich liegt, wird eine Fehlermeldung angezeigt: 'Angefordertes Element nicht in der Liste enthalten'.
5. Ende.

Zugehöriger Pseudocode für den Zugriff

Access-Verfahren (E-Liste: p; elementolista S: B, E integer: L, J)
Beginn
Wenn L = 0, dann
  Schreibe ('Liste leer')
Ansonsten
  Wenn (j >= 1) und (J <= L), dann
    B = P(J)
  Ansonsten
    Schreibe ('Fehler: kein Element vorhanden')
  Ende_Wenn
Ende_Wenn
Ende

Löschen eines Elements

Löschen eines Elements j in der Liste S.
Variablen:
L: Länge der Liste
J: Position des zu löschenden Elements
I: Index des Arrays P
P: Liste

Die Arbeitsschritte sind:
1. Prüfen Sie, ob die Liste leer ist.
2. Prüfen Sie, ob der Wert von J im Bereich des Index I der Anlage (1 ≤ j ≤ L) liegt.
3. Wenn dies zutrifft, verschieben Sie die Elemente von j+1 bis L auf die Positionen j bis L-1, um das alte Element an Position j zu überschreiben.
4. Dekrementieren Sie den Wert der Variablen L um eins, da die Liste nun L - 1 Elemente enthält.

Algorithmus zum Löschen

Beginn
Wenn L = 0, dann
  Schreibe ('Leere Liste')
Ansonsten
  Lese (J)
  Wenn (J >= 1) und (J <= L), dann
    Für I = J bis L-1 mache
      P[I] = P[I + 1]
    Ende_Für
    L = L - 1
  Ansonsten
    Schreibe ('Element nicht vorhanden')
  Ende_Wenn
Ende_Wenn
Ende

Zusammenfassung der zusammenhängenden Liste

Eine zusammenhängende Liste ist eine Struktur, in der die Elemente im Speicher oder auf einem Speichermedium angrenzend (adressierbar) abgelegt sind. Sie hat links und rechts begrenzte bzw. untere und obere Grenzen, die nicht überschritten werden können, wenn ein Element hinzugefügt wird.