Einführung
Du arbeitest an einem Projekt, um ein Zugplanungssystem für ein stark befahrenes Schienennetz zu entwickeln.
Du sollst einen Prototyp für die Zugstrecken im Planungssystem entwickeln. Jede Strecke besteht aus einer Abfolge von Bahnhöfen, an denen ein bestimmter Zug hält.
Anleitung
Dein Team hat beschlossen, jede Zugstrecke im Fahrplan durch eine doppelt verkettete Liste darzustellen.
Jeder Bahnhof entlang der Strecke des Zuges wird durch einen Knoten in der verketteten Liste dargestellt.
Du brauchst dir keine Gedanken über Ankunfts- und Abfahrtszeiten an den Bahnhöfen zu machen.
Jeder Bahnhof wird einfach durch eine Zahl dargestellt.
Strecken können erweitert werden, indem du Bahnhöfe am Anfang oder Ende einer Strecke hinzufügst.
Sie können auch verkürzt werden, indem du Bahnhöfe am Anfang oder Ende einer Strecke entfernst.
Manchmal wird ein Bahnhof geschlossen, und in diesem Fall muss er aus der Strecke entfernt werden, auch wenn er nicht am Anfang oder Ende der Strecke liegt.
Die Größe einer Strecke bemisst sich nicht danach, wie weit der Zug fährt, sondern danach, an wie vielen Bahnhöfen er hält.
Die verkettete Liste ist eine grundlegende Datenstruktur in der Informatik und wird oft bei der Implementierung anderer Datenstrukturen verwendet.
Wie der Name schon sagt, ist sie eine Liste von Knoten, die miteinander verknüpft sind.
Sie ist eine Liste von „Knoten“, wobei jeder Knoten mit seinem Nachbarn oder seinen Nachbarn verknüpft ist.
In einer einfach verketteten Liste ist jeder Knoten nur mit dem Knoten verknüpft, der auf ihn folgt.
In einer doppelt verketteten Liste ist jeder Knoten sowohl mit dem Knoten verknüpft, der vor ihm kommt, als auch mit dem Knoten, der nach ihm kommt.
Wenn du tiefer in verkettete Listen eintauchen möchtest, schau dir diesen Artikel an, der sie mit schönen Zeichnungen erklärt.
Wie diese Übung im C++-Track aufgebaut ist
Verkettete Listen lassen sich auf vielfältige Weise mit unterschiedlichen zugrunde liegenden Datenstrukturen umsetzen. Wir bitten dich hier, deine verkettete Liste objektorientiert umzusetzen.
In der Datei linked_list_test.cpp siehst du, dass eine templatisierte Klasse List verwendet wird.
Du sollst diese Klasse mit den folgenden Mitgliedsfunktionen schreiben:
-
push fügt ein Element am Ende der Liste hinzu,
-
pop entfernt das letzte Element der Liste und gibt es zurück,
-
shift entfernt das erste Element der Liste und gibt es zurück,
-
unshift fügt ein Element am Anfang der Liste hinzu, und
-
count gibt die Gesamtzahl der Elemente in der aktuellen Liste zurück.
Zum Schluss möchten wir, dass du zusätzlich zu den oben beschriebenen Methoden noch erase umsetzt.
erase nimmt ein Argument entgegen, nämlich den Wert, der aus der verketteten Liste entfernt werden soll.
Kommt der Wert mehrfach vor, soll nur das erste Vorkommen entfernt werden.
Die Funktion soll zurückgeben, ob ein Element gelöscht wurde oder nicht.
Auch wenn es nicht getestet wird, möchtest du vielleicht eine Exception auslösen, wenn pop und shift auf einer leeren List aufgerufen werden.
Quelle
Klassisches Thema der Informatik
