Algorithmen und Datenstrukturen

Eine Einführung mit Java

Gunter Saake, Kai-Uwe Sattler

• Publisher: dpunkt.verlag
• Year: 2020
• ISBN:
  9783969100677
• Edition: 6
• Topic: Computer Science
• Subtopic: Programming in Java
• Index: Computer Science

Algorithmen und Datenstrukturen von Grund auf verstehen

• Fundierte Einführung mit klarem didaktischen Aufbau
• Mit konkreten Anwendungsbeispielen
• Eine reichhaltige Fundgrube für Lehre und Selbststudium

Kenntnisse von Algorithmen und Datenstrukturen sind ein Grundbaustein des Studiums der Informatik und verwandter Fachrichtungen. Das Buch behandelt diese Thematik in Verbindung mit der Programmiersprache Java und schlägt so eine Brücke zwischen den klassischen Lehrbüchern zur Theorie von Algorithmen und Datenstrukturen und den praktischen Einführungen in eine konkrete Programmiersprache.

Die konkreten Algorithmen und deren Realisierung in Java werdenumfassend dargestellt. Daneben werden die theoretischen Grundlagen vermittelt, die in Programmiersprachen-Kursen oft zu kurz kommen: abstrakte Maschinenmodelle, Berechenbarkeit, Algorithmenparadigmen sowie parallele und verteilte Abläufe. Einen weiteren Schwerpunkt bilden Datenstrukturen wie Listen, Bäume, Graphen und Hashtabellen sowie deren objektorientierte
Implementierung mit modernen Methoden der Softwareentwicklung.

Die 6. Auflage führt einige neue Algorithmen ein und berücksichtigt die Neuerungen der aktuellen Java-Versionen, u.a. zu Themen wie Parallelisierung.

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...