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