Связанный список не удаляется должным образом при передаче в качестве параметра в С++
У меня есть метод deleteList, который принимает в качестве входных данных заголовок одного связанного списка и удаляет все узлы.
В методе deleteList я могу убедиться, что все узлы удалены, но когда выполнение возвращается обратно к основному, myList не пуст. Таким образом, при последующем вызове LengthOfList код завершается ошибкой с исключением.
[Обратите внимание, что я не могу изменить подпись deleteList]
Вот код:
#include <iostream>
using namespace std;
typedef struct CodeNode* List;
struct CodeNode
{
char data;
List next;
CodeNode(char new_data, List new_next)
: data(new_data), next(new_next) {
}
};
int LengthOfList(List head)
{
int len = 0;
for (List ptr = head; ptr != nullptr; ptr = ptr->next) {
len++;
}
return len;
}
void deleteList(List head)
{
List prev = head;
while (head)
{
head = head->next;
delete(prev);
prev = head;
}
// I can verify that head is null and all the nodes have been deleted
}
int main(void)
{
List temp1 = new CodeNode('3', nullptr);
List temp2 = new CodeNode('2', temp1);
List myList = new CodeNode('1', temp2);
cout << "Before " << LengthOfList(myList);
deleteList(myList);
cout << "After " << LengthOfList(myList); // CODE FAILS HERE because myList is pointing to a bad memory address (it SHOULD be NULL)
}
but when the execution returns back to the main, myList is not empty. Освобожденная память. Его использование является неопределенным поведением.
I can verify that head is null and all the nodes have been deleted. - Вы можете убедиться в этом, потому что указатель head находится в конце связанного списка.
Обратите внимание, что вы не должны использовать ключевое слово struct вместе с идентификатором, как в typedef struct CodeNode* List;, а вместо этого вы должны просто использовать typedef CodeNode* List; и, кроме того, использовать объявление using вместо typedef как using List = CodeNode*;
Ответы 2
Пройти по ссылке
void deleteList(List& head)
Все, что делает ваш код, — это модифицирует переменную head в функции deleteList, которая не является той же переменной, что и head в main. Используя ссылку, вы делаете head в deleteList псевдонимом для переменной, используемой в вызывающей функции, и поэтому изменения в ней влияют на эту переменную.
Другой вариант — вернуть измененную переменную, поэтому в main
myList = deleteList(myList);
И в deleteList
List deleteList(List head)
{
...
return head; // return modified head
}
Оба подхода работают, это выбор стиля, который вы выбираете.
Я только что заметил ваш комментарий: «Обратите внимание, я не могу изменить подпись deleteList». Тогда я боюсь, что ваш код гарантированно не сработает. Нет никакого решения, учитывая специфические ограничения, которые вам были даны.
Удивительно, как часто мы видим это здесь, когда новичок борется с какой-то проблемой, но не может использовать ни одно из решений, которые использовал бы любой нормальный программист, из-за искусственных ограничений, наложенных на задачу их учителем. В некоторых случаях, как у вас, эти ограничения настолько суровы, что поставленная перед ними задача буквально не решается. Я предлагаю вам обратиться к учителю за советом.
В дополнение к этому, это важно, потому что указатель на освобожденную память не становится автоматически nullptr. И чтение его (сравнение с nullptr) приведет к неопределенному поведению.
Короче говоря, ваше решение делает именно это.
#include <iostream>
typedef struct CodeNode* List;
struct CodeNode {
char data;
List next;
CodeNode(char new_data, List new_next): data(new_data), next(new_next) {}
};
int main() {
List myList = new CodeNode('1', nullptr);
cout<<myList->data<<endl;
delete(myList);
cout<<myList->data<<endl;
return 0;
}
// given error
// AddressSanitizer: heap-use-after-free on address
// 0x602000000010 at pc 0x000000342fd6 bp 0x7fffcb6b5110 sp 0x7fffcb6b5108
И доступ к myList после удаления должен быть undefined, поскольку это пример heap use after free, который возникает, когда программа продолжает use a pointer after it has been freed.
Полезные ссылки
Решение
Ответ Джона уже дал ответ о том, как passing by reference может фактически обновить базовую переменную и произвести желаемый эффект.
Я просто хотел дополнить причину вашего понимания.
"это должно потерпеть неудачу" на самом деле нет, это просто не определено
Ну, что-то вроде, предполагается, что не удастся вывести значение, поскольку оно не определено.
Нет. Он не должен выводить значение. Он может делать что угодно. Он может вывести значение, которое ранее было сохранено в data, в этом нет ничего плохого.
Разве инструмент AddressSanitizer не мог бы обнаружить эту проблему, прежде чем выводить ранее сохраненные данные или делать что-либо произвольно? Насколько мне известно, в таком языке, как ржавчина, эти сценарии запрещены даже во время компиляции. Извините за мое понимание, я знаю, что операция delete или free действительно может сохранить значение нетронутым в соответствии с его реализацией. Но в каком сценарии обнаружение инструмента AddressSanitizer для таких сценариев будет отключено или отключено?
«Но в каком сценарии вывод или обнаружение инструмента AddressSanitizer будет отключен или выключен?» по умолчанию AddressSanitizer отсутствует. Это инструмент, используемый только для отладки. После того, как вы сделаете сборку релиза, AddressSanitizer не будет.
Присвоение аргументу функции (не ссылочному) не имеет никакого эффекта вне этой функции. В указателях нет ничего особенного. (Кроме того, псевдонимы типов указателей — это одна из тех вещей, которые кажутся отличной идеей, пока она не станет ужасной, и вы больше никогда этого не сделаете.)