Dynamische Speicherstrukturen und Zeiger: Eine Einführung

Ziele der dynamischen Speicherverwaltung

Statische Strukturen können während der Programmausführung nicht verändert werden. Das Ändern der Anordnung von Elementen innerhalb einer statischen Struktur ist aufwendig (teuer). Beispiel: Die Positionen der Elemente in einem Array (die Größe des Arrays kann nicht nachträglich geändert werden).

Zur Design-Zeit wissen wir oft nicht genau, wie viel Speicher benötigt wird und wie dieser zu organisieren ist. Die Lösung besteht darin, diesen Speicher zur Laufzeit zu definieren und zu organisieren. Dies geschieht durch die Verwendung von dynamischen Speicherstrukturen.

• Dynamische Speicherverwaltung: Wird durch Zeiger (Pointer) realisiert.
• Dynamischer Speicher: Speicherbereich, in dem zur Laufzeit Platz reserviert werden kann.
• Dynamische Speicherstrukturen: Eine Sammlung von Elementen (sogenannte Knoten), die miteinander verbunden sind.
• Dynamische Variablen: Speicherpositionen, die zur Laufzeit reserviert werden.
• Definition: Eine Variable, die den Speicherort einer anderen Variablen angibt.
• Semantik: Deklariert einen Datentyp (ID), der ein Zeiger auf einen anderen Datentyp (Typ) ist.

Zeiger und ihre Operationen

1 Zeiger-Operationen

New: Ein Verfahren, das Platz im dynamischen Speicher reserviert.

• Syntax: new(Zeigervariable);
• Semantik: Reserviert Speicherplatz; die als Parameter übergebene Zeigervariable zeigt anschließend auf diesen Bereich.

Dispose: Ein Verfahren, mit dem dynamischer Speicher wieder freigegeben wird.

• Syntax: dispose(Zeigervariable);
• Semantik: Gibt den Speicherplatz frei, auf den die als Parameter übergebene Zeigervariable verwies.

Datenzugriff: Der Operator ^ (Zirkumflex) wird als Dereferenzierungs-Operator verwendet. Er greift auf den Wert der Daten zu, auf die der Zeiger referenziert.

Es muss nicht immer explizit Speicher zugewiesen werden, um einen Zeiger zu verwenden. Mit dem Operator @ (Referenz-Operator) kann die Speicheradresse einer bestehenden Variablen abgerufen werden.

NIL (Null-Zeiger): Ein konstanter Zeigertyp. Ein NIL-Zeiger gibt an, dass er auf keinen Speicherbereich verweist. Achten Sie darauf, Zeigerpositionen nicht zu verlieren, da sonst Speicherlecks entstehen können, wenn der Speicher vorher nicht freigegeben wurde.

Es sind nur Zuweisungen (:=) und Vergleiche mit relationalen Operatoren (= und <>) erlaubt. Die Operanden müssen Zeiger auf Variablen desselben Typs oder NIL sein.

Prozeduren und Funktionen

• Parameter können als Wert oder als Referenz übergeben werden.
• Zeiger können als Ergebnis einer Funktion zurückgegeben werden.
• Obwohl f eine Funktion ist, die einen Zeiger auf einen Datensatz zurückgibt, ist folgender direkter Zugriff nicht erlaubt: f(Parameter)^.name; (falsch). Stattdessen: varZeiger := f(Parameter); (richtig).

2 Zusammenfassung Zeiger

Einen Zeigertyp zu deklarieren, reicht nicht immer aus, um ihn zu benutzen. Um Informationen dynamisch zu erstellen, rufen Sie das New-Verfahren auf. Nach dem Aufruf von New ist der Wert, auf den der Zeiger weist, noch undefiniert. Es ist notwendig, ihm einen Wert zuzuweisen.

Es ist sehr wichtig, Speicherplatz mit Dispose freizugeben, wenn er nicht mehr benötigt wird, um freien Speicher zu behalten.

Verkettete Listen

Eine Liste besteht aus einer Sammlung von Elementen, den sogenannten Knoten. Jeder Knoten speichert zwei Werte:

• Das Listenelement: Die eigentlichen Daten (Informationsbereich).
• Einen Zeiger: Dieser gibt die Position des Knotens mit dem nächsten Element in der Liste an.

Die Verbindung wird durch den jedem Knoten zugeordneten Zeiger hergestellt. Wir müssen den Knoten kennzeichnen, der das erste Element der Liste enthält. Die verkettete Liste ist eine rekursive Struktur.

1 Einfache verkettete Listen

Dies ist die einfachste dynamische Struktur: Sie besitzt nur eine Verbindung. Ein Knoten wird durch einen Datensatz (Record) mit zwei Bereichen dargestellt: einer für die Daten und einer für den Zeiger auf den nächsten Knoten.

TYPE
  TDate = String[25];
  tlist = ^tNodoLista;
  tNodoLista = RECORD
    Name: TDate;
    sig: tlist; (Rekursive Struktur)
  END;
VAR
  Paux, aux, first, previous, list: tlist;

Erstellen einer leeren Liste: list := NIL;

Prüfen, ob eine Liste leer ist:
IF (list = NIL) THEN leere_Liste() ELSE (Elemente vorhanden);

Ende einer Liste:
IF (lista^.sig = NIL) THEN (letzter Punkt in der Liste);

2 Doppelt verkettete Listen

Diese unterhalten Verbindungen in beide Richtungen und benötigen zwei Zeiger:

• Ant: Zeigt auf den vorherigen Knoten.
• Sig: Zeigt auf den nächsten Knoten.

Nachteil: Operationen wie Einfügen und Löschen sind komplexer, da mehr Hilfszeiger benötigt werden.
Vorteil: Maßnahmen wie das Sortieren oder das Umkehren einer Liste sind einfacher durchzuführen.

Sonstige dynamische Strukturen

• Stacks (Stapel/Batterien): Eine spezialisierte Liste, bei der Elemente nur an einem Ende eingefügt und entfernt werden (LIFO-Prinzip: Last-In-First-Out).
• Queues (Warteschlangen): Eine Liste, bei der Elemente an einem Ende eingefügt und am anderen Ende entfernt werden (FIFO-Prinzip: First-In-First-Out).

Zusammenfassung dynamischer Strukturen

• Das Konzept einer Liste kann auch statisch (durch ein teilweise gefülltes Array) umgesetzt werden.
• Nachteile gegenüber Arrays: Die Zugriffskomplexität ist bei Listen O(n) im Vergleich zu O(1) bei Arrays.
• Seien Sie besonders vorsichtig, den Zeiger auf den Anfang der Liste nicht zu verlieren, da sonst die gesamte Liste im Speicher verloren geht.
• Beim Löschen von Elementen darf nicht vergessen werden, den Speicher des Knotens freizugeben (nicht nur den Zeiger umgehen).