C Doppelt Verkettete Liste

Sponny · 20. Januar 2015

Hallo Leute,

ich habe soeben ein Programm geschrieben, das eine doppelt verkettete Liste implementiert.

Meine Frage bezieht sich auf die Funktion free_list. Habe ich hier die Deallokierung des Speichers im Heap mit der free() Funktion aus der stdlib.h korrekt angewendet?

Vielen Dank im Voraus.

/*
* main.c
*
* Created on: 20.01.2015
* Author: Sponny
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct dl_list_t{
struct dl_list_t *prev;
int value;
struct dl_list_t *next;
}dl_list_t;

int sumlist(dl_list_t *a){
int sum = 0;
dl_list_t *h;
h = a;
while(h->next != NULL){
sum = sum + h->value;
h = h->next;
}
sum = sum + h->value;
return sum;
}

void free_list(dl_list_t *a){
dl_list_t *h;
h = a;
while(h->next != NULL){
free(h);
h = h->next;
}
free(h);
}

int main (){

dl_list_t *l1;
dl_list_t *l2;
dl_list_t *l3;

l1 = calloc (1, sizeof(dl_list_t));
l2 = calloc (1, sizeof(dl_list_t));
l3 = calloc (1, sizeof(dl_list_t));

l1->prev = NULL;
l1->value = 12;
l1->next = l2;

l2->prev = l1;
l2->value = 4;
l2->next = l3;

l3->prev = l2;
l3->value = 2014;
l3->next = NULL;

dl_list_t *anfang = l1;
printf("%d", sumlist(anfang));
free_list(anfang);
return 0;
}

togepi · 20. Januar 2015

Code:

free(h);
h = h->next;

Über diese zwei Zeilen solltest du noch einmal nachdenken.

Außerdem bitte Code-Tags nutzen, ist schwer lesbar.

HominiLupus · 20. Januar 2015

Nein hast du nicht, Stichwort "Use after free()".

Es ist auch schlicht sehr schlechtes Design eine fixe Anzahl von mallocs in main() zu machen und dann die free() Aufrufe dynamisch in einer Funktion. Das ist sehr unübersichtlich und lädt zu Fehlern gerade zu ein.

dcc22 · 21. Januar 2015

Bau dir doch zwei Funktionen, eine hängt links etwas dran, eine rechts.
Dann kannst gemütlich mit einer Schleife beliebig viele structs verketten.
Eine eigenständige Operation gehört in eine eigenständige Funktion.

Beim free machst es ja fast richtig, nur was soll a=h ?
Benutz doch direkt was übergeben wird ?

Und wie schon gesagt wurde, machst ein free(h), dann greifst du wieder auf h->next zu.
Das ist falsch da es dieses h nicht mehr gibt.

Ob du das mit free und malloc korrekt gemacht hast, lässt sich mit valgrind überprüfen, das zeigt dir dann an wenn du mehr mallocs als frees hast. Gibt es für die shell und auch für Eclipse mit CDT + Valgrind Plugin in grafischer Version.

Sponny · 29. Januar 2015

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct list{
	struct list*pre;
	int value;
	struct list*next;
}list;

int sum(list *l) {
	int sum = 0;
	while(l != NULL) {
		sum += l->value;
		l = l->next;
	}
	return sum;
}

list*  createlist(int x, list* mylist){
	list *neu;
	if((neu = malloc(sizeof(list))) != NULL){
		neu->value = x;
		neu->next = NULL;
		neu->pre = NULL;
		mylist = neu;
		return mylist;
	}
	else {
		printf("Fehler");
	}
	return NULL;
}

list* vorne(int x, list* l){
	list *new;
	if((new = malloc(sizeof(list))) != NULL) {
		new->value = x;
		new->pre = NULL;
		new->next = l;
		l = new;
		return l;
	}
	else {
		printf("Fehler");
	}
	return NULL;
}

list* hinten(int x, list* l){
	list *new;
	list *h = l;
	if((new = malloc(sizeof(list))) != NULL) {
		while(h->next != NULL){
			h = h->next;
		}
		h->next = new;
		new->value = x;
		new->next = NULL;
		new->pre = h;
		return l;
	}
	else {
		printf("Fehler");
	}
	return NULL;
}

void freelist(list* l){
	list* next;
	while (l->next != NULL) {
	      next = l->next;
	      printf("%d\n", l->value);
	      free(l);
	      printf("%d\n", l->value);
	      l = next;
	}
	printf("%d\n", l->value);
	free(l);
	printf("%d\n", l->value);
}

int main(){

	list* mylist = NULL;
	mylist = createlist(2015, mylist);
	mylist = vorne(1, mylist);
	mylist = vorne(29, mylist);
	mylist = hinten(22, mylist);
	printf("%d\n", sum(mylist));
	freelist(mylist);
	return 0;
}

Nochmal zu der "freelist" Funktion. Ich habe mit printf'ss versucht diese Funktion dezubuggen.
Jetzt klappt es nahezu fast. Bis auf das letzte Element in der Liste wird alles freigegeben.
Ich habe so das Gefühl, dass dies an meiner "hinten" Funktion liegt.

Kann mir jemand weiterhelfen. Ich finden den Fehler leider nicht. :'/
Vielen Dank im Voraus.

Harzerkas · 29. Januar 2015

Du prüfst erst ob das Element einen Nachfolger hat und gibst danach erst frei.
Edit: Dein printf nach free() ist wieder use-after-free

Sponny · 29. Januar 2015

Code:

void freelist(list* l){
	list* next;
	while (l != NULL) {
	      next = l->next;
	      free(l);
	      l = next;
	}
}

Wird so das Element am Ende auch korrekt freigegeben?

VikingGe · 29. Januar 2015

Klar. Die Schleife endet ja erst, wenn der l-Pointer null ist, also wirklich kein Element mehr existiert.

Sowas kann man am besten auch an Trivialbeispielen durchgehen. Was passiert bei einer leeren Liste? Offensichtlich gar nichts. Was passiert bei einer einelementigen Liste? Die Schleife wird einmal durchlaufen. Und so weiter.

Harzerkas · 29. Januar 2015

Ja das ist richtig!

Sponny · 29. Januar 2015

Cool, vielen Dank! (-

Eine kleine Frage habe ich noch dazu.
Wie kann es sein, wenn ich es mit Printf's wie folgt teste

Code:

void freelist(list* l){
	list* next;
	while (l != NULL) {
	      next = l->next;
	      printf("%d\n", l->value);
	      free(l);
	      printf("%d\n", l->value);
	      l = next;
	}
}

,dass ich dann folgende Werte bekomme:

29
5246352
1
5246352
2015
5246352
22
22

Das sieht für mich so aus, als würde das letzte Element nicht korrekt freigegeben werden?
Aber wie vorhin schon erwähnt, ist die printf ja eine use after free...

VikingGe · 29. Januar 2015

Aber wie vorhin schon erwähnt, ist die printf ja eine use after free...

Damit beantwortest du deine Frage doch selbst. Nach einem free auf die Region ist der Inhalt dieser Region aus deiner Sicht undefiniert und darf eben nicht mehr benutzt werden, weil da sonstwas drin stehen kann.

Sponny · 29. Januar 2015

Alles klar. Vielen Dank nochmal.
War nur etwas verunsichert, wegen der Ausgabe. :O

black90 · 29. Januar 2015

Free löscht es nur aus Verwaltungstabellen, aber nicht im Speicher.
Was im Speicher steht bleibt auch dort, bis es nicht von irgendetwas überschrieben wird.

Das ist das tückische an C, es sagt dir nicht viel, scheint zu gehen und stürzt dann ab wenn es nicht soll

antred · 30. Januar 2015

black90 schrieb:
Free löscht es nur aus Verwaltungstabellen, aber nicht im Speicher.
Was im Speicher steht bleibt auch dort, bis es nicht von irgendetwas überschrieben wird.

Das ist vollkommen implementierungsabhängig. Soweit es den C-Standard betrifft, kann sich durch ein free sehr wohl auch der Inhalt des freigegebenen Speichers ändern (auch wenn das in der Praxis wahrscheinlich kaum vorkommt). Das einzige, was zählt, ist dass Zugriff nach free immer undefined behavior nach sich zieht, sprich, es könnte funktionieren, es könnte manchmal funktionieren und manchmal nicht, oder es könnte auch deine lokale Pornosammlung zippen und an die Email-Adresse deiner Oma versenden.

Sponny · 30. Januar 2015

Stimmt.

Das habe ich doch schon wo gehört.

antred · 30. Januar 2015

Sponny schrieb:
Stimmt. Das habe ich doch schon wo gehört.

Dein Teil mit dem Porno verschicken, habe ich mal irgendwo auf stackoverflow gelesen. Ein klitze-kleines bißchen Plagiarismus hat noch keinem was geschadet.

Suche

C Doppelt Verkettete Liste

Sponny

Lt. Commander

togepi

Lt. Junior Grade

HominiLupus

Banned

dcc22

Lieutenant

Sponny

Lt. Commander

Harzerkas

Ensign

Sponny

Lt. Commander

VikingGe

Gast

Harzerkas

Ensign

Sponny

Lt. Commander

VikingGe

Gast

Sponny

Lt. Commander

black90

Gast

antred

Lt. Commander

Sponny

Lt. Commander

antred

Lt. Commander

Ähnliche Themen