Datenstrukturen

Objekte verwalten in ihren Attributen Daten unterschiedlchen Typs. Sie haben die einfachen Datentypen int, boolean und double kennengelernt. Wenn ein Attribut auf ein Objekt verweist, muss die Klasse des Objekts als Datentyp als Datentyp angegeben werden. Ein Array verwaltet mehrere Daten desselben Typs. In diesem Themenbereich werden Sie weitere Datenstrukturen kennenlernen.

Dazu eine erste Begriffsdefinition:

Beispiele sind

• Integer
  • Die möglichen Werte sind z.B. alle ganzen Zahlen zwischen -2147483648 und +2147483647
  • Die Operatoren sind die 5 Rechenoperatoren und weitere (in Java genannte) Methoden, die aus der Java-API ersichtlich sind.
  • Genauer
    Addition, Subtraktion, Multiplikation, ganzzahlige Division, ganzzahliger Rest
  • Die Dokumentation der Java-Klasse Integer findet man z.B.  hier
• Datum
  
  • Die möglichen Werte sind alle gültigen Charakterisierungen eines Datums
  • Zu den Operatoren gehört z.B. die Möglichkeit, die Anzahl der Tage zwischen zwei Daten zu ermitteln.
  • Die Dokumentation der Java-Klasse Date findet man z.B. hier

Aus einem Datentyp kann man Objekte bilden; jedes zulässige, zu dem Datentyp gehörige Objekt hat genau einen der möglichen Werte.

Jedoch kommt es sehr häufig vor, dass eine Sammlung vieler Objekte gleichen Typs zu verwalten ist. So verwaltet z.B. ein Autohaus mehrere Autos, eine Großfamilie mehrere Familienmitglieder, ein Staat mehrere Städte, ...

Die verwalteten Objekte stehen in der Regel in irgendeiner Weise miteinander in Beziehung, die Menge der Objekte ist also strukturiert. So stehen die Autos im Autohaus vielleicht in einer Reihe nebeneinander, die Familienmitglieder haben Verwandschaftsbeziehungen, die Städte sind durch Straßen verbunden.

In seltenen Fällen werden die Objekte unstrukturiert verwaltet (z.B. die Menge aller Kartoffeln in einem Sack); dann liegt halt eine Art "leere Struktur" vor.

Damit kann man im Sinne einer objektorientierten Modellierung bzw. Programmierung definieren:

Typischerweise ist bei der Modellierung und der Implementierung einer solchen Datenstruktur nicht bekannt, wie viele dieser gleichartigen Objekte zur Laufzeit des Programms verwaltet werden sollen. Und es ist davon auszugehen, dass sich diese Anzahl im Laufe der Zeit immer wieder ändert. So hat eine Schule heute z.B. 1234 Schüler, in der kommenden Woche 1237 Schüler und am Ende des Schuljahres, nachdem die Abiturienten die Schule verlassen haben, nur noch 1111 Schüler.

Das Konzept von Arrays, das wir bereits kennengelernt haben, um gleichartige Objekte zu verwalten, erfüllt diese Bedingungen nicht. Denn die Anzahl der zu verwaltenden Objekte muss zur Compilezeit feststehen und kann später, zur Laufzeit also, nicht mehr verändert werden. Hat man z.B. in der Schulverwaltungssoftware ein Array von 1000 Schülern angelegt, dann werden Speicher für 1000 Schüler reserviert, auch wenn noch kein Schüler in der Schule aufgenommen wurde. Und wenn dann der 1001-te Schüler kommen möchte, muss man den Java-Quellcode ändern und das Programm neu starten und ggf. sogar alle Daten erneut eingeben (oder den neuen Schüler abweisen).

Das führt zu der folgenden

Einige typische Strukturen werden in den folgenden Kapiteln näher untersucht.

Lineare Strukturen In der Einführungsphase wurde die lineare Struktur Array als Sammlung von Daten gleichen Typs behandelt. Der Zugriff auf einzelne Komponenten erfolgt über den jeweiligen Index. Mithilfe einer for-Schleife können alle Elemente eines Arrays bearbeitet werden. Ein Array hat den Nachteil, dass die einmal festgelegte Anzahl der Elemente des Arrays nicht mehr verändert werden kann. In diesem Kapitel lernen Sie lineare Datenstrukturen kennen, die eine beliebige, nur vom Speicher des Computers abhängige Anzahl an Elementen enthalten kann. Der Nachteil besteht darin, dass der Zugriff auf die Elemente sequentiell erfolgt und nicht mehr direkt über einen Index.
Baumstrukturen Bäume bieten eine Möglichkeit, Daten zu speichern, deren gegenseitige Beziehungen baumartig strukturiert sind. In diesem Kapitel werden hauptsächlich spezielle Bäume untersucht, Bäume, in denen in jedem Knoten maximal zwei Äste abzweigen. Wir lernen die Struktur solcher Bäume kennen, werden wichtige Algorithmen (Einfügen, Suchen, Löschen) entwickeln.
Graphstrukturen Graphen werden benutzt, um Objekte zu verwalten, die miteinander in einer Beziehung stehen, ohne dass die Struktur linear oder baumartig ist. Es gibt viele interessante und praxisrelevante Problemstellungen, die typischerweise mit Hilfe von Graphen beschrieben und gelöst werden können.