C ++中循环链表的析构函数？

Question

当为此循环单链表调用 'class LL' ~LL() 的析构函数时，程序崩溃而不是释放指针的堆 space。我该如何解决这个问题？

class Node {
public:
  int data;
  Node *next;
};

class LL {
private:
  Node *head, *tail;

public:
  LL() {
    head = NULL;
    tail = NULL;
  }
  // destructor
  ~LL() {
    Node *p = head;
    while (p->next != head) {
      p = p->next;
    }

    while (p != head) {
      p->next = head->next;
      delete head;
      head = p->next;
    }

    if (p == head) {
      delete head;
      head = nullptr;
    }
  }

  // circular singly Linked list

  void createLL() {
    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
      cin >> x;

      Node *t = new Node;
      t->data = x;
      t->next = NULL;

      if (head == NULL) {
        head = tail = t;
      } else {
        tail->next = t;
        tail = t;
      }
    }
    tail->next = head;
  }

Answer 1

您可以分两步完成：

使列表非循环。这有两个子步骤：
- ~~检测环路。有已发布的算法可以执行此操作。~~ 编辑：您的列表有一个尾指针，因此在您的情况下无需搜索它。
- 将后向引用节点指向空（或标记）
删除循环中非循环的列表。这是微不足道的。

Answer 2

在循环中尝试删除时，您的循环引用将导致内存被删除并具有未定义的行为。所以先考虑破环：

tail->next = 0;

然后循环删除

Node* p = head;
while(p)
{
    Node* temp = p;
    p = p->next;
    delete temp;
}

顺便说一句。 tail->next 总是指向头部。所以你总是会在同一个指针中同时拥有头部和尾部。所以你可以这样清理内存：

Node* p = tail->next; //this is head
tail->next = 0;
while(p)
{
    Node* temp = p;
    p = p->next;
    delete temp;
}

Answer 3

链接列表存在一些问题。

链表的析构函数假定 head 不为空，即使它有可能为空。在尝试清理内存之前，请务必检查 head 是否为空。完成后，您的原始析构函数看起来应该可以工作了。
如果用户输入小于或等于 0 的尺寸，函数 createLL 将调用未定义的行为。特别是这一行 tail->next = head;
TreateLL 用词不当，因为它实际上 'create' 不是预期意义上的新列表。内容未被清除，因此 n 个元素被附加到当前列表的末尾。
另外，循环链表可以只用一个尾指针创建。

然而，让循环链表的实现工作看起来像这样

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};
class LL {
private:
    Node* head, * tail;
public:
    LL() : head(nullptr),
        tail(nullptr) {
    }
    ~LL() {
        if (head) {
            Node* p = tail;

            while (p != head) {
                p->next = head->next;
                delete head;
                head = p->next;
            }
            if (p == head) {
                delete head;
                head = nullptr;
            }
        }
    }

    void storeUserInput() {
        int n, x;
        cin >> n;
        if (n <= 0) {
            return; //no input to retrieve.
        }
        for (int i = 0; i < n; i++) {
            cin >> x;
            Node* t = new Node;
            t->data = x;
            t->next = nullptr;

            if (head == nullptr) {
                head = tail = t;
            }
            else {
                tail->next = t;
                tail = t;
            }
        }
        tail->next = head;
    }

};
int main() {
    LL l;
    l.storeUserInput();

    char response;
    std::cin >> response;
}

您似乎可以访问 C++ 11 或更高版本的编译器，如果是这样，那么您应该使用 nullptr 代替 NULL，因为它是确定的指针类型。查看更多 here

C ++中循环链表的析构函数？

Destructor for circular linked list in c++?

c++

destructor

linked-list