Noch ein letzter organisatorischer Hinweis.
Ich habe jetzt endlich mal, etwas schwerfällig, auch den Semesterplan
mal an die Ist-Situation angepasst.
Wir hatten ja irgendwann seit Mitte Mitte November ein bisschen
Verzögerung in den einzelnen Vorlesungen, sodass wir jetzt eigentlich
schon bei einer ganzen Vorlesung Verzögerung sind.
Und ich habe es jetzt eben entsprechend auch für die Vergangenheit
angepasst, dass Sie nachher auch sehen können, welche Aufzeichnung von
welchem Tag Sie sich für welches Thema dann nachher noch zum Beispiel
bei YouTube anschauen können.
Und heute sind wir am 13.12.
Und es geht um Listen, abstrakte Datentypen und Rekursionen.
Dazu dann immer noch wieder mein leicht verwirrendes Bild für den
Vorlesungsüberblick.
Ich habe das Feedback auch von den Tutoren bekommen, dass das ein
bisschen voll und vielleicht viel ist, dieses Bild.
Aber es geht ja, wie gesagt, auch nicht darum, dass Sie jetzt von
Anfang an dieses ganze Bild nachvollziehen können, sondern dieses Bild
soll Sie eigentlich über die Vorlesung hinweg begleiten.
Und am Ende der Vorlesung, wenn wir diese ganzen Themen besprochen
haben, dann sollte das in einen Sinn machen für Sie.
Also jetzt kann man es natürlich noch nicht alles verstehen, aber wir
bauen uns das so Stück für Stück auf.
Hier habe ich jetzt auch noch mal in grün umkreist, was Sie jetzt
alles schon kennen.
Wir hatten sozusagen den Schwerpunkt bis jetzt auf der linken Seite
diesen Grundlagen von objektorientierter Programmierung und haben mit
den Arrays eben auch schon ein bisschen angefangen.
Ich sollte hier zeigen, ja, in diesem Bereich Systeme bauen,
vorzudringen, wo es eben darum geht, nicht nur einzelne Variablen und
einzelne Daten zu verarbeiten, sondern eben eine Menge von
gleichartigen Daten.
Und da machen wir dann heute auch weiter, wenn wir das dürfen.
Genau.
Mit den Listen.
Das ist nämlich eine alternative Art, wie ich viele gleichartige Daten
verwalten, verarbeiten kann.
Sieht ja auch hier auf dem Bildschirm ganz ähnlich aus.
Entsprechend sind hier jetzt die Lernziele für heute aufgeführt.
Es geht, wie gesagt, um Listen und um abstrakte Datentypen hier unten.
Und bei den Listen geht es mir darum, dass sie am Ende der
Veranstaltung den Aufbau von sowohl einfach als auch mehrfach
verketteten Listen kennen, dass sie Listen verwenden können, das
heißt, dass sie Daten in Listen ablegen können, dass sie die Daten,
die in Listen enthalten sind, verändern können und dass sie Daten aus
Listen auch wieder löschen können.
Dann, dass sie Iteratoren verwenden können, um über Listen zu
iterieren, also in einer Schleife eine Liste abzulaufen sozusagen.
Und dass sie auch wissen, wann es sinnvoll ist, Listen einzusetzen und
wann es sinnvoll ist, Arrays einzusetzen, was also jeweils die Vor-
und Nachteile sind.
Dann ist ein Teil des Themas heute eben auch noch diese abstrakten
Datentypen, wo die Liste ein Beispiel dafür ist.
Und da sollten sie eben nach der Vorlesung wissen, was die
Bestandteile von abstrakten Datentypen sind und sollten beschreiben
können, inwiefern eine Liste denn jetzt ein abstrakter Datentyp ist.
Aber dafür dazu dann natürlich später mehr.
Ja, steigen wir in die eigentliche Thematik ein.
Wie gerade schon gesagt, hatten wir bis jetzt Arrays verwendet, um
Folgen von Elementen zu implementieren, also mehrere Daten ablegen zu
können, die irgendwie gleichartig sind.
Was wir bis jetzt gelernt haben, Variablen, Klassenzeiger und so
weiter, ermöglicht es uns jetzt aber auch schon, solche Kollektionen
auch auf eine andere Weise zu implementieren, nämlich als sogenannter
rekursiver Datentyp.
Rekursiver Datentyp bedeutet, dass Objekte einer Klasse auch Verweise
auf Objekte derselben Klasse enthalten, dass sie also nicht direkt
sich selbst als einzelnes Objekt zeigen, sondern auf ein anderes
Objekt derselben Klasse.
Ein Beispiel dafür jetzt erst mal noch ohne Liste ist hier gezeigt.
Also eine Klasse nennt man rekursiven Datentyp, wenn sie selber ein
Attribut enthält, was wieder auf ein Objekt der gleichen Klasse zeigt.
Und wenn man dann mit diesem Schema hier eben komplexere
Datenstrukturen aufbaut.
Hier sieht man schon, dass es eine Klasse recursive, die hat ein
Element, was irgendwie ein Datum sein soll, wie Element Integer und
zeigt dann auf ein nächstes Recursive Element.
Da können Sie sich jetzt vielleicht schon vorstellen, dass man daraus
so eine Kette von Elementen ganz ähnlich wie so ein Array aufbauen
kann.
Das muss aber nicht unbedingt nur eine Kette sein von Elementen bei
solchen rekursiven Datentypen, sondern man kann sich auch vorstellen,
eine Baumstruktur aufzubauen, also hier eine Klasse zu haben, die
wiederum ein bestimmtes Datum enthält, also hier irgendein Element,
mal ein Integer als Beispiel, und die dann auf zwei gleichartige
Objekte, also Objekte vom gleichen Typ zeigt, nämlich den linken Sub
-Baum und den rechten Sub-Baum.
Und da kann man sich dann vorstellen, kann man so eine Struktur von
Daten, die so baumartig angeordnet ist, dann implementieren.
Das ist also diese Idee von rekursiven Datentypen.
Ich zeige wieder auf Objekte meiner eigenen Klasse, um so einen
Datentyp aufzubauen.
Wir schauen uns jetzt noch keine Bäume an, sondern erst mal den
einfachsten Fall von solchen rekursiven Datentypen, nämlich die
sogenannten einfach verketteten Listen.
Und einfach verkettete Listen bestehen aus Listenzellen.
Das sind erst mal die Elemente, die Daten enthalten können, sozusagen.
Und jede solche Zelle enthält das dann den eigentlichen Inhalt der
Zelle, die nicht abspeichern möchte, also zum Beispiel eine Integer
-Zahl und dann weiter noch eine Referenz auf die Zelle des nächsten
Listen -Elements.
Also enthält jede Zelle sowohl Inhalt, als auch Information zur
Verkettung der gesamten Liste.
In der letzten Listenzelle habe ich dann einen Verweis auf 0, was dann
anzeigt, hier ist die Liste jetzt zu Ende.
Genau.
Das Ganze kann man sich am besten grafisch dargestellt vorstellen.
Das hier wäre jetzt also eine Beispielliste für eben das Ablegen von
Integer -Zahlen.
Ich habe hier so dieses Graue, soll eine Listenzelle darstellen.
Und eine Listenzelle hat immer einen Inhalt, hier die 5, und enthält
eine Referenz auf die nächste Listenzelle.
Und das ist gerade das, was wir eben als Attribut, wie hieß es?
Next, glaube ich, gesehen hatten.
Also hier ein Attribut vom Typ Listenzelle selber wieder.
Wenn man dann in der ersten Listenzelle das nächste referenziert, die
nächste Zelle, in der zweiten Zelle die dritte referenziert und so
weiter, bekommt man eben insgesamt eine Liste, die ziemlich ähnlich
wie so ein Array aussieht.
Genau, das habe ich jetzt gerade gesagt.
Inhalt haben wir hier, Verkettung.
Und am Ende, hatte ich gerade auch schon kurz gesagt, aber hier
nochmal grafisch dargestellt, habe ich in der letzten Listenzelle dann
einfach ein Null-Wert für diese Referenz, was mir dann anzeigt, hier
ist die Liste zu Ende.
Genau, soweit die Idee.
Um uns jetzt mal anzuschauen, wie das in Java aussieht, schauen wir
uns mal Listen von diesen Vector2D-Objekten an und wie man das
umsetzen könnte in Java.
Dazu brauchen wir zuerst eine Klasse, die uns so eine einzelne
Listenzelle beschreibt.
Die würde hier wie folgt aussehen, also eine Klasse Listenzelle, die
enthält, wie gesagt, Inhalt und Referenz auf die nächste Zelle.
Also hier Content, ein Vector2D-Objekt und Next, eine Referenz auf die
nächste Listenzelle und hat jetzt in unserem Fall noch einen
Konstruktor, mit dem man eben eine neue Listenzelle erzeugt und den
Inhalt gleich übergibt als Parameter und auch schon gleich die nächste
Listenzelle als Parameter übergibt.
So werden dann diese beiden obigen Werte gleich sinnvoll
initialisiert.
Content wird auf den übergebenen Vector2D gesetzt und Next, das Next
-Element wird auf die übergebene Listenzelle gesetzt.
Das ist also die Klasse für so eine einzelne Zelle.
Daraus kann ich dann ganze Listen zusammenbauen, indem ich eine neue
Klasse Liste anlege, sage, diese hat als Attribut eine Referenz auf
eine einzelne Listenzelle, die den Kopf der Liste angibt, also hier
Head genannt und dann zum Beispiel einen Konstruktor, der erstmal eine
leere Liste erzeugt.
Und diese ganze Liste zeigt eben nur auf den Kopf der Menge oder der
Sequenz von Listenzellen, weil ich dann ja über die einzelnen
Referenzen, über die Verkettung auf die anderen Zellen zugreifen kann.
Schauen wir uns an, wie man so eine Liste erstellen kann.
Um so eine Liste, wie wir sie gerade gesehen hatten, grafisch
aufzubauen, muss man, so wie wir es jetzt haben, erstmal diese
Listenzellen -Objekte anlegen.
Also nehmen wir mal an, wir wollen diese Liste hier aufbauen.
Dann würde der folgende Code das für uns machen.
Wir bräuchten erstmal vier Objekte für unsere Vector2D, also vier
Instanzen unserer Vector2D-Klasse, die wir in die Liste hineinlegen
wollen.
Hier mal einfach als P, Q und R bezeichnet.
Und dann können wir drei Listenzellen-Objekte anlegen, indem wir
diesen Listzell-Konstruktor aufrufen.
Hier jetzt als erstes das letzte, die letzte Listenzelle, weil wir da
als Parameter dann in Null übergeben können.
Wir wollen ja hier hinten keine Referenz haben, sondern Null.
Dann können wir als zweites das zweite Listenzellen-Element oder
Objekt anlegen und hier als Parameter schon gleich die Zelle 3
übergeben.
Um dann schon gleich dieses Element und die Verknüpfung zu haben.
Und als letztes können wir dann die erste Zelle anlegen.
Auch wieder hier dargestellt.
Da würden wir bei dem Konstruktor dann als Parameter die zweite
Listenzelle übergeben, um dann dieses Objekt zu erstellen, gleich
schon mit der Referenz auf die zweite Listenzelle.
Also in diesem Beispiel würde man die Liste so von hinten aufbauen, um
dann gleich die Verknüpfung auch zu haben.
Das wäre jetzt eine Variante, wenn man nachher auch noch die
Referenzen auf die einzelnen Zellen braucht im weiteren Programmcode.
Wenn man das nicht braucht, kann man das auch kürzer schreiben und
einfach sagen Ich habe eine Listenzelle C.
Das soll eine neue Listenzelle sein, die P enthält und eine Referenz
auf eine neue Listenzelle, die als Inhalt Q enthält und eine Referenz
auf eine neue Listenzelle, die als Inhalt R enthält und als Referenz
Null.
Klammer zu, Klammer zu, Klammer zu.
Also ein Satz mit recht viel Nebensätzen sozusagen, kann man das hier
lesen.
Da würde man also jetzt quasi außen P anlegen, innen Q, ganz in R, was
ja dann in der Auswertung zu der gleichen Reihenfolge wie hier oben
führt, dass Java intern erst das R anlegt, dann das Q, damit den
Konstruktor von Q aufruft und damit den Konstruktor von P dann
aufruft.
Also von innen nach außen gesehen bei solchen geklammerten Ausdrücken.
Genau, wenn ich diese erste Referenz hier habe, dass die ersten
Listenzelle, reicht mir das auch, um mit der Liste zu arbeiten?
Denn wie gerade gesagt, habe ich dann ja mit dieser Referenz auch
Zugriff auf die gesamte Liste, indem ich eben über das Next Attribut,
also über diese Verkettung hier drüber gehen kann.
Genau, das ist auch schon der Aufbau von einer solchen Liste.
Wir hatten ja schon gesehen, Datentypen heißen auch nicht nur oder
bedeutet nicht nur was, was sind da für Daten drin?
Und hier geht es ja gerade um einen abstrakten Datentyp, um einen
Datentyp, sondern auch, welche Operationen sind damit verknüpft?
Das werden wir uns jetzt als nächstes anschauen.
Was sind so typische Operationen, die ich auf Listen durchführen
möchte?
Hier erstmal der Überblick darüber.
Ich möchte typischerweise Listen-Elemente einfügen können in eine
solche Liste.
Da gibt es verschiedene Möglichkeiten.
Insbesondere könnte ich die am Anfang der Liste einfügen können oder
am Ende der Liste einfügen können.
Ich könnte sie auch in der Mitte einfügen wollen, aber das haben wir
jetzt hier nochmal nicht drauf.
Ich könnte Listen-Elemente wieder aus der Liste entfernen wollen, also
löschen wollen.
Und was typisch ist, was ich machen möchte, ist, dass ich nach
Elementen in der Liste suchen möchte.
Und das, dafür könnte man sich die folgenden Methoden hier vorstellen,
dass man sagt, für diese Listen-Klasse möchten wir eine Methode At
First haben, um ein Element vorne anzufügen.
At Last, um ein Element hinten anzufügen.
Remove, um ein Element zu entfernen.
Und Contains, um zu prüfen, ob ein Element enthalten ist.
Also, da würde man auch ein Element als Parameter übergeben und würde
True oder False zurückhaben möchten, je nachdem, ob dieses Element
auch enthalten ist.
Genau, und durch diese verschiedenen Operationen gehen wir dann im
Folgenden mal durch mit ein bisschen Animationen, um zu sehen, was
passiert da?
Also, erstmal, wie kann ich das machen?
Diese Methoden hier umsetzen und was passiert dann auch mit der Liste
im Speicher?
Also, zunächst schauen wir uns die Operation At First an.
Das ist vielleicht auch die einfachste.
Wenn wir vorher eine Liste haben, die wie so aussieht, ich habe ein
Zeiger Head auf das erste Listen-Element innerhalb meiner Listen
-Klasse.
Ich habe ein Element und zwei Listenzellen da schon drin.
Eines enthält Q und eines enthält R.
Dann möchte ich nach dem Aufruf von At First mit dem Parameter P dann
eine solche Liste haben.
Ich möchte dann, dass das Head-Element nicht mehr auf Q, sondern jetzt
auf P zeigt und ich möchte, dass P dann auf Q zeigt.
Also, vorne angefügt ist dann die Liste.
Das Head-Element, gehe ich nochmal gerade zurück.
Das habe ich gerade, glaube ich, nicht erwähnt.
Genau, wenn ich jetzt so eine Liste insgesamt definiere, würde ich
jetzt in der äußeren Klasse, die Liste heißt, ein Attribut Head haben
wollen, was mir eben immer auf das erste Listen-Element zeigt und das
erste zeigt dann auf das zweite und so weiter, sodass, wie ich ja eben
aber auch schon gesagt hatte, das Listen-Element selber nur ein
Attribut hat, nämlich Head.
Das ist eben durch dieses Element hier in meinen Grafiken dargestellt.
Also, das ist die ganze Listen-Klasse sozusagen.
Genau.
Wenn ich also einfüge, möchte ich das P vorne haben und eine
Implementierung, wie ich das machen kann, sieht aus, wie hier gezeigt.
Ganz kurz, ich könnte einfach sagen, in der Methode addFirst mit
Parameter Vector2Dp habe ich eine neue Listenzelle, die nenne ich
jetzt erstmal newHead und erzeuge ein neues Objekt, Listenzelle, das
auf P dann zeigt, also erzeuge erstmal dieses Objekt hier als ersten
Schritt und setze dann die Referenz von Head, die vorher auf Q gezeigt
hat, jetzt auf P. Dazu auch nochmal eine Animation, die das gleiche
sagt.
Also, als erstes erzeuge ich mit dieser ersten Zeile ein neues
Listenzellen -Element, gebe auch gleich den bisherigen Head als
Parameter mit, sodass ich auch gleich diese Verkettung bekomme und in
der nächsten Zeile verschiebe ich dann sozusagen diese Head-Referenz.
Genau.
Das war einfach, könnte man sagen.
Das nächste, was wir machen wollen, ist hinten etwas anzufügen und da
wir ja nur die Referenz auf den Head vorne haben, ist das ein
bisschen, ein bisschen, nicht viel komplizierter.
Da wäre das Beispiel so, wenn ich vorher so eine Liste mit den
Elementen Q und R da drin habe, möchte ich danach, nach dem Aufruf von
addLast mit dem Parameter P eine solche Liste haben, wo das P hier als
letztes Element eingefügt wurde.
Und wie kann ich das machen?
Hier muss ich immer erst mal in meiner Methode, die das umsetzt, zum
Listenende gehen, also immer weiter iterieren und dann, wenn ich das
Listenende erreicht habe, diese Referenz des bisherigen letzten
Elements auf das neue setzen.
Auch dafür nochmal eine Animation.
Also als erstes fange ich an zu iterieren bei dem bisherigen Head.
Das heißt, ich erzeuge mir eine lokale Variable ListZellC, die auch
auf dem Head zeigt, hier.
Dann prüfe ich, ob cNext Null ist oder nicht.
Also, ob ich schon am Listenende angekommen bin.
Wenn es nicht Null ist, wie jetzt hier in diesem Fall, das hier ist ja
von C aus gesehen, cNext ist dieser Wert.
Dann gehe ich weiter, setze also c auf cNext.
Das heißt, an der Stelle oder nach der Ausführung dieser Anweisung
zeigt die Variable c jetzt auf das zweite Listen-Element.
Dann prüfe ich wieder die Bedingung.
In diesem Fall jetzt ist cNext Null, denn cNext ist ja dieser Wert.
Das heißt, ich gehe hier unten hin und kann jetzt eine neue
Listenzelle erst mal erzeugen.
Und, ach, was fehlt, ist die Verkettung, sehe ich gerade.
So müsste jetzt natürlich noch, das muss ich mir mal aufschreiben, im
Prinzip müssen Sie sich diesen Fall hier erst mal wegdenken.
Was ich jetzt erzeugt habe, ist erst mal diese neue Listenzelle.
Ich müsste dann noch sagen, nee, stimmt ja gar nicht, steht ja hier
vorne, c.Next, was ja auf dieses Objekt zeigt, wird auf den Wert
dieses neuen Objekts gesetzt.
Also, hier vorne erzeuge ich erst mal dieses neue Objekt und durch
diese Zuweisung hier erzeuge ich dann diese Verkettung.
Genau, wenn ich die Methode dann beende, wäre dieser c, diese lokale
Variable c, dann eben nicht mehr da.
Allerdings funktionierte das jetzt für diesen Fall ganz gut.
Sie können sich gerade nochmal selber überlegen, was passiert denn da
jetzt wohl mit dieser Methode, wenn meine Liste leer war.
Es ist ja nicht gesagt, dass eine Liste von Anfang an immer schon
Elemente enthält.
Ja, dann funktioniert das hier nämlich nicht so gut.
Gucken wir mal weiter.
Wenn die Liste, also das ist etwas, was ich bei der Implementierung
solcher Datentypen oft habe, dass ich gucken muss, was sind denn die
möglichen Fälle, die hier überhaupt auftreten können.
Und ein Fall, der hier bei einem Aufruf dieser Methode auftreten kann,
ist eben, dass die Liste sowieso von Anfang an schon leer war.
Und dann funktioniert es nämlich nicht, direkt hier unten mit c,Next
zu vergleichen.
Das würde direkt schon eine Ausnahme, eine sogenannte Null-Pointer
-Exception ergeben, sondern ich muss ja erst mal prüfen, ob ich mein
neues Listen-Element schon direkt da, wo mein Head-Zeiger hin zeigt,
also ins Leere, wenn es noch Null ist, direkt da schon einfügen soll.
Das heißt, eine richtige Implementierung hat dann auch diesen Teil
hier vorne, prüft erst mal, ob die Liste leer ist.
Sie ist leer, wenn List.head noch den Wert Null hat.
Wenn das der Fall ist, füge ich mein neues Listen-Zellen-Element
direkt unter head ein und habe danach eine Liste mit einem Element und
kann dann auch direkt die Methode beenden.
Wenn das nicht der Fall ist, gehe ich eben weiter und führe das aus,
was wir eben durchgespielt haben.
Gut, soviel zum Hinzufügen.
An der letzten Stelle kommen wir zum Löschen von Elementen, was noch
ein bisschen komplizierter ist.
Genau, wenn ich was löschen möchte, hätte ich vielleicht vorher so
eine dreielementige Liste und würde dann remove-r mit Parameter r
aufrufen wollen, was dann heißt, dieses Element hier in der Mitte soll
gelöscht werden.
Das, hier muss man jetzt erst mal klären, was heißt das überhaupt?
r löschen.
r ist ja jetzt hier sowohl der Parameter als auch das, was schon in
der Liste drinsteckt.
Also müssen wir uns erst mal überlegen, was heißt denn jetzt hier
Gleichheit zum Beispiel.
Also zu klären ist erst mal, was soll passieren, wenn r mehrfach in
der Liste vorkommt?
Soll ich dann nur das erste Element löschen oder mehrere?
Und weiter ist zu klären, was heißt denn hier jetzt eigentlich r kommt
in der Liste vor?
Wann ist dieser Parameter r gleich einem Listenelement?
Hier gibt es eigentlich zwei Möglichkeiten in Java, die wir ja auch
schon mal besprochen haben.
Entweder man sagt gleich im Sinne von gleicher Objektreferenz, also
wirklich die gleiche Objektidentität meinend oder einfach nur gleich
im Sinne von der Attribute, also der Werte der Attribute.
Das wäre ja das gleich, wie die Equals-Methode das auch überprüft.
Klären wir also hier noch ein bisschen mehr, was wir meinen.
Spezifizieren etwas genauer.
Wir nehmen jetzt mal an, wir wollen eine Remove-Methode
implementieren, die aus der Liste sämtliche Listenelemente, die
passen, löscht.
Und passen soll heißen, dass der Inhalt der Listenzelle dieselbe
Objektreferenz hat, wie r, also auf das gleiche Objekt zeigt.
Wir gucken nicht nach Gleichheit der Attribute.
Okay, und dann könnte man sich diese folgende Implementierung erstmal
vorstellen.
Also, so als ersten Versuch, sage ich gleich schon mal.
Und da gucken wir jetzt mal auch an der Animation an, was da genau
passiert.
Also, wir prüfen auch erstmal, habe ich eine leere Liste?
Wenn ja, ist nichts zu tun.
Wenn nein, komme ich hier unten an und sage wieder, ich will so einen
Zeiger C haben, der im Moment erstmal auf den Kopf der Liste zeigt.
Also so.
Und prüfe dann immer, wenn dieser Zeiger, also das Listenelement, auf
dem dieser Zeiger zeigt, die Referenz 0 hat.
Dann bin ich fertig.
Wenn nicht, wenn es nicht 0 ist, dann gehe ich weiter durch meine
Liste.
Dann prüfe ich, ob c.next.content den gesuchten Wert r enthält.
Das heißt, ich überprüfe c.next.content, sozusagen komme ich hier an,
ob das gleich r ist.
Wenn ja, habe ich mein r gefunden und kann es entfernen.
In dem Fall ist das tatsächlich auch gleich der Fall, denn c.next ist
eben diese Listenzelle und die enthält r.
Dann entferne ich das und Entfernen funktioniert so, dass ich einfach
die Verkettung umbiege.
Das heißt, ich würde jetzt c.next auf den Wert c.next.next setzen.
Das heißt, ich referenziere dasselbe Objekt, was auch hier hinten
referenziert wird.
Und biege sozusagen diese Verkettung um.
Und würde dann hier in dieser Implementierung weitergehen und sagen,
okay, bin ich jetzt an dieser Stelle fertig und setze c auf c.next.
Also c läuft weiter durch meine Liste durch.
Wundern Sie sich vielleicht und sagen, das sieht jetzt aber nicht aus
wie eine Liste.
Das ist in Java aber schon alles, was ich tun muss.
Irgendwann würde dann der sogenannte Garbage Collector vorbeikommen.
Ich hatte das in der vorherigen Vorlesung schon mal erläutert.
Und dieses r, was jetzt nicht mehr zugegriffen werden kann, löschen.
Also sofern es keine Referenzen mehr auf diese Listenzelle r gibt,
würde dieser Garbage Collector dann diese Listenzelle irgendwann mal
löschen.
Habe ich da noch eine Animation für?
Ja, ja, genau.
Und dann hätte ich dann tatsächlich meine Liste, wie ich sie haben
will.
Genau, auch hier wieder können wir uns fragen, was ist denn mit
irgendwelchen Randfällen?
Funktioniert das immer so, wie wir uns das gedacht haben?
Und wie gesagt, typische Randfälle sind, was passiert denn, wenn ich
das erste Listen-Element löschen möchte oder das letzte?
Oder wenn ich eine leere Liste habe, aber das hatten wir ja hier schon
abgedeckt.
Tatsächlich, wenn wir uns überlegen, was passiert, wenn wir das erste
Listen -Element löschen wollen, dann funktioniert das jetzt so noch
nicht.
Das war ein bisschen zu einfach gedacht.
Denn, ich blende das nochmal wieder aus, dass Sie es besser sehen
können.
Hier habe ich ja angefangen, C erstmal auf den Wert this.head zu
setzen.
Und dann gleich angefangen, mit C.next zu vergleichen.
Also ich habe gar nicht überprüft, ob das erste Listen-Element
vielleicht schon mein gesuchtes R enthält.
Oder beim hinteren Listen-Element ähnlich, bin ich zu schnell nach
vorne gesprungen.
Das heißt, so einfach geht es dann nun nicht, das löschen.
Wir müssen es ein bisschen komplizierter machen, wie jetzt hier
gezeigt.
Nämlich erstmal prüfen, will ich dann direkt das Head-Element, das
erste Element löschen.
Da muss ich erst überprüfen, ist das nicht 0, also ist meine Liste
leer.
Kann dann überprüfen, ob das Head-Element schon den gesuchten Content
hat.
Wenn ja, setze ich die Referenz sowohl vom Head, als auch von meiner
Zeigervariable, sozusagen C, auf das nächste Element.
Muss dann aber noch weiter prüfen, das kann ja sein, dass ich das
nächste auch gleich noch löschen will.
Also das heißt, ich iteriere hier so lange, bis der Kopf meiner Liste,
die ich sukzessive entferne, nicht mehr das gesuchte R enthält.
Dann prüfe ich nochmal, ob die Liste dann vielleicht leer ist, so wie
eben.
Und dann komme ich in den Code, den wir eben ausgeführt haben, so
ähnlich, und iteriere eben durch die Liste und gucke, ob es noch
weitere Elemente mit dem Inhalt R gibt.
Was ich dann aber damit für das letzte Element auch noch passt, auch
noch machen muss, ist hier unten aufpassen.
Eben hatten wir gesehen, da standen quasi beide Zeilen hintereinander,
ohne Else.
Also C next ist gleich C next next und dann nochmal C gleich C next.
Das hat dazu geführt, in der anderen Implementierung, dass man zu
schnell weiterschaltet und dann auch ein letztes Element nicht so gut
löschen kann.
Hier haben wir jetzt einen zusätzlichen Else-Zweig, sodass dann auch
zwei hintereinander liegende Objekte nicht übersprungen werden.
Genau, soweit zum Remove, haben wir noch eine Operation übrig, nämlich
dieses Contains, also die Suche nach Elementen in einer Liste.
Hier wieder ein kleines Beispiel, eine kleine Liste mit den Elementen
Q und P. Und wenn wir jetzt in Java so eine Liste, wie hier oben
gezeigt, erzeugt haben, möchten wir, dass diese Liste, wenn ich
Contains aufrufe, mit einem R, was nicht in der Liste enthalten ist,
den Wert false zurückliefert.
Also Contains heißt, ist R enthalten in meiner Liste und wenn das
Listenelement oder wenn es eine Listenzelle gibt, die als Inhalt P
hat, dann möchte ich den Wert true zurückgeben.
Also hier wieder die gleiche Bedeutung von Gleichheit.
Es geht auch hier jetzt wieder um die Gleichheit der Referenzen, also
wirklich gleiche Objektidentität.
Das könnte ich, wie hier gezeigt, implementieren.
Da gehen wir jetzt mal kurz drüber.
Sie haben jetzt ja schon einige Operationen gesehen.
Genau.
Ich starte hier, Parameter P wird übergeben und ich iteriere dann
wieder über meine Liste, diesmal mit einer Vorschleife, damit Sie das
auch mal gesehen haben.
Ich fange an, diese Vorschleife zu initialisieren, indem ich sage,
eine neue Listenzelle C, sozusagen als mein Zeiger, der durchgeht,
wird initialisiert auf den Wert von head, also auf das erste
Listenelement.
Dann prüfe ich in jedem Schritt, dann ist die Bedingung für meine
Iteration, für meine Schleife, dass C selber nicht null ist und meine
Schrittvariable ist, dass ich C auf C next setze.
Das heißt, hiermit würde ich erstmal anfangen mit einem Zeiger, der
direkt hier auf das erste Element zeigt und kann dann innerhalb der
Schleife überprüfen, ist C Punkt Content denn schon mein gesuchtes P?
Wenn ja, liefere ich schon wahr zurück.
Ich muss gar nicht mehr gucken, ob die restliche Liste auch noch P
enthält.
Interessiert mich nicht.
Wenn es nicht der Fall ist, würde ich die Schleife ja nochmal
durchführen, immer weiter, bis ich, wenn ich kein Element finde, was
meinem P entspricht, dann am Ende false zurückgebe.
Genau.
Soviel zu den verschiedenen Operationen, die ich auf Listen habe und
eben wie die funktionieren.
Ich hatte gerade schon das Thema abstrakte Datentypen kurz
angesprochen.
Wir haben jetzt die Operationen von so einer Liste gesehen und ich
muss mal eben hier was rüberschieben, Moment.
Und sie hatten in der letzten Vorlesung von Ralf Reusner auch schon
dieses Prinzip der Datenkapselung oder diese Idee der Datenkapselung
kennengelernt und wie man das umsetzen kann mit den verschiedenen
Modifizierern, Public, Private und so weiter.
Und die Motivation für Datenkapselung war ja, dass man möglichst lose
gekoppelte Programmteile haben möchte, also zum Beispiel lose
gekoppelte Klassen haben möchte, sodass die Programmteile nicht von
internen Implementierungsdetails von anderen Programmteilen abhängen.
Was insbesondere heißt, wenn ich etwas ändern möchte an meinem
Programm, ist die Wahrscheinlichkeit größer, dass ich nur meine
einzelne Klasse ändern muss.
Und wenn andere Klassen nicht von dem internen Detail abhängen, muss
ich die anderen Klassen hoffentlich nicht ändern.
Die Änderungen wirken sich dann hoffentlich nicht auf andere
Programmteile aus.
Und dieses Prinzip der Datenkapselung nennt man auch Geheimnisprinzip.
Geheimnis deswegen, weil man interne Informationen seiner Klasse
verstecken möchte, geheim halten möchte und nicht nach außen geben
möchte.
Bei unserer Liste heißt das, dass wenn wir eine Liste nur als solche
verwenden wollen, uns nicht interessiert, wie der interne Aufbau der
Liste eigentlich ist.
Um das zu erreichen, möchten wir eine abstrakte Sicht auf diese Liste
erstellen können, welche diese Implementierungsdetails, die ich gerade
angesprochen hatte, komplett vor dem Nutzer einer solchen Liste
verbirgt.
Und das kann ich in Java umsetzen, indem ich den Zugriff auf den
Inhalt einer Liste nur über eine definierte Schnittstelle verwende.
Das haben wir in der Implementierung gerade auch schon gemacht.
Wir haben gesagt, die internen Details der Liste sind mit dem
Schlüsselwort Private markiert.
Das heißt, darauf, auf die Attribute zum Beispiel, kann ein Nutzer
einer Liste in einer anderen Klasse gar nicht zugreifen.
Und eine solche Schnittstelle, eine definierte Schnittstelle, wie ich
bestimmen kann, wie ich auf so einen Datentyp zugreifen kann, nennt
man auch abstrakter Datentyp oder abgekürzt ADT.
So ein abstrakter Datentyp ist ein bisschen ähnlich wie ein Datentyp,
nämlich ich habe eine Menge von Typen jeweils mit Wertebereich und ich
habe die Signaturen, also die Funktionen mit Rückgabewerten und den
Parametertypen, wie wir das auch bei den Datentypen schon hatten.
Ich habe zusätzlich noch oder kann zusätzlich noch eine Menge von
Aktionen haben, sogenannten Einschränkungen, was dieser abstrakte
Datentyp machen muss.
Das ist anders als bei dem normalen Datentyp.
Und ich habe auch ein bisschen weniger als beim normalen Datentyp.
Ich habe nämlich noch keine Implementierung dabei.
Also normaler Datentyp heißt nicht abstrakt, weil er eben auch
Implementierung für diese Operationen hat.
Und abstrakter Datentyp bedeutet, ich habe nur die Sammlung der
Methoden sozusagen, die mein Datentyp anbieten soll.
Vielleicht noch ein paar Regeln da drauf, aber noch keine
Implementierung.
Und das bildet eben die Schnittstelle, wie ich mit diesen oder mit
Datentypen, die diesem abstrakten Datentyp entsprechen, umgehen kann.
Hier schauen wir uns an, wie so eine Liste als abstrakter Datentyp
eben in Java realisiert sein könnte.
Ich könnte also eine Klasse Vector2D-Liste definieren, die jetzt hier
nichts über die Attribute aussagt.
Die würde ich dann zu einem späteren Schritt hinzufügen.
Stichwort Vererbung nächste Woche oder Interface ist auch noch nach
Weihnachten.
Aber die Idee wäre erstmal, ich definiere dann eine Klasse in
abstrakter Art und Weise, die noch nichts darüber sagt, was die
Attribute denn intern von dieser Klasse sind, um so eine Liste
umzusetzen, sondern nur auflistet, was sind denn jetzt die möglichen
Methoden einer solchen Liste und wie können Nutzer einer solchen Liste
damit arbeiten.
Die Methoden haben wir ja gerade schon gesehen.
At First, At Last, Remove Contains wären da so typische.
Da würde man wahrscheinlich auch noch solche Methoden wie Size für die
Größe und Boolean ist Empty haben wollen, ob eine Liste leer ist.
Ach genau, Axiome haben wir jetzt hier keine in diesem Beispiel.
Man könnte bei einer Liste zum Beispiel als Einschränkung formulieren,
dass eine neu erzeugte Liste, wenn ich diesen Konstruktor aufrufe,
immer erstmal leer sein muss.
Das wäre so ein typisches Axiom, was für so einen abstrakten Datentyp
Liste sinnvoll wäre, was wir in Java jetzt aber nicht so einfach
hinschreiben können.
Gut.
Nun haben wir Liste kennengelernt.
Die Liste als abstrakten Datentyp hier gesehen, also die
Schnittstelle, wie hier gezeigt, wie man so eine Liste verwendet,
gesehen.
Was noch fehlt für die sinnvolle Verwendung von Listen, sind die
sogenannten Iteratoren.
Und zwar ist es bis jetzt mit der Listen-Schnittstelle, die wir gerade
gesehen haben, noch ein bisschen schwierig, mit solchen Listen auch zu
arbeiten.
Also insbesondere, wenn man dieses typische Gebrauchsmuster machen
möchte, dass man in einer Schleife über die Inhalte so einer Liste
drüber geht, ist das mit unserer jetzigen Listen-Implementierung noch
ein bisschen schwierig, weil man ja nur at first, at last hat.
Und so ein typisches Gebrauchsmuster ist, wie gesagt, ich möchte über
eine Liste drüber gehen und möchte für jedes Element irgendwas tun.
Bei Arrays hatten wir sowas auch gesehen, oder für Arrays können wir
uns hier ein Beispiel anschauen, da konnte ich ja so eine Vorschleife
formulieren und sagen, ich mache mir einen Index i, den setze ich am
Anfang auf 0 und gehe dann, indem ich den Index hochzähle, Schritt für
Schritt durch ein Array durch und mache irgendwas für jedes Array
-Element.
Für Listen möchte ich sowas gerne auch in Kurzschreibweise sozusagen
haben und dieses Prinzip über Dinge, über die einzelnen Elemente einer
Kollektion rübergehen zu können, lässt sich verallgemeinern zu dem
Konzept Iterator.
Und der Name sagt es ja schon, es ist etwas, um über etwas drüber zu
iterieren, um für jedes Element Dinge wiederholen zu können.
Die Definition von einem Iterator ist, dass ein Iterator einen Zeiger
bezeichnet, mit dem man über die Elemente einer Kollektion wandern
kann, also sozusagen iterieren kann.
Schauen wir uns an, wie das in Java aussehen würde für unsere Klasse
Vector2D -Liste.
Erstmal erweitern wir diese Schnittstelle, also erweitern den
abstrakten Datentyp Vector2D-Liste zu den Operationen, die wir eben
schon gesehen haben, die jetzt hier sozusagen ausgeblendet sind,
kommen dann noch zwei Dinge hinzu und zwar zum einen eine innere
Klasse, das hatten wir auch noch gar nicht gesehen, geht aber auch,
namens Iterator.
Also ich kann in Java auch eine Klasse in die andere hineinschachteln,
so wie hier gezeigt.
Und diese Iterator-Klasse hat zwei Methoden, einmal HasNext, um zu
prüfen, ob der Zeiger am Ende angekommen ist einer Liste und eine
Methode Next, um das nächste Listen-Element zurückzugeben.
Das wäre also so eine innere Klasse Iterator in der Liste und dann
bräuchte die Liste jetzt noch eine Methode, um auch eine Instanz von
diesem Iterator zurückzugeben.
Und diese Methode heißt meistens auch nur Iterator.
Genau, hier steht es nochmal in rot notiert, das ist als geschachtelte
Klasse hier realisiert, dazu später dann nochmal mehr.
Nehmen Sie das einfach mal so hin.
Verwenden kann ich sowas dann, wie hier gezeigt.
Ich könnte sagen, ich will eine neue Liste haben, Liste L und kann
dann mir für dieses Objekt L den Iterator geben lassen, indem ich L
.Iterator aufrufe und kann dann in einer While-Schleife immer
abfragen, hat mein Iterator, also zeigt der Iterator auf ein Element
der Liste, hinter dem noch was kommt, oder ist es das letzte, werde es
umgedrehte.
Wenn ja in diesem Fall, dann hole ich mir das nächste Element aus der
Liste mit Iterator.next, es liefert ein Vektor2D zurück und kann dann
halt irgendwelche Arbeit mit diesem Vektor2D machen.
Das heißt, diese Schleife hier ist dann das Äquivalent zu der
Vorschleife auf dem Array, was wir eben gesehen haben.
Genau.
Damit kann man jetzt also so eine Liste durchlaufen, ohne zu wissen,
wie die Liste intern iteriert ist.
Dieses List-Cell-Element kommt hier dann von außen sozusagen gar nicht
mehr vor.
Schauen wir uns jetzt mal an, wie dieses Iterator, diese Iterator
-Klasse selber implementiert ist.
Hier sind ja jetzt gerade nur die Methoden aufgeführt.
Wenn wir das sozusagen ein bisschen aufklappen, hätten wir hier sowas.
In unserer Listen-Klasse die innere Klasse Iterator mit den Methoden,
die wir eben gesehen haben, nämlich hasNext und next und intern mit
einem Attribut Cursor, was so ähnlich wie das Head-Element unserer
Liste selber eben ein Zeiger sozusagen auf ein Listen-Element ist.
Und außerdem noch was Privates, eine Konstruktor-Methode, mit der die
umgebende Liste so ein Iterator-Objekt erzeugen kann.
Die ist hier auf privat gesetzt.
Das heißt, dieser Konstruktor kann nur aus dieser Liste selber heraus
aufgerufen werden und nicht von ganz anderen Klassen, nicht von außen.
Also nur über diese Methode hier unten.
Genau.
Was kann ich jetzt hier also machen?
Bei dem Konstruktor für so einen Iterator setze ich, also erzeuge ich
dieses neue Objekt, Iterator-Objekt und setze den Cursor erstmal auf
den Start meiner Liste, den ich hier als Parameter übergeben habe.
Dann gibt es die Methode hasNext, die einfach überprüft, also an der
Stelle ein bisschen andersrum gedacht, ist der Cursor im Moment schon
übers Ende der Liste hinweggelaufen, also auf dem Wert 0 oder habe ich
hier noch einen Wert.
Also das heißt, wenn der Cursor 0 ist, dann gibt es kein nächstes
Element.
Wenn der Cursor noch auf ein Listenzellenelement zeigt, dann ist das
das nächste Element.
Dann gibt es eben noch diese Operation Next.
Da würde ich dann, oder in der Implementierung wird, das Inhaltsfeld
einer Listenzelle sozusagen ausgelesen und in der lokalen Variable
Vector2D gespeichert.
Dann setze ich den Cursor 1 weiter und kann dann dieses, den Current
Content, das Vector2D-Element, was da lag, wo der Cursor vorher
hingezeigt hat, zurückliefern.
Genau, und so funktioniert auch schon ein Iterator auf Listen.
Wie man es verwendet, hatten wir auf der vorherigen Folie ja schon
gesehen.
Jetzt kann man sagen, wenn man objektorientierte Prinzipien sich
anschaut, kann man sagen, das ist in Java eigentlich nicht so schön
gelöst, dieser Iterator.
Und zwar gibt es ein Prinzip in der Objektorientierung, die sogenannte
Command Query Separation, also die Trennung zwischen Methoden, die den
Zustand der Methode einfach nur zurückliefern und darüber etwas
aussagen und Methoden, die den Zustand eines Objektes ändern.
Also dieses Prinzip Command Query Separation sagt, dass eine Methode
nur entweder den, hier steht ja Zustand einer Komponente, es kann aber
eben auch Zustand eines Objekts, zurückliefern soll und etwas darüber,
also darüber informieren soll sozusagen, oder den Zustand eines
Objekts verändern soll, aber nicht beides gleichzeitig, um eben keine
unerwünschten und unerwarteten Nebeneffekte haben sollen.
Und ein Grund dafür ist, dass, wenn man das hier berücksichtigt, dann
sind nacheinander ausgeführte Aufrufe auf dieselbe Methode mit
denselben Parametern, liefern dann auch immer dasselbe Ergebnis.
Wenn ich also mehrmals hintereinander eine Abfrage mache über den
Zustand meiner Objekte, bekomme ich immer wieder die gleiche Antwort.
Und wenn ich den Zustand einer Komponente verändere, würde ich nicht
die gleiche Antwort bekommen.
Wenn das aber eine Methode ist, die Void ist, bekomme ich doch immer
das gleiche, nämlich Void zurück.
Nachteil, wenn man das so sauber aufteilt, ist, dass man mehr
Methodenaufrufe braucht.
Und deswegen, oder das ist wahrscheinlich auch der Grund, warum das in
manchen Sprachen immer nicht so sauber getrennt ist, dieses Command
and Query.
Und ein typisches und eine bekannte...
Violation...
Eine bekannte Stelle, wo das eben nicht erfüllt ist, ist das Iterator
-Muster in sowohl Java, wie wir es gerade gesehen haben, und auch in C
Sharp, um ein Beispiel für eine andere Programmiersprache zu bringen.
Wir hatten das in Java ja gerade schon gesehen.
Man würde so einen Iterator so verwenden, dass man sagt, while i
.hasNext setze ich, iteriere ich und setze immer meinen Wert, den ich
gerade haben will, auf i.next.
Hier ist hasNext unkritisch, das ist eine Query, die sagt mir einfach
nur, gibt es ein nächstes Element, aber diese Methode next ist sowohl
Query als auch Command, denn ich bekomme einen Wert eines Objektes
zurück, also ich habe einen Rückgabewert hier, und gleichzeitig
passiert aber auch was mit dem Zustand meiner Liste, und zwar wird
auch der interne Zeiger des Iterators einweiter gesetzt, also es wird
sowohl Command als auch Query durchgeführt.
In C Sharp ist es ähnlich, aber anders, denn in C Sharp gibt es die
Methode moveNext, die sowohl abfragt, ob es ein nächstes Element gibt,
aber dann den Cursor auch gleich ein zweiter setzt, also an der Stelle
Query und Command gleichzeitig ist, und dann die Methode current bei
so einem Iterator, die halt einfach nur den aktuellen Wert, auf den
gezeigt wird, zurückliefert.
Also da ist es ein bisschen anders gelöst, das moveNext ist Query und
Command, aber das gleiche Prinzip oder das gleiche Nichterfüllen
dieser Command Query Separation, nämlich eine der Methoden, ist sowohl
Query als auch Command.
Wenn man jetzt sagen, also wenn man jetzt eine Sprache entwickeln
wollen würde, wo diese Trennung ganz klar gemacht ist, oder auch
einfach nur eine Standardimplementierung für eine Liste und für einen
Iterator, könnte man das, oder müsste man das eigentlich, wie hier
gezeigt machen.
Man bräuchte eigentlich drei Methoden, in so einer neuen Java-Listen
-Standardimplementierung, indem man in einer While-Schleife erstmal
abfragt, ist der Iterator im Moment valide, das wäre eine reine Query.
Wenn ja, nehme ich mir den Wert des aktuellen Elements mit so einer
Methode wie eCurrent und dann trenne ich nochmal explizit diesen,
dieses, ich setze auch, gehe auf das nächste Listen-Element, also das
moveNext an der Stelle.
Und wenn ich das so in drei Methoden aufteile, was ein Iterator so
tut, hätte ich einmal isCurrent valid, eine Query, dann die Methode
current, auch eine Query und die Methode moveNext, die ein Command
ist, aber eben selber keinen Wert zurückliefert, also nicht Command
und Query gleichzeitig ist.
Genau, so viel zu dieser Command-Query-Separation, also man könnte
dieses Iterator-Prinzip, was dieses Prinzip angeht, in Java besser
umsetzen.
Genau, jetzt haben wir auch insgesamt so eine Listen-Implementierung
mal gesehen, also Sie sehen hier nochmal aufgeführt, die
Gesamtstruktur einer solchen Listen-Implementierung.
Wir haben einerseits hier in schwarz und in rot gezeigt, dass die
Schnittstelle, die öffentlich sichtbare Schnittstelle dieser Liste mit
dem Schlüsselwort public dann jeweils gekennzeichnet und hier oben,
das gelbe und das grüne, die geheimen, internen
Implementierungsdetails, nämlich dass ich intern auf ein erstes Listen
-Element zeige oder hier auf ein ersten Listen-Element zeige und
sowieso definiere, was diese Klasse Listen-Cell dann überhaupt ist und
macht, ist von außen eben auch nicht sichtbar.
Das Ganze, wie gesagt, kann man auch als abstrakten Datentyp ansehen,
wenn man sich diese Methoden hier nur als Schnittstelle betrachtet.
Wie könnte man sowas jetzt verwenden nochmal, um ein etwas größeres
Beispiel zu zeigen.
Wenn wir jetzt eine Liste mit drei Elementen erstmal anlegen wollen
und dann das, was wir gerade angelegt haben, wieder ausgeben wollen,
können wir das machen, wie hier dargestellt, also in einer Main
-Methode einer neuen Klasse Vector2D Listen-Test.
Diese Main-Methode könnte erstmal solche neuen Objekte vom Typ
Vector2D anlegen, wieder mal unsere P-, Q- und R-bezeichneten Objekte
mit irgendwelchen Werten für die Parameter.
Dann könnte diese Methode eine neue Liste anlegen, erstmal das Objekt
selber für die Liste und dann diese At-First-Methode benutzen, um die
einzelnen Elemente in die Liste hinzuzufügen.
Wenn ich das in dieser Reihenfolge aufrufe, At-First mit dem Parameter
R, At-First mit dem Parameter Q, At-First mit dem Parameter P, habe
ich eben nachher eine Liste, die P, Q, R, also wo zuerst P kommt, dann
Q, dann R.
Wenn ich diese Information, die ich gerade reingesteckt habe, in die
Liste dann auch wieder ausgeben will, kann ich mit einem Iterator über
diese Liste drüber iterieren, in einer While-Schleife zum Beispiel,
kann sagen, While der Iterator noch einen gültigen Wert hat, nehme ich
mir immer den aktuellen Content der aktuellen Listenzelle, gebe ihn
aus und mache dann eben in der nächsten Schleife eine Iteration weiter
und lasse mir den nächsten Wert geben, also gehe mit dem Cursor
Schritt für Schritt durch die Liste hindurch.
Genau.
So viel zu Listen.
Wir hatten die Arrays ja schon kennengelernt und da stellt sich jetzt
langsam auch mal die Frage, was ist denn der Unterschied oder warum
ist das eine besser, wozu braucht man überhaupt beide.
Die beiden haben Vorteile und Nachteile, wenn man sie gegeneinander
vergleicht, wie hier jetzt dargestellt.
Die Vorteile von Arrays sind, dass ich einfacher auf die Elemente
zugreifen kann.
Ich habe ja diesen Index.
Ich kann direkt sagen, ich will das sechste Element und muss nicht
erst lange durchiterieren.
Auch sind so Handhabung und Syntax relativ intuitiv, könnte man sagen,
mit dieser Index-Schreibweise, die kennt man eben auch schon aus der
Mathematik.
Und in Java ist das in der Sprache eben schon direkt eingebaut, solche
Arrays machen zu können.
Das ist also die Vorteile von Arrays gegenüber Listen, die da ein
bisschen komplizierter sind.
Die Arrays haben aber auch Nachteile und der größte Nachteil ist, dass
die Länge eines Arrays bei der Initialisierung schon gleich mit
angegeben werden muss.
Also man hat dann, man reserviert dann eine bestimmte Menge Speicher
und die bleibt auch so über die ganze Lebensdauer des Arrays.
Das heißt, wenn ich eine Situation habe, wo meine Datenmenge entweder
wächst oder schrumpft, kann ich das mit Arrays nur schwer machen.
Beziehungsweise, wenn ich dann irgendwelche Umstrukturierungen machen
möchte, also doch mehr Speicherplatz brauche, dann muss ich ein neues
Element, ein neues Array anlegen und dann meine Elemente umziehen.
Ähnlich ist es auch, wenn ich im Array zum Beispiel ein Element
löschen möchte und dann die anderen quasi wieder direkt anschließen
möchte an den vorherigen Teil so einer Kollektion, dann muss ich ein
Element löschen und dann alle anderen Elemente eins nach vorn kopieren
zum Beispiel.
Also auch so Umstrukturierung, einfügen, löschen sind schwierig.
Oft brauche ich diesen direkten Zugriff auf die inneren Elemente mit
Index gar nicht und wenn das eben der Fall ist, wenn ich ohnehin über
die Daten rüber iterieren will, dann kann ich besser eine Liste
verwenden.
Wir haben jetzt vorhin die einfach verketteten Listen kennengelernt,
wo also die Zeiger nur nach vorne zeigen.
Es gibt, oder erstmal was der Nachteil ist, der Nachteil davon ist,
man kann sie nur von vorne nach hinten durchlaufen, man kann nicht
rückwärts da durchgehen und man kann, wenn man oftmals auf das letzte
Element zugreifen muss, muss man da eben auch erst teuer sozusagen hin
iterieren.
Eine Lösung, wie man das ein bisschen flexibler gestalten kann, ist
sogenannte doppelt verkettete Listen zu verwenden.
Und bei doppelt verketteten Listen gibt es neben dieser
Vorwärtsverkettung, die wir jetzt schon kennen, auch eine
Rückwärtsverkettung, wie hier dargestellt.
Also das hier wäre jetzt erstmal so eine einfach verkettete Liste und
eine doppelt verkettete Liste hat auch noch Zeiger auf das vorherige
Listen -Element.
Also eigentlich ganz einfache Idee.
Das ist vorteilhaft, wie gesagt, ein bisschen flexibler, insbesondere,
wenn man sich dann anschaut, wie aufwendig es ist, ein Element am Ende
einzufügen, stellt man fest, dass das bei so einer doppelt verketteten
Liste sehr viel einfacher ist.
Das sollte ich vielleicht zuerst sagen.
Kenne ich meine Animation nicht.
Ich gehe erstmal zu dem einfacher ist.
Genau.
Wenn ich nämlich bei einer doppelt verketteten Liste am Ende etwas
einfügen will, kann ich das direkt machen, weil ich auch schon ein
Zeiger auf das letzte Listen-Element habe.
Bei einer einfach verketteten Liste ist es eben sehr aufwendig, hinten
etwas einzufügen, weil ich immer erst durch die ganze Liste
durchiterieren muss.
Und man sagt auch oder man schreibt auch hin zu dieser Frage der
Komplexität in der Informatik, dass die Komplexität einer einfach
verketteten Liste beim Einfügen am Ende O von N ist.
Das heißt, je mehr Elemente ich in der Liste drin habe, dann wächst
der Aufwand, etwas einzufügen, auch linear mit dieser Anzahl der
Elemente in meiner Liste.
Also je länger die Liste ist, desto länger dauert es, bis ich zu
diesem letzten Element hingelaufen bin.
Bei einer doppelten verketteten Liste ist dieser Aufwand konstant,
weil ich eben auch einen Zeiger auf das letzte Element habe und dann
eigentlich egal ist, wie lang die Liste vorher ist.
So viel aber zur Komplexität.
Ich komme doch nochmal zurück hier auf diese Animation.
Doppelt verkettete Liste heißt eben, ich habe den gewohnten Zeiger für
die Vorwärtsverkettung in einer Listenzelle, aber ich habe zusätzlich
in jeder Listenzelle noch ein Attribut, was auf das vorherige Listen
-Element zeigt.
Dann habe ich auch einen Zeiger, der auf das erste Element meiner
Liste, wir hatten es vorher Head genannt, zeigt und zusätzlich in
meiner Listenklassen-Implementierung dann noch ein Element, was auch
auf das letzte Element meiner Liste zeigt.
Genau.
So kann ich eben einfach, wie gerade erklärt, hinten auch was
einfügen.
Genau.
Eine Implementierung einer solchen doppelten verketteten Liste könnte
dann so aussehen.
Hier sind jetzt die grünen Elemente, die Dinge, die neu hinzukommen
gegenüber einer einfach verketteten Liste.
Also einfach ein weiteres Attribut previous, wo ich in einer
Listenzelle nicht nur das nächste Element referenziere, sondern auch
das vorherige.
Wenn ich so eine Listenzelle anlege, übergebe ich nicht nur das
nächste Element, sondern auch das vorherige.
Und wenn ich, genau, ich habe diese zwei Zeiger, sowohl auf das erste
als auch auf das letzte Element.
Und okay, wenn ich eine neue Liste anlege, dann setze ich beide
Attribute erstmal auf null.
Dann müsste man natürlich diese verschiedenen Methoden anders
implementieren.
At first bleibt eigentlich ziemlich gleich, aber wir schauen uns mal
an, wie man at last dann implementieren kann.
Da mussten wir in der alten Implementierung erstmal durchlaufen bis
zum Listenende und dann hinzufügen.
Und in so einer neuen Implementierung kann man jetzt eigentlich direkt
einfügen.
Man muss vorher natürlich noch wieder die Spezialfälle beachten und
erstmal schauen, handelt es sich gerade um eine sowieso schon leere
Liste?
Dann, also wenn first gleich null ist, habe ich eine leere Liste.
Dann füge ich das Element auch schon gleich vorne ein.
Und wenn nicht, füge ich das neue Element, was ich hier oben
zusammengebaut habe, direkt als last.next ein und muss dann noch
wieder den Zeiger, last Zeiger aktualisieren und den jetzt auf das neu
hinzugefügte Listenzellenelement zeigen lassen.
Also keine Schleife mehr notwendig.
Ich kann direkt das Element hinzufügen, muss eben nur prüfen, ob die
Liste leer ist oder nicht.
Ach, hier wieder die Animation dafür.
Ich erzeuge also eine neue Listenzelle hier in der ersten Zeile,
prüfe, ob meine Liste leer ist.
Das ist jetzt hier nicht der Fall.
Ersetze dann das bisherige letzte Element, verkette ich mit diesem
neuen Listenelement, nämlich so und muss dann noch meinen Zeiger
umbiegen.
Das last muss jetzt auf den letzten zeigen und nicht mehr auf den
vorletzten.
Genau, dann haben wir diese Operation erledigt.
Ein Beispiel für die Verwendung von Listen, einfach nochmal, um zu
motivieren, was man damit machen kann, wäre es, einen gerichteten
Graphen auch im Speicher ablegen zu wollen, also mit Graphen arbeiten
zu wollen in meinem Programm.
Ein Graph könnte so aussehen, ich habe verschiedene Knoten, ich habe
Kanten dazwischen, das kann ich abspeichern, für jeden Knoten kann ich
abspeichern, was denn die Liste der benachbarten Knoten ist.
Also für den Knoten 0 sind die benachbarten Knoten 1 und 3, ist jetzt
hier als Datenstruktur abgelegt.
Das kann ich in dieser Implementierung, die Sie sich dann ja auch im
Detail nochmal anschauen können, umsetzen, indem ich sage, ich habe
eine Klasse Knoten, die hat erstmal selber einen Content, also hier
die Zahlen 1, 2, 3 bis 5 und hat dann eine Liste von Nachfolgern in
dieser Adjacenzliste.
Diese Liste könnte eine doppeltverkettete oder einfachverkettete Liste
sein, ist egal, aber daraus kann ich dann eben insgesamt so eine
Graphen -Klasse zusammenbauen.
So als kurzes Beispiel dafür.
Ja, um dann diesen Teil mit den Listen zusammenzufassen, was haben wir
jetzt gesehen, was haben Sie jetzt gelernt über Listen?
Sie haben gesehen, dass Listen aus verketteten Listen-Elementen
bestehen und so ein rekursiver Datentyp sind, das heißt, Objekte
dieses Datentyps zeigen wieder auf gleichartige Datentype, also eine
Listenzelle zeigt wieder auf eine andere Listenzelle.
Sie haben gesehen, dass ein Hauptvorteil von Listen gegenüber Arrays
ist, dass ich die Länge der Liste dynamisch ändern kann und eben auch
Elemente vorne, hinten, in der Mitte flexibel einfügen kann.
Und wir haben uns die Implementierung in Java angeschaut, da habe ich
eben so eine Listenzelle, eine mögliche Implementierung in Java,
sollte ich noch dazu sagen.
Da habe ich eine Listenzelle, die einen Content und eine Verkettung
enthält.
Ich habe nach außen eine nach außen sichtbare Listenklasse, wie zum
Beispiel unsere Vector2D-Liste.
Die enthält nur eine Referenz auf diesen Listenstart, wenn es eine
einfachverkettete Liste ist, oder auf Start und Ende bei einer
doppeltverkettenden Liste.
Und diese Listenklasse außenrum stellt dann diese Methoden zur
Erstellung und Modifikation von Listen zur Verfügung, also At Last, At
First, Contains und so weiter.
Die Implementierung der Listenzellen würde man nach außen nicht
sichtbar machen wollen, deswegen hätten die diesen Modifikator
private, sodass ich diese ganze Listenklasse auch als abstrakten
Datentyp auffassen kann.
Eigentlich würde man da noch eine Interface verwenden, aber das kommt
dann später nochmal.
Und Iteratoren haben Sie kennengelernt als abstrakte Zeiger auf die
Listenelemente, um über eine Liste iterieren zu können.
Gut.
Soviel zu diesem Teil der Listen.
Ich wollte jetzt gerade sagen, wenn es Fragen dazu gibt, aber dann...
Vielleicht, wenn es eine brennende Frage zu dem Thema gibt.
Die Frage war, was spricht dagegen, den Lastzeiger auch bei einfach
verketteten Listen einzusetzen.
Also zum einen könnte man natürlich auch nur rückwärts für einfach
verkettete Liste machen, aber das meinten Sie wahrscheinlich nicht,
dass man sagt, man hat einen Lastzeiger und die Verkettung in die
andere Richtung.
Dann könnte man von hinten immer die Liste durch iterieren.
Ansonsten könnte man auch zusätzlich bei einer einfach verketteten
Liste einen Lastzeiger haben, aber mit dem könnte man nicht besonders
viel machen, außer auf das letzte Element zu greifen.
Also von daher kann man das machen, dass man sagt, ich kann zwar mit
dem Lastzeiger nirgends mehr hin iterieren, denn ich habe ja keine
Verknüpfung, aber ich könnte zumindest das letzte Element neu
hinzufügen, was vielleicht eine häufige Operation ist.
Also von daher könnte man auch zu einer einfach verketteten Liste
einen Lastzeiger hinzumachen, um diese wahrscheinlich recht häufig
auftretende Operation am Ende was hinzufügen, dann auch in O von 1
machen zu können.
Ja, kann man machen.
Das wäre so eine Optimierung dann je nach Situation.
Okay, aber wie gesagt, so viel dann zu den Listen.
Kommen wir zum nächsten Thema für heute, was noch in die Vorlesung
hineinpassen sollte, nämlich das Thema Rekursion.
Hier nochmal unser Überblick.
Wir haben jetzt also gerade dieses Element hier oder diese, Moment,
diesen Teil hier gefüllt, Listen, abstrakte Datentypen und kommen
jetzt doch nochmal zurück zu diesen Basisbausteinen hier, Bereich
Verhalten, nämlich das rekursive Aufrufen von Methoden selber.
Wir hatten gerade schon rekursiver Datentyp gehört.
Jetzt geht es um Rekursion im Verhalten in Form von Methoden, die sich
selbst aufrufen.
Die Lernziele dafür sind, dass Sie nach dem Hören dieser Vorlesung in
der Lage sind, rekursive Funktionen implementieren zu können und dabei
auch die dahinterliegende Motivation anwenden können, nämlich ein
Problem, was irgendwie groß ist, in kleinere Instanzen zu zerteilen,
im Kleinen zu lösen und dann die Lösung wieder zu einer großen Lösung
zusammenzubauen.
Darum geht es dabei nämlich.
Und dass Sie nach dieser Vorlesung in der Lage sind, zu beschreiben,
wie der sogenannte Aufrufstapel Callstack während der Abarbeitung von
Methoden eigentlich verwendet wird.
Die Motivation für Rekursion ist dieses Prinzip divide and conquer.
Ich glaube, es hat Cäsar erfunden ursprünglich mal, oder?
Kann das sein?
Er hat gesagt, Gallien aufteilen und dann Stück für Stück erobern.
Divide et impera, auf Lateinländern entsprechend, oder teile und
herrsche auf Deutsch.
In der Informatik bezeichnet das so ein Grundprinzip, dass man sagt,
wenn ich ein irgendwie großes Problem habe, versuche ich das in
mehrere gleichartige oder mehrere einfachere Teilprobleme zu
zerteilen.
Vielleicht sind diese Teilprobleme sogar auch gleichartig.
Dann die einzelnen Teilprobleme einzeln zu lösen und dann irgendwie
geeignet die Teillösung zu einer Gesamtlösung wieder zusammenführen,
um mir das Leben einfacher zu machen.
Und mein Beispiel dafür ist das sogenannte Merge Sort.
Das ist ein Sortierungsverfahren, was ich jetzt im Folgenden in einer
Animation mal darstellen möchte, wie das funktioniert.
Also das Problem ist, ich möchte eine Liste von Zahlen sortieren, wie
zum Beispiel diese hier.
Und das Merge Sort geht jetzt so vor, zu sagen, naja, das ist mir zu
schwer.
Ich teile das Problem erstmal auf in zwei Probleme.
Ich nehme mir zwei Listen, die ich sortieren muss.
Also bei Merge Sort ist es so, ich teile meine Liste immer in der
Hälfte einmal durch und habe dann zwei kleinere Probleme.
Jetzt muss ich nur noch vier Elemente sortieren.
Das ist mir immer noch zu groß, also teile ich das Problem nochmal
auf.
Das ist mir immer noch zu groß und zu kompliziert, also teile ich das
Problem nochmal auf.
Aha, jetzt habe ich plötzlich sortierte Listen.
Ganz viele.
Aber ich habe sortierte Listen jeweils mit einem Element drin.
Und wenn nur ein Element drin ist, ist es ja gleich schon sortiert.
Also habe ich das Problem jetzt aufgeteilt in kleine Probleme, die
sehr einfach sind.
Eine elementige Liste ist per Definition schon gleich sortiert.
Dann die nächste Frage, wie füge ich denn diese Teillösungen wieder
zusammen?
Hier schaue ich mir dann immer zwei Listen an im Merge Sort,
vergleiche zwei Listen und zwar insbesondere die beiden kleinsten
Elemente dieser Liste und nehme mir als erstes das kleinste Element
einer solchen Liste heraus.
Also ich vergleiche als ersten Schritt 6 und 5.
5 ist kleiner, ich nehme es mir heraus und danach schon direkt 6, weil
die Liste nicht besonders lang ist.
Dann nehme ich mir wieder die nächsten beiden Listen vor, vergleiche
welches ist das kleinere, also wo ist das erste Element das kleinste,
wäre hier die 1, danach die 3.
Schaue mir diese beiden Elemente an, hier ist die 7 kleiner, da sollte
jetzt eine 8 stehen, falsche Animation, dann die 8.
Und vergleiche diese beiden, da ist die 2 kleiner als die 4.
Also habe ich auch hier jetzt eine zusammengeführte Liste, habe mein
Problem also schon ein bisschen zusammengeführt.
Ich habe jetzt vier Listen, die jeweils sortiert sind.
Bin aber noch nicht fertig.
Ich vergleiche jetzt wieder, fange wieder von vorne an und vergleiche
zwei Listen.
Nehme ich diese beiden hier und da fange ich wieder an zu sagen, die
beiden ersten Elemente der Liste vergleiche ich und nehme mir das
kleinere, das wäre hier die 1.
Dann habe ich wieder zwei Listen, eine lange und eine kurze.
Die beiden ersten Elemente vergleiche ich und nehme mir das kleinere.
Und wenn die eine Liste von den beiden leer ist, kann ich die andere
direkt hinten dran hängen.
Habe ich also noch eine länger sortierte Liste.
Jetzt brauche ich noch diese zwei hier.
Auch da wieder, ich schaue mir die beiden kleinsten Elemente an der
jeweiligen Listen, die 7 und die 2.
Die 2 ist kleiner, also nehme ich mir die, schaue mir wieder die
kleinsten Elemente der Liste an.
Jetzt sind es die 4 und die 7.
4 ist kleiner, dann ist nur noch eine Liste über, die ich hinten
anhängen kann.
Fast fertig, einmal noch.
Ich schaue mir die kleinsten beiden Elemente der Liste an, nehme mir
das kleinere.
Schaue mir die kleinsten beiden Elemente der Liste an, nehme mir das
kleinere.
Und so weiter.
Nehme immer jeweils das kleinere.
Und habe dann am Ende eine sortierte Liste.
Indem ich eben nur einfache Dinge gemacht habe.
Ich musste mich nicht zwischendurch groß zwischenspeichern oder so.
Genau, und hier haben wir das Prinzip der Rekursion angewendet, das
besagt, man führt das gleiche Berechnungsmuster immer wieder mit
einfacheren bzw.
kleineren Eingabedaten aus, bis man zu einer trivialen Eingabe kommt.
Das selber ist die Rekursion.
Und das Zusammenführen, wie wir es beim Merge Sort gerade gesehen
haben, ist dann noch der zweite Schritt, das Zusammenführen der
Lösung.
Und das kann ich realisieren, so ein Prinzip der Rekursion, indem ich
Methoden habe, die dieses Berechnungsmuster enthalten, die sich selbst
direkt oder indirekt wieder aufrufen.
Und so eine Rekursion zu machen, mit solchen rekursiven Methoden, ist
so eine Standardimplementierung von diesem Divide & Conquer Prinzip.
Was ist dann eine rekursive Methode?
Dafür einige Definitionen hier.
Eine Methode F heißt rekursiv oder auch genauer gesagt direkt
rekursiv, wenn im Rumpf von F Aufrufe auf F selber wieder vorkommen.
Eine Methode F heißt indirekt rekursiv, wenn im Rumpf von F eine
Methode G aufgerufen wird, die ihrerseits direkt oder indirekt dann
wieder Aufrufe auf F führt.
Also es muss sich F nicht direkt selbst aufrufen, um rekursiv zu sein.
Und eine Methode F heißt endständig rekursiv, wenn im Rumpf von F,
also in der Implementierung von F, der Aufruf von sich selber als
letztes steht, also da kein weiterer Code drauf folgt.
Wenn jetzt eine Methode sich selbst aufruft, kann man sich das
vorstellen als es wird eine neue Instanz sozusagen der jeweiligen
Methode gestartet.
Also die eine Instanz der Methode läuft bis zu dem Punkt, wo sie sich
selbst aufruft, ruft dann eben sich selbst nochmal auf, dafür wird
dann neuer Speicherbereich reserviert und die neue aufgerufene Methode
abgearbeitet.
Wenn die dann irgendwann zurückkommt, würde ich dann bei der ersten
Instanz der Methode an der Stelle weitermachen, wo ich F aufgerufen
habe.
Und diese Instanzen, wie wir es jetzt mal nennen, jede von diesen
Instanzen hat dann eigene lokale Variablen, eigene Parameter.
Man muss das eben von der Vorstellung her nicht durcheinander bringen,
was die gerade aktuelle Instanz ist.
Ein Beispiel wäre die Fakultätsfunktion, die man gut rekursiv
implementieren kann.
Das kennen Sie vielleicht aus der Schule, geschrieben mit so einem
Ausrufezeichen.
Die Fakultätsfunktion N Ausrufezeichen, also geschrieben N Fakultät,
gelesen, berechnet das Produkt der Zahlen von 1 bis N.
Und man kann sich, man kann N Fakultät auch rekursiv berechnen, indem
man erstmal sagt, naja, die einfache Variante des Problems ist 0
Fakultät, das hat nämlich immer den Wert 1 per Definition und die
komplizierte Variante des Problems ist N Fakultät im Allgemeinen.
Da rechne ich aber auch einfach nur N mal N minus 1 Fakultät.
Und hier ist eben diese Rekursion, dass ich das nicht direkt in 1
hinschreibe, was die Berechnung ist, sondern mich beziehe auf die
vorherige, den vorherigen Wert von N.
Das kann ich dann als Funktion in Java schreiben, in so einer
Fakultätsfunktion, also public static int Fakultät mit dem Parameter
N.
Und ich überprüfe, wenn N größer ist als 0, dann liefere den Wert N
mal Fakultät von N minus 1 zurück.
Also hier ist der Aufruf an die Methode selber wieder.
Und wenn der Wert nicht größer als 0 ist, also vielleicht gleich nur
an der Stelle, dann liefere den Wert 1 zurück.
Und so kann ich auch schon die Fakultätsfunktion in Java rekursiv
berechnen.
Wir schauen uns hier aber nochmal im Detail an, was da passiert, weil
das mit diesen Instanzen von Methoden und verschiedenen Parametern,
die da relevant sind, können Sie sich vielleicht noch nicht gut
vorstellen.
Also, was passiert beim Aufruf dieser Fakultätsfunktion jetzt mal mit
dem Beispiel einer kleinen Zahl, Beispiel 4.
Ich kann mir das so vorstellen, dass ich jetzt die erste Instanz der
Methode hier sozusagen einsetze für diesen Methodenaufruf Fakultät von
4 mit den auch aktuellen Parametern.
Also was da denn passiert ist, dass geprüft wird, ist 4 größer gleich
0?
Hier unten habe ich nochmal die Implementierung gemacht.
Wenn ja, dann rechne 4 mal Fakultät von 4 minus 1, sonst liefere den
Wert 1 zurück.
Man würde hier jetzt ja, wenn man das auswertet, feststellen, man
würde den ersten Zweig nehmen, wo 4 eben größer als 0 ist und also
Fakultät 4 minus 1 bestimmen wollen und das Ganze mal 4 nehmen.
Das heißt, wenn ich das jetzt auswerte hier, habe ich den Ausdruck 4
mal Fakultät von 3 noch übrig.
Dann würde ich auch hier wieder den Code einsetzen.
Fakultät von 3 heißt, ich überprüfe, ob 3 größer als 0 ist.
Wenn ja, führe ich das hier aus.
Wenn nicht, gebe ich 1 zurück.
Wenn ich das auswerte, ist auch hier wieder der erste Zweig, der If
-Zweig sozusagen, wird genommen und ich bekomme dann den Ausdruck
sozusagen 4 mal 3 mal Fakultät von 2.
Das kann ich dann nochmal machen für die 2.
Auch das ist größer als 0.
Das heißt, ich rufe hier nochmal Fakultät von 1 auf.
Da komme ich jetzt endlich mal in den Else-Zweig.
Also, wenn ich so tief reingelaufen bin in meine Rekursion, komme ich
in den Else-Zweig und würde hier die 1 zurück.
Bei 1 immer noch nicht.
1 ist immer noch größer als 0.
Das heißt, ich rufe auch nochmal Fakultät von 0 auf.
Dann habe ich hier den Vergleich 0 größer 0.
Was nicht der Fall ist, würde eine 1 zurückgeben.
Dann habe ich endlich über so verschiedene tiefe Methoden-Aufrufe so
einen Ausdruck sozusagen zusammengebaut, den ich dann ausrechnen kann.
24 wäre hier das Ergebnis.
Das also als Beispiel einer solchen rekursiven Aufrufs.
Fakultätsfunktion ist ein einfaches Beispiel.
Ein bisschen interessanteres Beispiel ist die Binomial-Funktion.
Das verwendet man in einer Kombinatorik häufig.
Man liest das als n über k.
Es definiert über diese Fakultätsfunktion.
Und bekanntes Beispiel dafür wäre 49 über 6.
Was dann die Anzahl der möglichen Ergebnisse beim Lotto bezeichnet.
49 über 6.
Also solche kombinatorischen Dinge kann man mit dieser Funktion
berechnen.
Und die ist eben definiert als nFakultät durch n-kFakultät mal
kFakultät.
Sowas würde man wahrscheinlich nicht direkt implementieren wollen.
Das ist ein bisschen overflow gefährdet, weil hier recht große Werte
bei rauskommen können.
Und das nur für kleine n gut geht.
Es gibt aber auch so eine rekursive Formulierung dieser Binomial
-Funktion.
Dass man nämlich sagt, n über 0 ist 1, n über n ist auch 1.
Also wenn ich n Zahlen aus n Zahlen ziehe ohne zurücklegen, dann gibt
es nur eine Möglichkeit, wie ich das machen kann von der Kombinatorik
her.
Und das sind also meine Startpunkte, die einfachen Probleme.
Und das allgemeine n über k ist dann definiert als zwei verschiedene,
also eine Summe aus zwei anderen Binomial-Funktionen aufrufen
sozusagen.
Und so könnte ich das dann auch in Java, also diese mathematische
Vorschrift kann ich dann auch in Java implementieren.
Oder beziehungsweise, ich kann es erstmal als rekursive Berechnung
hinstellen, dass ich nämlich sage, n über k ist entweder 1, wenn k 0
ist oder k gleich n ist.
Oder hat sonst diesen Summenausdruck.
Wenn ich das dann in Java hinschreibe, ist es auch wieder recht kurz
und schön.
Ich kann nämlich sagen, die Binomial-Funktion mit den Parametern n und
k, prüft erstmal, ob k und n überhaupt irgendwelche sinnvollen Werte
hat.
In dem Fall gibt es 0 zurück, wenn nicht.
Das ist eigentlich außerhalb der Spezifikation hier oben.
Dann kommt hier der eigentlich interessante Teil, nämlich wenn k
gleich 0 ist oder k gleich n ist, gebe ich 1 zurück.
Das ist eben dieser einfache Fall.
Und wenn das nicht der Fall ist, dann rufe ich mich selbst noch
zweimal auf mit einmal n-1, k-1 als Parametern und einmal n-1 und k
als Parametern, bilde dann die Summe und gebe den Wert zurück.
Und so kann ich diese Binomial-Funktion in Java auch rekursiv
umsetzen.
Auch da wird die Frage, ist vielleicht jetzt ein bisschen noch schwer
vorzustellen, was passiert da jetzt eigentlich, deswegen auch hier mal
der Versuch, das mit einer Animation noch ein bisschen zu
verdeutlichen, was da passiert.
Wenn ich jetzt als Beispiel diese Methode aufrufe mit den Parametern 3
und 2, dann kann man sich das so vorstellen, dass die aktuellen
Parameter, also 3 und 2, eingesetzt werden in den Ablauf der Methode.
Also ich kann mir so vorstellen, ich sage n hat jetzt den Wert 3, k
hat den Wert 2 und ich setze überall da, wo n ist, die 2 ein, wo n
stand, wo k stand, Entschuldigung, und überall da, wo n stand, setze
ich den Wert 3 ein und kann das entsprechend hier auswerten.
Ich komme dann hier unten wieder an und habe diesen Ausdruck, BINOM 3
minus 1, 3 minus 2.
Das kann ich ausrechnen, welche Zahlen das sind und habe jetzt also
hier neue Aufrufe dieser Methoden mit neuen aktuellen Parametern.
Das heißt hier, BINOM 2, 1 wird aufgerufen, macht eine neue Instanz
der Methode auf, wo die aktuellen Parameter jetzt 2 und 1 sind.
Das kann ich auch wieder auswerten, komme hier unten wieder an beim
Aufruf der Methode mit den aktuellen Parametern 1 und 0.
Das heißt, es wird noch eine Instanz der Methode aufgerufen mit den
aktuellen Parametern 1 und 0.
Wenn ich diese jetzt auswerte, komme ich, laufe ich in diesen if
-Zweig, nicht in den else-Zweig, weil eben 0 gleich 0 ist, genau,
würde dann also den Wert 1 zurückliefern.
Das heißt, ich kann hier für diesen Funktionsaufruf eine 1 einsetzen,
jetzt noch hier diesen zweiten Funktionsaufruf machen, BINOM 1, 1.
Das läuft auch wieder in den if-Zweig hinein, in den ersten, in die
erste Bedingung, liefert also auch den Wert 1 zurück, das Ganze
liefert dann also eine 2 zurück.
Und dann habe ich den ersten Teil hier gemacht, kommt der zweite Teil
noch, BINOM, binomische Funktionen von 2 und 2, das würde direkt auch
hier in den Return 1 Fall hindurchlaufen, hineinlaufen, würde also
eine 1 zurückgeben und so hätte ich dann am Ende mein Ergebnis von 3
zusammengebaut.
Und hier sehen Sie so ein bisschen verdeutlicht, was heißt Instanzen
der Methode.
Die alte Methode bleibt so ein bisschen im Hintergrund, ruft eine neue
Methode auf, die abgearbeitet wird und der Kontrollfluss geht dann
zurück zur ersten Instanz der Methode, beziehungsweise zur vorherigen.
Genau, jetzt hatte ich gerade schon bei den Lernzielen kurz
angedeutet, dass ich auch noch erläutern würde, ein bisschen als
Einsteinfolie, was passiert da denn jetzt eigentlich im Speicher genau
mit diesen Instanzen von Methoden.
Das, wie gesagt, als Einsteinfolie markiert, also für, wenn Sie jetzt
schon genug haben, können Sie kurz sich entspannen und sich das später
nochmal angucken.
Wir hatten ja schon mal auf einer vorherigen Folie gesagt, dass lokale
Variablen und Parameter einer Methode im sogenannten Aufrufstapel oder
auf Englisch auch Stack, abgelegt werden.
Und da ist es jetzt so organisiert, in Java und in vielen anderen
Sprachen auch ähnlich, dass es für jede Methode einen neuen
Speicherbereich angelegt wird auf dem sogenannten Aufrufstapel.
Diesen Speicherbereich nennt man auch Rahmen oder Frame.
Der ist jetzt hier als diese vier Speicherzellen dargestellt und er
liegt sozusagen auf dem Aufrufstapel drauf.
Deswegen heißt es Stapel, weil man die dann übereinander stapelt
gedanklich.
Und in diesem Frame von einem Methodenaufruf liegen dann die lokalen
Parameter drin, wie wir ja schon gesagt hatten, lokalen Variablen
drin.
Entschuldigung, das sind sowohl die lokalen Variablen als auch die
übergebenen Parameter.
Und es ist da zusätzlich noch ein bisschen Speicherplatz reserviert
für die Operanten, also für Zwischenergebnisse, die die Methode
braucht, wofür es keine lokalen Variablen gibt.
Und auch für Rückgabewerte.
So ist also der Speicherbereich bei dem Aufruf der Methode BINOM32
dann reserviert.
Also in dem Moment, wo ich die Methode aufrufe, werden diese in
unserem Beispiel vier Speicherzellen reserviert und da werden dann die
aktuellen Parameterwerte 3 und 2 hineingeschrieben.
Wenn wir jetzt mal weiter durchgehen, was passiert beim Aufruf dieser
Methode?
Würde ich als erstes hier durchlaufen, käme in den Els-Zweig und würde
dann nochmal BINOM von N-1 K-1 aufrufen, also BINOM von 2,1.
Das heißt, wenn ich hier ankomme und diese Methode aufrufe, wird ein
neuer Speicherbereich, also ein neuer Frame für die neue Instanz der
Methode angelegt.
Also der Frame von BINOM 2,1, wo jetzt die aktuellen Parameter von K
und N eben 1 und 2 oder 2 und 1 sind.
Wenn ich dann auch diese Methode BINOM 2,1 ausführe, komme ich wieder
hier unten in den Bereich rein, würde dann wieder die Methode BINOM
aufrufen mit anderen Parametern, nämlich 1,0 und es wird auf dem Stack
nochmal ein Frame obendrauf gelegt, also auf den Stapel ein
Speicherbereich noch obendrauf gelegt für jetzt die Abarbeitung dieser
Methode.
Da hatten wir ja eben im Beispiel schon gesehen, wäre das Ergebnis 1,
also die Rekursion ist hier zu Ende.
Das heißt, die Methode gibt den Rückgabewert 1 zurück, der wird dann
hier bei den Operanten im Frame der zweiten Instanz abgelegt.
Und jetzt habe ich ja erst den ersten Ausdruck hier ausgewertet, fehlt
noch der zweite.
Würde hier jetzt also nochmal BINOM von 1,1 aufrufen, das war der
zweite Ausdruck hier.
Auch der liefert einfach nur 1 zurück.
Dann habe ich hier meine beiden Einsen auf dem sogenannten Operant
Stack als Operanten von dieser Summe.
Kann jetzt, also hier auch den Rückgabewert ausrechnen, der wäre 2 und
den an die Methode unten drunter sozusagen zurückgeben.
Die Methode unten drunter war ja gerade dabei, diesen ersten Aufruf
von BINOM auszuwerten und würde jetzt weitergehen und den zweiten
Aufruf von BINOM auswerten.
Also wieder BINOM 2,2 aufrufen, einen neuen Frame auf den Stack legen.
Das ist auch der einfache Fall, es würde 1 rauskommen, als
Rückgabewert zurückgeben werden und jetzt hat diese Instanz der
Methode quasi auch alle benötigten Informationen und kann jetzt den
Endwert 3 ausrechnen und dann auch an den aufrufenden Frame, das
könnte die Main-Methode sein, hier mit Punkten dargestellt, dann
zurückgeben.
Und so funktioniert das Ganze, die Methoden im Aufrufstapel.
Kleiner Hinweis, wir hatten ja, oder Sie hatten ja auch beim letzten
Mal schon mit Ralf Reusner über ein bisschen Optimierung von solchen
Dingen gesprochen.
Man könnte jetzt auch diese Funktion ein bisschen optimieren, indem
man ein Array als Cache verwendet und nicht immer die gleiche
Kombination von Zahlen, die gleiche Kombination von dieser
Binominalfunktion nochmal ausrechnen muss.
Aber da will ich jetzt, können Sie sich anschauen bei Interesse, will
ich jetzt gar nicht weiter darauf eingehen.
Einmal noch der Vergleich von Rekursion und Iteration.
Wir haben jetzt ja mit der Rekursion dieses Prinzip gesehen.
Ich verteile, ich zerteile mein Problem in kleine Instanzen und
realisiere das so, dass ich immer wieder die eigene Methode neu
aufrufe.
Man kann aber viele Probleme, die man mit Rekursion lösen kann,
allerdings nicht alle, auch über Iteration lösen, also eine geeignete
Datenstruktur für die Daten, auf denen man rechnet haben und dann in
der normalen Schleife oder mehreren das Ganze verarbeiten.
Da stellt sich dann auch wieder die Frage, wann ist was gut?
Rekursion ist dann oftmals vorteilhaft, wenn die Anzahl der
Iterationen unklar ist.
Also wir haben es, stimmt nicht, also wenn die Anzahl der Iterationen
unklar ist.
Der Nachteil ist aber, dass ich viele Methodenaufrufe brauche und das
kostet in Java einfach eine gewisse Zeit.
Das ist oftmals zeitaufwendiger und ich muss eben diesen Stack, den
wir gerade gesehen haben, diesen Aufrufstapel immer mit weiteren
Instanzen der Methoden belegen.
Es ist also auch oftmals speicheraufwendiger.
Und es ist manchmal ein bisschen schwierig zu erkennen, ob die
Funktion auch tatsächlich terminiert oder ob sie sich nur dauernd
immer wieder selber aufruft, bis ich selber meinen Computer dann
ausschalte.
Also nicht stoppt.
Iteration dahingegen ist vorteilhaft, wenn die Anzahl der Iterationen
bekannt ist.
Also wenn ich leicht eine Vorschleife über irgendwas schreiben kann,
dann brauche ich nicht anfangen, das zu versuchen mit Rekursion zu
lösen.
Und wenn das der Fall ist, dann kann ich auch die Komplexität oftmals
leichter abschätzen.
Also eben über eine Vorschleife iterieren dauert halt so viel, wie
Elemente drin sind.
Und wenn das der Fall ist, kann ich eben auch leichter abschätzen, ob
diese Iteration, die ich da formuliert habe, terminiert.
Kompliziert wird es bei Iterationen auch, wenn ich zum Beispiel eine
While -Schleife habe, wo gar nicht klar ist, wann denn die Bedingung
mal true wird.
Oder wenn ich auch anfange, innerhalb des Schleifenrumpfes die
Zählvariable einer Vorschleife zu ändern.
Dann wird es da eben auch schwieriger und dann kann man sich auch
überlegen, ob man es nicht besser rekursiv hätte lösen können.
Okay, zum Abschluss.
Jetzt haben wir nur noch acht Minuten, aber trotzdem.
Zum Abschluss habe ich noch was Passendes zur Jahreszeit mitgebracht,
nämlich die Kochsche Schneeflockenkurve, was auch ein schönes Beispiel
für die Anwendung von Rekursionen ist.
Und Schneeflockenkurve kann man es nennen, man kann es auch einfach
nur Kochkurve nennen.
Das ist ein Fraktal, das heißt da, wenn man weiter reinsucht, entsteht
immer wieder das gleiche Muster und das wird gebildet.
Also hier sehen wir schon das Endergebnis nach acht Iterationen.
Aber diese Kochkurve wird gebildet, indem ich erstmal eine gerade
Linie habe und dann aus diesem geraden Stück das mittlere Stück
entferne und dafür einen oberen Teil eines gleichseitigen Dreiecks
aufsetze.
Also das ist mein Startpunkt und die Iteration hier ist, dass ich das
mittlere Element rausnehme aus meiner Linie und ein Dreieck
hineinsetze.
Und dann für jede Linie, die sich da ergibt, mache ich das gleiche
nochmal.
Ich nehme das mittlere Stückchen heraus und setze ein Dreieck drauf.
Hier auch, hier auch, hier auch.
Und dann habe ich wieder eine Menge von Linien.
Für jede Linie mache ich wieder das gleiche.
Nehme das mittlere Element, setze ein Dreieck drauf.
Das sieht dann nach drei Iterationen schon so ein bisschen
schneeflockenähnlich aus.
Und wenn ich das jetzt ein bisschen weitermache und acht Iterationen
habe, viel mehr sieht man auf dem Bildschirm dann auch nicht.
Dann sieht das so wie die Seite einer Schneeflocke aus.
Das Ganze kann ich also... genau, wenn ich das jetzt zusammensetze zu
einem Dreieck, hätte ich eben so eine Schneeflocke.
Und das Ganze, wie gesagt, kann man auch mit Rekursion sehr schön
umsetzen.
Und das wäre jetzt eine Aufgabe, die wir in sieben Minuten
wahrscheinlich nicht mehr ganz hinbekommen.
Aber ich würde sie da auch so Stück für Stück durchnehmen.
Eine Denkaufgabe für Sie.
Wie könnte man diese Schneeflockenkurve rekursiv umsetzen?
Und damit wir jetzt nicht bei Null anfangen, sind einige Sachen hier
schon vorgegeben, damit wir nur zu diesem wichtigen Punkt der
Rekursion kommt.
Wir nehmen mal an, es gibt schon eine Klasse Point mit den Attributen
X und Y.
Es gibt eine Klasse Graphics, wo wir dann eine Linie zeichnen können
von Punkt 1 zu Punkt 2 mit diesem G.Jawline.
Es gibt schon vorgegeben ein Parameter Level, wo ich angeben kann,
wann ich aufhöre.
Bei einem Fraktal würde ich ja eigentlich niemals aufhören zu
iterieren.
Aber das ist bei der Programmierung mit Rechnern eben ein bisschen
unpraktisch, sage ich mal.
Also man würde hier sagen wollen, iteriere nur bis Tiefe 8 und dann
hör auf.
Das ist das Level hier.
Und wir nehmen an, es gibt Hilfsmethoden, wo ich für diese Seite, wenn
ich einen Punkt 1 und einen Punkt 2 habe, dann schon die richtigen
Positionen von den verschiedenen Ecken hier zurückbekomme.
Also GetPoint A würde mir diese erste Ecke zurückgeben, GetPoint B
diese zweite Ecke hinten und der Tipp würde mir die dritte Ecke
zurückgeben, wenn ich jeweils diese beiden Startpunkte P1 und P2
übergebe, sozusagen als Referenz, also immer relativ zu der Position
dieser beiden Punkte, würden mir diese Hilfsmethoden die anderen drei
benötigten Punkte implementieren.
Und die Aufgabe wäre jetzt, diese Methode DrawSegment rekursiv zu
implementieren.
Und da würde ich Sie erstmal kurz nachdenken lassen, wie würden Sie
das lösen und dann Schritt für Schritt Lösungshinweise geben, die ich
im Moment noch ausgeblendet habe, fällt mir gerade ein.
Also denken Sie erstmal kurz einen Moment nach, während ich die Lösung
suche.
Wie müsste man hier vorgehen?
Erster Hinweis vielleicht schon gleich.
Die Frage war ja, oder bei der Rekursion war das Prinzip, das Problem
zu zerteilen und irgendwie immer eine einfache Version des Problems zu
haben, die ich dann am Ende löse und eine kompliziertere Version des
Problems, die ich löse, indem ich irgendwas Detaillierteres oder etwas
rekursiv nochmal aufrufe.
Das heißt, jetzt hier mal alles oben ein bisschen zusammengequetscht.
Ich kann mir hier überlegen für diese DrawSegments Methode, es muss
irgendwie einen einfachen Fall geben, wo ich schon am Ende meiner
Rekursionstiefe angekommen bin und mein Level auf Null ist und es gibt
irgendwie einen schwierigen Fall, wo ich mich selbst nochmal aufrufen
will.
Ich gebe mal noch einen Hinweis, der noch nicht die eigentliche
Rekursion verrät, sondern nur ein bisschen das Drumherum, was
vielleicht jetzt auch schwierig zu erfassen ist, mitgibt, wenn ich
sage, ich habe einen einfachen Fall, heißt es ja nur, ich will jetzt
nicht mehr weiter Dreiecke in irgendwelche Linien reinsetzen, sondern
ich will einfach nur am Ende meiner Rekursion eine Linie von P1, also
P1 nach P2 ziehen und da hatten wir ja diese Hilfsmethode dafür
definiert.
Also das mache ich in der untersten Rekursionstiefe einfach nur eine
Linie von P1 zu P2 ziehen.
In der komplizierteren Variante müsste ich mir jetzt erstmal diese
neuen Punkte bestimmen, also ich habe übergeben als Parameter P1, P2
und würde mir jetzt erstmal lokale Variablen anlegen mit den weiteren
Hilfspunkten hier, also PA, habe ich das mal genannt, PB und PTIP.
Jetzt ist eben die Frage, wenn ich diese fünf Punkte jetzt ja
insgesamt habe, P1, PA, PTIP, PB und P2, wie kann ich dann diese Draw
-Segment -Methode wieder geeignet rekursiv aufrufen?
Und das ist eigentlich der Knackpunkt dann hier in diesem Beispiel.
Überlegen Sie nochmal eine Minute ungefähr und dann klappe ich es auf.
Es ist jetzt vielleicht in gewisser Weise einfacher, als Sie sich das
vorstellen.
Ich weiß natürlich jetzt nicht, wo Sie gedanklich alle gerade sind.
Was ich hier eigentlich nur noch machen muss, ist zu sagen, naja,
meine Schneeflocke besteht aus vier Teilen, eins, zwei, drei, vier,
also rufe ich dreimal, viermal noch Draw-Segment auf.
Und zwar will ich das Segment von P1 nach PA haben, also rufe ich Draw
-Segment mit den Parametern P1, PA auf, dann will ich das Segment von
A nach TIP haben, das ist die nächste Zeile, dann das Segment von TIP
nach B, das ist die dritte Zeile und das Segment von B nach TOO.
Also rufe ich einfach für diese vier Kanten sozusagen die Methode
nochmal rekursiv auf.
Ich muss dabei daran denken, diese Level-Variable immer eins runter zu
zählen, damit ich irgendwann auch mal aufhöre, sonst würde ich eben so
endlos in die Tiefe absteigen, sich vorgestellt.
Genau, und wenn ich das realisiere, dann wird eben die Methode selber
wieder aufgerufen mit den neun Punkten und dem eins niedrigeren Level.
Ich steige so tief in diese Methoden ab, man sagt auch tief bei
Rekursion, oder wenn ich mir den Stapel vorstelle, stapel ich so viele
Methodeninstanzen übereinander, bis ich zu dem einzelnen, zu dem
einfachen Fall komme.
Da würde ich wieder zurückgehen.
Hier habe ich jetzt nicht nur eine Aufspaltung in zwei Threads oder
zwei Möglichkeiten, wie bei unserer Binomialfunktion, sondern in vier,
aber das geht genauso.
Und dann hätte ich eben am Ende in der Tiefe abgestiegen, die
Schneeflockenkurve.
Das war es dann auch schon zum Thema Rekursion.
Zusammenfassend nochmal, es geht darum, Probleme zu lösen, indem man
eine kleinere Instanz des Problems identifiziert, immer so lange
kleiner macht, bis die Lösung offensichtlich ist.
Wir haben diese verschiedenen Methodeninstanzen, die ich Ihnen auch
auf dem Aufrufstapel gezeigt habe, die von den Parametern abhängen.
Es ist immer die Frage, ob etwas terminiert oder nicht.
Das kann man auch natürlich ausprobieren, aber sollte man nicht
unbedingt.
Und der Speicherverbrauch ist hier linear zur Zahl der Aufrufe, wie
wir das eben schon gesehen haben.
Genau, damit muss ich jetzt auch eiligst aufhören.
Ich zeige vielleicht hier gleich auf der Projektion nochmal, wie diese
Schneeflocke gebildet wird.
Aber Sie können auch schon mal loslaufen, wenn Sie möchten.
Gehört nicht mehr zum offiziellen Teil der Vorlesung dazu.