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…
# 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.