3.5. Operationen für verkettete Listen implementieren (Teil 2)#
In diesem zweiten Teil der Programmieraufgabe findest du
weitere Methoden, die du implementieren sollst, und
Musterlösungen für die Methoden aus dem ersten Teil. (Manche davon kannst du vielleicht in abgewandelter Form für die neuen Aufgaben nutzen 😉)
In diesem Notebook wirst du weitere Operationen der Klasse VerketteteListe implementieren,
s. Abb. 3.3. Automatische Tests werden dir dabei helfen, deine Implementierungen zu überprüfen. Diese
Tests werden weiter unten definiert. Wie genau sie arbeiten ist für dich nicht wichtig; du
musst nur sicherstellen, dass du die Operationen der Klasse VerketteteListe so implementierst,
dass die Tests erfolgreich durchgeführt werden.
Hinweis:
Lade dieses Notebook von der Webseite herunter und bearbeite es auf deinem Computer.
Führe mit Run All das gesamte Notebook am Anfang einmal aus. Dadurch werden die Tests definiert, mit denen du deinen Fortschritt beim Bearbeiten der Übungen überprüfen kannst.
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, f"Test mit Liste '{liste}'\nDie Liste enthält das Element 'Anna', aber deine Methode gibt False zurück."
assert liste.enthaelt("Bibi") == True, f"Test mit Liste '{liste}'\nDie Liste enthält das Element 'Bibi', aber dfeine Methode gibt False zurück."
assert liste.enthaelt("Coco") == True, f"Test mit Liste '{liste}'\nDie Liste enthält das Element 'Coco', aber deine Mfethode gibt False zurück."
assert liste.enthaelt("Dina") == True, f"Test mit Liste '{liste}'\nDie Liste enthält das Element 'Dina', aber deine Methodef gibt False zurück."
assert liste.enthaelt("Ella") == False, f"Test mit Liste '{liste}'\nDie Liste enthält das Element 'Ella' nicht, aber deine Methodef gibt True zurück."
assert liste.enthaelt("Fiona") == False, f"Test mit Liste '{liste}'\nDie Liste enthält das Element 'Fiona' nicht, aber deine Methode gibtf 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
knoten = self.erster
while knoten is not None:
anzahl += 1
knoten = knoten.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
knoten = self.erster
for i in range(index):
if knoten.naechster is None:
return None
knoten = knoten.naechster
return knoten.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 None
knoten: Knoten = self.erster
for i in range(index):
if knoten.naechster is None:
return
knoten = knoten.naechster
knoten.inhalt = neuer_inhalt
def enthaelt(self, inhalt: Any) -> bool:
"""gibt True zurück, wenn inhalt in der Liste enthalten ist, sonst False"""
... # Hier Lösung ergänzen
def anhaengen(self, inhalt: Any) -> None:
"""hängt einen neuen Knoten mit dem Inhalt inhalt ans Ende der Liste an"""
... # Hier Lösung ergänzen
def entfernen_vorne(self) -> Any:
"""entfernt den ersten Knoten und gibt dessen Inhalt zurück"""
... # Hier Lösung ergänzen
def entfernen(self, index: int) -> Any:
"""entfernt den Knoten an der Stelle index und gibt dessen Inhalt zurück"""
... # Hier Lösung ergänzen
def einfuegen(self, index: int, inhalt: Any) -> None:
"""fügt einen neuen Knoten mit inhalt an der Stelle index ein"""
... # Hier Lösung ergänzen
def entfernen_inhalt(self, inhalt: Any) -> None:
"""entfernt alle Knoten mit dem Inhalt inhalt"""
... # Hier Lösung ergänzen
# 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 = ["enthaelt", "anhaengen", "entfernen_vorne", "entfernen", "einfuegen", "entfernen_inhalt"]
test.fuehre_tests_aus(reihenfolge)
Mögen die Tests beginnen!
Starte Test: teste_enthaelt...
!!! teste_enthaelt fehlgeschlagen: Test mit Liste 'Dina -> Coco -> Bibi -> Anna'
Die Liste enthält das Element 'Anna', aber deine Methode gibt False zurück.
Leider waren noch nicht alle Tests erfolgreich. Probiere es noch einmal!