内存泄漏，节点列表 C++

Question

我有这个旧考试的代码，我想修复它的错误。每次我调用 insertlast/insertfirst 时，我都会为我的列表分配新的内存，但我似乎无法释放它。我有运行它与 valgrind 并且每次我调用 insertfirst/insertlast 都会得到一个新的泄漏。 Valgrind 还抱怨我试图释放内存的循环。我得到这样的东西：

Invalid free() / delete / delete[] / realloc()
==4548==    at 0x4C2C2BC: operator delete(void*)(in/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4548==    by 0x4007D6: main (code6.cpp:67)
==4548==  Address 0xffefffea0 is on thread 1's stack

代码如下：

#include <iostream>
using namespace std;

template <class T>
struct Node {
    Node() : data(T()), next(nullptr) {}
    Node(T d, Node * p) : data(d), next(p) {}
    T data;
    Node<T> * next;
};

template <class T>
void insertlast (Node<T> * p, T data) { 
    if (p == nullptr) {
        p = new Node<T>(data, nullptr);
    } else {
        while (p -> next != nullptr) {
            p = p -> next;
        }
        p -> next = new Node<T>(data, nullptr);
    }
}

template <class T>
void insertfirst (Node<T> * & p, const T & data) {
    Node<T> * tmp = new Node<T>(data, p);
    p = tmp;
}

template <class T>
void printNode(Node<T> *& node) {
    cout << node->data << " -> ";
    while (node->next != nullptr) {
        node = node->next;
        cout << node->data << " -> ";
    }
    cout << endl;
}


template <class T>
void printNode2(Node<T> & node) {
    cout << node.data << " -> ";
    while (node.next != nullptr) {
        node = *node.next;
        cout << node.data << " -> ";
    }
    cout << endl;
}


int main() {
    Node<int> node;
    Node<int> * temp = &node;
    Node<int> * ref = &node;

    insertlast(ref, 5);
    insertfirst(ref, 3);
    insertlast(ref, 6);
    insertfirst(ref, 2);

    //printNode(ref);
    //printNode2(node);

    while(ref->next != nullptr){
        temp = ref->next;
        delete ref;
        ref = temp;
    }
    return 0;
}

如果你能帮我找出代码有什么问题，那就太好了。我的猜测是 insertfirst 中的指针引用有点可疑，但我无法弄清楚。提前致谢！

Answer 1

在你的 insertlast 函数中，如果参数 p 是 NULL，那么你的代码将泄漏 Node 的一个实例。您创建了新实例并将其地址分配给 p，但是一旦您离开该函数，p 就会超出范围并且您不再拥有指向新创建实例的指针。

我想你想像在你的 insertfirst 函数中一样传递对 p 的引用，但忘了把 & 字符放在那里。

Answer 2

当您第一次调用insertfirst时，您将创建一个新节点，其next指针是来自main的静态分配的node对象，然后当您遍历列表以删除其中的节点，您将尝试删除此 node 对象。

如果你想让一个哨兵对象位于列表的头部，你应该做的是让它的 next 指针指向新节点，并且新节点的 next 指针应该设置为p->next。所以像

template <class T>
void insertfirst (Node<T> * head, const T & data) {
    Node<T> * tmp = new Node<T>(data, head->next);
    head->next = tmp;
}

最后提示一下如何调试这些东西：画在纸上！每次操作后，画在纸上，这样的问题就很容易解决了现货.

Answer 3

这两个函数的接口不一致

template <class T>
void insertlast (Node<T> * p, T data) { 
    if (p == nullptr) {
        p = new Node<T>(data, nullptr);
    } else {
        while (p -> next != nullptr) {
            p = p -> next;
        }
        p -> next = new Node<T>(data, nullptr);
    }
}

template <class T>
void insertfirst (Node<T> * & p, const T & data) {
    Node<T> * tmp = new Node<T>(data, p);
    p = tmp;
}

在第一个函数中，参数声明为 Node<T> * p, T data，而在第二个函数中，参数声明为 Node<T> * & p, const T & data

在第一个函数中，您还应通过引用传递第一个参数。否则p是函数的局部变量，改变它不会影响原参数。

In可以这样定义

template <class T>
void insertlast ( Node<T> * &p, const T &data ) 
{ 
    if ( p == nullptr ) 
    {
        p = new Node<T>(data, nullptr);
    } 
    else 
    {
        Node<T> *tmp = p;
        while ( tmp->next != nullptr ) 
        {
            tmp = tmp->next;
        }

        tmp->next = new Node<T>( data, nullptr );
    }
}

另外你必须将main中的第一个节点初始化为nullptr

Node<int> *node = nullptr;

在堆栈中定义列表的第一个节点是个坏主意。简直是无效设计

内存泄漏，节点列表 C++

Memory leak, Node list C++

c++

pointers

memory-leaks