Освобождение памяти, выделенной в простом связанном списке - C

Question

У меня проблема с освобождением памяти, выделенной в простой реализации связанного списка. C. Valgrind говорит мне, что я не освободил все, но я не могу понять, где проблема вранье. Мой код и выход Valgrind ниже:

#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 показывает следующую ошибку

==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

В то время как вы можете выделить для head снаружи insert, как вы сделали, вы, как правило, проходят адресhead к insert вместо этого, так что head могут быть выделены и назначены в insert и имеют значение указателя сохраняется и видимо main.

Основная проблема. Когда вы передаете указатель на функцию, функция получает копию указателя с его собственным (и очень отличающимся адресом). Для того, чтобы выделить первый узел (например, head), вы должны пройти адресhead вставки, в противном случае вы выделить память и присвоить адрес для блока памяти в копииhead в insert и по возвращению до main, оригинальная указатель для head остается NULL.

Прототип для insert, передающий адрес head, стал бы, например.

void insert (node_t **head, int num) 

и вы могли бы назвать insert из main как:

insert (&head, tmp); 

(это проблема только для первого узла, так как после head выделяется, копия указателя, полученная insert может иметь его собственный адрес, но он содержит тот же адрес для первого узла в main или insert)

Если вы выделяете для fi первый узел в функции, и вы не возвращаете адрес узла для назначения в вызывающем абоненте, вы обычно хотите передать адрес в список insert.

Другие вопросы

Когда вставляя значения в связанный список вы должны обрабатывать два условия. (фактически 3, если вы хотите оптимизировать ненужный вызов цикла).Это ввод первого узла и вставка все остальные. (вы можете проверить на вставку второго узла, так как нет необходимости настраивать обход узлов в этом случае). Для обработки всех трех случаев, ваш insert бы что-то выглядеть следующим образом:

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; 
    } 
} 

Ваши свободным это также немного неловко, как вы обычно проверить, выделяются ли ->next принять решение относительно текущего узла, а затем убирать отступать вне цикла. (Во многом это зависит от вас, я просто представить альтернативу ниже, мой iter вашего cur и мой victim вашего previous)

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

Наконец, с valgrind вы можете получить ошибку относительно основывая прыжок на неинициализированном значных при использовании malloc (ваши варианты использования malloc затем memset, или просто использовать calloc - которые оба выделяет и устанавливает новую память для 0/NULL)

Собираем все вместе, вы могли бы сделать что-то вроде следующего, чтобы разрешить вопросы:

#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; 
} 

Пример входных данных

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

Пример использования/вывода

$ 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) 

Посмотрите на все решения, и дайте мне знать, если у вас есть какие-либо вопросы, ,

Answer 2

В функции insert вы выделить структуру дважды:

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

Первый получает потерянную вы перезаписываете указатель в item со следующим распределением.

Кроме того, вы не инициализируете член недавно назначенного узла next, который вызывает предупреждения, выданные valgrind, поскольку вы разыскиваете данные, которые не были инициализированы.

Answer 3

Внутри вашей вставки():

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

вы звоните таНос() дважды на item, в результате чего первый кусок памяти, выделяемой быть потеряно навсегда ..

С, что я имею в виду, что вы убежище теперь не отслеживайте этот кусок памяти, поэтому в конце вашей программы, которая является последним шансом освободить память, вы этого не делаете, что приводит к выделенной памяти, но никогда не освобождается!

Представьте, что ОС обрабатывает всю память вашего компьютера. Ваша программа входит в игру и запрашивает некоторую память. ОС дает вам указатель на тот кусок памяти, который он выделил для вас (вы должны выпустить его, когда вам это больше не нужно). Этот указатель имеет значение, которое мы не знаем априори.

Что вы делаете с заходом malloc() во второй раз и назначая его возвращаемое значение item, является перезапись, что уникальное значение указателя (адрес памяти, который вы получили) и получил новый адрес, указывающий на вновь выделенная память.

Итак, теперь вы запросили два куска памяти, но знаете только адрес второго куска памяти. Итак, как вы можете освободить первый кусок памяти, когда вы не знаете его адрес?

Вы не можете! И это неправильно, так как это приведет к утечке памяти, как вы покажете.

_{Аналогия будет состоять в том, что память представляет собой театр (например, Epidaurus), и каждое место является ячейкой памяти. ОС - менеджер мест в театре. Вы запрашиваете место, менеджер дает вам один идентификатор места, которое он назначил вам, и вы записываете его на электронную заметку. Затем вы запрашиваете еще одно место, менеджер проверяет, имеются ли еще доступные места в театре, да, есть, поэтому он дает одно место и, конечно, соответствующий идентификатор. Вы ошибочно напишите это по электронной записке, которую вы написали предыдущий идентификатор. Итак, теперь вы знаете только второй идентификатор, таким образом, второе место, а не первый идентификатор, таким образом, вы не знаете, где находится это место (театр большой, и вы об этом мало знаете).}

---

Однако это не единственная проблема, когда вы «создать» item, присвоить значение, но не назначить что-то next. Идем дальше и сделать:

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

---

После всего этого, вы должны быть в состоянии произвести следующий вывод:

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

Answer 4

Вы два mallocs для каждого узла. Вы только хотите. Вы можете оставить его в объявлении и отбросить следующую строку, которая дублирует malloc и перезаписывает первый.