Freigeben von Speicher in einfache verkettete Liste - C

Question

Ich habe ein Problem, den Speicher in einer einfachen verketteten Liste Implementierung in C. freigegeben. Valgrind sagt mir, ich habe nicht alles befreit, aber ich bin nicht in der Lage herauszufinden, wo das Problem Lügen. Mein Code und valgrind Ausgabe unter:

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

typedef struct node { 
    int value; 
    struct node *next; 
} node_t; 

void insert(node_t *head, int num) { 

    // Create new node to insert 
    node_t *item = malloc(sizeof(node_t)); 
    item = malloc(sizeof(node_t)); 
    if (item == NULL) { 
     exit(2); 
    } 
    item->value = num; 

    // Insert new node at end of list 
    node_t *cur = head; 
    while (cur->next != NULL) { 
     cur = cur->next; 
    } 
    cur->next = item; 
} 

int main(int argc, char *argv[]) { 

    // Create head or root node 
    node_t *head; 
    head = malloc(sizeof(node_t)); 
    head->value = 0; 
    head->next = NULL; 

    // Insert nodes to end of list 
    insert(head, 1); 


    // Traverse list and print out all node values 
    node_t *cur = head; 
    while (cur != NULL) { 
     printf("%d\n", cur->value); 
     cur = cur->next; 
    } 

    // Free the list 
    cur = head; 
    node_t *previous; 
    while (cur != NULL) { 
     previous = cur; 
     cur = cur->next; 
     free(previous); 
    } 

    return 0; 

} 

// EOF 

Valgrid zeigt folgende Fehler

==9054== Memcheck, a memory error detector 
    ==9054== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. 
    ==9054== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info 
    ==9054== Command: ./linkedlist 
    ==9054== 
    0 
    1 
    ==9054== Conditional jump or move depends on uninitialised value(s) 
    ==9054== at 0x100000ED0: main (in ./linkedlist) 
    ==9054== Uninitialised value was created by a heap allocation 
    ==9054== at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so) 
    ==9054== by 0x100000E03: insert (in ./linkedlist) 
    ==9054== by 0x100000EBF: main (in ./linkedlist) 
    ==9054== 
    ==9054== Conditional jump or move depends on uninitialised value(s) 
    ==9054== at 0x100000F0E: main (in ./linkedlist) 
    ==9054== Uninitialised value was created by a heap allocation 
    ==9054== at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so) 
    ==9054== by 0x100000E03: insert (in ./linkedlist) 
    ==9054== by 0x100000EBF: main (in ./linkedlist) 
    ==9054== 
    ==9054== 
    ==9054== HEAP SUMMARY: 
    ==9054==  in use at exit: 26,456 bytes in 193 blocks 
    ==9054== total heap usage: 274 allocs, 81 frees, 32,608 bytes allocated 
    ==9054== 
    ==9054== 16 bytes in 1 blocks are definitely lost in loss record 5 of 65 
    ==9054== at 0x100008EBB: malloc (in /usr/local/Cellar/valgrind/3.11.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so) 
    ==9054== by 0x100000DF0: insert (in ./linkedlist) 
    ==9054== by 0x100000EBF: main (in ./linkedlist) 
    ==9054== 
    ==9054== LEAK SUMMARY: 
    ==9054== definitely lost: 16 bytes in 1 blocks 
    ==9054== indirectly lost: 0 bytes in 0 blocks 
    ==9054==  possibly lost: 0 bytes in 0 blocks 
    ==9054== still reachable: 0 bytes in 0 blocks 
    ==9054==   suppressed: 26,440 bytes in 192 blocks 
    ==9054== 
    ==9054== For counts of detected and suppressed errors, rerun with: -v 
    ==9054== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 18 from 18) 

Answer 1

Während Sie kostenlos zuzuteilen für head außerhalb von insert sind, wie Sie getan haben, werden Sie in der Regel die Adresse vonhead zu insert stattdessen passieren, so dass head und in insert zugewiesen zugeordnet werden können, und der Zeigerwert haben beibehalten und sichtbar zu main.

Grundproblem. Wenn Sie einen Zeiger auf eine Funktion übergeben, erhält die Funktion eine Kopie des Zeigers mit seiner eigenen (und sehr unterschiedlichen) Adresse. Um die ersten Knoten (zB head) zuzuweisen, müssen Sie die Adressehead einzufügen geben, andernfalls weisen Sie Speicher und weisen die Adresse für den Speicherblock an die Kopie vonhead in insert und bei der Rückkehr zu main, der ursprüngliche Zeiger für head bleibt NULL.

Der Prototyp für insert, der die Adresse head übergibt, würde z.

void insert (node_t **head, int num) 

und Sie würden insert von main nennen wie:

insert (&head, tmp); 

(dies ist nur ein Problem für den ersten Knoten, denn nach head zugeordnet ist, kann die Kopie des Zeigers erhalten durch insert haben eine eigene Adresse, aber sie enthält die gleiche Adresse für den ersten Knoten in main oder insert)

Wenn Sie für die fi zuweisen ersten Knoten in einer Funktion, und Sie geben die Knotenadresse für die Zuweisung im Aufrufer nicht zurück. Normalerweise möchten Sie die -Adresse der-Liste an Ihre insert-Funktion übergeben.

Weitere Themen

Wenn Werte in eine verknüpfte Liste Einfügen Sie zwei Bedingungen umgehen müssen. (eigentlich 3, wenn Sie einen unnötigen Aufruf zur Schleife optimieren wollen).Das sind die Einfügung des ersten Knotens und das Einfügen von alle anderen. (Sie können nach dem Einfügen des zweiten Knotens suchen, da in diesem Fall keine Traversierung von Knoten eingerichtet werden muss). So behandeln alle drei Fälle, Ihre insert aussehen würde, etwa wie folgt:

void insert (node_t **head, int num) 
{ 
    /* Create new node to insert */ 
    node_t *node = calloc (1, sizeof *node); 
    if (node == NULL) { 
     fprintf (stderr, "error: virtual memory exhusted.\n"); 
     exit (2); 
    } 
    node->value = num; 
    node->next = NULL; 

    /* Insert node at end */ 
    if (!(*head))    /* handle first node */ 
     *head = node; 
    else if (!(*head)->next) /* handle second  */ 
     (*head)->next = node; 
    else {      /* handle remaining */ 
     node_t *cur = *head; 
     while (cur->next) 
      cur = cur->next; 
     cur->next = node; 
    } 
} 

Ihr frei ist ebenfalls ein wenig umständlich, wie Sie in der Regel überprüfen, ob ->next zugeordnet ist, eine Entscheidung in Bezug auf den aktuellen Knoten zu machen und dann aufzuräumen die Nachzügler außerhalb der Schleife. (Dies ist weitgehend an Ihnen, stelle ich nur die Alternative unten, mein iter ist Ihr cur und meine victim ist Ihr previous)

/* Free the list */ 
    iter = head; 
    while (iter->next) { 
     node_t *victim = iter; 
     iter = iter->next; 
     free (victim); 
    } 
    if (iter) free (iter); 

schließlich mit valgrind Sie den Fehler kann einen Sprung auf einem nicht initialisierten bezüglich stützen Wert bei der Verwendung von malloc (Optionen malloc zu verwenden sind dann memset oder einfach calloc verwenden - die sowohl zuordnet und setzt den neuen Speicher zu 0/NULL)

Putting alle Teile zusammen, könnten Sie so etwas wie die folgenden tun zu lösen die Themen:

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

typedef struct node { 
    int value; 
    struct node *next; 
} node_t; 

void insert (node_t **head, int num) 
{ 
    /* Create new node to insert */ 
    node_t *node = calloc (1, sizeof *node); 
    if (node == NULL) { 
     fprintf (stderr, "error: virtual memory exhusted.\n"); 
     exit (2); 
    } 
    node->value = num; 
    node->next = NULL; 

    /* Insert node at end */ 
    if (!(*head))    /* handle first node */ 
     *head = node; 
    else if (!(*head)->next) /* handle second  */ 
     (*head)->next = node; 
    else {      /* handle remaining */ 
     node_t *cur = *head; 
     while (cur->next) 
      cur = cur->next; 
     cur->next = node; 
    } 
} 

int main (void) { 

    int tmp; 
    node_t *head = NULL, *iter = NULL; 

    /* Insert nodes to end of list (from stdin) */ 
    while (scanf (" %d", &tmp) == 1) 
     insert (&head, tmp); 

    /* Traverse list and print out all node values */ 
    iter = head; 
    while (iter) { 
     printf ("%d\n", iter->value); 
     iter = iter->next; 
    } 

    /* Free the list */ 
    iter = head; 
    while (iter->next) { 
     node_t *victim = iter; 
     iter = iter->next; 
     free (victim); 
    } 
    if (iter) free (iter); 

    return 0; 
} 

Beispiel Eingabedaten

$ cat ../dat/10int_nl.txt 
8572 
-2213 
6434 
16330 
3034 
12346 
4855 
16985 
11250 
1495 

Beispiel Verwendung/Output

$ valgrind ./bin/llvalgrind <../dat/10int_nl.txt 
==31935== Memcheck, a memory error detector 
==31935== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. 
==31935== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info 
==31935== Command: ./bin/llvalgrind 
==31935== 
8572 
-2213 
6434 
16330 
3034 
12346 
4855 
16985 
11250 
1495 
==31935== 
==31935== HEAP SUMMARY: 
==31935==  in use at exit: 0 bytes in 0 blocks 
==31935== total heap usage: 10 allocs, 10 frees, 160 bytes allocated 
==31935== 
==31935== All heap blocks were freed -- no leaks are possible 
==31935== 
==31935== For counts of detected and suppressed errors, rerun with: -v 
==31935== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1 from 1) 

Blick über alle Lösungen, und lassen Sie mich wissen, wenn Sie Fragen haben, .

Answer 2

In Funktion insert Sie die Struktur zuordnen zweimal:

node_t *item = malloc(sizeof(node_t)); 
item = malloc(sizeof(node_t)); 

Die erste verloren geht als Sie überschreiben den Zeiger in item mit der nächsten Zuordnung.

Außerdem initialisieren Sie das next Mitglied des neu zugewiesenen Knotens nicht, was die Warnungen verursacht, die von Valgrind ausgegeben werden, während Sie Daten, die nicht initialisiert wurden, dereferenzieren.

Answer 3

Innerhalb Ihres Einsatzes():

// Create new node to insert 
node_t *item = malloc(sizeof(node_t)); 
item = malloc(sizeof(node_t)); 

Sie rufen malloc() zweimal auf item, das erste Stück des Gedächtnisses verursacht zugeordnet immer ..

Damit verloren meine ich, dass Sie haven Behalte den Speicherblock jetzt nicht im Auge, also am Ende deines Programms, was die letzte Möglichkeit ist, den Speicher freizugeben, den du nicht hast. führt dazu, dass Speicher reserviert wird, aber nie freigegeben!

Stellen Sie sich vor, dass das Betriebssystem den gesamten Speicher Ihres Computers handhabt. Ihr Programm kommt ins Spiel und fragt nach etwas Speicher. Das Betriebssystem gibt Ihnen einen Zeiger auf das Stück Speicher, das es für Sie reserviert hat (Sie müssen es freigeben, wenn Sie es nicht mehr benötigen). Dieser Zeiger hat einen Wert, den wir nicht a priori kennen.

Was Sie tun mit malloc() zum zweiten Mal aufrufen und den Rückgabewert zu item zuweisen, ist, dass eindeutige Zeigerwert zu überschreiben (die Adresse des Speichers, die Sie gegeben wurden) und bekam eine neue Adresse, an die neu zeigen zugewiesenen Speicher.

Sie haben jetzt zwei Speicherabschnitte angefordert, aber Sie kennen nur die Adresse des zweiten Speicherbereichs. Also, wie kannst du den ersten Teil des Gedächtnisses freigeben, wenn du seine Adresse nicht kennst?

Sie können nicht! Und das ist falsch, da es zu einem Speicherverlust führen wird, wie Sie zeigen.

_{Eine Analogie wäre, dass die Erinnerung ein Theater ist (wie Epidaurus) und jeder Platz eine Zelle der Erinnerung ist. Das OS ist der Sitzleiter des Theaters. Sie beantragen einen Sitzplatz, der Manager gibt Ihnen eine ID des Sitzplatzes, den er Ihnen zugewiesen hat, und Sie schreiben ihn auf eine E-Note. Dann fordern Sie einen weiteren Sitzplatz an, der Manager prüft, ob noch Plätze im Theater vorhanden sind, ja, es gibt ja, also gibt er einen Platz und natürlich einen entsprechenden Ausweis. Sie schreiben es fälschlicherweise über die E-Note, in der Sie die vorherige ID geschrieben haben. Sie wissen also nur die zweite ID, also den 2. Platz und nicht die erste ID, also wissen Sie nicht, wo dieser Platz ist (das Theater ist groß und Sie wissen nicht viel darüber).}

---

Dies ist jedoch nicht das einzige Problem ist, wenn Sie item „create“, weisen Sie einen Wert, aber Sie zuweisen, etwas nicht zu next. Gehen Sie weiter und tun:

item->value = num; 
item->next = NULL; 

---

Nach all dem sollten Sie in der Lage sein, die folgende Ausgabe zu erzeugen:

C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall main.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
0 
1 

Answer 4

Sie haben zwei mallocs für jeden Knoten. Du willst nur eins. Sie können die eine in der Deklaration belassen und die folgende Zeile löschen, die das malloc dupliziert und die erste Zeile überschreibt.