Einführung
Stellen wir uns vor, wir schreiben ein Programm, welches eine Filmsammlung verwalten soll. Einfachheitshalber werden nur Merkmale wie Titel, Erscheinungsjahr und Genre erfasst.
Diese Daten werden in einer Datenstruktur zusammengefasst.
struct Film
{
std::string titel;
unsigned int jahr;
int genre;
};
Jetzt stellt sich die Frage wie die Filme in unserem Programm intern dargestellt werden.
Man könnte ein Array mit Filmen anlegen.
const int filmAnzahl = 100; Film filme[filmAnzahl];
So weit so gut. Wir programmieren das Programm fertig und verschicken es an alle unseren Bekannte und Freunde. Es dauert nicht lange bis sich einer von ihren beschwert, dass das Programm nicht mehr als 100 Filme verwalten kann. Es bleib uns nichts anderes übrig als den Quellecode des Programms abzuändern um die Filmenanzahl anzupassen. Nicht gerade optimal.
Man könnte auch gleich ein Array für 10000 Filme anlegen, damit auch der größte Filmfreak zufrieden ist, aber dann nimmt man in Kauf, dass das Programm den Arbeitsspeicher unnötig blockiert, wenn vielleicht nur 200 Filme verwaltet werden.
Wie man sieht, ist die Verwendung eines statischen Arrays in diesem Fall nicht optimal. Man benötigt eine dynamische Datenstruktur, die nur sowieso Objekte verwaltet, die auch wirklich nötig sind. Wohl die einfachste dynamische Datenstruktur ist eine einfach verkettete Liste.
Einfach verkettete Liste
Eine Liste ist eine Kette aus beliebig vielen Listenelementen (Knoten), die untereinander über Zeiger verbunden sind. Die Anzahl von Elementen kann zu Laufzeit des Programms beliebig variieren.
Jedes Listenelement besteht aus dem Datenbereich und einen Zeiger, der auf das nächste Listenelement zeigt. Mit dem Datenbereich ist eine oder mehrere Variablen gemeint, die die eigentlichen Daten(Werte, Strings u.s.w.) speichern.
Schematische Darstellung eines Listenelements:
Ein einzelnes Element hat keine Informationen über seine Position in der Liste. Alles was es weiß, ist die Adresse seines Nachfolgers. Eine Abbildung soll das ganze Prinzip noch mal verdeutlichen.
Schematische Darstellung einer einfach verketteter Liste mit vier Elementen:
Das erste Element in der Liste wird als Listenkopf (head oder root) bezeichnet und das letzte als Listenende (tail). Da das letzte Element keinen Nachfolger hat, wird der Zeiger auf Null gesetzt, damit man später das Listenende erkennen kann.
So eine Liste wird als einfach verkettet bezeichnet, da die Elemente untereinander nur eine 1-fache Verbindung haben. Es gibt auch eine doppelt verkettete Liste, aber dazu kommen wir später.
Kommen wir zu der Implementierung.
// Definition eines Listenelements
struct Listenelement
{
// Das sind die Daten die wir verwalten wollen (Datenbereich)
Film film;
// Zeiger auf den Nachfolger (Zeiger)
Listenelement *nachfolger;
};
Damit haben wir ein Listenelement definiert, auf dem wir unsere Liste aufbauen.
Wie wir bereits wissen, beginnt die Liste mit einem Listenkopf, also erstellen wir dynamisch einen.
// Listenkopf erstellen Listenelement *listenkopf = new Listenelement();
Da der Listenkopf auch ein Element der Liste ist müssen wir es auch mit Daten belegen.
// Listenkopf mit Daten belegen listenkopf->film.titel = "Stargate"; listenkopf->film.jahr = 2005; listenkopf->film.genre = 1; // Den Zeiger auf Null setzen, da kein weiteres Element in der Liste existiert listenkopf->nachfolger = NULL;
Nach dem der Listenkopf erstellt wurde, können weitere Listenelemente in die Liste eingefügt werden.
Die Erzeugung von Elementen erfolgt durch dynamische Speicherreservierung.
// Ein Listenelement erzeugen Listenelement *neuesListenelement = new Listenelement(); // Element mit Daten belegen neuesListenelement->film.titel = "V"; neuesListenelement->film.jahr = 2009; neuesListenelement->film.genre = 1; neuesListenelement->nachfolger = NULL;
Nach dem ein neues Listenelement erstellt wurde, hat es noch keine Verbindung zum Listenkopf.
Symbolische Darstellung von beiden Elementen im RAM:
Um die Elemente zu verbinden, müssen wir den Nachfolgerzeiger vom Listenkopf auf das zweite Listenelement (neuesListenelement) setzen.
Und das geschieht durch eine einfache Adressenzuweisung.
// Listenkopf mit neuesListenelement verbinden listenkopf->nachfolger = neuesListenelement;
Symbolische Darstellung von beiden verbundenen Elementen im RAM:
Um mit einer Liste produktiv arbeiten zu können, erstellen wir eine Klasse und implementieren elementarste Listenoperationen.
// Grundgerüst
class FilmListe
{
// Definition eines Listenelements
class Listenelement
{
public:
// Konstruktor
Listenelement(Film film)
{
this->film.genre = film.genre;
this->film.jahr = film.jahr;
this->film.titel = film.titel;
this->nachfolger = NULL;
}
// Das sind die Daten die wir verwalten wollen (Datenbereich)
Film film;
// Zeiger auf den Nachfolger (Zeiger)
Listenelement *nachfolger;
};
// Listenkopf
Listenelement* kopf;
// Listenende
Listenelement* ende;
public:
// Konstruktor
FilmListe(void)
{
kopf = ende = NULL;
}
// Destruktor
~FilmListe()
{
}
// einen Film in die Liste einfügen
void hinzufuegen(Film film)
{
// ...
}
// prüft ob die Liste leer ist
bool istLeer()
{
return (kopf == NULL) ? true : false;
}
// Liste löschen
void loeschen(void)
{
// ...
}
// zeigt alle Listenelemente
void elementeAnzeigen(void)
{
// ...
}
};
Wie man ein neues Element erstellen haben wir bereits gesehen. Man erstellt dynamisch ein neues Element und lässt den Zeiger im letzten Element auf das neue Objekt zeigen. Wir müssen uns also merken, welches Element an der letzten Position ist. Dazu wird das Attribut Listenelement* ende verwendet. Dieses wird nach jedem einfügen in die Liste aktualisiert.
Zusätzlich muss unterschieden werden ob die Liste leer ist oder nicht, denn in einer leeren Liste können wir nicht auf das letzte Element zugreifen.
Zusammengenommen ist die Methode recht überschaubar.
// einen Film in die Liste einfügen
void hinzufuegen(Film film)
{
// Ein neues Listenelement erstellen und mit 'film' initialisieren
Listenelement *neuesListenelement = new Listenelement(film);
// liste ist leer
if(istLeer())
ende = kopf = neuesListenelement;
else
{
// das letzte Element zeigt auf das neue Element
ende->nachfolger = neuesListenelement;
// das neue Element wird zum Letzten
ende = neuesListenelement;
}
}
Damit wir überhaupt überprüfen können ob die Liste wie gewünscht funktioniert, brauchen wir eine Methode die uns den Listeninhalt auf den Bildschirm bringt.
// zeigt alle Listenelemente
void elementeAnzeigen(void)
{
// aktueller Knoten
Listenelement *p = kopf;
// solange der Knoten nicht Null ist, also das Ende nicht erreicht ist...
while(p != NULL)
{
// ...Inhalt ausgeben
std::cout << "Titel: "<< p->film.titel.c_str()
<< " Jahr: " << p->film.jahr
<< " Genre: " << p->film.genre << std::endl;
// der Nachfolger wird zum aktuellen Knoten
p = p->nachfolger;
}
}
Der Eifrige hat bereits den Code kompiliert und ausgeführt, doch das war ein etwas zu früh. Warum? Beim Erstellen eines neuen Elementes reservieren mit new Arbeitsspeicher und geben diesen nicht wieder frei. Doch das sollten wir, wenn wir nicht wollen, dass unser Computer wegen eines Arbeitsspeicherfehlers abstürzt. Also bauen wir uns eine Funktion, die die komplette Liste löscht und den reservierten Speicher wieder frei gibt.
Wir müssen bedenken, dass wir mit dem letzten Element anfangen müssen und dann von hinten nach vorne alle Elemente nacheinander löschen sollten. Würden wir zum Beispiel von vorne anfangen und das erste dynamisch erzeugte Element löschen, würden wir die Adresse zum nächsten Element verlieren und könnten dieses dann nicht finden bzw. löschen.
Eine weitere Schwierigkeit ist, dass wir mit einer einfach verketteter Liste arbeiten, d.h. wir können uns in der Liste nur in eine Richtung bewegen, nämlich nach vorne.
Wir löschen immer das letzte Element in der Liste, dass uns bereits bekannt ist. Zuerst müssen wir aber das vorletzte Element finden, damit wir den Zeiger für den nächsten Durchgang auf null setzen können.
Dieser Vorgang wird so lange wiederholt bis die Liste nur aus einen Element besteht – den Listenkopf. Dieser wird anschließend separat gelöscht.
// Liste löschen
void loeschen(void)
{
if(istLeer())
return;
// solange der Zeiger nicht Null ist, also noch Elemente vorhanden sind...
while(kopf->nachfolger != NULL)
{
// ...suche das vorletzte ELement
Listenelement *vorletztesElement = kopf;
while(vorletztesElement->nachfolger != ende)
{
vorletztesElement = vorletztesElement->nachfolger;
}
// lösche das letzte Element
delete ende;
// das vorletzte Element wird zum Letzten
vorletztesElement->nachfolger = NULL;
ende = vorletztesElement;
}
// zuletzt noch den Listenkopf löschen
delete kopf;
}
Somit hätten wir eine einfache Implementierung einer einfach verketteten Liste.
Kompletten Quellcode downloaden:
Einfach verkettete Liste
Unsere Implementierung funktioniert zwar, ist aber bei Weitem nicht optimal. Zum Beispiel ist die Liste auf eine feste Datenstruktur festgelegt. Man bräuchte also für verschiedene Datenstrukturen unterschiedliche Listenklassen, was selbstverständlich nicht akzeptabel ist.
Des Weiteren ist das Löschen sehr langsam, weil für jedes Listenelement die ganze Liste durchgelaufen werden muss.
Allgemein kann man diese Implementierung nur bedingt in der Praxis einsetzen. Sie verdeutlicht aber die Funktionsweise einer verketteten Liste.
Im zweiten Teil des Tutorials implementieren wir eine doppelt verkettete Liste.
Für Kritik, Anregungen, Fragen oder Verbesserungsvorschläge steht wie immer die Kommentarfunktion zu Verfügung.
Referenz:
Jaja die schöne LinkedList :)
Aber gibt es in PHP nicht sowas wie eine ArrayList in Java, sodass man sich keine LinkedList selber basteln muss?
In PHP wird kein Unterschied zwischen einer Liste und einem Array gemacht. Zumindest soweit ich weiß.
Wie kommst du auf PHP? Im Tutorial wird doch C++ verwendet ;)
In C++ gibt es auch Standardimplementierungen für Listen, nennt sich std::list.
Unabhängig davon ob es eine Standardimplementierung gibt oder nicht gibt, muss man wissen wie es intern aufgebaut ist ;)
Auweia… da war ich gestern Abend wohl etwas verplant. Ich dachte ich wäre bei http://www.phphatesme.com/
Hehe, passiert =)
Werde als nächstes den zweiten Teil des Tutorials schreiben ^^
Meinst du etwa die doppelt verkettete Liste? :D
Ja, doppelt verkettet und als Template Klasse aufgebaut (also generisch, wie man es in Java so nennt).
Vielleicht kommt auch noch was zu Bäumen. Ich habe die Themen sowieso gerade an der Uni.
Bäume klingt gut… Mit denen habe ich mich bisher nur theoretisch befasst, nie aber eine Implementierung dafür gebastelt.
..Bäume?
Bäume sind toll.. hab ich auch in der Uni gehabt..sowohl auf den Folien, als auch um die Gebäude rum.
/sinnloses Kommentar ende
ich versteh zwar nur die Hälfte(oder weniger) von dem was du erklärt hast,aaaaber ich finde es super erklärt.
Leider muss ich den Speicher meines Hirns mit anderen, unwichtigen, Dingen zu Müllen;9
@Butterkeks
ich habe von dir auch keinen anderen Kommentar erwartet :D
pflege mal dein blog! ;P
Interessantes Tutorial, schön, mal den „inneren Aufbau kennenzulernen“.
Vielleicht bringt mich das ja mal wieder dazu, mal wieder zu versuchen, mal wieder meine C++-Fähigkeiten zu verbessern -.- Aber eigentlich bin ich mit C# schon ganz gut bedient… Und sonst müssen deine Tutorials herhalten ;)
Hallo Maxim,
sehr gelungenes Tutorial. Ich arbeite mich gerade in die C++ Standardbibliothek ein und endlich kapiere ich wie so eine Liste intern aufgebaut ist. Die Autoren empfehlen ja auch die Listen nicht selber zu programmieren, jedoch sollte jeder wissen wie sie so in etwa arbeiten. Sehr große Klasse was du hier auf die Beine gestellt hast.
Als nächstes schaue ich mir die doppelt verkette Liste bei dir an.
Viele Grüße und Danke!!
Hi,
das ist echt super verständlich erklärt. Echt toll!
Vielen Dank ;-)
Danke für den Honig! ;-)
Wenn unser Professor so sein Skript oder die Vorlesung gestalten würde wäre ich nen 1er Student. Danke für die schöne Beschreibung am direkten Beispiel.
Danke!
Moin, also das war bissher auch die beste info über verkette listen die ich finden konnte.
Ich muss mal dazu sagen ich schreib bald ne Klausur in Programmieren und ich hasse es wie die pest. Liegt mir überhaupt nicht von daher auch mal schönen dank an das vollständige programmbeispiel. :D sowas hilft mir wirklich weiter.
Aber eine Frage bleibt mir da noch.
Du sagtest wenn man ein Array benutzt und es voll ist muss man in den quellcode um die Anzahl zu erhöhen. So weit so gut.
Nun weiß ich wie ich Programmieren muss um ein Array zu füllen ohne in den quellcode zu gehen, über ne if oder for schleife je nachdem.
Aber wie Programmiere ich ein Programm um in diesem Beispiel einen neuen film anzulegen der dann bei der ausgabe auch mit erscheint?
Hier sind die Filme ja auch alle im Quellcode schon angegeben worden und ein neuer film lässt sich nur im quellcode hinzufügen. Oder sehe ich das falsch??
Wie füge ich hier eine neue Liste hinzu ohne in den Quellcode gehen zu müssen???
Das raff ich echt nicht.
Vielen dank dafür schonmal im vorraus
Hallo,
danke.
Um neue Filme hinzufügen muss man den Benutzer danach Fragen und mit den Eingaben eine Film-Struktur füllen.
Also so ungefähr (in einer do-while-Schleife wegen Wiederholung):
FilmListe filme; bool weiter = false; do { Film film; std::cout<< "Geben Sie den Titel ein" << std::endl; std::cin >> film.titel ; std::cout<< "Geben Sie den Erscheinungsjahr ein" << std::endl; std::cin >> film.jahr ; // weitere Eingaben // Film in die Liste einfügen filme.hinzufuegen(film); std:cout << "noch einen Film hinzufuegen? (0=nein, 1=ja)"<< std::endl; std::cin >>weiter; }while (weiter); // hier ausgabe und weitere programm-steuerungIch habe den Code nicht getestet, aber so ungefähr kann man es machen. Natürlich ist es nur ein Beispiel. Ein benutzbares Programm würde mal wohl mit einer grafischen Benutzeroberfläche erstellen.
Vielen dank dafür.
Ich glaube auch das dieser zusatz für die Klausur nicht relevant sein wird. Aber wenn man schon dabei ist, dann will man das auch mal weitergedacht haben und hier kam ich einfach nicht weiter.
Aber das hilft mir wirklich ungemein weiter.
Hallo,
du hast das wirklich gut erklärt. Wenn ich mir allerdings wieder die Folien meines Info2-Skriptes anschaue, versteh ich wieder nichts mehr.
Um es nochmal kurz in meinen Worten zusammenzufassen:
Ich erstelle eine Struktur, die bspw. name, Matrikelnummer und eben einen Zeiger enthält, der auf die gleiche Struktur zeigt. Also:
struct Bsp { char name; int Alter; … ; struct Bsp *next ; }
Als Kopfelement soll laut Skript einfach ein leeres Datenfeld definiert werden. Das mache ich ja dann bspw. mit struct Bsp *kopf ;
Dieser Zeiger ‚kopf „zeigt“ also auf irgendeinen Speicherplatz, wo der Datentyp dieser Struktur gespeichert werden kann.
Dann geht es mit der Initialisierung der Liste weiter:
kopf = (Bsp*) malloc(sizeof(Bsp)); . Dem Zeiger wird hier die Speicheradresse im Heap übergeben. Dann wird mittels “ kopf->next “ dem Zeiger in der Struktur ein Null-Zeiger zugewiesen.
Bis hierher hätte ich ja also nur einen Kopfzeiger auf mein erstes Element, welches wiederum keine Daten enthält (wie Name, Alter etc..) sondern nur einen Zeiger mit dem namen next.
Im Skript wird nun der folgende Befehl ausgeführt:
void Listeausgeben(void) {
Bsp *cursor= kopf->next ;
while (cursor != NULL) {
printf („%s %d “ , cursor->name , cursor->alter) ;
cursor = cursor->next ; }
Hier komme ich nicht mehr weiter.. Was wird in der ersten Zeile genau gemacht? Es wird wieder ein Zeiger names cursor definiert, aber womit wird dieser nun gleichgesetzt? Erhält der Zeiger „cursor“ die Adresse des zuvor generierten Null-Zeigers? Das Ganze wird dann solange wiederholt, bis das Listenende (NULL) erreicht wird.
Wie kann ich denn nun weitere Elemente einfügen?
Ist etwas lang geworden. Ich hoffe dennoch, dass mir jemand weiterhelfen kann. Dafür bereits im Voraus vielen Dank.
Grüße,
Marius
Hallo Marius,
deine Methode stimmt doch mit meiner ListeAusgeben überein. Der Unterschied ist nur, dass bei mir das Element ‚Kopf‘ bereits Daten enthält. In deiner Implementierung ist das Kopf-Element leer und wird nur verwendet um auf das erste Element kopf->next zu verweisen. Das finde ich persönlich unschön, aber an der Logik der Liste ändert sich grundsätzlich nichts.
Der Zeiger *cursor zeigt zuerst auf das erste Element und wird in jedem Schleifendurchgang geändert.
Das Einfügen von neuen Elementen geschieht genauso wie bei mir. Man erzeugt einfach ein neues Element und lässt den letzten next-Zeiger darauf zeigen.
// Ein neues Listenelement erstellen und mit 'film' initialisieren Listenelement *neuesListenelement = new Listenelement(film); // das letzte Element zeigt auf das neue Element ende->next= neuesListenelement; // das neue Element wird zum Letzten ende = neuesListenelement;Falls du keinen Zeiger auf das letzte Element hast, dann musst du vom Kopf anfangen und bis zum Ende durchlaufen und dann das Element einfügen. Also im Prinzip:
Bsp *cursor= kopf->next ; while (cursor != NULL) { cursor = cursor->next ; } // ab hier zeigt cursor auf das letzte Element // Ein neues Listenelement erstellen und mit 'film' initialisieren Listenelement *neuesListenelement = new Listenelement(film); // das letzte Element zeigt auf das neue Element cursor ->next= neuesListenelement; // das neue Element wird zum Letzten cursor = neuesListenelement;Hallo Maxim,
zunächst vielen Dank für deine schnelle Rückmeldung.
Ich komme allerdings immer noch nicht richtig weiter.. Vor allem, wenn ich ein komplettes Programm über Initialisieren, Einfügen bis hin zum Sortieren schreiben muss. Deshalb hier nochmal ein Beispiel, eventuell kannst du mir ja an diesem die Sache nochmal im Einzelnen erklären.
struct Beispiel {
int data ;
struct Beispiel *next ; }
struct Beispiel *kopf = NULL ;
// Struktur angelegt. Der Zeiger „kopf“ ist ein Nullzeiger und soll später auf das erste Element der Liste zeigen.
// erstes Element erzeugen
void Elementeinfuegen (void) {
struct Beispiel *neu ;
neu = (struct Beispiel *) malloc (sizeof(struct Beispiel)) ;
// Zeiger *neu wird Speicherplatz zugewiesen
if (neu = NULL) { printf=(„Es ist kein Speicherplatz mehr verfügbar“) ; }
else
neu -> next = NULL ;
neu -> data = 1860 ;
// Es wird hier ein neues Element erstellt. In ihm ist zum einen der Wert „1860“ gespeichert und zum anderen entspricht sein Zeiger einem Null-Zeiger. Die Liste wäre hier also zu Ende.
Passt das soweit? Wenn ja, hier noch einige Unklarheiten:
Ich habe anfangs ja den Zeiger *kopf als Null-Zeiger gesetzt. Dieser sollte aber doch als „Kopf-Element“ auf das erste Element zeigen. Wie kann man das dann regeln?
Wie füge ich nun ein weiteres Element dieser Liste hinzu? Wie sortiere ich die Liste, wenn mehrere Elemente in der Liste stehen?
Im Skript ist noch vom Initialisieren und Ausgeben der Liste die Rede. Was hat es damit auf sich?
.. wieder viele Fragen. Ich möchte das Ganze aber endlich mal verstehen..
Ich hoffe dennoch, dass du mir erneut weiterhelfen kannst. Dafür besten Dank :)
Grüße,
Marius
Hallo,
vielen Dank für das wirklich gut zu verstehende Beispiel! Habe es genutzt um mir einen Task Scheduler (für Arduino) daraus abzuleiten. Mein erstes PJ mit Klassen und verketteter Liste. Funktioniert auch super.
Meine Frage, wie sieht die .h und .cpp Datei aus, wenn ich das ganze in extra Dateien verlagern möchte.
Das Grundlegende Prinzip habe ich verstanden (Code in die .cpp und Funktion und Variablen Deklaration in die .h), aber mir ist bei den verschachteln Klassen nicht ganz klar, wie der Syntax aussieht.
Könntest Du bitte Dazu noch Informationen bzw. die .h und .cpp Datei posten?
Vielen Dank!!
Schöne Grüße Jan
Hallo Jan,
danke schön!
Vielleicht hilft dir der zweite Teil des Tutorials weiter: https://www.virtual-maxim.de/dynamische-datenstrukturen-%E2%80%93-doppelt-verkettete-liste/
Da geht es auch darum die geschriebenen Funktionen in einer Klasse zu kapseln.
Ansonsten kannst du noch mal fragen.
Hallo Maxim,
ich habe eine Frage zu den verschachtelten Klassen.
Leider habe ich das noch nicht ganz durchschaut. Kannst du mir
vielleicht erklären was der große Nutzen daraus ist wieso man
diese Klassen verschachtelt?
Vielen Dank im Voraus.
Schöne Grüße,
Timo