Verkettete Liste

Googlehupf

Erfahrenes Mitglied
Hallo,

wir lernen gerade Verkettete Listen und ich bin mir nicht ganz im Klaren wie das genau funktioniert.

Im Grunde kann das Programm: Spielzüge von Ticatactoe auslesen aus einem Binärfile(x-position, y-position und zeichen).

In den comments steht alles.

h-file:
C++:
struct spielzug_struct
{
  int posx;
  int posy;
  char zeichen;
	struct spielzug_struct * next;//dieser pointer zeigt auf das nächste element
	struct spielzug_struct * prev;//dieser pointer zeigr auf das vorherige element 
/*aber wie funktioniert das hier genau zeigt der pointer jetzt nur auf einen Wert oder auf den ganzen Block/Struktur? Wo sieht man jetzt das der prev-pointer auf den vorheriegen zeigt und next auf den nächsten? Irgendwie hab ich voll das Blackout grad^^*/
};

typedef struct spielzug_struct spielzug;

struct spielzugfile_struct
{
  int posx;
  int posy;
  char zeichen;
};
typedef struct spielzugfile_struct spielzugfile;


void zuege2file(char filename[], spielzug zug);

spielzug * file2zuege(char filename[]);

1. c-file
C++:
#include "spielzuege.h"
#include <stdio.h>
#include <stdlib.h>



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));//warum braucht man hier ein malloc, das es öfter als einmal aufgerufen wird durch die while ja?
			if (act_spielzug == NULL) 
			{
				exit(-1);
			}
			act_spielzug->posx=buffer.posx;//ja hier werden einfach die werte zugeweisen
			act_spielzug->posy=buffer.posy;//dasselbe...
			act_spielzug->zeichen=buffer.zeichen;//dasselbe
			act_spielzug->next=NULL;//warum lässt man hier den next-pointer auf "Nichts" zeigen?
			if (liste == NULL)//wann soll den bitte der pointer liste auf was anderes außér NULL zeigen?
			{
			  liste = act_spielzug;//was bringt das hier?
			}
			else
			{
				letzer_spielzug->next= act_spielzug;//Warum macht man das hier, falls liste != NULL ist?
			}
			letzer_spielzug=act_spielzug;//Und da?

		}

		fclose(infile);
	}
  return liste;//warum übergibt man liste? und net actSpielzug oder so?
}

2.c-file(main):
C++:
#include "spielzuege.h"
#include <stdio.h>
#include <stdlib.h>


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

  zuege_first = file2zuege("zuege.dat");
  alle_zuege=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;
	}

	return 0;
}

Ja ich weiß sehr viele Frage, unter anderem auch sicher grundlegende, aber ich verstehe das irgendwie nicht.

Wäre auch aufejdenfall sehr dankbar, wenn ihr mir das erklären könntet.

Danke im voraus! :)

Gruß

Googlehupf
 
Der Sinn solcher Liste ist es, so etwas wie ein dynamisches Array zu erstellen. Die next- und previous-Pointer zeigen beide auf eine Variable vom Typ spielzug_struct, um eine Verkettung zu ermöglichen. Natürlich verkettet die der Compiler nicht selbst, das musst du selbst machen (wegen deiner Frage woran man sieht, dass z.B. next auf das nächste Element zeigt). Die Pointer sind dazu da, dass so eine Liste überhaupt möglich ist.

c-file:
Zeile 40: Mit malloc() reservierst du dir Speicher für ein neues spielzeug_struct Element. Das neue Element kann dann an die Liste angehängt werden.

Zeile 48: Das neue Element, das angehängt wird, wird ja logischerweise am Ende angehängt. Und am Ende gibt es logischerweise auch kein nächstes Element, deshalb lässt man next auf NULL zeigen.

Zeile 49: liste ist der Zeiger auf den Anfang der Liste. Wenn dieser auf NULL zeigt, bedeutet das, dass die Liste noch leer ist, also keine Element angehängt wurden.

Zeile 51: Wenn die Liste leer ist, soll der Anfangszeiger list natürlich auf das neu erstellte Element zeigen (irgendwo muss man ja anfangen).

Zeile 55: letzter_spielzug ist ein Zeiger auf das letzte Element der Liste. Wenn man ein neues Element erstellt, möchte man das natürlich am Ende der Liste anhängen. Deshalb zeigt das next vom letzten Element jetzt auf das neue letzte Element (für das am Anfang Speicher reserviert wurde). Das macht man nur wenn list != NULL ist, denn wenn list auf NULL zeigt, ist ja keine Liste vorhanden und dann zeigt letzter_spielzug auch nicht auf das letzte Element, weil es ja keins gibt.

Zeile 57: Das neue Element wurde hinten an der Liste angehängt, jetzt muss nur noch letzter_spielzug auf das neue letzte Element zeigen, das wird hier erreicht.

Zeile 63: Zurückgegeben wird ein Zeiger auf den Anfang der Liste. Warum sollte man die Adresse eines Elements der Liste zurückgeben? Mit dem Anfangspointer hast du am leichtesten auf alle Elemente Zugriff.

Ich hoffe ich habe dir ein bisschen Licht in die Sache gebracht :)

Lg
 
Danke, jup ich sehe eindeutig Licht :D.

Aber was ich noch nicht ganz begriffen habe, wie funktioniert das genau mit dem next und prev Pointern?

Also wie funktioniert das, das der next pointer von 1. Element auf 2. zeigt und 2. auf 3? Das selbe mit prev nur umgekehrt?

Danke!

Gruß
 
Versteh die Frage irgendwie nicht?
Das sind ganz normale Pointer.

Anders als beim Array (bei dem alles genau hintereinander im Speicher ist)
wird bei einer Liste ja jedes Element getrennt angelegt.
Wo gerade Platz ist.
Und weil man nur zB. das erste Element in einer Variable hat
muss man die anderen dann ja irgendwie wiederfinden können.
Deswegen hat jeder Wert die Pointer dabei
(deren Inhalt man beim Anlegen/Einfügen der/in die Liste eben setzen muss).
 
Danke!

Mh ok ich versuchs anders zu formulieren:

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?
 
Zuletzt bearbeitet:
Dafür ist ja der next-Zeiger. Es ist ein Zeiger auf das nächste Element in der Liste. Mit pointer++ kannst du bei einem Array auf das nächste Element zugreifen und bei Listen eben auf list->next.

Lg
 
Ich hab mir mein Programm etwas näher angeschaut, d.h. ich bin mit Einzelschritt durchgegangen und hab folgendes festgestellt:

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.

Wieso ist dann in list->next automatisch die gleiche Adresse wie in letzter_spielzug->next?
 
letzter_spielzug zeigt, wie er Name schon sagt auf das letzte Element der Liste. list zeigt auf den Anfang der Liste.
Am Ende des 1. Durchlaufes zeigen list und letzter_spielzug auf dasselbe Element (weil es nur eins gibt und das zugleich das erste und letzte ist).
Am Ende des 2. Durchlaufes wird ein Element angehängt, das bedeutet list zeigt natürlich noch immer auf den Anfang und letzter_spielzug zeigt auf list->next.
Am Ende des 3. Durchlaufes kommt wieder ein Element dazu, das bedeutet list zeigt natürlich noch immer auf den Anfang und letzter_spielzug zeigt auf list->next->next.

So geht das immer weiter, ich hoffe ich habe deine Frage richtig verstanden. Versuch einmal dir das alles aufzuzeichnen, also die liste und wie das verkettet ist, das mach ich auch immer und mir hilft es ziemlich gut.

Lg
 
Danke! Ich habs jetzt verstanden! :)

Wir sollen nun einen einen Spielzug irgendwo in die Liste einfügen. Dazu soll ein Pointer auf einen Spielzug zeigen und vor dem darauf gezeigten Spielzug wird dann der Spielzug eingefügt.

Nur wie kann ich den pointer "steuern"? Ich mein wie kann der "Kunde" dem Pointer sagen, dass er auf den 2. Spielzug der Kette zeigen soll, damit ich den neuen dann davor einfügen kann?

Soll ich die Spielzüge durchnummerieren und der "Kunde" gibt dann eine Zahl ein: 2 --> und ich gehe dann mit einer schleife bis 2. Spielzug und lasse dann den Pointer dahin zeigen?

War das so gemeint, oder was haltet ihr davon? Wie würde es man sonst machen?
 
Wenn die Züge nicht sortiert in der Liste vorkommen sollten und der Kunde entscheidet, wo er den Zug einfügen möchte, ist deine Idee sicher eine gute Möglichkeit. Geht so sicher am besten.

Lg
 

Neue Beiträge

Zurück