Блог

Я пишу код на основе двусвязного списка на C. Я ошибочно предположил, что удаление головного узла выполняется free(head_node) . И я мог видеть, что компьютер замедляется по мере выполнения (что, по-видимому, связано с утечкой памяти). Я искал stackoverflow и другие сайты, и код, с которым я обычно сталкивался для удаления связанного списка, был следующим :

 Node* current = head;
while( current != NULL ) {
Node* next = current->Next;
free( current );
current = next;
}
  

Когда я попробовал это в своем коде, программа просто зависает прямо там после оператора free, не возвращаясь к функции, которая вызывает эту функцию. Имеет ли приведенный выше код отношение к двусвязному списку? Данные моего члена списка также содержат много указателей. Когда я делаю free по одной из ссылок, освобождает ли это все данные, на которые указывают участники? Пожалуйста, предложите и уточните с помощью фрагментов кода или ссылок на книги.
Спасибо.

Когда я делаю free по одной из ссылок, освобождает ли это все данные, на которые указывают участники?

Нет. Это то, что произойдет, если вы удалите последнюю ссылку на объект на языке, собирающем мусор, но C так не работает. Вам нужно вручную освободить каждый бит выделенной вами памяти.

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

Данные моего члена списка также содержат много указателей.

Поскольку они есть, вам current->value также необходимо освободить каждую из них (и если они являются указателями на указатели …).

Опубликованный вами код должен работать для односвязных или двусвязных списков, но содержит некоторые предположения:

• Что нет необходимости выполнять очистку узла перед его освобождением; это часто неверное предположение.
• Конец списка отмечен нулевым указателем (т. Е. Последний Next элемент узла NULL )

Что касается первого предположения: поскольку вы динамически распределили данные в своих узлах и предполагаете, что у вас нет другого указателя на него где-то еще, который вы будете использовать для его очистки позже, вам нужно будет освободить эти данные перед освобождением каждого узла. В C это делается не для вас; общее правило таково, что если вам пришлось выделить его самостоятельно, вы также должны освободить его самостоятельно. Разумный способ справиться с этим — написать функцию для очистки и освобождения узла и вызвать ее вместо простого вызова free() ; ваша функция очистки все равно освободит узел, но сначала она освободит данные узла.

Что касается второго предположения: довольно распространенной практикой является установка указателя последнего узла Next NULL для обозначения конца, поскольку это позволяет легко определить, когда вы прошли весь путь по списку. Для двусвязного списка то же самое относится и к указателю первого узла Prev . Однако, если это циклический список, последний узел просто указывает на первый узел вместо этого — и это нарушило бы опубликованный вами код. В этой ситуации вы должны начать с узла head->Next вместо head , и проверить, является ли current это не head так, а не нет NULL . Затем разберитесь с head в конце, поскольку вы пропустили его изначально.

И еще одно: после освобождения списка убедитесь, что вы не оставили head указание на недопустимый (уже освобожденный) узел, а затем снова попробуйте получить доступ к списку…