Verkettete Liste in C

M

miniME

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.
Code: 
#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;
}
 
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
 
Völlig richtig. Und wenn man zu faul ist, den Speicher selber zu initialisieren, verwendet man calloc().
 
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.
Code: 
#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;
}
 
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
 
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;
C: 
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:
C: 
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ß
 
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:
Code: 
#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.
 
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..
Zum Vergrößern anklicken....
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
C: 
//
	while(list->nextElement != NULL) {
		list = list->nextElement;
	}
	...
	list->nextElement->nextElement = NULL;
sondern
C: 
//
	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
 
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:
C: 
#if NULL!=0 && NULL!=0L
#error 'Inkompatible NULL-Darstellung'
#endif
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück