# Verkettete Liste in C



## miniME (22. Februar 2010)

Hey Leute,

hab da ein Problem mit einer Verketteten Liste in C. Meiner Meinung nach müsste das doch alles so gehen, ich kann den Fehler einfach nicht erkennen.
Beider Funktion addElement muss ein Fehler irgendwo bei der while-Schleife liegen um an das letzte Element in der Liste zu kommen. Bei der Ausgabe stimmt auch was nicht, da wird auch wenn es ein Null-Pointer ist die Schleife ausgeführt.

```
#include <stdio.h>
#include <string.h>

typedef struct movie MOVIE;
int ID = 0;

struct movie {
	int id;
	char title[100];
	double rating;
	struct releaseDate {
		int day;
		int month;
		int year;
	} releaseDate;
	MOVIE *nextElement;
};

void addElement(MOVIE *list, char title[100], double rating, int releaseDay, int releaseMonth, int releaseYear) {
	while(list->nextElement != NULL) {
		list = list->nextElement;
	}

	list->id = ID;
	strcpy(list->title, title);
	list->rating = rating;
	list->releaseDate.day = releaseDay;
	list->releaseDate.month = releaseMonth;
	list->releaseDate.year = releaseYear;
	list->nextElement = (MOVIE *)malloc(sizeof(MOVIE));

	ID++;
}

void printList(MOVIE *list) {
	while(list != NULL) {
		printf("ID: %i\n", list->id);
		printf("Titel: %s\n", list->title);
		printf("Bewertung: %lf\n", list->rating);
		printf("Veroeffentlichungsdatum: %i.%i.%i\n", list->releaseDate.day, list->releaseDate.month, list->releaseDate.year);
		printf("==========================================\n");
		list = list->nextElement;
	}
}

int main() {
	MOVIE *list = (MOVIE *)malloc(sizeof(MOVIE));

	addElement(list, "Titel 1", 7.8, 5, 10, 2005);
	addElement(list, "Titel 2", 6.5, 20, 5, 2008);

	printList(list);

	return 0;
}
```


----------



## Matthias Reitinger (23. Februar 2010)

Hallo,

malloc „nullt“ den reservierten Speicherplatz nicht, du musst den nextElement-Zeiger also selbst auf NULL setzen. Außerdem hast du noch einen kleinen Denkfehler drin: das letzte Element der Liste ist bei dir immer uninitialisiert/nicht verwendet, aber printList versucht es trotzdem auszugeben.

Grüße,
Matthias


----------



## Vereth (23. Februar 2010)

Völlig richtig. Und wenn man zu faul ist, den Speicher selber zu initialisieren, verwendet man calloc().


----------



## miniME (23. Februar 2010)

Hab jetzt mal ein bischen rumgespielt und irgendwie will es einfach nich funktionieren. Hab das jetzt so probiert, dass ich beim erstellen der Liste erstmal nen NULL-Pointer hab (in main), somit gibt es 0 Elemente zu beginn. Wenn ich jetzt eins hinzufüge wird über die while-Schleife bis an das Ende der Liste gegangen, dh bis zum ersten NULL.Pointer und da wird dann über malloc der Speicherplatz angefordert und es werden die Daten reingeschrieben. Der nextElement Pointer wird dann wieder als NULL-Pointer initialisiert. Leider geht das nicht! Ich versteh einfach meinen Denkfehler nicht. Komischerweise ist der Zeiger liste (in main) am Schluss noch immer ein NULL-Pointer. Wäre nett wenn mir wer das Programm verbessern könnte. Vielen Dank.

```
#include <stdio.h>
#include <string.h>
typedef struct movie MOVIE;
int ID = 0;

struct movie {
	int id;
	char title[100];
	double rating;
	struct releaseDate {
		int day;
		int month;
		int year;
	} releaseDate;
	MOVIE *nextElement;
};

void addElement(MOVIE *list, char title[100], double rating, int releaseDay, int releaseMonth, int releaseYear) {
	while(list != NULL) {
		list = list->nextElement;
	}
	list = (MOVIE *)malloc(sizeof(MOVIE));
	list->id = ID;
	strcpy(list->title, title);
	list->rating = rating;
	list->releaseDate.day = releaseDay;
	list->releaseDate.month = releaseMonth;
	list->releaseDate.year = releaseYear;
	list->nextElement = NULL;

	ID++;
}

int main() {
	MOVIE *list = NULL;
	addElement(list, "Titel 1", 7.8, 5, 10, 2005);
	addElement(list, "Titel 2", 6.5, 20, 5, 2008);
	addElement(list, "Titel 3", 9.0, 25, 2, 2007);
	printf("%p\n", list);

	return 0;
}
```


----------



## sheel (23. Februar 2010)

Das liegt daran, das die Variable in Main nichts davon mitbekommt,dass sie Speicher bekommt
Eine Möglichkeit wäre, am Schluss von add den Pointer returnen und im main halt
list=addElement(list...)
zu schreiben

Oder du übergibst die Adresse vom Pointer und schreibst in add immer einen * vor list 

Oder du nimmst die Referenz vom Pointer


----------



## deepthroat (23. Februar 2010)

Hi.

So kann das nicht funktionieren.

Du übergibst doch nur _NULL _an die Funktionen, also keinerlei Information. D.h. Änderungen innerhalb der Funktion wirken sich auch nicht aus und der Wert der Variablen *list* in der main Funktion bleibt immer NULL.

Um die Variable zu modifizieren, müßtest du einen Zeiger auf den Listenzeiger an die Funktionen übergeben;

```
void addElement(MOVIE **list, char title[100], double rating, int releaseDay, int releaseMonth, int releaseYear) {
    if (*list == NULL)  { // Liste existiert noch gar nicht, neu anlegen
      *list = malloc(sizeof(MOVIE));
      (*list)->nextElement = NULL;
    }
    // ...
}

int main() {
	MOVIE *list = NULL;

   addElement(&list, ...);
}
```
Du solltest dir aber evtl. nochmal Gedanken machen ob das so günstig ist jedesmal zu prüfen ob die Liste existiert.

Es ist schöner extra eine Liste zu erstellen und darin die Knoten zu verwalten:

```
typedef struct Node {
  // ... Datenelemente
  Node* next;
} Node;

typedef struct List {
  Node* start;
} List;

void addElement(List* list, int data) {
  Node* p = list->start;

  while (p != NULL) {
    p = p->next;
  }
  
  p = malloc(sizeof(Node));

  p->next = NULL;
  p->data = data;
}

int main(void) {
  List liste = { NULL }; // eine Liste, leer

  addElement(&liste, x);
}
```
Auf diese Weise kommst du nicht in die Schwierigkeit einen Knoten verschwenden zu müssen um überhaupt eine Handhabe für die Liste zu haben oder die Variante mit Zeigern auf Zeiger umsetzen zu müssen.

Gruß


----------



## miniME (23. Februar 2010)

Ich habs auch schon mit dem pointer auf pointer probiert, bei mir hats aber irgendwie nich hingehauen. Aber danke für die Hilfe. Ist auch irgendwie blöd von mir nen NULL-Pointer zu übergeben und mich dann zu Fragen wieso sich nix ändert. (Notiz an mich: Nächstes mal 2 mal nachdenken!)
Ich hab das jetzt mit dem pointer auf pointer weggelassen und einfach schon in main den Speicherplatz für das erste Element der Liste freigegeben.
Meine funktionierende Lösung lautet jetzt so:

```
#include <stdio.h>
#include <string.h>
typedef struct movie MOVIE;
int ID = 0;

struct movie {
	int id;
	char title[100];
	double rating;
	struct releaseDate {
		int day;
		int month;
		int year;
	} releaseDate;
	MOVIE *nextElement;
};

MOVIE* initList() {
	MOVIE *list = (MOVIE *)malloc(sizeof(MOVIE));
	list->nextElement = NULL;
	return list;
}

void addElement(MOVIE *list, char title[100], double rating, int releaseDay, int releaseMonth, int releaseYear) {
	while(list->nextElement != NULL) {
		list = list->nextElement;
	}
	list->id = ID;
	strcpy(list->title, title);
	list->rating = rating;
	list->releaseDate.day = releaseDay;
	list->releaseDate.month = releaseMonth;
	list->releaseDate.year = releaseYear;
	list->nextElement = (MOVIE *)malloc(sizeof(MOVIE));
	list->nextElement->nextElement = NULL;

	ID++;
}

void printList(MOVIE *list) {
	while(list->nextElement != NULL) {
		printf("ID: %i\n", list->id);
		printf("Titel: %s\n", list->title);
		printf("Bewertung: %lf\n", list->rating);
		printf("Veroeffentlichungsdatum: %i.%i.%i\n", list->releaseDate.day, list->releaseDate.month, list->releaseDate.year);
		printf("==========================================\n");
		list = list->nextElement;
	}
}

int main() {
	MOVIE *list = initList();

	addElement(list, "Titel 1", 7.8, 5, 10, 2005);
	addElement(list, "Titel 2", 6.5, 20, 5, 2008);
	addElement(list, "Titel 3", 9.0, 25, 2, 2007);
	
	printList(list);

	return 0;
}
```

Diese Lösung find ich jetzt eigentlich nicht perfekt, da selbst wenn 0 Elemente exisiteren es trotzdem Speicherplatz für 1 Element belegt ist. Na ja, da will ich jetzt mal nich so kleinlich..

Vielen Dank für die Hilfe.


----------



## Vereth (24. Februar 2010)

miniME hat gesagt.:


> Diese Lösung find ich jetzt eigentlich nicht perfekt, da selbst wenn 0 Elemente exisiteren es trotzdem Speicherplatz für 1 Element belegt ist. Na ja, da will ich jetzt mal nich so kleinlich..


Das braucht dich nicht zu stören, das ist normal. Ein solches Element nennt man Start-Knoten oder Listenkopf. Du verwaltest deine Liste als FIFO-Speicher (First-In-First-Out), was man auch Warteschlange oder englisch Queue nennt. Du kannst es aber auch als LIFO-Speicher (Last-In-First-Out) verwenden, das nennt man dann Stapelspeicher oder Stack. Dabei werden die neuen Elemente nicht hinten an das Ende angehängt, sondern vorne eingefügt; dadurch ersparst du dir dann die while-Schleife. Du schreibst dann nicht

```
//
	while(list->nextElement != NULL) {
		list = list->nextElement;
	}
	...
	list->nextElement->nextElement = NULL;
```
sondern

```
//
	MOVIE *tmp = (MOVIE *)malloc(sizeof(MOVIE));
	tmp->nextElement = list->nextElement;
	list->nextElement = tmp;
	...
```
Allerdings würden dann deine Einträge in umgekehrter Reihenfolge ausgegeben.
Als nächste Übung solltest du vielleicht versuchen, eine doppelt verzeigerte Liste zu implementieren, die ringförmig verkettet ist.

Viel
Vergnügen
Vereth


----------



## deepthroat (24. Februar 2010)

Vereth hat gesagt.:


> Völlig richtig. Und wenn man zu faul ist, den Speicher selber zu initialisieren, verwendet man calloc().


Ein NULL Zeiger wird allerdings nicht unbedingt mit dem Bitwert 0 repräsentiert, so das es ein reiner Glücksfall ist falls das in diesem Zusammenhang funktioniert.

Gruß


----------



## Vereth (24. Februar 2010)

Von Glück würde ich nicht reden, es wäre eher unwahrscheinliches Pech, wenn dem nicht so ist. Aber wer genau wissen will, ob das so ist, kann in _stdlib.h_ nachlesen, wie NULL definiert ist. In C++ dagegen ist tatsächlich definiert, dass ein NULL-Pointer durch 0 bzw. 0L dargestellt wird, siehe beispielsweise C++ - Referenz für NULL.
Und wer ganz sicher sein möchte, kann folgende Zeilen in seine Quelldatei schreiben:

```
#if NULL!=0 && NULL!=0L
#error 'Inkompatible NULL-Darstellung'
#endif
```


----------



## deepthroat (24. Februar 2010)

Vereth hat gesagt.:


> Von Glück würde ich nicht reden, es wäre eher unwahrscheinliches Pech, wenn dem nicht so ist. Aber wer genau wissen will, ob das so ist, kann in _stdlib.h_ nachlesen, wie NULL definiert ist. In C++ dagegen ist tatsächlich definiert, dass ein NULL-Pointer durch 0 bzw. 0L dargestellt wird, siehe beispielsweise C++ - Referenz für NULL.
> Und wer ganz sicher sein möchte, kann folgende Zeilen in seine Quelldatei schreiben:
> 
> ```
> ...


Das ist nicht richtig. Es gibt immer noch einen Unterschied zwischen der Repräsentation eines Nullzeigers im Speicher und der Repräsentation eines NULL Zeigers im Programmcode. Ein C Compiler wird die Konstante _0 _im Programm entsprechend in den Wert übersetzen der als Nullzeiger verwendet wird. Siehe z.B. http://www.lysator.liu.se/c/c-faq/c-1.html#1-10

Gruß


----------

