链表中的指针没有按预期工作

Question

这种链表的实现被打破了。节点地址[0]。Next与节点[1]地址不匹配。所以节点[1]。接下来是NULL(作为默认值)。我在搜索方法中添加了一些地址打印。看起来节点[1]没有初始化?

#include <iostream>
#include <vector>
using namespace std;
typedef struct Node_T {
    int data;
    Node_T *next;
} Node;
class LinkedList{
    public:
        vector<Node> nodes;
            LinkedList(){
        }
        void insert(int data) {
            Node temp_node;
            temp_node.data = data;
            temp_node.next = NULL;
            size_t len = nodes.size();
            nodes.push_back(temp_node);
            if (len > 0) {
                nodes[len - 1].next = &nodes[len];
            }
        }
        int search(int val){
            if (nodes.empty())
                return -1;
            Node *node_ptr = &nodes[0];
            // Debug
            cout << &nodes[1] << "n";
            cout << &nodes[0].next << "n";
            int i = 0;
            do {
                if (node_ptr->data == val) return i;
                    i++;
            } while((node_ptr = node_ptr->next) != NULL);
            return -1;
        }
};
int main()
{
    LinkedList llist;
    llist.insert(1);
    llist.insert(2);
    llist.insert(3);
    llist.insert(4);
    llist.insert(5);
    cout << llist.search(3) << "n";
    return 0;
}

显示:0x8e6a060 0x8e6a05c -1

Answer 1

当您向vector添加元素时，对vector元素的引用(以及因此的地址)无效。因此，您必须不要使用&nodes[0]或&nodes[len]这样的值，因为它们没有意义。

Answer 2

这样做的目的是掌握链表内部结构的窍门。您已将该内部结构替换为vector<Node>。

用

代替vector

private:
    Node* head;

作为你的数据成员。

在你的插入函数中，你应该动态地为节点分配内存

Node* newNodePointer = new Node;

并使用next等操作指针

值得指出的是，这是一个很好的练习，但你的"真正的"代码应该使用标准的库工具。

Answer 3

首先，您的打印输出不正确:这一行

cout << &nodes[0].next << "n";

打印next的地址，而不是打印next本身。改为

cout << nodes[0].next << "n";

给出正确的打印输出(演示)。

然而，主要问题是您保留了指向std::vector元素的指针。这些在第一次写入后失效，因为为增长的向量分配了新的存储空间。

你当然可以通过预先预留足够的空间来解决这个问题(从列表的构造函数调用nodes.reserve(1000);demo)，但这只是一个hack:您应该使用new和delete手动分配链表的元素。这就是这个练习的全部意义。

但是我仍然需要一个容器来确保节点将像预期的那样运行?

不，你不需要。类是容器。通过从头指针引用整个节点链，它可以确保整个链保持"活动"。