链表的递归析构函数

Question

我试图搜索该主题，但我找到的所有线程都使用了 while 循环。但是我想递归地做这个：

template <typename S>
struct node {
    S data;
    node<S> * next; 
};

这是我在链表的析构函数（传递头部作为参数）中调用的函数：

void destroy(node<T> * n) {
    if(n->next != NULL){
        destroy(n->next);
    }
    delete n;
}

很遗憾，结果是分段错误。有人可以帮助我吗？

编辑：完整代码

#include <iostream>

using namespace std;


template <typename T>
class List {
    private:

    template <typename S>
    struct node {
        S data;
        node<S> * next; 
    };

    node<T> * first;

    node<T> * get_last_p() {
        if(first != NULL){
            return get_last(first);
        }
        return NULL;
    }

    node<T> * get_last(node<T> * n) {
        if(n->next != NULL) {
            return get_last(n->next);
        } else {
            return n;
       }
       return NULL;
    }

    void destroy(node<T> * n) {
        if(n->next != NULL){
            destroy(n->next);
        }  
        delete n;
    }


    public:

    List() {first->next = 0;}
    ~List() {destroy(first);}

    void add(T element) {
        node<T> * new_element = new node<T>;
        new_element->data = element;
        if(first == NULL){
            first = new_element;
        } else {
            get_last_p()->next = new_element;
        }
    }

    T get_last() {
        return get_last_p()->data;
    }

    T get_first() {
        return first->data;
    }

};

Answer 1

据我所知，在List的构造函数中，first没有被初始化，然后被立即访问。那是未定义的行为。即使 first 以某种不可靠的方式初始化为 null，并且 first->next = 0; 不会以某种方式崩溃，您的析构函数的 destroy 也会失败，因为 destroy假定其原始参数不为空。

我想你是故意的 List() : first{ new node{} } { first->next = nullptr; }

如果 first 不打算保存一个值，那么您将不得不重构您的代码以首先将 first 初始化为 null - 没有解决方法 - 并处理在所有代码中 first 明确为 null 的情况。您不能分配 first->next 空指针、无效指针或未定义指针。

链表的递归析构函数

recursive destructor for linked list

c++

recursion

linked-list

destructor