Verkettete Liste

[list1]

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?

[DirkB]

Richtig.

[liste1]

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?

[DirkB]

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 .....

[list1]

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?

[DirkB]

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.

[liste1]

Achso danke, dann habe ich mir vertan.

Beim 1. While durchgang geht "es" in die if rein, da noch keine spielzüge da sind.

Beim 2. While durchgang, geht "es" statt in die if in die else(Zeile 49) und kopiert act_spielzug zu letzter_spielzug->next und wenn ich dann unten schaue, im visual c, da wo die ganzen variable steht, hat nun auch liste->next den gleichen Wert wie letzter_spielzug->next.

Beim 3. While durchgang, geht "es" wieder in die else, kopoiert act_spielzug zu letzter_spielzug->next und das was in letzter_spielzug->next steht, steht jetzt nun auch in liste->next->next... Also es entsteht nun eine "verkettung" bzw. es ist verschachtelt.

Das ist die Frage WARUM das so ist.

[DirkB]

liste1 schrieb:

Das ist die Frage WARUM das so ist.

Das ist schon die Antwort. Glückwunsch.

[list1]

Das heißt die 3 Punkte die gerade selber aufgezählt habe sind die Antwort?^^

Das erklärt aber nicht warum das so ist, oder kann man sagen "das ist einfach so"?

Genau so wie der Schnee weiß ist?

[DirkB]

Wie baust du eine Kette aus Büroklammern?

Du nimmst eine (die erste) Klammer in die Hand. Da besteht deine Kette nur aus einer Klammer.
Dann bastelst du eine zweite Klammer daran und nimmst die neue Klammer in die Hand.
Daran bastelst du die nächste Klammer und nimmst die neue Klammer in die Hand.
Den letzten Satz beliebig wiederholen.

Jetzt hast du eine Kette.
Warum ist das so?

--
^Auch die Reise von 1000 Meilen beginnt mit dem ersten Schritt.^

[list1]

mh ok danke :).

Ich hab jetzt daraus eine doppelt verkettete Liste gemacht:

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 = 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;
				act_spielzug->prev=NULL;
			}
			else
			{
				letzer_spielzug->next= act_spielzug;
			  act_spielzug->prev=letzer_spielzug;
			}			
			letzer_spielzug=act_spielzug;
		}

		fclose(infile);
	}
  return liste;
}

Ich werden jetzt die einzelnen While-Durchgänge kurz erläutern:

1. Durchgang:
Hier zeigt liste auf den 1. Spielzug.

2. Durchgang:
act_spielzug zeigt auf das 2. Element. Die adresse des 2. Element wird nun zu letzer_spielzug->next kopiert.
liste->next ist gleich letzer_spielzug->next warum sind die beiden ident? Wo sieht man das?

Ich verstehe das noch immer nicht, warum den letzer_Spielzug->next genau die gleiche Adresse hat wie liste->next im 2. Durchgang?

act_spielzug hat doch auch nicht die selbe Adresse wie die beiden?

Bitte erklärt es mir.

Danke!

[DirkB]

In welcher Zeile bist du denn?

letzer_spielzug zeigt auf den Vorgänger.
Also zeigt es beim 2. Element auf das 1. Element, welches auch Anfang der Liste ist und somit auch liste darauf zeigt.

[list1]

Aso, sorry in Zeile 29

[DirkB]

Nochmal kurz:
liste zeigt auf 1. Element
act_spielzug zeigt auf 2. Element
letzer_spielzug zeigt auf 1. Element
Dann ist letzer_spielzug->next das gleiche wie liste->next

liste
 |   
 |    
 |    
 |  +---------+
 +->|1.Element|
    +---------+       +---------+
    | next    | ----> |2.Element|
    +---------+       +---------+
                      | next    |  ----> NULL
                      +---------+
letzer_spielzug       act_spielzug

Beim 3. Element sieht es dann so aus

liste
 |   
 |    
 |    
 |  +---------+
 +->|1.Element|
    +---------+       +---------+
    | next    | ----> |2.Element|
    +---------+       +---------+       +---------+
                      | next    | ----> |3.Element|
                      +---------+       +---------+
                                        | next    | ----> NULL
                                        +---------+
                     letzer_spielzug    act_spielzug

[liste1]

Danke! Jetzt verstehe ich wie das ganze zusammenhängt!

Und so siehts bei doppelt verketteten liste aus?

liste
    |  
    |    
    |    
    |   +---------+
    +-> |1.Element|
        +---------+       +---------+
        | next    | ----> |2.Element|
        +---------+	  +---------+       +---------+
NULL<---| prev    |       | next    | ----> |3.Element|
        +---------+       +---------+       +---------+
        |1.Element| <---- | prev    |       | next    | ----> NULL
        +---------+       +---------+       +---------+
			  |2.Element| <---- | prev    |
			  +---------+       +---------+	
					    |3.Element|
					    +---------+
											                 letzer_spielzug    act_spielzug

liste->prev muss immer NULL sein, genau wie liste->next->next->next.
D.h. also, dass man auf mehrere Arten auf z.B. das 1. Element zugreifen kann, richtig?
Mit dem liste-pointer direkt und mit liste->next->prev.
Und auf 2. Element: liste->next, oder liste->next->next->prev.

Ist richtig so oder?

Und wie kann ich von hinten nach vorne ausgeben, also den prev-pointer zu hilfe nehmen beim Ausgeben? Ich hab mir das so gedacht, das ich das Ende finde, also der pointer muss NULL sein. Und dann halt immer mit ->prev zurück gehe und ausgebe. Aber iwie klappt das nicht so recht.

int main()
{
  spielzug * alle_zuege = NULL;
	spielzug * zuege_first = NULL;
	spielzug * alle_zuege1 = NULL;

  zuege_first = file2zuege("zuege.dat");
  alle_zuege=zuege_first;
	alle_zuege1=zuege_first;

	while(alle_zuege != NULL)
	{
		printf("x:%d,y:%d,stein:%c\n",alle_zuege->posx,alle_zuege->posy,alle_zuege->zeichen);
		alle_zuege=alle_zuege->next;
	}

	printf("------------------\n");

	while(alle_zuege1 != NULL)
	{
	  alle_zuege1=alle_zuege1->next;
	}

  while(alle_zuege1->prev != NULL)
	{
	  printf("x:%d,y:%d,stein:%c\n",alle_zuege->posx,alle_zuege->posy,alle_zuege->zeichen);
		alle_zuege1=alle_zuege1->prev;
	}

	return 0;
}

Was mache ich da genau falsch?

Könntet ihr mir vielleicht noch bitte Tipps geben wie ich die GANZE Liste löschen kann?

[liste1]

EDIT:

liste
    |  
    |    
    |    
    |   +---------+
    +-> |1.Element|
        +---------+       +---------+
        | next    | ----> |2.Element|
        +---------+       +---------+        +---------+
NULL<---| prev    |       | next    | ----> |3.Element|
        +---------+       +---------+       +---------+
        |1.Element| <---- | prev    |       | next    | ----> NULL
        +---------+       +---------+       +---------+
                          |2.Element| <---- | prev    |
                          +---------+       +---------+   
                                            |3.Element|
                                            +---------+
                        letzer_spielzug    act_spielzug

[DirkB]

Welchen Wert hat alle_zuege1 in Zeile 23?
Tipp: printf("alle_zuege1: %p\n", alle_zuege1);

Die Liste musst du Knoten für Knoten löschen. So wie du sie auch angelegt hast.

[liste1]

alle_zuege1 zeigt in Zeile 23 auf NULL.

Also wir sind am Ende der Kette.

[DirkB]

Das Programm geht doch aber weiter.
Was meinst du ergibt dann alle_zuege1->prev in Zeile 24?

[liste1]

Mh ok das ist dann natürlich auch 0.

Aber wie könnte ich das anders machen?