c++.de :: Verkettete Liste

Unregistrierter

Hallo!

Ich hab mal ein paar Fragen zu Verkettet Listen. Ich weiß sind sicher grundlegende Dinge drinnen, aber leider weis ich keinen anderen Ausweg, darum Frage ich hier.

Ich hab mir schon in nen Buch das durchgelesen, aber so nen Durchblick hatte ich leider nicht

.

Der Unterschied zwischen Array und Listen ist ja das die Größe ja vorher nicht bekannt sein muss bei Listen, bei Arrays bzw. normalen Pointer aber schon.

Bei normalen Pointern muss man ja pointer++ machen um auf die nächste addresse zu zeigen also um da den nächsten Wert abspeichern zu können stimmt das oder stehn die Werte alle auf den selben Adressen?

Ja und bei Arrays macht mann einfach x++, also man erhöht den Index des Array um den nächsten Wert dann zu speichern.

Wie funktioniert das dann bei den Listen? In meinem code kann ich nirgends einen Ersatz für "pointer++" erkennen? Also zeigen hier verschiedene Pointer auf verschiedene Werte? Und die Werten stehen dann auf verschiedene Adressen?

Und wie funktioniert das genau mit den prev und next pointern?

C++:
1 2 3 4 5 6 7 8	struct spielzug_struct { int posx; int posy; char zeichen; struct spielzug_struct * next; struct spielzug_struct * prev; };

mfg List

Unregistrierter 00:59:32 22.04.2012 Titel:

Diesen Einsatz wirst du bei verketten Listen nicht finden, da die Werte bei Arrays beispielsweise hintereinander stehen, was bei verketteten Listen nicht gegeben ist: Die Zeiger können überall hinzeigen!
Sowas geht vielleicht in C++, wo man Operatoren überladen kann...

Aber du könntest dir einen Iterator bauen mit dem du dann hasNext(it) aufrufst, was noch eleganter ist, finde ich.

Unregistrierter

Danke!

Aber das ist es ja was ich nicht verstehe wie das funktioniert mit dem überall hinzeigen

.

Erklärt es mir bitte anhand dieses Bsp:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58	void zuege2file(char filename[], spielzug zug) { FILE* infile = NULL; infile = fopen(filename,"a+b"); if(infile == NULL) { printf("FILE %s counld not be opened!",filename); exit(-1); } else { fwrite(&zug,sizeof(spielzug),1,infile); } fclose(infile); return; } spielzug * file2zuege(char filename[]) { FILE* infile = NULL; spielzug* liste = NULL; spielzug* act_spielzug = NULL; spielzug* letzer_spielzug = NULL; spielzugfile buffer; if ( ( infile = fopen(filename,"rb")) != NULL) { while(fread(&buffer,sizeof(spielzugfile),1,infile) == 1) { act_spielzug = (spielzug* )malloc(sizeof(spielzug)); if (act_spielzug == NULL) { exit(-1); } act_spielzug->posx=buffer.posx act_spielzug->posy=buffer.posy; act_spielzug->zeichen=buffer.zeichen; act_spielzug->next=NULL; if (liste == NULL) { liste = act_spielzug;//was bringt das hier? } else { letzer_spielzug->next= act_spielzug; } letzer_spielzug=act_spielzug; } fclose(infile); } return liste; }

Und malloc muss man verwenden da immer der gleiche Pointer auf die Werte zeigt?

Nochmal die anderen Fragen:
Wo in diesen Bsp sehe ich wie die verketteten Listen funktionieren? Das mit den next-pointer verstehe ich gar nicht.
Wie ist das den aufgebaut?

Gruß

Unregistrierter

In Zeile 49: letzer_spielzug->next= act_spielzug; wird dem vorhergehenden Eintrag mitgeteilt, das er einen Nachfolger hat.

Wenn du jetzt den Anfang der Liste hast, kannst du dich so durch alle Elemente hangeln.
Du holst dir die Adresse des Nachfolgers aus dem Element next.
Und da geht dann wieder das Gleiche: Du holst dir die Adresse des Nachfolgers aus dem Element next.
Und da geht dann ...

Wenn du nur next benutzt hast du eine einfach verkettete Liste (nur in eine Richtung)
Wenn du next und prev benutzt hast du eine doppelt verkettete Liste. Da kannst du von jedem Element aus die Liste durchgehen.

Unregistrierter

Ok, danke.

Also mach Zeile 49 folgendes es kopiert die Adresse des letzen Wertes in den next-pointer richtig?

Und weill next != NULL ist heißt das für den compiler, dass die liste noch nicht zu Ende ist richtig?

Unregistrierter

Richtig.

Unregistrierter

Hi,

ich bins nochmal. So richtig hab ich es noch immer nicht verstanden.

Ich bin das ganze Programm mal mit Einzelschritt durchgegangen, um zu sehn was wirklich geschieht.

Wenn man die Adresse bzw. Werte von act_spielzug auf letzter_spielzug->next kopiert, warum wird das gleichzeig auch zu liste->next kopiert?

Und was hat Zeile 51 für einen Sinn, es wurde eh schon in Zeile 49 die Adresse des letzten spielzuges angehängt?

Unregistrierter

liste1 schrieb:

Wenn man die Adresse bzw. Werte von act_spielzug auf letzter_spielzug->next kopiert, warum wird das gleichzeig auch zu liste->next kopiert?

Das passiert nicht gleichzeitig, sondern nur wenn die Liste leer ist, d.h. keine Einträge hat.

liste1 schrieb:

Und was hat Zeile 51 für einen Sinn, es wurde eh schon in Zeile 49 die Adresse des letzten spielzuges angehängt?

In Zeile 51 steht etwas anderes als in Ziel 49.

In Zeile 49 teilst du deinem aktuellen Element mit, wo das nächste zu finden ist.
In Zeile 51 machst du das nächste Element zu deinem akuellen.

Beispiel: Du baust einen Weg und hast vor dir nichts. Dann legst du vor dir eine Platte hin (Zeile 49). Dann betrittst du diiese Platte (Zeile 51) und schon ist vor dir wieder nichts.
Dann legst du die nächste Platte hin .....

Unregistrierter

Danke!

DirkB schrieb:

liste1 schrieb:

Wenn man die Adresse bzw. Werte von act_spielzug auf letzter_spielzug->next kopiert, warum wird das gleichzeig auch zu liste->next kopiert?

Das passiert nicht gleichzeitig, sondern nur wenn die Liste leer ist, d.h. keine Einträge hat.

Mh, aber wenn ich mit Einzelschritt gerade bei Zeile 49 bin, dann wir die Adresse von act_spielzug in letzter_spielzug->next kopiert.

Man sieht dann gleich, dass liste->next die gleiche Adresse hat wie letzter_spielzug->next.

Warum?

Unregistrierter

Hast du schon mal mehr als 2 Knoten angelegt?

liste ist der Zeiger auf das erste Element der Liste.
Also Zeigen beide beim ersten Element auf den gleichen Speicher.

Beim 2. Element ist das anders.