Mit Google fortfahren
Abstrakter Datentyp: ADT einfach erklärt
Ein abstrakter Datentyp (ADT) legt fest, welche Werte und Operationen es gibt und wie sich diese Operationen verhalten. Wie die Daten intern gespeichert werden, bleibt verborgen und darf ausgetauscht werden, solange das sichtbare Verhalten gleich bleibt.
Auf dieser Seite lernst du, Signatur und Semantik zu unterscheiden, einen Stack als ADT zu spezifizieren und eine Implementierung von ihrer Schnittstelle zu trennen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Was macht einen Datentyp abstrakt?
Stell dir einen Stack in einem Programm vor. Du darfst Elemente ablegen, das oberste Element ansehen und es entfernen. Ob das Programm dafür ein Array oder verkettete Knoten verwendet, musst du beim Benutzen nicht wissen.
Abstrakter Datentyp
Ein abstrakter Datentyp beschreibt einen Wertebereich, die zulässigen Operationen und deren Verhalten. Der Zugriff erfolgt ausschließlich über die festgelegte Schnittstelle; die interne Darstellung gehört nicht zur Definition.
Die Trennung beantwortet zwei verschiedene Fragen:
- Spezifikation: Was dürfen die Operationen, und welches Ergebnis müssen sie liefern?
- Implementierung: Wie werden Daten gespeichert und Operationen programmiert?
Beim ADT zählt das beobachtbare Was. Das interne Wie darf wechseln.
Signatur und Semantik gehören zusammen
Eine Signatur nennt den Operationsnamen sowie die Typen der Eingaben und des Ergebnisses. Zum Beispiel bedeutet push: ELEMENT × STACK → STACK: Die Operation erhält ein Element und einen Stack und liefert einen Stack.
Die Signatur sagt noch nicht, welches Element später oben liegt. Dafür braucht man die Semantik: Sie beschreibt die Bedeutung einer Operation und die Regeln ihres Zusammenwirkens mit anderen Operationen.
Die Signaturen insert: ELEMENT × CONTAINER → CONTAINER und next: CONTAINER → ELEMENT könnten sowohl zu einem Stack als auch zu einer Queue passen.
Erst die Semantik entscheidet:
- Beim Stack liefert
nextdas zuletzt eingefügte Element: LIFO. - Bei der Queue liefert
nextdas zuerst eingefügte Element: FIFO.
Gleiche Typangaben bedeuten also nicht automatisch gleiches Verhalten.
Einen Stack vollständig spezifizieren
Ein Stack oder Stapel arbeitet nach dem LIFO-Prinzip: Last In, First Out. Das zuletzt eingefügte Element wird zuerst betrachtet oder entfernt.
Eine mögliche Signatur lautet:
emptyStack: → STACKerzeugt einen leeren Stack.isEmpty: STACK → BOOLprüft, ob er leer ist.push: ELEMENT × STACK → STACKlegt ein Element oben ab.top: STACK → ELEMENTbetrachtet das oberste Element.pop: STACK → STACKentfernt das oberste Element und liefert hier den verbleibenden Stack.
Diese Regeln legen das Verhalten fest:
isEmpty(emptyStack()) = trueisEmpty(push(x, s)) = falsetop(push(x, s)) = xpop(push(x, s)) = s
Wir beginnen mit s0 = emptyStack().
s1 = push(4, s0): Oben liegt nun4.s2 = push(7, s1): Oben liegt nun7.top(s2)liefert7, veränderts2aber nicht.pop(s2)liefert nach der hier gewählten Konvention wieders1.
Der entscheidende Gedanke: Weil 7 zuletzt eingefügt wurde, wird 7 zuerst betrachtet und entfernt.
Randfälle und Konventionen eindeutig festlegen
Eine Spezifikation ist erst brauchbar, wenn sie auch Randfälle klärt. Bei einem leeren Stack können top und pop kein vorhandenes Element bearbeiten. Deshalb muss die Semantik festlegen, ob die Operation einen Fehler meldet oder anders behandelt wird.
In der Spezifikation dieser Seite gelten top(emptyStack()) und pop(emptyStack()) als Fehler. Damit besitzen top und pop die Vorbedingung, dass der Stack nicht leer ist.
Auch der Rückgabewert von pop ist keine universelle Sprachregel. Verschiedene Schnittstellen verwenden unterschiedliche Konventionen:
popliefert den verbleibenden Stack,popliefert das entfernte Element,- oder
popverändert den Stack und liefert keinen Wert.
Diese Varianten dürfen nicht vermischt werden. Signatur und Semantik müssen gemeinsam eindeutig festlegen, welche Konvention gilt.
Warum Implementierungen austauschbar sein können
Eine Implementierung realisiert die Spezifikation mit konkreten Mitteln. Ein Stack kann zum Beispiel intern ein dynamisches Array oder eine verkettete Liste verwenden.
Bei einer arraybasierten Umsetzung kann die Stackspitze am letzten belegten Feld liegen. Bei einer verketteten Umsetzung kann sie der erste Knoten sein. Von außen bleiben dennoch dieselben Operationen sichtbar.
In Java können öffentliche Methoden die Operationen darstellen und private Felder die interne Repräsentation verbergen. Ein Interface kann die Methodensignaturen vorgeben, drückt die vollständige Semantik aber nicht automatisch aus. Vorbedingungen, Wirkungen und Ergebnisse müssen zusätzlich klar beschrieben und von der Implementierung eingehalten werden.
Eine Anwendung führt nur push, top, pop und isEmpty aus. Die Implementierung wird von einem Array auf verkettete Knoten umgestellt.
Wenn jede Operation weiterhin dieselben Ergebnisse, Wirkungen und Fehlerfälle besitzt, muss die Anwendung nicht geändert werden. Ändert sich dagegen etwa der Rückgabewert von pop, wurde nicht nur die Implementierung ausgetauscht, sondern die Schnittstelle oder Semantik verändert.
So prüfst du eine ADT-Spezifikation:
- Nenne den Wertebereich und benötigte weitere Typen.
- Notiere für jede Operation eine eindeutige Signatur.
- Beschreibe die Wirkung und das Zusammenspiel der Operationen.
- Lege Vorbedingungen und Randfälle fest.
- Prüfe an Operationsfolgen, ob das gewünschte Verhalten eindeutig folgt.
- Halte interne Speicherentscheidungen aus der Spezifikation heraus.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Abstrakter Datentyp
- legt Werte und Operationen fest
- verbindet Signatur mit Semantik
- beschreibt Vorbedingungen und Randfälle
- verbirgt die interne Darstellung
- erlaubt austauschbare Implementierungen
- Stack als Beispiel
- push fügt oben ein
- top betrachtet oben
- pop entfernt oben
- LIFO bestimmt die Reihenfolge
Abschluss-Check
Wenn du jede Operation durch Signatur, Wirkung und Randfälle beschreiben und eine Operationsfolge vorhersagen kannst, hast du die zentrale Idee des ADT verstanden: Spezifikation festlegen, Implementierung offenlassen.