3.6. Lösungen: Operationen für verkettete Listen implementieren#
In diesem Notebook sind mögliche Implementationen für die Operationen der verketteten Liste aus dem Klassendiagramm Abb. 3.3 gezeigt. Diese Implementation besteht (hoffentlich!) alle Tests…
Show code cell content
# DIESE TESTS BITTE NICHT VERÄNDERN
class TestsVerketteteListe:
def __init__(self, KlasseVerketteteListe):
self.ZuTestendeKlasse = KlasseVerketteteListe
tests = [methode for methode in dir(self) if methode.startswith('teste') and callable(getattr(self, methode))]
self.anzahl_tests = len(tests)
self.bestandene_tests = 0
def erfolgreicher_test(self, methodenname, anzahl_tests=None):
if anzahl_tests is not None:
self.anzahl_tests = anzahl_tests
self.bestandene_tests += 1
print(f" {methodenname} war erfolgreich. Aktuelle Punktzahl: {self.bestandene_tests}/{self.anzahl_tests}")
def fuehre_tests_aus(self, reihenfolge: list[str]):
anzahl_tests = len(reihenfolge)
print("Mögen die Tests beginnen!")
for test_name in reihenfolge:
test_name = "teste_" + test_name
if not hasattr(self, test_name):
print(f"Test {test_name} existiert nicht.")
continue
test_methode = getattr(self, test_name)
print(f"Starte Test: {test_name}...")
# Fange Fehler ab und gib die Fehlermeldung aus
try:
test_methode()
except AssertionError as e:
print(f"!!! {test_name} fehlgeschlagen: {e}")
break
self.erfolgreicher_test(test_name, anzahl_tests)
if self.bestandene_tests == self.anzahl_tests:
print("\nHerzlichen Glückwunsch! Alle Tests erfolgreich.")
else:
print("\nLeider waren noch nicht alle Tests erfolgreich. Probiere es noch einmal!")
def beispiel_liste(self):
# print("Liste vorbereiten")
test_liste = self.ZuTestendeKlasse()
test_liste.einfuegen_vorne("Anna") # Diese Methode existiert schon
test_liste.einfuegen_vorne("Bibi")
test_liste.einfuegen_vorne("Coco")
test_liste.einfuegen_vorne("Dina")
# print("Die Liste sieht am Anfang so aus:", test_liste)
return test_liste
def teste_ist_leer(self):
leere_liste = self.ZuTestendeKlasse()
assert leere_liste.ist_leer() == True, "Ein leere verkettete Liste wurde nicht als leer erkannt. Tipp: Die Methode ist_leer() sollte True zurückgeben, wenn der Kopf der Liste None ist."
liste = self.beispiel_liste()
assert liste.ist_leer() == False, "Für eine Liste, die Elemente enthält, hat die Methode ist_leer() False zurückgegeben."
def teste_anzahl_elemente(self):
leere_liste = self.ZuTestendeKlasse()
korrekt = 0
ergebnis = leere_liste.anzahl_elemente()
assert ergebnis == korrekt, f"Die korrekte Anzahl der Elemente in einer leeren Liste ist 0, aber deine Methode gibt {ergebnis} zurück."
liste = self.beispiel_liste()
korrekt = 4
ergebnis = liste.anzahl_elemente()
assert ergebnis == korrekt, f"Test mit Liste '{liste}'\nDie korrekte Anzahl der Elemente in der Liste ist {korrekt}, aber deine Methode gibt {ergebnis} zurück."
def teste_gib_inhalt(self):
liste = self.beispiel_liste()
erwartet = "Dina"
erhalten = liste.gib_inhalt(0)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nDas erste Element sollte {erwartet} sein, ist aber {erhalten}."
erwartet = "Coco"
erhalten = liste.gib_inhalt(1)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nDas zweite Element sollte {erwartet} sein, ist aber {erhalten}."
erwartet = "Anna"
erhalten = liste.gib_inhalt(3)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nDas letzte Element sollte {erwartet} sein, ist aber {erhalten}."
def teste_ersetzen(self):
liste = self.beispiel_liste()
liste.ersetzen(0, "Ella")
erwartet = "Ella -> Coco -> Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Ersetzen des ersten Elements sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.ersetzen(1, "Fiona")
erwartet = "Ella -> Fiona -> Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Ersetzen des zweiten Elements sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.ersetzen(3, "Greta")
erwartet = "Ella -> Fiona -> Bibi -> Greta"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Ersetzen des letzten Elements sollte die Liste {erwartet} sein, ist aber {erhalten}."
def teste_einfuegen(self):
liste = self.beispiel_liste() # Dina -> Coco -> Bibi -> Anna
liste.einfuegen(2, "Cocobibi")
erwartet = "Dina -> Coco -> Cocobibi -> Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Einfügen an Position 2 sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.einfuegen(0, "Ella")
erwartet = "Ella -> Dina -> Coco -> Cocobibi -> Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Einfügen an Position 0 sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.einfuegen(6, "Greta")
erwartet = "Ella -> Dina -> Coco -> Cocobibi -> Bibi -> Anna -> Greta"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Einfügen an Position 6 sollte die Liste {erwartet} sein, ist aber {erhalten}."
def teste_enthaelt(self):
liste = self.beispiel_liste()
assert liste.enthaelt("Anna") == True, "Test mit Liste '{liste}'\nDie Liste enthält das Element 'Anna', aber deine Methode gibt False zurück."
assert liste.enthaelt("Bibi") == True, "Test mit Liste '{liste}'\nDie Liste enthält das Element 'Bibi', aber deine Methode gibt False zurück."
assert liste.enthaelt("Coco") == True, "Test mit Liste '{liste}'\nDie Liste enthält das Element 'Coco', aber deine Methode gibt False zurück."
assert liste.enthaelt("Dina") == True, "Test mit Liste '{liste}'\nDie Liste enthält das Element 'Dina', aber deine Methode gibt False zurück."
assert liste.enthaelt("Ella") == False, "Test mit Liste '{liste}'\nDie Liste enthält das Element 'Ella' nicht, aber deine Methode gibt True zurück."
assert liste.enthaelt("Fiona") == False, "Test mit Liste '{liste}'\nDie Liste enthält das Element 'Fiona' nicht, aber deine Methode gibt True zurück."
def teste_anhaengen(self):
liste = self.beispiel_liste()
liste.anhaengen("Ella")
erwartet = "Dina -> Coco -> Bibi -> Anna -> Ella"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Anhängen sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.anhaengen("Fiona")
erwartet = "Dina -> Coco -> Bibi -> Anna -> Ella -> Fiona"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Anhängen sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste = VerketteteListe()
liste.anhaengen("Anna")
erwartet = "Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Anhängen sollte die Liste {erwartet} sein, ist aber {erhalten}."
def teste_entfernen(self):
liste = self.beispiel_liste()
liste.entfernen(3)
erwartet = "Dina -> Coco -> Bibi"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Anna' sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.entfernen(1)
erwartet = "Dina -> Bibi"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Coco' sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.entfernen(0)
erwartet = "Bibi"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Dina' sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.entfernen(0)
erwartet = ""
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Bibi' sollte die Liste {erwartet} sein, ist aber {erhalten}."
def teste_entfernen_vorne(self):
liste = self.beispiel_liste()
liste.entfernen_vorne()
erwartet = "Coco -> Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen des ersten Elements sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.entfernen_vorne()
erwartet = "Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen des ersten Elements sollte die Liste {erwartet} sein, ist aber {erhalten}."
def teste_entfernen_inhalt(self):
liste = self.beispiel_liste()
liste.entfernen_inhalt("Coco")
erwartet = "Dina -> Bibi -> Anna"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Coco' sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.entfernen_inhalt("Anna")
erwartet = "Dina -> Bibi"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Anna' sollte die Liste {erwartet} sein, ist aber {erhalten}."
liste.entfernen_inhalt("Dina")
erwartet = "Bibi"
erhalten = str(liste)
assert erhalten == erwartet, f"Test mit Liste '{liste}'\nNach dem Entfernen von 'Dina' sollte die Liste {erwartet} sein, ist aber {erhalten}."
# Die Klasse Knoten werden wir in dieser Aufgabe benutzen, aber nicht verändern.
# Es gilt weiterhin: Ein Knoten speichert einen Inhalt und eine Referenz auf den nächsten Knoten.
from __future__ import annotations # brauchen wir, weil wir in der Klasse Knoten den Typ Knoten verwenden
from typing import Any
class Knoten:
def __init__(self, inhalt):
""" Konstruktor für die Klasse Knoten: speichert den Inhalt und legt
eine Referenz auf den nächsten Knoten an. """
self.inhalt: Any = inhalt # Any = inhalt kann beliebiger Datentyp sein
self.naechster: Knoten|None = None # Typ-Annotation: naechster ist ein Knoten oder None
def __str__(self):
return str(self.inhalt)
class VerketteteListe:
def __init__(self):
self.erster: Knoten|None = None # Der erste Knoten in der Liste (Listenkopf)
def __str__(self) -> str:
""" Gibt die Liste als Zeichenkette, getrennt durch Pfeile, zurück. """
inhalte = []
knoten = self.erster
while knoten is not None:
inhalte.append(knoten.inhalt)
knoten = knoten.naechster
return " -> ".join(inhalte)
def einfuegen_vorne(self, pInhalt):
"""Fügt einen neuen Knoten mit pInhalt am Anfang der Liste ein."""
neu = Knoten(pInhalt) # "Verpacke" den Inhalt in einen Knoten
neu.naechster = self.erster # Nachfolger des neuen Knotens ist der bisherige Listenkopf
self.erster = neu # Der neue Knoten ist ab jetzt der Listenkopf
# AUFGABE: Implementiere die folgenden Methoden für die Klasse VerketteteListe:
def ist_leer(self) -> bool:
"""gibt True zurück, wenn die Liste leer ist, sonst False"""
if self.erster is None:
return True
else:
return False
def anzahl_elemente(self) -> int:
"""gibt die Anzahl der Elemente in der Liste zurück"""
anzahl = 0
aktuell = self.erster
while aktuell is not None:
anzahl += 1
aktuell = aktuell.naechster
return anzahl
def gib_inhalt(self, index: int) -> Any:
"""gibt den Inhalt des Knotens an der Stelle index zurück"""
if self.erster is None:
return None
aktuell = self.erster
for i in range(index):
if aktuell.naechster is None:
return None
aktuell = aktuell.naechster
return aktuell.inhalt
def ersetzen(self, index: int, neuer_inhalt: Any) -> None:
"""ersetzt den Inhalt des Knotens an der Stelle index durch neuer_inhalt"""
if self.erster is None:
return
aktuell: Knoten = self.erster
for i in range(index):
if aktuell.naechster is None:
return
aktuell = aktuell.naechster
aktuell.inhalt = neuer_inhalt
def enthaelt(self, inhalt: Any) -> bool:
"""gibt True zurück, wenn inhalt in der Liste enthalten ist, sonst False"""
aktuell = self.erster
while aktuell is not None:
if aktuell.inhalt == inhalt:
return True
aktuell = aktuell.naechster
return False
def anhaengen(self, inhalt: Any) -> None:
"""hängt einen neuen Knoten mit dem Inhalt inhalt ans Ende der Liste an"""
neu = Knoten(inhalt)
if self.erster is None:
self.erster = neu
else:
aktuell = self.erster
while aktuell.naechster != None:
aktuell = aktuell.naechster
aktuell.naechster = neu
def entfernen_vorne(self) -> Any:
"""entfernt den ersten Knoten und gibt dessen Inhalt zurück"""
if self.erster is None:
return None
inhalt = self.erster.inhalt
self.erster = self.erster.naechster
return inhalt
def entfernen(self, index: int) -> Any:
"""entfernt den Knoten an der Stelle index und gibt dessen Inhalt zurück"""
if self.erster is None:
return None
if index == 0: # Spezialfall: Erstes Element entfernen
inhalt = self.erster.inhalt
self.erster = self.erster.naechster
return inhalt
aktuell = self.erster
for i in range(index - 1):
if aktuell.naechster is None:
return None
aktuell = aktuell.naechster
if aktuell.naechster is None:
return None
inhalt = aktuell.naechster.inhalt
aktuell.naechster = aktuell.naechster.naechster
return inhalt
def einfuegen(self, index: int, inhalt: Any) -> None:
"""fügt einen neuen Knoten mit inhalt an der Stelle index ein"""
if index == 0:
self.einfuegen_vorne(inhalt)
return
neu: Knoten = Knoten(inhalt)
# Knoten vor der Einfügeposition finden
aktuell = self.erster
for i in range(index - 1):
if aktuell is None:
return
aktuell = aktuell.naechster
if aktuell is None:
return
# Knoten zwischen den Knoten einfügen
neu.naechster = aktuell.naechster
aktuell.naechster = neu
def entfernen_inhalt(self, inhalt: Any) -> None:
"""entfernt alle Knoten mit dem gegebenen Inhalt"""
if self.erster is None:
return
while self.erster is not None and self.erster.inhalt == inhalt:
# Spezialfall: Erstes Element (und evtl. weitere) enthält den gesuchten Inhalt
self.erster = self.erster.naechster
aktuell = self.erster
while aktuell is not None and aktuell.naechster is not None:
if aktuell.naechster.inhalt == inhalt:
aktuell.naechster = aktuell.naechster.naechster
else:
aktuell = aktuell.naechster
# Mit den folgenden Tests kannst du deine Implementierung überprüfen.
# Führe einfach diese Zelle aus, um die Tests zu starten.
test = TestsVerketteteListe(VerketteteListe)
reihenfolge = ["ist_leer", "anzahl_elemente", "gib_inhalt", "ersetzen",
"enthaelt", "anhaengen", "entfernen_vorne", "entfernen", "einfuegen", "entfernen_inhalt"]
test.fuehre_tests_aus(reihenfolge)
Mögen die Tests beginnen!
Starte Test: teste_ist_leer...
teste_ist_leer war erfolgreich. Aktuelle Punktzahl: 1/10
Starte Test: teste_anzahl_elemente...
teste_anzahl_elemente war erfolgreich. Aktuelle Punktzahl: 2/10
Starte Test: teste_gib_inhalt...
teste_gib_inhalt war erfolgreich. Aktuelle Punktzahl: 3/10
Starte Test: teste_ersetzen...
teste_ersetzen war erfolgreich. Aktuelle Punktzahl: 4/10
Starte Test: teste_enthaelt...
teste_enthaelt war erfolgreich. Aktuelle Punktzahl: 5/10
Starte Test: teste_anhaengen...
teste_anhaengen war erfolgreich. Aktuelle Punktzahl: 6/10
Starte Test: teste_entfernen_vorne...
teste_entfernen_vorne war erfolgreich. Aktuelle Punktzahl: 7/10
Starte Test: teste_entfernen...
teste_entfernen war erfolgreich. Aktuelle Punktzahl: 8/10
Starte Test: teste_einfuegen...
teste_einfuegen war erfolgreich. Aktuelle Punktzahl: 9/10
Starte Test: teste_entfernen_inhalt...
teste_entfernen_inhalt war erfolgreich. Aktuelle Punktzahl: 10/10
Herzlichen Glückwunsch! Alle Tests erfolgreich.