3.4. Operationen für verkettete Listen implementieren (Teil 1)#
In diesem Notebook wirst du die 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):
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]):
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)
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"Die 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)
# sicherstellen, dass kein Typ Knoten zurückgegeben wird
assert type(erhalten) != Knoten, f"Die Methode gib_inhalt() sollte den Inhalt des Knotens zurückgeben, nicht den Knoten selbst."
assert erhalten == erwartet, f"Das erste Element sollte {erwartet} sein, ist aber {erhalten}."
erwartet = "Coco"
erhalten = liste.gib_inhalt(1)
assert erhalten == erwartet, f"Das zweite Element sollte {erwartet} sein, ist aber {erhalten}."
erwartet = "Anna"
erhalten = liste.gib_inhalt(3)
assert erhalten == erwartet, f"Das 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"Nach 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"Nach 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"Nach dem Ersetzen des letzten Elements 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)
Jetzt geht’s los! Implementiere in der folgenden Zelle nach und nach die fehlenden Operationen/Methoden. Immer wenn du mit einer Methode fertig bist, führe die Zelle aus um zu prüfen, ob die Tests zu dieser Methode jetzt bestanden werden.
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"""
... # Hier Lösung ergänzen
def anzahl_elemente(self) -> int:
""" Gibt die Anzahl der Elemente in der Liste zurück. """
... # Hier Lösung ergänzen
def gib_inhalt(self, index: int) -> Any:
""" Gibt den Inhalt des Knotens an der Stelle index zurück. """
# ACHTUNG: Gib nicht den Knoten selbst zurück, sondern nur den Inhalt!
# D.h. dein Code sollte sowas enthalten wie: return aktuell.inhalt
... # Hier Lösung ergänzen
def ersetzen(self, index, neuer_inhalt: Any) -> None:
""" Ersetzt den Inhalt des Knotens an der Stelle index durch neuer_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 = ["ist_leer", "anzahl_elemente", "gib_inhalt", "ersetzen"]
test.fuehre_tests_aus(reihenfolge)
Mögen die Tests beginnen!
Starte Test: teste_ist_leer...
teste_ist_leer fehlgeschlagen: 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.
Leider waren noch nicht alle Tests erfolgreich. Probiere es noch einmal!
Hat dein Code alle Tests bestanden? Dann herzlichen Glückwunsch! Du bist bereit für Teil 2.