Как этот деструктор с односвязным списком вызывает бесконечный цикл? - PullRequest
Новая
       19

Как этот деструктор с односвязным списком вызывает бесконечный цикл?

0 голосов
/ 14 декабря 2018

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

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

Однако, поскольку этот связанный список не является частью внешнего класса и управляет всеми операциями, я немного запутался в том, как написать деструктор.

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

Версия 2 вызвала бесконечный цикл.Я не понимаю почему, так как это один из способов реализации деструктора для класса контейнера, который управляет связанным списком Node.

Версия 3 работает хорошо, но слишком многословно.

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

Любая помощь, объясняющая, почему Версия 2 не работает и почему неправильно реализовывать деструктор таким образом, приветствуется!

Структурный связанный список 

#include <iostream> 
#include <string> 
using namespace std; 

struct Node
{   
    int id; 
    Node* next; 
    Node(int newId = 0, Node* newNext = NULL)
    : id(newId), next(newNext) { } 
};

Версия деструктора 1 

~Node()
{
    if (next != NULL)
        delete next; 
}

Версия деструктора 2 

~Node()
{
    Node* lead = this; 
    Node* follow = this;

    while (follow != NULL)
    {
        lead = lead->next; 
        delete follow; 
        follow = lead; 
    }
}

Версия деструктора 3 

~Node()
{
    Node* lead = this; 
    Node* follow = this;

    if (follow != NULL)
    {
        lead = lead->next; 
        delete follow; 
        follow = lead; 
    }
}

Main 

int main()
{
    Node* head = NULL; 
    head = new Node(23, head); 
    head = new Node(54, head); 
    head = new Node(81, head);
    head = new Node(92, head); 
    delete head;     
    return 0; 
}

Ответы [ 2 ]

0 голосов
/ 14 декабря 2018

Вам нужно только каждый Node удалить (максимум) один другой Node, чтобы в конечном итоге удалить все узлы.Переназначение локальных указателей не влияет на структуру списка.

И 2, и 3 - delete this, что в лучшем случае является подозрительным, плюс некоторая неуместная церемония в деструкторе.Они оба неопределенное поведение, удаляя один и тот же объект (как минимум) дважды.

Ваша первая попытка близка.

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

struct Node
{   
    int id; 
    std::unique_ptr<Node> next; 
    Node(int id = 0, std::unique_ptr<Node> next = {})
    : id(id), next(std::move(next)) { } 
    // correct destructor is implicit
};
0 голосов
/ 14 декабря 2018

В версии 2 вы написали цикл, который очищает весь список за один вызов деструктора, просматривая список и удаляя каждый элемент.Однако происходит не то, что у вас есть только один вызов деструктора.Каждый раз, когда элемент удаляется, он снова вызывает деструктор.

Таким образом, в итоге delete follow преобразуется в delete this (потому что follow = this;) для первого вызова.Затем это вызывает повторный вызов деструктора первого узла, вызывая бесконечный цикл.

Следующие узлы будут уничтожены несколько раз, что приведет к неопределенному поведению, но он даже не попадет из-за этого бесконечного цикла.

...