Блог

Главная - Вопросы по программированию - Утечка памяти при вставке в отсортированный связанный список

Утечка памяти при вставке в отсортированный связанный список

#c #memory-leaks #linked-list #valgrind #free

#c #утечки памяти #связанный список #valgrind #Бесплатно

Вопрос:

Я использовал функцию, предоставленную моим профессором, которая вставляет данные (целые числа) в отсортированный связанный список.

 void sorted_insert(int x,node_t **list)
{
  node_t *q = NULL, *pq = NULL, *new_node = NULL;

  q = *list;

  while (q amp;amp; x > q->data)
  {
    pq = q;
    q = q->next;
  }

  new_node = malloc(sizeof(node_t));
  new_node->data = x;
  new_node->next = q;

  if (!pq) { *list = new_node; }
  else { pq->next = new_node; }

}

Основные вызовы:

 node_t *list = NULL
sorted_insert(x,amp;list);

Я протестировал его, сохранив 100 случайных целых чисел, и он делает то, что ожидается, поскольку числа отсортированы. Позже я использовал пользовательскую функцию free для освобождения каждого узла, например:

 void free_list(node_t *list)
{
  node_t *tmp = NULL;

  for (; list; list = list->next)
  {
    tmp = list;
    free(tmp);
  }
  return;
}

Однако, когда я анализирую программу с помощью valgrind, это показывает, что я пропускаю память в функции sorted_insert , а если быть точным, в этой строке: new_node = malloc(sizeof(node_t));

Вывод Valgrind:

 ==9478== 160 (16 direct, 144 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==9478==    at 0x483C7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9478==    by 0x109270: sorted_insert (list_insert_sorted.c:23)
==9478==    by 0x10938D: main (list_insert_sorted.c:55)

Почему это происходит? Что-то не так с моей бесплатной функцией? Заранее благодарю вас.

РЕДАКТИРОВАТЬ: я изменил цикл for, и даже если я не пропускаю узлы, я все еще пропускаю память.

Комментарии:

1. list = list->next; выполняется дважды за цикл, фактически вы освобождаете только каждый другой узел в списке.

2. @PhilippGesang Это ошибка с моей стороны, я исправил ее, но я все еще протекаю…

3. непроверено: но ваша бесплатная функция list в качестве условия тестирования перепроверена после бесплатной второй итерации и затем не будет очищать все. Также я бы посоветовал вам удалить ненужные переменные и указатель на указатель, потому что более простой код проще отлаживать.

Ответ №1:

Ваш свободный итератор пропускает узлы, у вашего тела цикла есть list=list->next , и у итератора тоже, поэтому это происходит дважды. вам повезло, что у вас было четное количество узлов, что позволило избежать разыменования нулевого указателя, если у вас было нечетное число.

 void free_list(node_t *list)
{
  node_t *tmp = list;

  while(tmp)
  {
    list = list->next;
    free(tmp);
    tmp = list;
  }
  return;
}

Затем вы отредактировали код, чтобы удалить повторяющийся итератор, но в вашем отредактированном коде после free(tmp) этого память list , указывающая на, больше не действительна (тот же адрес, что и в tmp конце концов), и ваш отредактированный код разыменовывает только что освобожденную память, на которую list указывает итератор, поэтому попробуйте то, что я написал вместо этого.