C++ 链表 HEAD 不断重置为 NULL

Question

我需要帮助来理解为什么我的链表方法没有按预期工作。

#include <iostream>
using namespace std;

class Node {
public:
    int Data;
    Node* Next;
    
    Node(int data) {
        Data = data;
        Next = NULL;
    }
};

void insertNodeAtEnd(Node* HEAD, int data) {
    Node* it = HEAD;
    if (HEAD == NULL) { HEAD = new Node(data); }
    else {
        while (it->Next != NULL) { it = it -> Next; }
        it -> Next = new Node(data);
    }
}

void printLinkedList(Node* HEAD) {
    Node* it = HEAD;
    while (it != NULL) {
        cout << it->Data << endl;
        it = it -> Next;
    }
}

int main() {
    Node* HEAD = NULL;
    // Node* HEAD = new Node(0);
    
    insertNodeAtEnd(HEAD, 5);
    insertNodeAtEnd(HEAD, 2);
    insertNodeAtEnd(HEAD, 10);
    
    printLinkedList(HEAD);
    return 0;
}

上面的main()函数不起作用（即：没有输出，一旦控件离开insertNodeAtEnd()，HEAD就会一直重置为NULL），我在这里发现了类似的问题在 SO 上解释说这是因为指针是按值传递的，这对我来说有部分意义。
为什么当我在 main() 函数中用 Node* HEAD = new Node(0); 替换 Node* HEAD = NULL; 时，如果指针作为值传递，它会按预期工作？

如果我像 Node* HEAD = new Node(0); 一样初始化 HEAD，但在最初 HEAD = NULL 的情况下，如何添加节点？我能够通过使用 pointer to pointer 使其正常工作，但我不明白为什么这种方法不起作用。很抱歉，如果我没有正确解释我的问题，如果需要任何澄清，请告诉我。

Answer 1

问题来自您的第一次插入。您更改退出该功能时重置的 head 值。您只能更改指针后面的值，不能更改指针本身。

一个解决方案是传递指针的指针。类似于：（未测试）

void insertNodeAtEnd(Node** HEAD, int data) {
    
    if (*HEAD == NULL) { *HEAD = new Node(data); }
    else {
        Node* it = *HEAD;
        while (it->Next != NULL) { it = it -> Next; }
        it -> Next = new Node(data);
    }
}

int main() {
    Node* HEAD = NULL;
    // Node* HEAD = new Node(0);
    
    insertNodeAtEnd(&HEAD, 5);
    return 0;
}

因为你不改变指针的指针，而只改变它后面的值（指向头的实际指针），一旦你退出函数，改变就会保留。

Answer 2

基本问题可以简化为这段代码：

void insertNodeAtEnd(Node* HEAD, int data) {
    //...
    if (HEAD == NULL) { HEAD = new Node(data); }
    //...
}

int main() {
    Node* HEAD = NULL;
    insertNodeAtEnd(HEAD, 5);
    //...

您似乎假设在 insertNodeAtEnd 内分配给 HEAD 会更改 main 内的 HEAD 变量。这不是真的。你的指针是按值传递的，所以地址是为函数复制的。更改此复制的变量不会更改 main.

内部的 HEAD 的值

要解决此问题，您可以将指针传递给指针，如下所示：

void insertNodeAtEnd(Node** HEAD, int data) {
    //...
    if (*HEAD == NULL) { *HEAD = new Node(data); }
    //...
}

int main() {
    Node* HEAD = NULL;
    insertNodeAtEnd(&HEAD, 5);
    //...

这个指向指针的指针仍然按值传递，但是它指向的指针将与 main 中的指针相同。

Answer 3

@Brotcrunsher 已经给出了答案。我发帖是为了帮助您实施更好的解决方案，它将列表的概念与列表的元素的概念分开，封装了所使用的方法当它超出范围时，它会释放它使用的资源：

#include <iostream>
using namespace std;

class Node {
public:
    int Data;
    Node* Next;

    Node(int data = 0) {
        Data = data;
        Next = nullptr;
    }
};

class List {
public:
    Node* Head = nullptr;

    void Insert(int data) {
        if (Head == nullptr)
            Head = new Node(data);
        else {
            Node* ptr;
            for (ptr = Head; ptr->Next != nullptr; ptr = ptr->Next)
                ;
            ptr->Next = new Node(data);
        }
    }

    void Print() {
        for (Node* ptr = Head; ptr != nullptr; ptr = ptr->Next)
            cout << ptr->Data << endl;
    }

    ~List() {
        Node* ptr = Head;
        while (ptr != nullptr) {
            Node* tmp = ptr;
            ptr = ptr->Next;
            delete tmp;
        }
    }
};

int main() {
    List list;
    list.Insert(5);
    list.Insert(2);
    list.Insert(10);
    list.Print();
    return 0;
}

C++ 链表 HEAD 不断重置为 NULL

C++ Linked List HEAD keeps resetting to NULL

c++

pointers

linked-list