Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!
Ich versuch mich mal an einem Tutorial ... ich hoffe es ist nicht zu wirr *ggg* und nicht falsch, aber ich hab's eig. getestet dürfte keine Fehler drin haben.
Willkommen zu meinem Tutorial über verkettete Listen
Theorie
verkettete Liste (linked list)
Element an erster Stelle einfügen
beliebiges sowie erstes Element holen
Länge der Liste
Element an erster Stelle löschen
doppelt verkettete Liste (double linked list)
Element an letzter Stelle einfügen und löschen
Element an beliebiger Stelle einfügen und löschen
Source Code
1. Theorie
//<!Statement zurückgezogen *ggg*-->
Auf jeden Fall ist dieses Tutorial eher an Anfänger gerichtet und dient auch eher dafür bestimmte Mechanismen von C++ an einem konkreten Beispiel zu sehen.
(Naja, einen praktischen Nutzen hat das Tutorial vielleicht doch, wer mit dem Gedanken spielt Informatik zu studieren, da wird sowas sicherlich drankommen. Zumindest war es bei mir so, keine Ahnung wie es an anderen Hochschulen ist.)
Am Anfang ein kleiner Theorieteil. Was sind Listen und wozu brauch ich sie?
Nun eine Liste ist eine Datenstruktur die quasi als Container für mehrere Elemente dient. Selbst als Anfänger dürfte man mindestens eine weitere Datenstruktur kennen die etwas ähnliches macht, und zwar denn Array.
Da kann man sich sicherlich Fragen wozu Listen ich hab doch Arrays. Nun eine Liste ist nicht besser als ein Array, sie ist anders und je nachdem was man machen will muss man sich entscheiden was man nutzt.
Eine grobe Aufschlüsselung für was sich eine Liste und für was sich ein Array eher lohnt. Das ist wirklich sehr grob und geht immer vom „worst case“ aus. (Die Zahl in der Klammer gibt an wieviele andere Elemente der Datenstruktur maximal „angefasst“ werden müssen. n:=Gesamtzahl der Elemente)
C-/C++-Quelltext
1
2
3
4
5
6
7
8
9
10
11
12
13
Liste Array
einfügen:
beliebig: O(n) O(n)
am Anfang: O(1) O(n)
am Ende: O(1) O(1)
löschen:
beliebig: O(n) O(n)
am Anfang: O(1) O(n)
am Ende: O(1) O(1)
suchen:
„normal“: O(n) O(n)
über Index: O(n) O(1)
mit Iterator: O(n) O(n)
Wie man sieht ist ein Array immer dann sinnvoll wenn man nur über Indizes sucht und nur am Ende einfügen und löschen will. Wenn man am Anfang und am Ende einfügen und löschen will und nicht so viele Suchen durchführen muss ist die Liste auf jeden Fall die bessere Lösung. Wenn man sowohl das eine wie das andere brauch, dann muss man sich überlegen wo man Abstriche machen kann und danach entscheiden.
So genug Theorie, fangen wir an. Ich werde versuchen dieses Tutorial aufbauend zu gestalten, sprich erst das Nötigste damit es Funktioniert und dann Verbesserungen und Erweiterungen einbauen.
Zwecks des objektorientierten Ansatzes wird die Liste bei mir durch eine Klasse repräsentiert. Als erstes muss man sich überlegen was man alles brauch um etwas in einer Liste zu speichern.
#include<cstdlib.h>template<typename T>class List
{
private:struct Item
{
T m_data;
};
public:inline List()
{
}
inline~List()
{
}
};
Für die Liste benutzte ich ich ein Template, für die die sich nicht mit Templates auskennen ist natürlich die MSDN zu empfehlen, aber als kleine Verständnishilfe ist zu sagen das dieses Template dafür sorgt das diese Liste mit allen möglichen Datentypen gefüllt werden kann. Die Liste wird dann später so initialisiert.
C-/C++-Quelltext
1
2
3
//[...]
List<int>* list =new List<int>();
//[...]
Und der Compiler erstzt dann jedes T in der Klasse durch, in diesem Fall, int. Die Liste kann natürlich auch für selbst definierte Datentypen erstellt werden.
Noch etwas zu dem Wörtchen „inline“, dies zeigt dem Compiler, in diesem Fall, nur an das diese Methode in die Klasse geschrieben wird und nicht außerhalb in einer cpp, die Verwendung ist ähnlich wie bei dem this-Pointer nicht zwingend notwendig, d. h. es würde auch ohne funktionieren. (Ich benutzt normalerweise weder this noch inline, aber da das ein Tutorial ist wollt ich's ma' "richtig" machen)
So jetzt können schon Daten in der Liste gespeichert werden, aber wir bekommen sie noch nicht in die Liste, also brauchen wir eine Methode die Liste mit Elementen zu füllen. Als erstes versuchen wir ein Element vorne in die Liste einzufügen.
So jetzt können wir zwar neue Elemente erstellen aber das ist nicht wirklich eine Liste, denn die Items haben keinen Bezug zu einander. Um dieses Problem zu lösen müssen wir uns Pointer zu nutzte mache. Wir geben einfach jeden Element der List seinen Nachfolder mit und schon hat man eine verkettete Liste (LinkedList).
C-/C++-Quelltext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private:struct Item
{ //[...]
Item* m_succ; //NEU successor = Nachfolger
};
public://[...]
inlinebool pushFront(T& _data)
{
Item* current =new Item();
current->m_data = _data;
current->m_succ =?;//NEU
}
Und schon tit sich das nächste Problem auf, woher soll das Element wissen welches Element der Liste nun sein Nachfolger ist? Die beste Lösung ist es ein erstes Element zu definieren, somit hat man auch immer einen Einstiegspunkt in die Liste.
Das aktuelle erste Element wird zum Nachfolger des neu Eingefügten, und dieses danach zum ersten Element der Liste gemacht.
So wir können nun endlich Elemente in der Liste speichern und die Liste ist auch schon ein Konstrukt welches man wirklich Liste nennen kann. Nur Elemente reinschaufel nützt uns relativ wenig, man muss sie natürlich wieder irgendwie aus der Liste auslesen können, darum kümmern wir uns jetzt.
private:inline Item* get(unsignedint _index)//NEU
{
Item* current =this->m_first;
if(current == NULL || _index >=this->m_length) return NULL;
for(int i =0; i < _index; i++)
{
current = current->m_succ;
}
return current;
}
public://[...]
inline T get(int _index)//NEU
{
Item* temp =this->getItem(_index);
if(temp == NULL) return NULL;
return temp->m_data;
}
inline T getFirst()//NEU
{
if(this->m_first == NULL) return NULL;
returnthis->m_first->m_data;
}
Da Listenelemente nicht direkt über Indizes angesprochen werden können muss man vom ersten Element zum Nächsten gehen und das solange bis man an dem Element ist welches man haben will. Um die Vorzüge der Liste zu nutzen habe ich gleich noch eine Methode geschrieben die mir das erste Element der Liste liefert.
2.3 Länge der Liste
Einen Wert den man sicherlich gut gebrauchen kann ist die Länge der Liste. Man könnte das ähnlich wie die Methode „get(int)“ was bei jedem Aufruf eine Traversion der gesamten Liste zur folge hätte. Oder man legt in der Liste eine neue Variable an in der man die Länge speichert, dass hat 4 Byte zusätzlicher Speicherplatzverbrauch und eine weiter Rechenoperation pro Einfügen oder Löschen eines Elements zur folge. Ich bevorzuge die zweite Variante.
Methode 1
C-/C++-Quelltext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public://[...]
inlineint length()//alternativ
{
Item* current =this->m_first;
int count =0;
while(current != NULL)
{
current = current->m_succ;
count++;
}
return count;
}
Die ersten Methode funktioniert wie ich schon sagt nach dem Prinzip der get-Methode nur läuft die Schleife nicht bis zu einem bestimmten vorher übergebenen Wert sondern solange bis das Element NULL ist, zurückgegeben wird die Anzahl der Schleifendurchläufe -> Anzahl der Elemente die nicht NULL sind.
In der zweiten Methode wird durch aufrufen von length() die Membervariable length zurückgeben, damit diese Variable die aktuelle Länge der Liste beinhaltet muss sie bei jedem hinzufügen eines Elements erhöht und bei jedem löschen erniedrigt werden.
2.4 Element an erster Stelle löschen
Apropos löschen, wir können ja noch gar nix aus der Liste entfernen, dass werden wir jetzt implementieren. Als erstes werden wir das Löschen des erste Elements einer Liste annehmen, indem wir uns das erste Element holen, dann den Nachfolger zum ersten Element machen und zum Schluss das temporäre Element, welches die Informationen des alten ersten Elements beinhaltet, löschen.
So, jetzt haben wir schon eine funktionierende Liste, wir können vorn einfügen und löschen, sowie uns ein Element an beliebiger Stelle geben lassen. Aber das Konstrukt bietet immer noch nicht alle die Vorteile die ich am Anfang erwähnte.
Um das Bestmögliche aus einer einfach verketteten Liste zu holen können wir uns das letzte Element der Liste speichern, ebenso wie wir es mit dem ersten Element gemacht haben.
So nun wird das letzte Element gespeichert, damit das geschieht müssen wir bei pushFront() prüfen ob das Element das wir einfügen wollen das erste Element ist (current->succ == NULL), wenn das der Fall ist ist dieses Element sowohl erstes als auch letztes Element der Liste.
Wo wir jetzt schon das letzte Element speichern können, was ist mit dem Einfügen oder Löschen eines Elements am Ende? Dies ist ja eines der Vorteile von Arrays. Probieren wir es einfach mal
So, wir erstellen ein neues Element und sagen der Nachfolger ist NULL, nun haben wir aber ein Problem. Wir müssen dem Element welches vorher das Letzte war mitteilen das es nicht mehr das Letzte ist sonst würden wir es überschreiben und zudem müssen wir eine Verbindung zwischen dem letzten und dem neuen letzten Element schaffen. Ein ähnliches Problem hatten wir am Anfang schon mal, beim Einfügen am Anfang der Liste. Um uns zu behelfen haben wir dem Element seinen Nachfolger gegeben, also müsste uns jetzt das Speichern des Vorgängers weiterhelfen. Und damit hätten wir eine ...
So, der Predessor ist implementiert und die schon vorhandenen Methoden die dieses verwenden wurden dementsprechend erweitert. Beim pushFront() wird der Vorgänger auf NULL gesetzt und wenn schon Elemente in der Liste sind müssen wir dem Nachfolger des gerade eingefügten Elements sagen das dieses nun sein Vorgänger ist(current->m_succ->m_pred = current. Sieht komisch aus, ist aber so *ggg*. Bei popFront() müssen wir dem neuen ersten Element nur mitteilen das er keinen Vorgänger mehr hat(current->m_succ->m_pred = NULL.
Nun können wir uns endlich der push-/popBack()-Methoden annehmen.
3.1 Element an letzter Stelle einfügen und löschen
In pushBack() wird ein neues Element erstellt, der Vorgänger ist das letzte Element, der Nachfolger ist NULL. Wenn der Vorgänger, sprich das letzte Element, NULL ist wird dieses Element zum ersten Element der Liste. Wenn nicht wird dieses Element zum Nachfolger seines Vorgängers gemacht und schlussendlich wird das Element zum letzten Element der Liste gemacht. Die Methode popBack() ist genauso aufgebaut wie popFront(), nur wurden „first“ und „last“ ausgetauscht, sowie „pred“ und „succ“.
3.2 Element an beliebiger Stelle einfügen und löschen
Um die Implementierung der Liste zu vervollständigen fehlt eigentlich nur noch das Einfügen und Löschen an einer beliebigen stelle.
Bei push() und pop() bin ich zur Veranschauung mal zwei verschiedene Wege gegangen, bei push() benutze ich bei passenden Fällen die schon vorhandenen Implementierungen pushFront()/-Back() und pop() ist komplett neu implementiert.
In der push()-Methode prüfe ich als erstes ob der Index an dem ich das Element einfügen will größer ist als die aktuelle Länge der Liste, wenn das der Fall ist liefert die Methode ein false zurück, da in einer verketteten Liste keine Lücke sein kann. Man könnte in diesem Fall auch einfach hinten anfügen, was ich aber persönlich als irreführend einstufen würde.
Danach wird geprüft ob der Index gleich 0 ist wenn das der Fall ist wird pushFront() aufgerufen.
Im zweiten Fall Index gleich Länge der Liste kann einfach pushBack() aufgerufen werden, denn das letzte Element der Liste ist ja an Position m_legth-1.
Der letzte Fall behandelt den eigentlichen Sinn dieser Methode, ein Element irgendwo in der Mitte der Liste zu platzieren. Das könnte recht tricky werden, da wir aber durch die ersten beiden Fälle schon durch sind wissen wir auf jeden Fall schon das die Liste mindestens zwei Elemente beinhaltet und das das Element das wir einfügen wollen nicht das erste und auch nicht das letzte Element der Liste sein wird und somit wird das Problem wieder ganz einfach.
Ich denke diesen Fall beschreibe ich mit einem Beispiel. Stellen wir uns vor das die Liste schon zwei Elemente beinhaltet, an Index 0 und 1 (logischerweise). Nun wird die Methode mit dem Paramenter Index = 1 aufgerufen, somit würden alle if-Bedinungen nicht erfüllt und schließlich der letzte else-Zweig ausgeführt. Das erste was gemacht werden muss ist sich das Element zu holen welches aktuell an der Position Index ist, dieses wird nun zum Nachfolger des Neuen Elements und dessen Vorgänger wird zum Vorgänger des Neuen. Danach muss dem Vorgänger des alten Elements mitgeteilt werden das sein Nachfolger nicht mehr das alte sondern das neue Element ist. Zum Schluss muss dem Alten nur noch gesagt werden das dessen Vorgänger nun das neue Element ist und schon haben wir wieder eine komplette doppelt verkettete Liste mit drei Elementen.
Ich hab da auch gleich mal spontan was vorbereitet:
Fehlt nur noch die pop()-Methode, dort wird erst einmal das Element der Liste gesucht welches gelöscht werden soll, wenn dies aus irgendeinem Grund NULL ist, Index zu groß oder ein anderer Fehler, wird false zurückgegeben. Als erstes wird geprüft ob der Vorgänger des Elements NULL ist wenn ja wissen wir das wir das erste Element haben und so müssen wir den Nachfolger des Elements zum First-Element der Liste machen. Wenn das nicht der Fall ist hat des Element irgendeinen Vorgänger und diesem muss mitgeteilt werden das sein Nachfolger nicht mehr das Element ist, sondern der Nachfolger des Elements. Im zweiten if-else-Block prüfen wir ob der Nachfolger des Elements NULL ist, wenn ja wissen wir das wir das letzte Element haben und genau umgedreht zum First-Pointer müssen wir in dem Fall den Vorgänger des Elements zum Last-Element der Liste machen. Wenn das nicht der Fall ist müssen wir dem Nachfolger des Elements mitteilen das dessen Vorgänger nun nicht mehr das Element ist sondern der Vorgänger des Elements. Somit wären alle nötigen Pointer „umgebogen“ und wir können das Element löschen ohne das die Kette auseinander gerissen würde.
so das war's erstmal, die Liste könnte man noch um einen Iterator erweitern, welcher die Liste noch Vorteilhafter machen würde ... ma' sehen vielleicht mach ich demnächst noch 'n Update
wenn das hier gut angenommen wird würd' ich in nächster Zeit ein mehrteiliges Tutorial über Bäume verfassen, momentan geplant:
binärer Baum, arithmetischer Baum und Rot-Schwarz-Baum
ob ich 2-3-4-Bäume auch mitmache weis ich noch nicht ... ma' sehen wie viel Zeit ich locker machen kann [list=][/list][list=][/list][list=][/list]
aktuelle Projekte:
Ruby on Rails
XNA & Touchless
Progr. mobiler Endgeräte (GPS Trekking)
Ein Satz gleich vorne Weg eine selbst programmierte Liste im eigenen Projekt zu benutzen ist in der Regel nicht sinnvoll, da diese Liste nie so performant sein wird wie die Listen in den verschiedenen Bibliotheken
Ich hab das Tutorial noch nicht gelesen, aber ich werds heut abend mit großer Wahrscheinlichkeit mal tun. Was mir beim "Überfliegen" jedoch aufgefallen ist, möchte ich dir jedoch noch nicht vorenthalten.
1. Das Tutorial ist sehr lang, da ist meiner Meinung nach ein Inhaltsverzeichnis/Gliederung sehr schön. Kannst dir ja eines aus meinen Tutorials hier abkupfern.
2. Der erste Code-Block ist sehr wirr, wirf noch mal einen blick auf die Formatierung.
3.
C-/C++-Quelltext
1
2
3
#include <stdlib.h>template<typename T>class List
bitte cstdlib benutzen und zwischen > und class ein leerzeichen, das sieht irgendwie lieblos aus.
4.
C-/C++-Quelltext
1
2
3
4
5
6
7
inline List()
{
}
inline~List()
{
}
bitte inline wegmachen, es ist das selbe. Sofern wie ich glaube gelesen zu haben, sind alle Methoden aus Templates inline. Die big 3, sollte man sowieso nie inline machen.
Irgendwie macht die Sache mit deiner Code-Formatierung alles irgendwie wirr. z. B. oben machst du zwischen klammer und Text kein Leerzeichen, unten jedoch nach der Klammer. Dies kann über den ganzen Quelltext verfolgen. Hier solltest du etwas mehr einheitlichkeit zeigen. Dein Code repräsentiert ja dich, also sollte er nicht uneinheitlich sein - das könnte als "konfus" gelten.
7. Die Grafik: Gut Photoschop hätte man nicht benutzen müssen, aber damit das nicht so gekritzelt aussieht: Öffne PowerPointer oder ein anderen Präsentationsprogramm und mach da alles mit Pfeilen und Kästchen. Schwupp hast du eine sehr schöne klare Grafik, die man sich gerne anguckt.
Ansonsten vermiss ich noch paar kommentare und am Ende ein download des ganzen Codes als ZIP.
Wie schon gesagt, vom Inhalt her kann ich noch nichts sagen, aber ich werd das Tutorial noch auseinanderrupfen und hoffe du kannst mit den 7 - 8 Punkten Kritik schon was anfangen.
bitte inline wegmachen, es ist das selbe. Sofern wie ich glaube gelesen zu haben, sind alle Methoden aus Templates inline. Die big 3, sollte man sowieso nie inline machen.
Alle Methoden die in einer Klassendefinition definiert werden sind automatisch inline. Aber das die "Big 3" nie "inline" deklariert werden sollten ist mir unverständlich! Dann dürfte man die Definition auch nie direkt in die Klassendefinition schreiben!
Zitat
binärer Baum, arithmetischer Baum und Rot-Schwarz-Baum
Ein RB Tree, ist doch ein Binärbaum! :-p Oder meintest du einen Binären Suchbaum?
Achja: Bitte verstärkt auf Const-Correctness achten!
@unsigned long
zu 3. und 6., das sind Tippfehler ... hab teilweise in OpenOffice programmiert *ggg*, werd es noch ma' durchschauen ... das Bild hatt' ich schon kurz danach geändert
und den Rest werd' ich mir noch anschauen
@David_pb
ja bessere Formulierung wäre gewesen
Binäre Bäume und die Spezialfälle arithmetischer Baum und Rot-Schwarz-Baum
(da ein rbTree ein sich einigermaßen selbstbalancierenter binärer Baum ist)
edit:
hab ich glatt übersehe
Zitat von »"David_pb"«
Zitat von »"Ba'el"«
Ein Satz gleich vorne Weg eine selbst programmierte Liste im eigenen Projekt zu benutzen ist in der Regel nicht sinnvoll, da diese Liste nie so performant sein wird wie die Listen in den verschiedenen Bibliotheken
Wieso denn?
naja wie soll ich sagen, weil man es eben kaum schafft ... wenn du es schaffst ... dann ... dann geb ich dir 'n Kaffee aus
ein Dozent von mir, der leider nicht mehr an meiner FH ist, hat letztens erzählt das er das mal versucht hat, ich weis jetzt nicht ob mit 'ner Liste oder mit 'nem Baum, auf jeden Fall hat er das komplett in Assembler geschrieben ... und seins war trotzdem langsamer,
und er ist ein guter Programmierer, arbeitet nicht umsonst grad als lead programmer
aktuelle Projekte:
Ruby on Rails
XNA & Touchless
Progr. mobiler Endgeräte (GPS Trekking)
Müsste es bei den Landau-Symbolen nicht O(1) antatt O(0) heißen, wenn der Aufwand konstant ist?
Ich hab es es bisher auch nur kurz überflogen, aber so auf den ersten Blick sieht es schonmal ganz gut aus. Ich werds mir mal genauer ansehen wenn ich mehr Zeit habe.
naja wie soll ich sagen, weil man es eben kaum schafft ... wenn du es schaffst ... dann ... dann geb ich dir 'n Kaffee aus
ein Dozent von mir, der leider nicht mehr an meiner FH ist, hat letztens erzählt das er das mal versucht hat, ich weis jetzt nicht ob mit 'ner Liste oder mit 'nem Baum, auf jeden Fall hat er das komplett in Assembler geschrieben ... und seins war trotzdem langsamer,
und er ist ein guter Programmierer, arbeitet nicht umsonst grad als lead programmer
Assembler ist kein garant für schnellen Code! Aber auch die Listen aus "diversen" Bibliotheken wurden "nur" programmiert. Und häufig sind das möglichst allgemeine Implementationen die für Spezialfälle z.T. extrem optimiert werden können.
Edit:
Hab mal einen schnellen Vergleich meiner Implementation mit std::list<> gemacht. Getestet hab ich die verfügbaren Operationen (push_back, push_front, insert, pop_back, ...). (Threasupport, Checked Iteratoren usw hab ich ausgeschaltet)
Und tataaaa... Meine Liste ist im Schnitt 23% schneller also std::list! :-p
Edit:
Hab mal einen schnellen Vergleich meiner Implementation mit std::list<> gemacht. Getestet hab ich die verfügbaren Operationen (push_back, push_front, insert, pop_back, ...). (Threasupport, Checked Iteratoren usw hab ich ausgeschaltet)
Und tataaaa... Meine Liste ist im Schnitt 23% schneller also std::list! :-p
nich' schlecht, wir ham nur mal so 'nen Test mit Java gemacht, und keine Implementation im Seminar war schneller als die java.util.LinkedList ...
(kannst du mal den Code deiner "Test-Main" posten will ma' meine Testen)
aktuelle Projekte:
Ruby on Rails
XNA & Touchless
Progr. mobiler Endgeräte (GPS Trekking)