Функция очистки выделенной памяти не работает
Пытаюсь сделать DTC на C. Вот структура узлов:
typedef struct node {
int value;
struct node *lower;
struct node *higher;
} node;
Чтобы освободить память, выделенную с помощью malloc(), я реализовал эту функцию:
void free_nodes(node*a) {
if (a->higher != NULL) {
free_nodes(a->higher);
}
if (a->lower != NULL) {
free_nodes(a->lower);
}
if (a->higher == NULL && a->lower == NULL) {
free(a);
}
}
В качестве параметра он принимает указатель на корневой узел.
Я пытался использовать здесь рекурсию, но, похоже, она не освобождает все узлы. Он способен освободить только два узла (я проверял с помощью valgrind).
Ответы 2
И если так?
void free_nodes(node*a){
if (a-> higher != NULL){
free_nodes(a-> higher);
a-> higher = NULL; // This isn't necessary if you remove the last check
}
if (a-> lower != NULL){
free_nodes(a-> lower);
a-> lower = NULL; // This isn't necessary if you remove the last check
}
// If you remove this check, then you don't need to set anything to NULL
if (a-> higher == NULL && a-> lower == NULL){
free(a);
}
}
Таким образом, его можно упростить до:
void free_nodes(node*a){
if (a-> higher != NULL){
free_nodes(a-> higher);
}
if (a-> lower != NULL){
free_nodes(a-> lower);
}
free(a);
}
Одиночная проверка в начале (if (a == NULL)) более лаконична, но она выполняет одну ненужную проверку для корневого узла.
Нет смысла устанавливать указатели на ноль, если вы знаете, что в конце освободите узел. Правильное решение – просто избавиться от чека.
Бармар, проверка NULL этих указателей вызвала проблему, поэтому я оставил это в коде.
Полезная причина для установки значений NULL заключается в том, что ложный доступ к свободной памяти с большей вероятностью вызовет более раннюю UB. Хотя здесь никаких гарантий.
Ваш код не проверяет, что аргумент указателя не равен нулю перед его использованием. Такое количество защитного кодирования, вероятно, того стоит. Это позволяет упростить функцию: if (a != NULL) { free(a->lower); free(a->higher); free(a); }.
Я просто хотел остановиться на распространенной ошибке, когда указатель на удаленный объект остается. И эту ошибку допустил ОП.
@JonathanLeffler, а если мы будем относиться к этой функции как к деструктору в C++? То есть зачем проверять NULL, если никто, кроме меня, не может сбросить мой указатель.
Что насчет этого? Это будет работать. Проверка значения null вверху означает, что вам не нужно проверять значение null перед рекурсивным вызовом. И я вижу, что сделал опечатку; вызовы free(a->lower); free(a->higher); должны быть рекурсивными вызовами — free_nodes(a->lower); free_nodes(a->higher);. Извините, это трудно обнаружить на мобильном телефоне (и гораздо легче обнаружить на ноутбуке).
@JonathanLeffler, я тебя сразу понял, опечатка не страшна, если говорить о более простой функции, то wohlstad дал нам максимально подробный ответ, и я проголосовал за его ответ.
@KonstantinMakarov То есть зачем проверять NULL, если никто, кроме меня, не может сбросить мой указатель, потому что ты через шесть месяцев не будешь знать, что ты сделал шесть месяцев назад. Или, может быть, даже через шесть дней. Если вы напишете достаточно кода, в конце концов вы вернетесь к своему старому коду и задаетесь вопросом, кто же был этот полный идиот...
@AndrewHenle, если ты не доверяешь себе, ты можешь пойти на крайние меры, например, в C#. Допустим, нам нужно присвоить значение элементу массива: 1. Проверка массива на наличие NULL. 2. Проверка параметра Типа. 3. Сравнение индекса с 0. 4. Сравнение индекса с размером массива. 5.Задание.
Я пытался использовать здесь рекурсию, но, похоже, она не освобождает все узлы.
Текущий узел (a) считается freed, только если его a->higher и a->lower равны NULL. Поскольку они нигде не установлены в NULL, a не будет freed.
Вместо этого a всегда следует freed, пока это само по себе не NULL.
void free_nodes(node*a) {
if (a == NULL) {
return; // nothing to do
}
free_nodes(a->higher); // no need to check for `NULL` here, it will be done in the recursive call
free_nodes(a->lower); // no need to check for `NULL` here, it will be done in the recursive call
free(a); // we know that a is not NULL since it was checked in the beggining
}
Обратите внимание, что ни один из указателей на самом деле не устанавливается на NULL после free их. Для подузлов это не имеет особого значения. Но корневой узел должен быть установлен в NULL вызывающей стороной после вызова free_nodes с его помощью.
В качестве альтернативы вы можете изменить free_nodes, чтобы принять node**a (указатель на указатель) и установить его в NULL внутри него. Для этого потребуется использовать *a повсюду, что немного более громоздко, но с точки зрения дизайна это имеет то преимущество, что гарантирует, что указатель не останется отличным от NULL после того, как он был freed, поэтому нет риска двойного бесплатно.
И последнее замечание:
Тело free_nodes также можно записать эквивалентно:
if (a) { // the same as `if (a != NULL)`
free_nodes(a->higher); // no need to check for `NULL` here, it will be done in the recursive call
free_nodes(a->lower); // no need to check for `NULL` here, it will be done in the recursive call
free(a); // we know that a is not NULL since it was checked in the beggining
}
Какой стиль лучше — вопрос личных предпочтений (лично я предпочитаю первый вариант, когда в первую очередь обрабатывается крайний случай, а остальное безоговорочно).
Ох чувак, это намного проще. Спасибо за ответ.
Еще проще с одной точкой выхода: if (a != NULL) { ... }.
@AugustKarlstrom Я обдумывал это. Я думаю, это вопрос личных предпочтений, но в конечном итоге я подумал, что логика становится чище, когда сначала обрабатывается крайний случай, а остальное безоговорочно.
@wohlstad Да, чисто структурированное программирование не для всех :-)
@AugustKarlstrom добавил примечание в альтернативном стиле.
Я забыл упомянуть, что значения
*higherи*lowerконечных узлов установлены в NULL и не имеют мусорных значений.