Verkettete Listen in C++ und Visual Basic (Informatik)


zurück zu Informatik, Homepage


3. Realisierung einer doppelt verketteten Liste in C++

Da die verkettete Liste eine sehr einfache und grundlegende Datenstruktur ist, gibt es auch sehr viele unterschiedliche Realisierungmöglichkeiten. Diese sind natürlich auch von der verwendeten Programmiersprache abhängig. Da sie so grundlegend ist kommt sie auch in sehr vielen Büchern vor, und auch im Internet gibt es unzählige Seiten zu diesem Thema.

Meine Realisierung ist daher nur eine von vielen Möglichkeiten.

In C++ ist es zweckmäßig die gesamte Liste mit Hilfe von zwei Klassen zu implementieren:

Realisierung einer doppelt verketteten Liste in C++

Anmerkung: Dies hier ist kein C++-Kurs. Ich beschreibe hier nur kurz die wesentlichen Punkte für eine mögliche Realisierung der doppelt verketteten Listen in C++.
Ich gehe davon aus, dass der/die Leser(in) die Grundlagen von C++ kennt und diese auch beherrscht. Begriffe wie Klasse, Konstruktor, Destruktor, Member-Variablen usw. sind ihnen also bekannt. Wenn nicht so empfehle ich das Buch C++ in 21 Tagen [2].

C++ stellt keine speziellen Befehle und Unterprogramme dafür zur Verfügung. Es muss also alles selbst programmiert werden!

nach oben

3.1. Klasse CNode

In C++ lässt sich ein einzelner Knoten sehr gut durch eine Klasse beschreiben. Diese Klasse kann z.B. wie folgt deklariert werden (Datei CNode_h.pdf (30 KB) )

Anmerkung zu den Zeilennummern: Die Zeilennummern sind nicht Bestandteil des Quellcodes. Sie dienen hier nur der besseren Orientierung. In vielen Entwicklungsumgebungen können diese so eingestellt werden, dass sie automatisch vom Editor hinzugefügt werden.

Da diese Klasse nur einen Knoten beinhaltet, ist sie auch sehr einfach. Hier beinhaltet dieser Knoten als Daten nur eine Integer-Variable (hier m_nValue, Zeile 53) in Form einer Member-Variable und die Zeiger zum vorhergehenden und folgenden Knoten (m_pLast und m_pNext, Zeilen 53 und 54).

Da die Funktionen zum Setzen und Auslesen dieser Membervariablen sehr einfach sind wurden diese gleich in der Header-Datei ausgeführt, Zeilen 42 bis 48.
Die Realisierung der restlichen Funktionen (hier eigentlich nur die Konstruktoren) erfolgt in der Datei CNode_cpp.pdf (36 KB). Auch diese sind sehr einfach, da nur die Membervariablen initialisiert werden müssen.

nach oben

3.2. Klasse CLinkedList

Die KLasse CLinkedList ist schon etwas umfangreicher. Diese Klasse realisiert die verkettete Liste, so wie sie in Kapitel 2 beschrieben wurde, daher ist eine ausführliche Beschreibung hier nicht mehr notwendig. Auch hier dient wieder eine Header-Datei zur Deklaration ( LinkedList_h.pdf (35 KB) ) und eine Datei, welche den Quellcode beinhaltet ( LinkedList_cpp.pdf (123 KB) ).

Anmerkungen zur Klassendefinition (CLinkedList.h):

Da diese Klasse auch die CNode-Klasse benötigt muss dies hinzugefügt werden (siehe Zeile 20).

Das Scrollen, also das Blättern innerhalb der Liste, wurde mit nur einer Memberfunktion realisiert (Zeile 57). Da es aber 4 Scrollmöglichkeiten gibt, ist ein Übergabeparameter der die Scrollart bestimmt notwendig. Dies wird hier mit einer so genannten Aufzählungsvariable realisiert (Zeilen 24 bis 30).

Das Hinzufügen eines neuen Knotens, das Anzeigen der gesamten Liste und das Löschen eines Knotens oder der gesamten Liste ist mit je einer eigenen Memberfunktion realisiert (Zeilen 50 bis 55).
Da bei diesen Funktionen während der Laufzeit Fehler entstehen können, z.B. wenn kein neuer Knoten mehr hinzugefügt werden kann, oder wenn versucht wird eine leere Liste zu löschen, dann sollte das aufrufende Programm über diesen Fehler informiert werden. Daher ist es gängige Praxis, Funktionen, die einen Fehler verursachen können mit einem Rückgabewert zu versehen. Dieser Rückgabewert gibt dann den Fehler in Form einer Zahl (Fehlercode) an das aufrufende Programm zurück. Tritt während der Ausführung dieser Funktion kein Fehler auf, so ist es üblich den Wert 0 zurückzugeben. Dieser Fehlermechanismus muss natürlich selbst ausprogrammiert werden, und ist nur eine von mehreren Möglichkeiten zur Fehlererkennung. Hier wurde diese einfache Methode für sämtliche Memberfunktionen gewählt (Zeilen 50 bis 57).

Anmerkungen zu CLinkedList.cpp):

Aufgrund der ausgiebigen Kommentare und der ausführlichen Abhandlung in Kapitel 2 ist hier eine weitere Beschreibung überflüssig!

Zu Beachten ist vielleicht, dass hier Speicher dynamisch angefordert wird. Daher ist es auch ganz wichtig dass der Destruktur diesen Speicher wieder freigibt. Hier, indem er einfach die Memberfunktion DeleteList() aufruft. Denn diese Memberfunktion erfüllt genau diesen Zweck (Zeilen 96 bis 98).

nach oben

3.3. Demonstrationsbeispiel

Anhand eines einfachen Demonstrationsbeispiels soll nun die Klasse CLinkedList ausprobiert werden. LinkedList_Demo.pdf (36 KB) zeigt dieses sehr einfache und selbsterklärende Demonstrationsbeispiel. Es sollen nur die realisierten Funktionen angewendet werden, also Knoten hinzufügen, Liste anzeigen, Knoten löschen und Scrollen. Auf eine Werteingaben wurde bewusst verzichtet, da dies das Demonstrationsbeispiel nur unnötig komplex machen würde.

Die folgende Abbildung zeigt einen Bildschirmausdruck des Ergebnisses des Demonstrationsbeispiels (Konsolenanwendung).

Realisierung einer doppelt Verketteten Liste in C++ (Demo)
nach oben


zurück zu Informatik, Homepage

Autor: Buchgeher Stefan
Erstellt: 10. März 2007
Letzte Änderung: