Verwaltung von variablen Datenmengen

In den meisten nicht-trivialen Programmen benötigen Sie Datenstrukturen und Operationen zur Verarbeitung von Objekten, deren Anzahl nicht von vornherein feststeht, sondern variabel ist. Zur Organisation dieser variablen Datenmengen gibt es verschiedene Ansätze.

Sequentielle Organisation

Sie können die Objekte z.B. lückenlos hintereinander in den Speicher schreiben -- um nun Informationen über die Anzahl der Einzelobjekte zu erhalten, müssen Sie entweder das Ende des Speicherblocks durch eine besondere Marke kennzeichnen oder die Anzahl der Objekte in einer separaten Variablen abspeichern. Die Voraussetzung ist allerdings die Verfügbarkeit von ausreichendem zusammenhängenden Speicherplatz (sogenanntem linearen Speicherplatz).

Diese Art der Verwaltung wird für sequentielle Dateien verwendet, da der Platz auf einem Massenspeicher immer als linear angesehen werden kann. Entweder ist die Länge der Datei im Inhaltsverzeichnis des Massenspeichers abgelegt oder ein besonderes Zeichen dient als Ende-Markierung. Ein Beispiel: die frühen Versionen von MS-DOS verwendeten das ASCII-Zeichen Nr. 26 -- auch ,,Control-Z`` genannt -- als Ende-Kennung für Textdateien; in den neueren Versionen ist für alle Dateien der Längeneintrag im Verzeichnis relevant.

Im Hauptspeicher des Rechners allerdings kann mit dieser Methode nur selten erfolgreich gearbeitet werden, vornehmlich bei kleineren Datenmengen -- der verfügbare lineare Speicher ist meist nicht sehr groß. Eine Anwendung sind Zeichenketten, deren Länge nur selten 256 Zeichen übersteigt: in C dient das Zeichen mit der Zeichensatz-Nummer 0 als Endekennung, das daher in C-Strings nicht vorkommen darf; die Pascal-Variante ,,Turbo-Pascal`` hingegen benutzt das erste Zeichen der Zeichenkette, um die aktuelle Länge zu speichern.

Zu der Schwierigkeit mit dem linearen Speicher kommt ein weiteres Problem: die Reihenfolge der einzelnen Objekte ist festgelegt und jede Umsortierung ist mit großem Aufwand verbunden (wenn man nicht mit zusätzlichen Index-Tabellen arbeitet, die wieder Speicherplatz kosten und die vielleicht auch einmal geändert werden müssen...). Gerade die Sortierung von Datensätzen nach verschiedenen Kriterien ist aber eine sehr oft benötigte Operation; eine andere Form der Datenstrukturierung, die diese Anforderungen besser unterstützt, ist dann notwendig.

Rekursionskonzepte

Eine rekursive Datenstrukturierung weist Eigenschaften auf, die sie der sequentiellen Anordnung überlegen macht. Rekursion bedeutet ,,Rückbezüglichkeit`` in dem Sinne, daß eine Klasse (unter anderem) durch sich selbst definiert ist, daß ein Objekt dieser Klasse also weitere, gleichartige Objekte ,,enthält``. Damit die Rekursion nicht unendlich tief ist, muß es allerdings eine abbrechende Alternative geben.

Was bedeutet ,,ein Objekt enthält ein anderes`` ? Eine seiner Komponenten ist in diesem Fall ein Verweis auf das andere Objekt, ein ,,Zeiger``, der z.B. in C als Variable vom Typ Pointer implementiert ist und darin die Adresse des enthaltenen Objekts speichert.

Daraus ergibt sich aber, daß die Objekte nicht sequentiell im Speicher angeordnet zu sein brauchen; die Verweise können sozusagen ,,kreuz und quer`` durch den Speicherraum verlaufen! Die logische Reihenfolge ist damit von der physikalischen Reihenfolge unabhängig -- wir können Abstraktion von einer abstrakten, d.h.\ von der Repräsentation losgelösten Reihenfolge der Objekte sprechen.

Erstes Konzept Ein mögliches Konzept ist, daß jedes Objekt zusätzlich zu seinen eigenen Daten eine feste Anzahl weiterer, gleichartiger Objekte enthält, so daß ein Objekt also jederzeit von seinem ,,Vorgänger`` aus erreicht werden kann. Ein besonderer Wert zur Anzeige, daß ein Objekt keine weiteren Nachfolger hat, ist hier nötig, genau wie bei sequentiellen Strukturen; dazu kann der Wert nil herangezogen werden, das Objekt wird also als Optional modelliert. Neben den Verweisen enthält ein Objekt auch Daten; es ist also ein Tree.

Enthält ein Objekt genau ein weiteres gleichartiges Objekt, bildet die Gesamtstruktur eine verkettete Liste (wie im folgenden Beispiel). Bei n Verweisen (wie im folgenden Beispiel) entsteht im allgemeinen eine Baumstruktur mit einem Objekt an der ,,Spitze`` und n Nachfolgeknoten auf jeder Ebene -- wenn es keine Rückwärtsbezüge im Baum gibt. Ein typisches Beispiel für solche Rückwärtsbezüge ist die doppelt verkettete Liste: ein Knoten enthält seinen Nachfolger und seinen Vorgänger. Nur wenn kein Verweis auf ein hierarchisch höheres Objekt existiert, handelt es sich um einen echten Baum.

A = [ B ]
* B :: s_data : Datas_next : A
* C = [ D ]
* D :: s_data : Datas_first : C ... s_last : C
*[1.5ex]

Wie aber können Sie Objekte mit einer variablen Anzahl von Nachfolgern erzeugen ? Man unterscheidet vier Typen, die jeweils zunehmende Flexibilität aufweisen. Bei den ersten drei Typen enthält ein Knoten mit Nachfolgern selbst keine Daten; die Daten sind nur in den sogenannten Blättern, das sind Knoten ohne Nachfolger, gespeichert -- indem ein Knoten entweder Verweise auf Nachfolgeknoten oder Daten enthält. Der vierte Typ entsteht durch Kombination eines dieser Typen mit dem ersten Konzept, das auf Trees basiert.

Zweites Konzept Mit Sets, die entweder gleichartige Sets oder Datenelemente enthalten, können Sie eine einfache rekursive Struktur aufbauen; die Daten sind allerdings aufgrund der einzig möglichen, zufälligen Element-Selektion nur schlecht gezielt erreichbar, da ein Datum jeweils gesucht werden muß. Diese Struktur eignet sich, wenn in der Regel die gesamte Struktur zu bearbeiten ist.

E = F -set
* F = E | Data
* Data = ...
*[1.5ex]

Die Daten sind natürlich von beliebigem Typ; häufig handelt es sich um Trees, die ja mehrere Daten zusammenfassen.

Drittes Konzept Mit Tuples erreichen Sie zusätzlich, daß Sie gezielt auf die Daten zugreifen können, indem Sie jeweils eine Liste von Indizes als Zugriffspfad angeben; die Blätter sind auf diese Weise eindeutig und gezielt erreichbar.

G = H
* H = G | Data
* Data = ...
*[1.5ex]

Viertes Konzept Wählen Sie statt Tuple bzw. Set die Map, können Sie die Zugriffspfade mit Hilfe beliebiger Datentypen definieren, da die Argumentwerte der Map den Zugriffspfad eindeutig charakterisieren und von beliebigem Typ sein können! Mit anderen Worten: Sie können mit Maps auch die Tuple-Rekursion simulieren, indem Sie den Datentyp Nat1 als Argument-Domain wählen; ebensogut sind aber Tuples, Sets, Trees oder wieder Maps als Argumentwerte möglich.

J = K L
* K = Zugriffspfad-Typ
* L = J | Data
* Data = ...
*[1.5ex]

Beispiel: Ein Beispiel haben Sie bereits kennengelernt: das hierarchische Datei-System , in dem die Daten in Dateien (z.B. als Tuples modelliert) am Ende eines Verzeichnispfades stehen. Ein Verzeichnis (Directory) ist eine Map von Strings auf Verzeichniseinträge; die Strings enthalten die Namen der Einträge, die entweder Dateien sind oder wiederum Verzeichnisse. Die inneren Knoten sind zwar durch Strings identifizierbar, enthalten aber keinerlei Daten. Die Zugriffspfade sind durch die Abfolge von Verzeichnisnamen und einem Dateinamen am Ende eindeutig definiert. Die Domain-Gleichungen haben folgendes Aussehen:

 DOMAINS 
 *
Direc=Str    Direntry 
 *
Direntry		=		Datfile | Direc

Fünftes Konzept Schließlich können Sie auch in den inneren Knoten Daten unterbringen, indem Sie den Elementtyp von Tuples, Sets bzw. Maps anders wählen: statt der Union, bestehend aus Daten ODER Verweisen, nehmen Sie den Tree, bestehend aus Daten UND Verweisen! Der Tree enthält dann als ,,Verweis-Komponente`` keinen gleichartigen Tree, sondern wieder ein Tuple, einen Set oder eine Map von Trees. Ein Beispiel:

A = B -set
* B :: s_data : Datas_sub : A
*[1.5ex]

Eine Anwendung dafür finden Sie übrigens im Kapitel 7.

Organisation der Knoten und Verweise

Organisation Wie die Verweise organisiert sind, ist nicht determiniert. Es gibt zahlreiche grundlegende Datenstrukturen für die Verwaltung der Objekte, die mehr oder weniger komplex sind: die einfachen Strukturen haben ein schlechteres Zeitverhalten (für Zugriffe, Sortierung usw.), benötigen aber auch nur wenig Verwaltungsinformation; die komplexen Strukturen basieren auf umfangreichen, raffinierten Verweis-Pfaden, die natürlich mehr Speicherplatz und kompliziertere Algorithmen zur Manipulation der Objekte benötigen, aber einen wesentlich schnelleren Zugriff erlauben. Zur ersten Kategorie zählen z.B. einfach verkettete Listen, zur zweiten die sogenannten B-Bäume, deren Einfüge- und Löschoperationen immer einen balancierten, im Mittel zu 75-80% ausgelasteten Baum erzeugen.

Einige Datenstrukturen bieten einen Kompromiß zwischen den beiden genannten Extremen und sind für bestimmte Probleme und Konstellationen die ideale Lösung; ein Binärbaum zum Beispiel, den Sie im Abschnitt 5.8.4 kennengelernt haben, benötigt pro Knoten zwei Verweise auf weitere Knoten und bietet eine recht einfache Möglichkeit der Einsortierung neuer Objekte, kann aber leicht ,,entarten`` -- wenn die Objekte vor der Einsortierung bereits sortiert sind, entsteht eine verkettete Liste, weil alle Knoten nur einen Nachfolger erhalten. Dabei wird der Speicherplatz für den jeweiligen zweiten Verweis innerhalb eines Objekts verschwendet und die sogenannte ,,Tiefe`` des Baumes, also die Anzahl von Stufen, um das am weitesten von der Wurzel enfernte Objekt zu erreichen, ist maximal -- die Suchzeiten steigen an. Wenn Sie aber geeignete Randbedingungen schaffen, ist der Binärbaum eine effiziente Organisationsform. Seine Domain-Gleichung:

 Btree=[ Node ] 
 *
Node		::		s_lt : Btrees_data : Datas_rt : Btree

Implementation rekursiver Strukturen Rekursive Typdefinition Rekursive Typdefinition

VDM Class Library