Dynamische Datenstrukturen

Dynamische Datenstrukturen

Statische Datenstruktur , Datenstruktur, die während der Laufzeit eines Programmes nicht verändert werden kann.

ARRAYs und RECORDs sind statische Datenstrukturen. Die Dimensionierung eines ARRAYs kann während der Laufzeit eines Programmes nicht mehr verändert werden. Wenn die Zahl der Daten, die ein ARRAY aufnehmen soll, nicht bereits bei der Programmierung bekannt ist, muß das ARRAY so groß dimensioniert werden, daß es auch für große Anwendungen noch ausreicht. Dies hat den Nachteil, daß eventuell viel Speicherplatz verschwendet wird.

Dynamische Datenstruktur , Datenstruktur, die während der Laufzeit eines Programmes verändert werden kann. In Pascal arbeiten alle dynamischen Datenstrukturen mit Zeigern. Mit den Prozeduren new und dispose ist es möglich, zur Laufzeit eines Programmes Speicherplatz bereitzustellen und wieder freizugeben.

Die wichtigsten dynamischen Datenstrukturen sind lineare Listen (einfach oder doppelt verkettete Listen) und Bäume.

Lineare Liste, eindimensionale Anordnung von Listenelementen.

Einfach verkettete Liste, jedes Listenelement enthält einen Zeiger auf das nächste Listenelement.

Doppelt verkettete Liste, jedes Listenelement enthält Zeiger auf das nächste und das vorhergehende Listenelement.

Das letzte Element einer Liste hat keinen Nachfolger. Der entsprechende Zeiger wird daher auf den Wert NIL gesetzt.

Ringliste, lineare Liste, deren letztes Element einen Zeiger zurück auf das erste Element enthält.

Einfügen und Löschen in einer einfach verketteten linearen Liste.

TYPE element=RECORD
key: ~integer;
next: element;
END;
VAR listenanfang,hilf,position: element;
.
.
(* Einfuegen in Liste *)
new(hilf);
hilf .next:=position.next;
position.next:=hilf;
.
.
(* Loeschen aus Liste *)
hilf:=position .next;
position .next:=hilf.next;
dispose(hilf);
.
.
(* Ausdrucken der Listenelemente *)
position:=listenanfang;
WHILE position<>NIL DO BEGIN
writeln(position.key);
position:=position.next;
END;
.
.

Hier wird jeweils nach dem Element, auf das der Zeiger position deutet, in die Liste eingefügt bzw. der Nachfolger des Elementes, auf das position zeigt, gelöscht.