неправильный способ освободить структуру данных - PullRequest
Новая
       79

неправильный способ освободить структуру данных

2 голосов
/ 04 июля 2019

У меня был экзамен по C-программированию в университете, один из вопросов на этом экзамене состоял в том, как освободить структуру данных связанного списка.

Мой подход заключался в освобождении данных для каждого узла, но без уважительной причины я не получил баллов за это упражнение.

Это был мой код, который не был принят: 

#include <stdlib.h>

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

void free_list(struct node *head) {
  for (struct node *p = head; p != NULL; p = p->next) {
    free(p);
  }
}

Может кто-нибудь объяснить, что с ним не так и как правильно освободить связанный список из памяти?

Ответы [ 4 ]

4 голосов
/ 04 июля 2019

Последняя часть цикла for читает p->next после тело цикла вызвало free(p);.

Вам нужно буферизовать указатель: 

while (p != NULL)
{
  struct node * const next = p->next;
  free(p);
  p = next;
}
2 голосов
/ 04 июля 2019

раскручиваем удары ногтем по голове.Использование описательных имен делает это немного более очевидным.Вы хотите сохранить сохраненный указатель и затем перейти к следующему узлу в вашем списке до того, как вызовете free для сохраненного указателя, например, 

void free_list(struct node *head) 
{
    while (head) {
        struct node *victim = head;     /* save node to free */
        head = head->next;              /* advance to next before free */
        free (victim);                  /* free node */
    }
}
2 голосов
/ 04 июля 2019

Комментарий от Сандер де Дайкер потрясающий,

Найдите время, и вы поймете, что:

p освобождается до выполнения p->next, поэтому p->next считывает память, которая уже была освобождена.

Если вы ищете хороший способ освободить связанный список, используя for loop, попробуйте это: 

#include <stdlib.h>

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

void free_list(struct node *head) {
  struct node *q;
  for (struct node *p = head; p != NULL; p = q) {
    q = p->next;
    free(p);
  }
}

Эта ошибка задокументирована в C Библии Денниса Ритчи

0 голосов
/ 04 июля 2019

Может кто-нибудь объяснить, что с ним не так

Когда вы вызвали free на узле, вы не можете получить доступ к head->next. Вы должны освободить head->next до head.

и как правильно освободить связанный список из памяти?

Довольно элегантное решение - рекурсия. Рекурсия хороша для того, чтобы сделать код понятным, но если вы не знаете об опасностях, избегайте этого в рабочем коде. Я часто использую это для прототипирования. Вот пример. 

void free_list(struct node *head) 
{
    if(head) {
        // Before freeing the first element, free the rest
        free_list(head->next)     
        // Now it's only one element left to free
        free(head);
    }
}

Это работает так. Допустим, у нас есть список: [e0, e1, e2, ..., en]. Мы хотим освободить все элементы. Мы делаем это, сначала освобождая список [e1, e2, ..., en], а затем освобождая элемент e0. Следующий шаг работает так же. Мы хотим освободить [e1, e2, ... en], поэтому мы начнем с вызова того же алгоритма из списка [e2, e3, ..., en], а когда это закончится, мы освободим e1. Базовый случай - это когда мы получаем пустой список [], в этом случае мы ничего не делаем.

Вы также можете делать это не рекурсивно. Это не так красиво, но часто более эффективно и устраняет риск переполнения стека. Вот как бы я написал это в рабочем коде. 

void free_list(struct node *head) 
{
    struct node *tmp;
    while(head) {
        tmp = head;
        head = head->next;
        free(tmp);
    }
}
...