Programmiersprachen II
Fortsetzung
Datenstrukturen
Prof. Dr. Reiner Güttler
Fachbereich GIS
HTW
Kapitel 2: Folge Datenstrukturen
2.4 Einschub: abstrakte Datentypen ADT‘s
abstrakte Datentypen (ADT)
Datentypen bisher: primitive Datentypen wie int, ... oder
selbstgebildete in Form von Klassen. In der objektorientierten
Programmierung hat man „unbewusst“ eigentlich die
Grundlagen der Idee von „abstrakten Datentypen“ von Anfang
an benutzt (aus der Sicht des Lernenden, in Wirklichkeit ist es
anders herum, die schon seit den 50er Jahren ständig in der
Forschung behandelten ADT’s bilden eine! Grundlage für die
OOP).
 Abstraktion: beinhaltet im wesentlichen die Abstraktion von der
Implementierung und zwar auch für die eigentlichen Daten und
nicht nur für die Operationen.
Prof. Dr. R. Güttler
Programmiersprachen 2
-2-
Kapitel 2: Folge Datenstrukturen
Beispiele:
 Für einen ADT „stack“ kennt der Benutzer nur den „logischen
Typ“ der „Nutzdaten“ und die Operationen push() und pop() mit
ihrer Wirkung (vorher<->nachher). Er weiss nicht ob der stack
realisiert ist als ein Array (ring buffer), eine verkettete Liste oder
was anderes wie z.B. ein Baum jeweils mit der dazu passenden
Implementierung der Operationen, die natürlich sehr!!
unterschiedlich ist..
 Betrachtet man z.B. einen ADT „Liste“, so muss man diesen
unterscheiden von den vorhin besprochenen verketteten Listen.
Ein ADT Liste (manchmal auch lineare Liste) ist eine ist eine
Gruppierung von Elementen mit ein paar Operationen wie
insert, delete, find,... . Eine Liste kann wiederum implementiert
werden durch eine verkettete Liste, aber auch durch ein Array
(wie könnte das gehen?) oder was anderes.
Prof. Dr. R. Güttler
Programmiersprachen 2
-3-
Kapitel 2: Folge Datenstrukturen
 Eine ADT-Spezifikation ist also eine Art „Schnittstelle“ und beinhaltet
die public Methoden.
 Die Grundidee der ADT’s sollte im Software-Design-Prozess
berücksichtigt werden und führt zu den immer wieder zitierten Benefits
der OOP. Wenn man Daten strukturiert speichern muss, sollte man
also zuerst überlegen, welche Operationen auf den Daten benötigt
werden, welcher Strategie sie folgen (z.B. FIFO, LIFO oder Zugriff
über einen Index). All dies führt zur Definition eines ADT. Wenn der
eigentliche Anwendungscode sich nur auf die ADT-Schnittstelle
bezieht, sollte ein kompletter Austausch der ADT-Implementierung
möglich sein ohne den Anwendungscode „anzufassen“.
 Beachte: In der Realität ist es sinnvoll, nicht zu scharf zu
unterscheiden zwischen Datenstrukturen die ADT’s sind und solchen,
die es nicht sind. Eine verkettete Liste kann als eigener ADT dienen
oder auch als Implementierungstyp für andere ADT’s wie z.B. stacks
oder queues.
Prof. Dr. R. Güttler
Programmiersprachen 2
-4-
Kapitel 2: Folge Datenstrukturen
2.5 Einschub: Rekursion
Bekannt aus Mathematik: Induktion als Beweismethode.
Grundidee: Unterteilung in zwei Schritte
 Beweis für einen einfachen Fall, den Induktionsanfang
 Beweis für einen „komplizierten“ Fall unter Zuhilfenahme der
Voraussetzung, dass die Behauptung für „weniger komplizierte“
Fälle richtig ist.
Übertragung der Grundidee auf Algorithmen als „Sonderform“ der
Strategie „Teile-und Herrsche („Aufteilung in „einfachere“
Teilprobleme, Zusammenbauen der Gesamtlösung aus den
Lösungen der Teilprobleme): wird häufig intuitiv gemacht, z.B.
beim Spielen
Prof. Dr. R. Güttler
Programmiersprachen 2
-5-
Kapitel 2: Folge Datenstrukturen
2.5 Einschub: Rekursion
Bekannt aus Mathematik: Induktion als Beweismethode.
Grundidee der Induktion: Unterteilung in zwei Schritte
 Beweis für einen einfachen Fall, den Induktionsanfang
 Beweis für einen „komplizierten“ Fall unter Zuhilfenahme der
Voraussetzung, dass die Behauptung für „weniger komplizierte“
Fälle richtig ist.
Rekursion:
Übertragung der Grundidee auf Algorithmen als „Sonderform“ der
Strategie „Teile-und Herrsche („Aufteilung in „einfachere“
Teilprobleme, Zusammenbauen der Gesamtlösung aus den
Lösungen der Teilprobleme): wird häufig intuitiv gemacht, z.B.
beim Spielen
Prof. Dr. R. Güttler
Programmiersprachen 2
-6-
Kapitel 2: Folge Datenstrukturen
Grundidee der Rekursion: die Teilprobleme selbst werden wieder
nach der gleichen Strategie gelöst. Damit dies funktionieren
kann, muss dieses „Aufteilen“ irgendwann stoppen und für die
dort vorliegenden „sehr kleinen“ Teilprobleme eine Lösung
gefunden werden können ohne wieder die gleiche Strategie
anzuwenden.
Also:
 ein rekursiver Algorithmus ruft sich selbst wieder auf
 allerdings für eine „kleinere“ Version des Problems
 Es gibt Problemversionen, die klein genug sind, um ohne
erneuten Aufruf direkt gelöst werden zu können.
Prof. Dr. R. Güttler
Programmiersprachen 2
-7-
Kapitel 2: Folge Datenstrukturen
Beispiele:
1. Berechnung der „triangular numbers“:
 es handelt sich um die Folge 1,3,6,10,15,21,...
 Das n-te Element erhält man, indem man n zum vorherigen
Element addiert.
Etwas formaler:
int triangular(int n)
{
return(n + triangular(n-1)); // Achtung, noch nicht komplett
}
Prof. Dr. R. Güttler
Programmiersprachen 2
-8-
Kapitel 2: Folge Datenstrukturen
Die Idee ist wie “das übergeben des schwarzen Peters”:
 wenn ich die 9-te triangular-Zahl finden soll, so weiss ich, das
ist 9 plus die 8-te triangular-Zahl.
 Also frage ich jemanden nach der 8. und warte auf dessen
Antwort.
 Der macht das genauso usw.
 Irgendjemand in der Kette muss allerdings in der Lage sein,
eine Antwort zu finden ohne jemanden zu fragen. In unserem
Fall muss also jemand wissen, dass die 1. Zahl 1 ist und das
reicht.
Prof. Dr. R. Güttler
Programmiersprachen 2
-9-
Kapitel 2: Folge Datenstrukturen
Also:
int triangular(int n)
{
if (n==1)
return 1;
else
return(n + triangular(n-1));
}
Prof. Dr. R. Güttler
Programmiersprachen 2
-10-
Kapitel 2: Folge Datenstrukturen
2. Einfügen in eine sortierte Liste:
Offensichtlich ist die Methode insertFirst(NewNode, k) mit
 newNode ist Pointer auf das einzufügende Listenelement
 k ist First-Pointer der Liste, in die eingefügt werden soll
(natürlich mit gleichem Knotentyp)
 Jeder Knoten Node hat ein Datenelement Node.data, nach dem
sortiert ist
sehr einfach.
Prof. Dr. R. Güttler
Programmiersprachen 2
-11-
Kapitel 2: Folge Datenstrukturen
Also folgende Grundidee für die Funktion insert:
insert (NewNode, k) // k ist First-Pointer einer Liste oder nextPointer eines vorher besuchten Listenknotens, s.u.
{
if (NewNode.data < k.data) //richtige Einfügeposition gefunden
insertFirst(NewNode,k);
else
insert(NewNode, k.Next);
}
Erster Aufruf: sei first First-Pointer der betreffenden Liste:
insert (NewNode, first);
Prof. Dr. R. Güttler
Programmiersprachen 2
-12-
Kapitel 2: Folge Datenstrukturen
Eines der bekanntesten „Theoriebeispiele“ aus der
Literatur: Türme von Hanoi
Beispiel im Applet in Vorlesung
Lösungsidee mit Rekursion:
 Funktion „Umsetzen“ mit 4 Parametern
 Anzahl der umzusetzenden Scheiben
 „von“-Stab
 „nach“-Stab
 „Hilfs“-Stab
Prof. Dr. R. Güttler
Programmiersprachen 2
-13-
Kapitel 2: Folge Datenstrukturen
Umsetzen (N,A,B,C):
 Umsetzen (N-1,A,C,B)
 Setze einen Stein von A nach B (das ist ja jetzt der
unterste!)
 Umsetzen (N-1,C,B,A)
Aufrufbaum?
Prof. Dr. R. Güttler
Programmiersprachen 2
-14-

datenstruktur_2_adt_rek