Lernziele
Sie können...
- einfache dynamische Datenstrukturen objektorientiert implementieren.
- Methoden für einfach verkettete und doppelt verkettet Listen implementieren.
Aufgabe 1 - die einfach verkettete Liste
A1a: Dynamische Datenstrukturen - Die einfach verkettete Liste
Implementiere eine dynamische Liste. Diese soll eine Funktion zum Hinzufügen von Listenelementen bieten. Listenelemente beinhalten einen Wert (Attribut value) und eine Referenz auf das nachfolgende Listenelement (Attribut nextElement).
- Implementiere die Klasse
ListElement. Als Attribut bekommt diese einevalueund eine Referenz auf das nächste Element der ListenextElement. - Implementiere die Klasse Liste. Diese hat ein Attribut
root. Dieses ist das Wurzelelement an der die Liste startet. - Füge der Klasse Liste eine Hilfsmethode
_findLastElement(self, element)hinzu, die das letzte Element der Liste zurückgibt. - Füge der Klasse Liste eine Methode
append(self, element)hinzu, die ein Element an das Ende der Liste hinzufügt. Du kannst hier auf die Hilfsmethode_findLastElementzurückgreifen. - Erzeuge eine neue Liste und füge dieser 4 Elemente mit den Werten 6, 66, 77 und 9 hinzu. Lasse dir die Liste ausgeben.
- Überschreibe die magische Funktion
__str__und lasse die Liste im Pythonstil [6,66,77,9] ausgeben.
A1b: Dynamische Datenstrukturen - Funktionen auf einer einfach verketteten Liste
- Implementiere eine Funktion
mult_iterativ(liste), die eine Liste übergeben bekommt und das Produkt (Multiplikation) aller Elemente der Liste zurückliefert. Diese Funktion soll rein iterativ implementiert werden. - Implementiere eine Funktion
mult_rekursiv(liste), die eine Liste übergeben bekommt und das Produkt (Multiplikation) aller Elemente der Liste zurückliefert. Diese Funktion soll eine Hilfsfunktion_mult_rekursiv(listenElement)aufrufen, welche die Berechnung des Produktes rekursiv löst.
A1c: Dynamische Datenstrukturen - Beispiele für Rekursive und Iterative Lösungsansätze
Zur Übung können folgende Ideen als Methoden der Liste oder als Funktionen rekursiv oder iterativ implementiert werden. Dabei können Methoden und Funktionen auch kombiniert werden.
- Eine Methode
deleteElement(index), die ein Element an der Stelle index der Liste löscht. - Eine Methode, die alle Elemente mit einem bestimmten Value als Python-Liste zurückliefert.
- Eine Methode, die alle Elemente mit einem bestimmten Value aus der Liste löscht.
- Eine Methode, die das Value jedes Elements der Liste mit der Position in der Liste multipliziert.
Aufgabe 2 - die doppelt verkettete Liste
Diese Aufgabe ist für SE-GY in der ersten Woche zu bearbeiten. Für alle anderen ist diese erst in der zweiten Woche der Dynamischen Datenstrukturen zu bearbeiten.
Eine einfach-verkettete Liste besteht aus einer Klasse Liste, die eine Referenz auf das erste Listenelement enthält. Listenelemente haben eine Wert und eine Referenz auf ihr Nachfolgeelement.
Um die Liste und die Navigation innerhalb der Liste flexibler zu gestalten, wird die einfach-verkettete Liste in eine doppelt-verkettete Liste umgewandelt. Dazu soll jedes Element in der Liste nicht nur die Referenz auf das Nachfolgeelement beinhalten, sondern auch auf das Vorgängerelement.
A2: Dynamische Datenstrukturen - Die doppelt verkettete Liste
- Passe den Programmcode aus Aufgabe 1 so an, dass die Liste die geforderte Funktionalität aufweist.
- Implementiere innerhalb der doppeltverketteten Liste eine Funktion
beforeLastElement(element), die ein übergebenes Element an die vorletzte Stelle der Liste einfügt - Implementieren Sie außerhalb der doppeltverketteten Liste eine Funktion
findFirstElement(lastElement), die ein beliebiges Element der Liste übergeben bekommt und dann das erste Element der Liste ermittelt und zurückliefert. Gebe dazu eine iterative Lösung an. - Geben Sie zu der Funktion
findFirstElement(lastElement)eine rekursive Lösung an.