Einführung in die Informatik für Naturwissenschaftler und Ingenieure

3 Datenstrukturen (S. 169-170)

Algorithmen, sei es in Form von Programmen oder Prozessen, arbeiten stets mit Daten [Mehlhorn 86]. Diese Daten können einfach und wenig strukturiert oder komplex und stark strukturiert sein. Daten, denen eine de.nierende Struktur aufgeprägt wurde, heißen Datenstrukturen. Einfache Datenstrukturen sind Stapel und Schlangen (Abschn. 3.2) und lineare Listen (Abschn. 3.3). Bäume, Graphen und relationale Dateien stellen komplexe Datenstrukturen (Abschn. 3.5 und 3.6) dar. Diese werden wiederum durch einfachere Datenstrukturen implementiert. So werden beispielsweise Graphen üblicherweise durch Adjazenzlisten repräsentiert (Abschn. 3.4).

Die einfachen Datenstrukturen Stapel und Schlangen werden mit Hilfe zusammengesetzter Datenstrukturen aufgebaut. Felder (engl. arrays) und Verbunde (engl. records) sind typische Vertreter solcher zusammengesetzten Datenstrukturen (Abschn. 3.1, Abschn. 5.3.1.5). Die Elemente zusammengesetzter Datenstrukturen sind jedoch nicht von einem beliebigen Datentyp, der den erlaubten Wertebereich vorgibt, sondern sie gehören Grundtypen wie z. B. integer oder real an (Abschn. 5.3.1.4).

Naturgemäß besteht ein enger Zusammenhang zwischen dem verwendeten Algorithmus und der dafür am geeignetsten Datenstruktur. Wegen dieser engen Kopplung wurden Datentypen (Abschn. 2.2.2) eingeführt. Es besteht jedoch ein deutlicher Unterschied zwischen einer Datenstruktur und einem darauf arbeitenden Datentyp, obwohl häufig beide Begriffe gleichbedeutend verwendet werden. Ein Datentyp enthält nicht nur eine Datenstruktur, sondern er umfasst gleichzeitig die Menge der dazugehörenden Operationen.

Aus Sicht der objektorientierten Programmierung ist eine Datenstruktur noch kein Objekt, denn es muss die folgenden Bedingungen erfüllen (Abschn. 5.3.4): Ein solches Objekt vereinigt in sich nicht nur eine Datenstruktur und die dazugehörenden Operationen, sondern es wechselwirkt mit anderen Objekten durch Nachrichtenaustausch und es kann seine Variablen und Operationen vererben.

In diesem Kapitel konzentrieren wir uns auf die am häu.gsten gebrauchten Datenstrukturen. Die zugehörigen Algorithmen werden im nächsten Kapitel vorgestellt. Neben der Klassi.kation der Datenstrukturen nach ihrer Komplexität, d.h. ihrer internen Struktur, benutzen wir noch die Begriffe der statischen und dynamischen Datenstrukturen, um dieses Kapitel einzuteilen.

Wir sprechen von einer statischen Datenstruktur, wenn sie während ihrer gesamten Lebensdauer ihre Struktur oder Beziehung zu anderen Datenstruktur-Elementen und Größe beibehält. Die in den ersten beiden Abschnitten besprochenen Datenstrukturen sind statisch. In den restlichen Abschnitten werden dynamische Datenstrukturen behandelt.

Eine Datenstruktur heißt dynamisch, wenn sie sich während der Programmausführung verändert. Diese Veränderungen können sich dabei nur auf ihre Struktur und Größe beziehen, aber auch ihre Erzeugung bzw. Vernichtung beinhalten. Typisch für dynamische Datenstrukturen ist, dass sie während ihrer Lebenszeit wachsen und schrumpfen. Beispiele für solche Datenstrukturen sind lineare Listen, Bäume und Graphen. Sie alle werden durch Elemente, die durch Zeiger verkettet sind, implementiert.

3.1 Konstruktion zusammengesetzter Datenstrukturen: Feld und Verbund
Zusammengesetzte Datenstrukturen werden üblicherweise konstruktiv aufgebaut [Nievergelt, Hinrichs 93], [Ottmann, Widmayer 96]. Die meisten höheren Programmiersprachen bieten dafür Konstruktoren als Schlüsselworte, wie z.B. array, an. Bei der Aufzählung solcher Konstruktoren orientieren wir uns, auch in der Notation, an OBERON, der Nachfolgesprache von PASCAL [Reiser, Wirth 94]. Es werden die beiden elementaren Datenstrukturen Feld und Verbund beschrieben.

Feld. Die Datenstruktur Feld entsteht durch das Aneinanderreihen gleichartiger Elemente, wobei die Reihenfolge dieser Elemente wichtig ist. Diese statische Datenstruktur wird in einem Programm in einer Vereinbarung, auch Deklaration genannt, mit Hilfe des Konstruktes array de.niert. Dabei wird üblicherweise ein Feld von einem ganz bestimmten Typ mit einem Bezeichner explizit vereinbart.