Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

EIG: Abstrakter Datentyp Wörterbuch

Name: EIG: Abstrakter Datentyp Wörterbuch
Uploaded: 2024-06-26T09:45:04+00:00
Duration: 30 min 20 s
Channel: Harald Selke
Description: Ein Wörterbuch ist ein dynamischer abstrakter Datentyp für Schlüssel-Wert-Paare: Neue Einträge können jederzeit eingefügt und später über ihren Schlüssel …

Harald Selke30:20 40 Aufrufe veröffentlicht 26. Juni 2024 Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 252 Zeilen

Herunterladen

willkommen zur Einführung in die Informatik für Geisteswissenschaftler dieses Video ist entstanden im Rahmen der gleichnahigen Veranstaltung an der
Universität Paderborn in diesem Video wollen wir uns einen dritten abstrakten Datentyp angucken nämlich das sogenannte Wörterbuch ein Wörterbuch soll für uns
etwas dynamisches sein anders also als ein klassisches Wörterbuch das wir aus dem Regal nehmen und in dass wir nichts schreiben können sollen unsere
Wörterbücher so aufgebaut sein dass wir in sich jederzeit etwas einfügen können daraus ergibt sich dann auch schon die erste Operation die wir für unsere
Wörterbücher haben wollen nämlich eine insert diese soll einen Schlüssel und einen Wert bekommen solche Paare aus Schlüsseln und Werten kennen wir schon
sie sind uns schon mal im Zusammenhang mit Attributen begegnet und hier ist es ganz ähnlich nehmen wir an wir wollten ein deutsch-englisches Wörterbuch haben
der Schlüssel oder key wäre dann das deutsche Wort und der englische Begriff dazu wäre entsprechend der Wert der Value wir könnten das natürlich auch
genau umgekehrt machen für ein englischdeutsches Wörterbuch da wäre dann das englische Wort der Schlüssel nachdem wir suchen und der valje dazu
wäre dann die deutsche Übersetzung solche Wörterbücher sind aber auch allgemeiner einsetzbar es könnte sich beispielsweise auch um ein Lexikon
Handeln ein Lexikon wäre dann eben so aufgebaut dass der Schlüssel das Wort ist unter dem wir den Eintrag im Lexikon finden würden und der Wert dazu wäre
dann eben der gesamte Text der zu diesem Stichwort im Lexikon steht oder vielleicht sogar ein noch komplexeres Objekt das nicht nur aus Text besteht
sondern vielleicht sogar Bilder oder was auch sonst noch immer enthält das heißt also die Schlüssel müssen einfach sein in dem Sinn dass sie schnell
durchsuchbar sind sie müssen vor allem vergleichbar sein dafür können wir beispielsweise Zeichenketten oder Zahlen nehmen unsere W Werte aber können
beliebig komplex sein sie können beliebige Objekte sein wir könnten also z.B ein Wörterbuch von den Studierenden unserer Universität verwalten in diesem
Fall würden wir dann eher von einer Liste als von einem Wörterbuch sprechen dann wären beispielsweise die Matrikelnummer die Schlüssel und alle
Daten die wir zu einem Studenten oder einer Studentin gespeichert haben wären entsprechend der Wert zu diesem Schlüssel wir könnten beispielsweise
auch ein Telefonbuch haben in einem Telefonbuch wäre der Name der Schlüssel und die Telefonnummer dazu wäre der Wert da merken wir jetzt allerdings dass wir
ein kleines Problem haben der Schlüssel wäre nämlich nicht eindeutig es könnte ja mehrere Leute gleichen Namens geben und das kommt gar nicht me mal so selten
vor das ist natürlich etwas was bei uns nicht zulässig ist der Schlüssel muss eindeutig sein so verlangen wir das in unseren Wörterbüchern jeder Schlüssel
darf nur genau einmal im Wörterbuch vorkommen man kann modifizierte Wörterbücher schreiben wir es erlauben dass ein Schlüssel mehrfach vorkommen
darf das machen wir hier aber nicht wir wollen uns das Leben ein bisschen einfacher machen s dass unser Schlüssel immer eindeutig sein muss eben wie
beispielsweise die Matrikelnummern oder wenn wir beispielsweise einen onlineeshop hätten könnten wir Produktnummern verwenden diese
Produktnummern wären dann der eindeutige Schlüssel der Wert dazu wäre die komplette Produktbeschreibung und vielleicht nicht nur die Beschreibung
sondern auch noch ein Bild und Kundenbewertungen und was weiß ich noch alles unsere Werte können also beliebige Komplexität erlangen wenn wir etwas in
unserer Wörterbuch einfügen wollen müssen wir natürlich festlegen unter welchem Schlüssel unser Objekt das wir da jetzt haben abgespeichert werden soll
und was der Wert ist der dazu gehört was unsere Werte sind lassen wir wie gesagt offen das ist einer der Gründe warum es sich bei diesem worörterbuch einen
abstrakten Datentyp handelt wir sagen also nicht was für Objekte wir hier speichern wollen beliebige Werte sollen das sein was wir auch im Moment nicht
vorsehen wollen ist dass wir den Wert zu einem Schlüssel aktualisieren können zu dem Zweck könnte man noch eine zusätzliche Methode Update einführen die
es dann beispielsweise erlauben würde dass wir einen Eintrag nachträglich modifizieren also beispielsweise den Preis eines Produkts ändern oder den
Namen einer Person das wollen wir hier nicht machen wir machen es uns wie gesagt relativ einfach wir wollen nur neue Objekte unter einem gegebenen
Schlüssel einfügen und wir wollen Sie nachschlagen können nehmen also einfach einmal den einfachen Fall eines wirklichen Wörterbuchs in dem wir
deutsche Begriffe nachschlagen und die englischen Übersetzungen dazu herausfinden können die Methode insert die wir als erstes betrachten müssten
wir dann dementsprechend so aufbauen dass wir ein Insert zwei Zeichenketten übergeben nämlich zuerst als Schlüssel das deutsche Wort und als Wert dann das
entsprechende englische Wort jeweils als Zeichenkette so sollte dann mit insert unser Wort oder unser Eintrag sollte ich vielleicht allgemeiner sagen in unser
worörterbuch eingefügt werden wir wollen natürlich auch in der Lage sein zu einem gegebenen üs den entsprechenden Wert wieder aus dem Wörterbuch auszulesen es
wäre ja dumm wenn man nur Sachen in das Wörterbuch einfügen aber nie wieder nachschlagen könnte der Sinn alses Wörterbuchs ist ja vor allem dass wir
etwas nachschlagen können wir wollen also bei unserem Beispiel eines richtigen deutsch-englischwörterbuchs eben den deutschen Wert eingeben sagen
wir wir suchen jetzt zu dem Wort Hirsch beispielsweise die Übersetzung dann soll das Wörterbuch natürlich entsprechend die englische Übersetzung zurückliefern
oder allgemeiner gesprochen zu einem gesuchten Schlüssel soll der entsprechende Eintrag geliefert werden zu einer Matrikelnummer das
entsprechende studentenobjekt zu einer ISBN-Nummer das entsprechende buchobjekt zu einer Bestellnummer das entsprechende Produkt oder was auch immer wir in
unserem Wörterbuch gespeichert haben der Wert sollte also zurückkommen unsere Methode lookup zum nachschlagen muss also einen Rückgabewert liefern und der
Rückgabewert soll der Wert sein den wir zu diesem Schlüssel im Wörterbuch gespeichert haben auch die Methode insert wollen wir übrigens mit einem
Rückgabewert versehen sie soll nämlich true zurückgeben wenn das Einfügen geklappt hat und fals wenn es nicht geklappt hat und klappen soll das immer
genau dann wenn zu dem Schlüssel noch kein Eintrag vorhanden ist das bedeutet also dass wir mit dem insert auch feststellen können ob ein Wort schon
enthalten war dann durften wir sie nicht erneut einfügen weil ein Schlüssel ja wie gesagt nur einmal vorkommen darf wenn wir diese Prüfung nicht machen
würden wäre es an dieser Stelle ein bisschen einfacher dafür aber an anderer Stelle komplizierter wir wollen daher diese Prüfung machen das heißt wir
überprüfen grundsätzlich erst einmal ob das Wort schon enthalten ist ob also ein entsprechender Schlüssel schon vorhanden ist wenn das der Fall ist erlauben wir
das Einfügen nicht ansonsten erlauben wir es und geben das auch nach außen als Rückmeldung zurück indem wir den rückgabewer true bei Erfolg zurückgeben
oder false wenn das Element nicht eingefügt werden konnte weil zu dem Schlüssel bereits ein Eintrag vorhanden ist lookup wie gesagt erhält einen
Schlüssel als Parameter und gibt dann entsprechend den Wert dazu zurück dann haben wir noch eine dritte Methode die wir umsetzen wollen das ist die Methode
remove mit der wir ein Wort aus dem Wörterbuch löschen können also einen Eintrag aus dem Wörterbuch entfernen nehmen wir wieder das Beispiel eines
Produktkatalogs wenn das Produkt nicht mehr bei uns existiert weil wir es nicht nicht mehr anbieten dann wollen wir es aus unserem Katalog entfernen oder ein
Student oder eine Studentin an unserer Universität wird exmatrikuliert weil er oder sie z.B den Abschluss geschafft hat und dann natürlich anschließend nicht
mehr Mitglied der Universität ist dann muss er oder sie also aus den entsprechenden Listen gelöscht werden und das ist genau das was wir mit remove
machen auch dieser Methode übergeben wir natürlich nur einen Schlüssel also beim Studenten bzw der Studentin die Matrikelnummer und dann wurde das
entsprechende Objekt gelöscht werden das kann offenbar nur gelingen wenn der Eintrag auch tatsächlich vorhanden ist und dann gibt ihr mit Methode true
zurück weil es in diesem Fall wirklich gelungen ist dieses Element zu entfernen wenn es dagegen nicht gelingt weil nämlich beispielsweise der Schlüssel gar
nicht im Wörterbuch enthalten war also der Student bzw die Studentin schon gar nicht mehr in unserer Liste drin war oder wir eine zufällig geratene
Matrikelnummer verwendet haben die es aber gar nicht gibt dann würde unsere Methode remove entsprechend false zurückgeben und auch hier feststellen ob
unsere Aktion erfolgreich war wir werden später noch eine vierte Methode dazu haben wollen nämlich eine Methode to String die das komplette Wörterbuch
ausgibt aber darum kümmern wir uns später auf diese Art und Weise können wir dann also diese ganzen Operationen durchführen und auch wenn das erst
einmal sehr eingeschänkt klingt haben wir mit diesem wterbuch schon ein sehr umfangreiches Anwendungsspektrum man kann also schon eine ganze Menge mit
einem solch doch recht einfachen Ding machen deshalb wollen wir uns dieses Ding jetzt genauer angucken wenn wir das nun praktisch umsetzen und ausprobieren
wollen müssen wir uns einmal kurz Gedanken machen auch wenn uns das hier eigentlich noch am Rande interessiert was wir denn tatsächlich hier in unseren
Wörterbüchern speichern wollen und das können wir gerade schon beschrieben verschiedenste Dinge sein wir machen es un hier ganz einfach unsere Wörter
sollen tatsächlich Wörter sein also Übersetzungen von deutschen Wörtern in englische Wörter unsere Wörter sind daher einfach so aufgebaut dass sie zwei
Komponenten haben nämlich ein Wort ein deutsches als Schlüssel und ein Wort ein englisches als Wert man kann sich das also im Grunde so vorstellen wie das
hier rechts auf der Folie sehen zu sehen ist also wie ein doppelkästchen bei dem ich hier in fett gedruckt oben den Schlüssel stehen habe und als Wert
darunter die entsprechende englische Übersetzung so zumindest kann man sich das vorstellen intern ist dann natürlich nicht als Kästchen gespeichert sondern
wir haben ein wortobjekt mit zwei Eigenschaften und das sehen wir hier links in unserem Quelltext die Klasse Word hat einen Konstruktor dem wir einen
Schlüssel und einen Wert übergeben können wir würden also dann beispielsweise Hirsch und dir übergeben diese beiden Werte werden dann in den
Eigenschaften key und value gespeichert der erste Parameter als Key der zweite als value unsere Wörter verfügen außerdem über eine Methode to String mit
der sie sich ausgeben können wir machen es uns hier wieder ganz einfach sie geben sich einfach als Absätze aus so können wir dann später einfach einzelne
Wörter oder auch das ganze Wörterbuch ausgeben jedes Wort steht dann in einem eigenen Absatz in dem zunächst der Schlüssel steht also das deutsche Wort
dann ein Doppelpunkt und dahinter dann der Wert also die englische Übersetzung zu diesem Wort bei diesem beispielwort würde also Hirsch Doppelpunkt dir als
Absatz auf unserer Webseite ausgegeben werden wenn wir diese Methode aufrufen wir können dann wie wir das ganz unten auf der Folie im Beispiel sehen mit New
World in Klammern dann Hirsch und der oder New World Feuerwehr 112 beispielsweise einen entsprechenden Wörterbucheintrag bzw Telefonbucheintrag
vornehmen komplizierter sind unsere Objekte hier nicht wir könnten aber wie gesagt auch ganz andere Dinge haben viel komplexere Objekte und dann tatsächlich
würde das alles was wir hier gleich machen werden sogar auch funktionieren wenn wir unsere Buchobjekte vom letzten Mal als Werte einsetzen würden das
könnten wir hier deshalb machen weil auch diese Buchobjekte ja wissen wie sie sich als Zeichenkette ausgeben würden wir müssen das ein kleines bisschen
modifizieren weil wir damit Tabellen gearbeitet haben aber das ist gar nicht so kompliziert wir werden relativ schnell dabei dass wir auch einen
Buchkatalog beispielsweise haben könnten da müssten wir uns nur überlegen was wir als Schlüssel verwenden würden das könnten z.B isbnnummern sein die genau
zu einem solchen Zweck erfunden worden sind so einfach sehen also unsere Wörter aus und jetzt können wir die Wörter in ein Wörterbuch schreiben Wörterbuch
heißt auf Englisch dictionary und deshalb nennen wir unseren abstrakten Datentyp auch so auch für das Dictionary benötigen wir natürlich einen
Konstruktor und wenn wir ein neues Wörterbuch erstellen wollen mit new dictionary und das dann in einer Variablen speichern leted d gleich new
dictionary beispielsweise könnten wir zunächst ein leeres Wörterbuch erzeugen und bei diesem Wörterbuch machen wir das ähnlich wie wir das in den letzten
beiden Videos gesehen haben wir haben eine interne Eigenschaft die wir wieder data nennen die soll wieder nur intern verwendet werden von außen wird man
keinen Zugriff auf Sie verwenden wollen man bräuchte da ein spezielles Konstrukt mit dem wir uns hier nicht beschäftigen wollen um einen solchen Zugriff auch
tatsächlich zu unterbinden hier ist es zwar theoretisch möglich auf die Eigenschaft data zuzugreifen aber wir wollen das auch hier wieder nicht tun
wir wollen nur mit den Methoden die wir für das dictionary gleich noch definieren werden darauf zugreifen in der nächsten Woche werden wir uns diese
interne Datenstruktur noch einmal genauer angucken da werden wir uns angucken was die hier von mir gewählte Variante nämlich ein Array zu verwenden
für Nachteile hat und wir werden Sie dann durch eine komplett andere Datenstruktur ersetzen ohne dass sich aber an dem dictionary nach außen hin
etwas ändert das heißt dass ich unsere Abstraktion die wir in dem Datentyp vornehmen dann noch einmal zeigen wird da wir nämlich die interne Struktur
dieses Datentyps zunächst einmal eigentlich gar nicht festgelegt haben erst in dem Moment in den wir ihn implementieren wollen und das ist der
Punkt an dem wir gerade stehen müssen wir uns überlegen wie wir das konkret machen möchten hier verwenden wir wie gesagt ein Array und dann können wir uns
das so vorstellen wie ich das da rechts schon einmal angefangen habe hinzumalen das können wir jetzt zunächst einmal z.B für das erste Tier machen wenn wir jetzt
ein weiteres Tier einfügen würde das entsprechend hinten dran geschrieben werden wir können dann ein drittes Tier einfügen und dann fügen wir noch ein
viertes Wort hinten an hier sind das immer Tiere also immer deutsch-englische Wortpaare von Tieren aber das ist natürlich nur mehr oder weniger zufällig
so wenn wir hier nur den Hasen einfügen sehen wir allerdings auch dass unser dictionary eine kleine Merkwürdigkeit aufweist es ist nämlich nicht sortiert
wir fügen die Elemente einfach immer hinten an die Einträge sind also nicht alphabetisch sortiert wie wir das normalerweise von einem Wörterbuch
erwarten würden warum nun das einfügen würde viel komplizierter werden wenn wir das machen würden zum Nachschlagen hätte das allerdings auch gewisse Vorteile das
gucken wir uns aber später noch mal an für den Augenblick machen wir es einfach also einfach so dass wir immer wenn wir ein neues Wort haben dieses einfach
hinten anfügen und jetzt müssen wir uns natürlich überlegen wie wir diese Methoden umsetzen können also die Methoden lookup insert remove und to
String ich beginne mit der Methode insert wir wollen uns also überlegen wie wir zunächst einmal einen neues Wort in unser Wörterbuch einfügen nun das
funktioniert so dass wir einen Key und einen value übergeben bekommen also Hirsch und dir beispielsweise als deutsches und als englisches Wort das
sind unsere beiden Parameter was müssen wir jetzt machen wir müssen zunächst einmal über prüfen ob das Wort schon in unserem Wörterbuch vorhanden ist dafür
können wir die Methode lookup verwenden die werden wir noch schreiben müssen zum Glück verfügt unser worörterbuch ja über eine solche Methode aber noch haben wir
sie nicht trotzdem wir sind ja vorausschauend wir wissen dass wir diese Methode gleich noch schreiben werden werden wir die hier verwenden wir wissen
auch schon das hatten wir schon festgelegt dass die Methode lookup den wird fals zurückliefern wird wenn der Schlüssel nicht im Wörterbuch enthalten
ist das heißt also wenn this.lup für den Schlüssel den wir gerade übergeben bekommen haben gleich false ist dann wissen wir dass in unserem Wörterbuch
bislang kein entsprechendes Wort unter diesem Schlüssel gespeichert ist und das bedeutet wir können dieses Wort nun selber bedenkenlos einfügen dafür bauen
wir ein neues wortobjekt zusammen mit neww key value key und value haben wir hier als Parameter übergeben bekommen bauen wir jetzt ein wortobjekt zusammen
und dieses wortobjekt fügen wir dann wo ein na ja in unsere interne Datenstruktur natürlich unsere interne Datenstruktur ist im Moment ein Array
und an ein Array können wir einfach hinten etwas anfügen indem wir die Methode Push für dieses Array aufrufen dieses interne Array heißt dis. datata
dann schreiben wir hinter dahinter pun Push und übergeben dem als Parameter unser Wort das wir gerade mit New World key value erzeugt haben wir hätten
dieses Wort auch erst in einer lokalen Variablen in der Methode speichern können und dann diese Variable an dis.data.push übergeben aber so ist es
kürzer und funktioniert mindestens genauso gut mit dieser einen Zeile sorgen wir also dafür dass ein neues wortobjekt erzeugt wird und dieses
wortobjekt in das aray eingeführt wird und zwar an die hinterste Stelle anschließend wissen wir dass das funktioniert hat und deshalb können wir
jetzt true zurückgeben und sind fertig wenn hingegen this. lookup von Key nicht false ist also true ist dann muss das Insert umgekehrt aber false zurückgeben
denn wenn das Objekt schon im Wörterbuch gefunden wurde ein Eintrag mit dem entsprechenden Schlüssel also schon vorhanden ist dann bedeutet das dass wir
auf keinen Fall den neuen Wert einfügen dürfen und wenn wir das übergebene Wort nicht einfügen so hatten wir gesagt dann soll insert den Wert false zurückliefern
auf diese Art und Weise haben wir also jetzt sichergestellt dass ein neues Wort eingefügt wurde wenn es zu dem entsprechenden Schlüssel noch kein Wort
gab wir geben mit dem Fall true zurück wenn das funktioniert hat und wir geben false zurück wenn das nicht funktioniert hat jetzt müssen wir natürlich dafür
sorgen dass wir die Methode lookup implementieren wie gucken wir denn jetzt bitteschön nach ob ein Wort in diesem Wörterbuch schon enthalten ist gut da
bleibt uns gar nichts anderes übrig als unsere interne Datenstruktur zu durchsuchen im Augenblick ist das ein Array und so müssen wir denn das interne
Array von vor vorne bis hinten durchlaufen denn wir haben ja keine Ahnung wo in diesem aray der Hirsch vielleicht stehen könnte als ich eben
den Hirsch eingefügt habe war das wörterbook ja noch sehr klein aber nehmen wir z.B den Hasen als der eingefügt wurde da wussten wir nicht wo
wir suchen sollen wir können ja nicht sagen dass wir am Anfang gucken müssten oder in der Mitte oder am Ende wir haben ja keine Ahnung wie das Wörterbuch
aufgebaut ist es ist ja unsortiert bzw die Wörter stehen in der Reihenfolge darin in der die Wörter eingefügt wurden wir haben also keine andere Wahl als das
was wir bislang auch schon immer gemacht haben also wenn wir beispielsweise ein bestimmt des Elementen der Bücherliste gesucht haben die wir neulich umgesetzt
haben auch da mussten wir immer das komplette Array von vorne bis hinten durchlaufen das hat gewisse Nachteile und ist oft nicht geschickt aber bislang
hatten wir uns dann nie einen Kopf drum gemacht und so wie wir hier jetzt angefangen haben haben wir erst einmal gar nicht viele Möglichkeiten das anders
zu machen aber das werden wir wie gesagt noch thematisieren wir machen es also wieder ähnlich wie wir das neulich bei den Bücherlisten gesehen haben genau wie
dort nehmen wir uns eine Schleife her die wie wir das nun wahrlich schon oft gesehen haben von Null losläuft und dann durch das gesamte Array läuft wie lange
ist das Array das interne Array heißt disp datata das hat length viele Elemente also läuft die Schleife solange unser Index i kleiner als disp data pun
length ist und wir erhöhen i in jeder Runde um eins in der Schleife überprüfen wir in einer Abfrage if abfrage jeweils ob der Key den wir als Parameter über
übergeben bekommen haben identisch ist mit dem Key des gerade betrachteten Elements im Array das heißt wenn wir beispielsweise den has und suchen gucken
wir als erstes das nullte Element an das ist der Hirsch gewesen ist das deutsche Wort Hirsch zufälligerweise identisch zu H haben den gesuchten Schlüssel gefunden
das ist natürlich nicht der Fall also gucken wir uns das nächste Wort an das ist das Schaf dann der Wahl und so weiter bis wir irgendwann beim Hasen
angekommen sind und wenn die beiden Wörter übereinstimmen also der übergebene Schlüssel Hase mit dem Schlüssel unseres gerade betrachteten
Wörterbuch eininttrags übereinstimmt Hase dann wissen wir in dem Moment dass wir jetzt den richtigen Schlüssel das richtige Wort gefunden haben und können
den Wert das entsprechende englische Wort dazu das ja im value dieses Array Elements gespeichert ist zurückgeben unsere Methode liefert in diesem Fall
also this. data an der Stelle i. value zurück wir erhalten also die englische Übersetzung zum Hasen wenn wir dagegen niemals eine Übereinstimmung finden dann
läuft unsere Schleife bis zum Ende durch wir haben nie eine Übereinstimmung gefunden und wir wissen also dass der Gesuchte Schlüssel nicht im areay
enthalten war und in diesem Fall geben wir forszeug weil wir ja nun sagen können tut mir leid zu dem Schlüssel haben wir keinen Eintrag gefunden und
das ist genau das was luup machen sollte in diesem Fall soll die Methode false zurückgeben wenden wir uns jetzt im Löschen von Einträgen zu wie können wir
das machen wie können wir einzelne Wörter aus dem Wörterbuch entfernen wir sehen schon dass der Code einigermaßen kompliziert ist woran liegt das nun wir
hatten neulich ja schon bei einem Beispiel einmal diesen Effekt dass wenn wir aus einer Liste beispielsweise also also aus einem Array irgendwo mittendrin
etwas herauslöschen Lücken in diesem Ding entstehen das möchte ich hier bei dem Wörterbuch vermeiden deshalb verwenden wir folgenden Trick den ich da
oben mit diesem kleinen Diagramm das ich da aufgemalt habe illustrieren möchte nehmen wir an dass wir aus dem beispielwörterbuch von eben den Wahl
löschen wollen unsere Methode kriegt also wieder einen Schlüssel übergeben z.B Wahl wir müssen jetzt wieder unser Array durchsuchen bis wir das
entsprechende Element gefunden haben in unserem Beispiel befand sich dieser Eintrag an der dritten Stelle des Arrays es soll also das dritte Element gelöscht
werden jetzt könnten wir es theoretisch einfach entfernen und dann nichts hineinschreiben dann haben wir aber hier ein undefiniertes Element mitten in
unserem Wörterbuch hätten also sozusagen ein Loch darin wenn man so möchte das möchten wir vermeiden und deshalb gehen wir kurz so vor dass wir einfach das
letzte Element nehmen und es an diese Stelle packen das letzte Element müssen wir dann natürlich löschen damit es nicht zweimal im Wörterbuch steht das
darf nicht sein das letzte Element wird also in die gerade frei gewordene Stelle hineinverschoben und wenn wir das so machen vermeiden wir dass ein Loch in
unserem Array entsteht jetzt kommt allerdings noch eine kleine zusätzliche Komplikation was machen wir denn wenn ausgerechnet das letzte Element gelöscht
werden soll dann funktioniert der Mechanismus so nicht denn dann darf das letzte Element ja nicht woanders hinverschoben werden oder genauer gesagt
auf sich selbst verschoben werden schaut euch den Code mal genau an und spielt das mal auf Papier durch in diesem Fall müssen wir direkt das letzte Element
löschen und dann nichts weitermachen und das macht diese Methode remove jetzt ein kleines bisschen kompliziert das solltet ihr euch einmal ganz detailliert auf den
Hirnwindungen zergehen lassen was machen wir also nun der Reihe nach wir bekommen einen Schlüssel übergeben Wahl beispielsweise jetzt laufen wir wieder
durch unser Array genau wie wir das eben bei der Methode lookup gemacht haben wir machen fast genau das gleiche nur können wir die Methode lookup hier nicht
verwenden weil die uns nicht sagt an welcher Stelle wir das Element gefunden haben wenn wir es denn finden sie sagt uns nur ich habe es gefunden und gibt
dann den entsprechenden englischen Begriff zurück oder sie sagt einfach ich habe es nicht gefunden hier brauchen wir aber jetzt die Position an der wir das
Element gefunden haben deshalb müssen wir hier im Grunde genommen dasselbe wie eben bei dem lookup noch einmal machen nur dass wir innerhalb der ifabfrage in
dem Fall dass wir das Element gefunden haben nun etwas anderes tun wir laufen also wieder durch unser Array V let i = 0 i kleiner dis. datata.length i++ das
komplette Array wird also von vorne bis hinten durchlaufen für überprüfen in jeder Runde ob der Schlüssel den wir übergeben bekommen haben übereinstimmt
mit dem Schlüssel des gerade betrachteten Objekt soweit also alles wie eben wenn wir den gesuchten Schlüssel also das gesuchte Element
gefunden haben müssen wir einmal überprüfen ob wir uns nicht an der letzten Stelle befinden wir prüfen also if I kleiner dis. dat L-1 wenn wir uns
also nicht beim letzten Element befinden das ist die Situation wie sie in dem Bild oben dargestellt ist sondern irgendwo mittend drin nehmen wir das
letzte Element in unserem Array wir wissen dass wir das kriegen mit this.data.pop die Methode Pop des Arrays liefert uns das letzte Element des
Arrays und entfernt das aus ihm jetzt haben wir es quasi in der Hand und was machen wir mit dem Element das stecken wir jetzt genau an die aktuelle Position
an der wir gerade stehen this. data an der Stelle i wird also dieses letzte Element zugewiesen wir brauchen keine neuen Wörter zu erzeugen sondern wir
nehmen einfach das wortobjekt dass wir dort an der letzten Stelle des Ars gefunden haben und verschieben es an diese Position das haben wir mit dieser
Anweisung erreicht jetzt müssen wir uns noch den elsfall angucken wenn also i== this. datap l -1 ist größer als dieser Wert kann i nie werden dafür sorgt
unsere vorschleife ja i wird niemals größer als disp datap l -1 sein wenn i also gleich diesem Wert ist dann kommen wir in diesen zweiten Zweig hinein und
dann machen wir einfach nur this.data.p das heißt wir entfernen einfach nur das letzte Element wir wollen das gar nicht zurückgeben und
damit irgendetwas ma sondern lassen das Element dass die Methode Pop des Ars zurückgibt einfach verpuffen das Wort verschwindet es ist nicht mehr im
worörterbuch enthalten in beiden Fällen folgt anschließend die Anweisung return true denn wir haben ja in beiden Fällen erfolgreich das gewünschte Element
entfernt gucken uns das ganze jetzt noch einmal von innen nach außen an ganz innen haben wir also diese If Abfrage mit dem elszweig diese Abfrage überprüft
nur ob es sich bei dem Gefundenen Element um das letzte Element des Arrays handelt oder nicht also ein inneres Element sozusagen in jedem beiden Fälle
können wir das Element entfernen müssen dabei aber etwas unterschiedlich vorgehen wir wissen aber auf jeden Fall dass wir einen Schlüssel gefunden haben
der mit dem Schlüssel des aktuell betrachteten Elements übereinstimmt das ist die äußere ifabfrage gewesen if key= this. data an der Stelle i. key wenn das
also übereinstimmte können wir auf jeden Fall das Element entfernen und dazu gehört jetzt entsprechend diese Anweisung return true die wir hier sehen
wir geben also genau in diesem Fall true zurück sagen also ja das Element konnte entfernt werden mit der Anweisung return true endet auch die Ausführung dieser
Methode sobald wir ein Return erreicht haben wird die Abarbeitung einer Funktion oder Methode abgebrochen und wir gehen an die aufrufende Stelle
zurück die Kontrolle ist also wieder an der aufrufenden Stelle beispielsweise im Hauptprogramm oder von wo auch immer wir aufgerufen worden sind zu der Anweisung
return false die ganz unten als allerletztes noch außerhalb der vorschleife steht kommen wir immer nur dann wenn wir das komplette Array von
vorne bis hinten durchlaufen haben und niemals eine Übereinstimmung des gesuchten Schlüssels mit im Schlüssel eines Eintrags gefunden haben wenn es
irgendwann eine Übereinstimmung gegeben hätte wären wir irgendwann bei dem return true angekommen und hätten die Ausführung der Methode beendet nur wenn
es sie nicht gibt kommen wir bei dem return false an und das heißt also dass in dem Fall unsere Methode remove entsprechend den Wert false
zurückgliiefert also zurückmeldet dass das Element nicht entfernt werden konnte weil es kein Element mit dem entsprechenden Schlüssel dazu gab bleibt
zu guter letzt noch die Methode to String die ich gerne umsetzen wollte die gehört wie gesagt streng genommen nicht zu dem Wörterbuch dazu aber auch die
wollte ich hier gerne einmal zeigen wir wollen einmal das komplette Wörterbuch ausgeben können wie machen wir das nun ähnlich wie wir das schon mehrfach an
anderer Stelle gesehen haben wir müssen im Prinzip nur unser komplettes aray von vorne bis hinten durchlaufen wir bauen uns in einer Ergebnis varariable die ich
hier result genannt habe einfach eine Zeichenkette zusammen wir initialisieren die Variable result zunächst mit der leeren Zeichenkette wir durchlaufen das
Array dann wie üblich von vorne bis hinten das ist unsere Schleife die wir das wie so oft haben und hängen jeweils das aktuelle Element an das aktuelle
Element ist jeweils ein wortobjekt und wie sich ein wortobjekt ausgibt hatten wir vorhin schon gesehen nämlich als Absatz in der Form deutsches Wort
Doppelpunkt englisches Wort so werden also alle Wörter nacheinander angefügt und das ganze als Zeichenkette zurückgegeben was wir an dieser Stelle
allerdings auch schon sehen ist dass wir ein unsortiertes Wörterbuch zurückbekommen das ist für den Benutzer gar nicht schön wenn wir das anders
haben wollten müssen wir uns jetzt erst noch irgendwie ein paar Gedanken dazu machen wie man ein solches Wörterbuch vielleicht auch sortieren könnte das
machen wir aber nicht an dieser Stelle die Gedanken die ich mir an dieser Stelle gerne noch machen möchte betreffen die Frage wie denn eigentlich
das Laufzeitverhalten dieses Wörterbuchs aussieht wie aufwendig ist denn das eigentlich was wir da machen überlegen wir dazu einmal was wir für die einzelne
Operation machen müssen zunächst einmal für das Einfügen eines neuen Wortes was wir machen müssen ist dass wir und das klingt zunächst sehr einfach das neue
Element nur hinten an das Array anhängen indem wir die Methode Push für das interne Array aufrufen aber tatsächlich ist es so einfach nicht wir müssen ja
erst einmal nachgucken ob das Wort irgendwo in unserem Wörterbuch schon vorhanden ist das heißt wir müssen erst einmal das komplette Wörterbuch von
vorne bis hinten durchlaufen im schlimmsten Fall im günstigsten Fall finden wir das Wort schon ganz vorne aber im schlimmsten Fall finden wir das
Wort erst an der allerletzten Stelle und stellen fest ach das Wort ist ja schon im Wörterbuch der Schlüssel ist also schon vorhanden dann können wir es nicht
einfügen das heißt wir durchlaufen im ungünstigsten Fall erst einmal das komplette areay und können dann erst sagen so jetzt können wir es einfügen
dann hängen wir es hinten an das areay an und das eigentlich einfügen selber ist dann gar nicht mehr kompliziert und geht ganz schnell aber das nach schlagen
am Anfang ob der Schlüssel schon im Wörterbuch vahen ist das ist genau das was es sehr aufwendig macht und wenn wir sehr große Wörterbücher haben stellen
wir uns jetzt nicht irgendwie ein Wörterbuch mit zehn Einträgen vor sondern stellen wir uns vor unser Wörterbuch steht besteht aus einer
Million Einträgen dann bedeutet das dass wir eine Million Schritte benötigen bis wir dann tatsächlich erstmal sagen können ja das Wort können wir einfügen
es ist okay es gibt noch kein Wort mit diesem Schlüssel erst dann können wir mit dem einfügeprozess beginnen der ist dann in ull kom nichts erledigt da
müssen wir nur einmal hinten an das er ein Element anfügen und das geht sehr schnell die Wortsuche das ist die zweite Methode
die wir eben geschrieben haben die ist damit also das eigentliche Problem weil wir das ganze Ding das ganze are von vorne bis hinten durchlaufen müssen das
hatten wir bei dem lookup auch gesehen auch da müssen wir alles von vorne nach hinten durchsuchen die Methode in der Methode insert sah man das nicht so
direkt an weil dort gar keine Schleife vorkam aber wenn wir genauer hinsehen finden wir natürlich den Aufruf von lookup und wir wissen dann dass wir
dessen Laufzeit mit berücksichtigen müssen wir könnten also jeweils dafür sorgen dass wir wenn wir ein neues Wort in unser Wörterbuch einfügen das
komplette Wörterbuch immer sofort sortieren dann könnten wir uns ein clevereres Verfahren für das lookup ausdenken allerdings ist das Sortieren
ebenfalls sehr aufwendig unter bestimmten Umständen kann sich das lohnen aber dafür müssten wir wissen wie das Wörterbuch verwendet wird werden z.B
eher selten neue Einträge eingefügt aber häufig nachgeschlagen wäre die Sortierung vermutlich ein Gewinn denken wir noch einmal an eine Uni zurück die
in einem solchen dictionary die Daten von Studierenden verwaltet da kämen vermutlich nur einmal pro Semester eine ganze Reihe neuer Einträge hinzu aber
den Rest des Semesters wird man nur nachschlagoperationen haben da könnte es sich also lohnen über entsprechende Verbesserungen nachzudenken das
Kernproblem dass wir hier bei allen drei Methoden insert lookup und remove haben ist dass wir erst einmal das richtige Wort suchen müssen also einen bestimmten
Schlüssel in dem Array suchen müssen dafür müssen wir dieses Array von vorne bis hinten durchlaufen weil wir eben keine Sortierung haben deshalb müssen
wir Element für Element für Element angucken diese Schleifen das hatten wir auch schon gesehen brechen zum Teil früher ab nämlich wenn der Schlüssel
früh gefunden wird wir haben also keine feste Laufzeit die wir hier angeben können sondern die Laufzeit hängt gewissermaßen davon ab ob wir Glück
haben oder Pech haben wenn wir Pech haben finden wir nämlich den richtigen Schlüssel erst im letzten oder vorletzten Element dann haben wir
praktisch das gesamte Worterbuch durchlaufen und eine Million Einträge heißt eben eine Million vergleichsoperation die wir durchführen
müssen wenn wir Glück haben haben wir immer nur den Hirschen gesucht wollten also immer ein Element das ganz weit vorne steht suchen finden oder entfernen
das wäre schon ein riesiger Zufall jetzt kann man sich auch überlegen wie lange man denn so im Durchschnitt braucht dazu machen wir uns nächste Woche noch ein
paar Gedanken das wollen wir in dieser Woche noch nicht angehen die Frage die man sich jetzt aber stellen kann und da kommen wir
jetzt richtig in die Informatik hinein genau gesagt in das Themenfeld der Algorithmik ist ob es geeignete Algorithmen und Datenstrukturen gibt mit
denen man so etwas geschickter hinbekommt als wir das jetzt gerade hier angestellt haben und da gibt es in diesem konkreten Fall zwei mögliche
Strategien die eine besteht darin dass wir eben anders als wir es hier jetzt gerade gemacht haben eben doch eine solche sortierte Liste pflegen und dann
in dieser Liste geschickt suchen das hat gewisse Vorteile es hat aber auch gewisse Nachteile und über die werden wir uns in der nächsten Woche Gedanken
machen und das zweite was wir machen können ist dass wir eine ganz andere Datenstruktur verwenden die vielleicht in der Lage ist die Vorteile zu nutzen
und die Nachteile dennoch zu vermeiden sie wird auch kleine Nachteile haben die nach aber die Nachteile sind vielleicht so geringfügig dass wir sie in Kauf
nehmen einer der Nachteile wird insbesondere sein dass die Implementierung erheblich kompl erter wird und das ist etwas was wir uns in
der nächsten Woche angucken wollen da wollen wir uns als krönenden Abschluss Gedanken dazu machen wie man zum einen eben über Effizienz nachdenken kann und
wie man zum anderen verschiedene Strategien verfolgen kann um eine solche Datenstruktur effizienter hinzekommen damit sind wir mit dem abstrakten
Datentyp Wörterbuch durch einer Datenstruktur die sehr flexibel einsetzbar ist die sehr umfangreiche Anwendungen hat und eben nicht nur für
Wörterbücher sondern für alle möglichen Dinge wo man etwas nachschlagen möchte geeignet ist wir steigen in dieser Vorlesung noch nicht in das Thema der
Datenbanken ein das kommt erst im übernächsten Semester aber eine Datenhaltung mit Hilfe von solchen schlüsselwertparen wo wir nach einem
Schlüssel suchen wollen und ein Wert dazu zurückgeliefert bekommen wo wir einen Datenbestand dynamisch aufbauen können indem wir neue Elemente
hinzufügen können wo wir Elemente entfernen können l sich hiermit sehr gut umsetzen dazu brauchen wir wie eben gesehen drei Operationen nämlich die
drei Methoden die wir eben für das Wörterbuch vorgesehen haben insert lookup und remove man könnte sich noch eine Methode Update dazu vorstellen um
Einträge aktualisieren zu können und weil wir neugierig sind sind haben wir auch noch eine zusätzliche Methode dur String implementiert um das Ganze
Wörterbuch auszugeben die muss man nicht unbedingt haben wenn man das Wörterbuch vielleicht gar nicht als Ganzes ausgeben möchte aber wir haben das an dieser
Stelle mal mit vorgesehen im beispielkode zu dieser Vorlesung könnt ihr euch auch anschauen wie das ganze denn funktioniert und dass man mit
diesem Wörterbuch durchaus arbeiten kann tschüss bis zum nächsten Video

Zum Nachlesen

ZuordnungstabelleDie Zuordnungstabelle (auch assoziatives Array, Dictionary, Hash, Map, Objekt oder Liste von Schlüssel-Wert-Paaren) ist eine Datenstruktur, bei der anders … WörterbuchWörterbücher im engeren Sinn dienen zum Nachschlagen sprachlicher Information, während der Ausdruck in der weiteren Bedeutung auch andere nach Stichwörtern …