![]()
Teil III
Datenstrukturen
![]()
11Abstrakte Datentypen
Abstrakte Datentypen wurden bereits im Abschnitt 2.3 kurz eingeführt. Ein abstrakter Datentyp fasst die wesentlichen Eigenschaften und Operationen einer Datenstruktur zusammen, ohne auf deren tatsächliche Realisierung im Rechner einzugehen. Hier soll dieser Stoff nun rekapituliert und vertieft werden.
Geheimnisprinzip oder programming by contract
Um Programme möglichst wiederverwendbar zu gestalten und von unnötigen Details zu abstrahieren, sollte man Datenstrukturen unabhängig von ihrer späteren Implementierung in einer konkreten Programmiersprache spezifizieren. Diese Beschreibung ist so zu gestalten, dass Programmierer sich dieser Datenstrukturen bedienen können, um Probleme zu lösen, dass aber die Implementierung jederzeit geändert werden kann, ohne dass die Anwender der Datenstruktur etwas davon merken. Diese Eigenschaft wird auch als Geheimnisprinzip oder programming by contract bezeichnet.
Die Motivation hinter der Spezifikation abstrakter Datentypen lässt sich somit kurz gefasst wie folgt formulieren:
Beschreibung von Datenstrukturen unabhängig von ihrer späteren Implementierung in einer konkreten Programmiersprache
Im Folgenden werden wir das Kürzel ADT für derartig spezifizierte abstrakte Datentypen benutzen.
Ein ADT kann das Verständnis eines in einer Programmiersprache fest integrierten Datentyps verdeutlichen, indem die wesentlichen Eigenschaften knapp und eindeutig festgelegt werden. Interessant ist der Einsatz von ADTs für neu entwickelte Datentypen, die zum Beispiel Teil einer neu realisierten Bibliothek von Funktionen werden. Bei neu entwickelten Datentypen muss man daher jeweils die folgenden beiden Aspekte unterscheiden:
Konkrete vs. abstrakte Datentypen
- Konkrete Datentypen werden aus Basisdatentypen bzw. Java-Klassen konstruiert und sind somit direkt in einer Implementierung einsetzbar.
- Abstrakte Datentypen bilden nur eine Spezifikation der Schnittstelle nach außen, indem sie Operationen und ihre Funktionalität festlegen. Sie sind nicht direkt in ein Programm einbindbar.
Es kann mehrere konkrete Datentypen zu ein und demselben abstrakten Datentyp geben.
In der Softwaretechnik entsprechen Realisierungen von ADTs Softwaremodulen. Derartige Softwaremodule beachten die folgenden Prinzipien:
Kapselung
- Kapselung: Ein ADT-Modul darf nur über seine Schnittstelle benutzt werden.
Geheimnisprinzip
- Geheimnisprinzip: Die interne Realisierung eines ADT-Moduls ist verborgen.
Solche Softwaremodule haben Eigenschaften analog zu Klassen in objektorientierten Programmiersprachen, und somit sind ADTs gewissermaßen Grundlage des Prinzips der objektorientierten Programmierung. Allerdings werden wir sehen, dass ADTs eine einfachere Modellbildung als objektorientierte Programmiersprachen haben und die beiden Konzepte nicht einfach gleichgesetzt werden sollten.
Wir gehen in diesem Kapitel wie folgt vor: Wir beginnen mit der Konkretisierung des Begriffs der Schnittstelle eines ADT und des Modellbegriffs für ADTs, indem das Modell eines ADT eine Algebra bildet. Als Beispiel für die Spezifikation von ADTs betrachten wir die algebraische Spezifikation mittels Gleichungen. In dem darauf folgenden Abschnitt werden wir einige nichttriviale Beispiele für (parametrisierte) ADTs betrachten, um ein Gefühl für das Arbeiten mit der algebraischen Spezifikation zu bekommen. Der letzte Abschnitt ist dann der Umsetzung von ADTs in Programmiersprachen, insbesondere natürlich in Java, gewidmet.
11.1Signaturen und Algebren
Ziel dieses Abschnittes ist es, einige bereits in Abschnitt 2.3 ei...
