C++ 指针不起作用？

Question

我在使用 C++ 指针时遇到问题。我正在尝试使用 Node 结构和 Tree 结构编写 splay 树。但是，经过测试，我遇到了一个问题。我的代码部分不起作用如下:

struct Node {
    Node* l, *r, *p;
    int v;
    Node() {}
    Node(int _v, Node* _p) : v(_v), p(_p) {}
};

struct Tree {
    Node* root;

    Tree() : root(0) {}

    //...

    void insert(int k) {
        if (!root) {
            root = new Node(k, 0);
            return;
        }
        Node* cur = new Node();
        cur->v = root->v;
        while (1) {
            int x = cur->v;
            cout << x << endl;
            return;
            if (k <= x) {
                //cout << x << endl;
                //return;
                if (!cur->l) {
                    cur->l = new Node(k, cur);
                    //splay(cur->l);
                    return;
                } else cur = cur->l;
            } else {
                if (!cur->r) {
                    cur->r = new Node(k, cur);
                    //splay(cur->r);
                    return;
                } else cur = cur->r;
            }
        }
    }

    //...
};

int main() {
    Tree t = Tree();
    t.insert(1);
    t.insert(5);
    return 0;
}

首先，我在树中插入了一个值为1的节点；由于没有根，树将其根分配为值为 1 的新节点。然后，当我将 5 插入树中时，发生了一些奇怪的事情。如果您保留原样的代码(保留第一个 cout)，那么它将为 x 打印出 1。但是，如果您注释掉第一个 cout 并返回并取消注释第二个 cout 并返回，您会发现它为 x 打印出一个随机垃圾编号，即使没有进行任何修改。谁能告诉我怎么了？

Answer 1

C++ 不会自动初始化类成员。

struct Node {
    Node* l, *r, *p;
    int v;
    Node() {}
    Node(int _v, Node* _p) : v(_v), p(_p) {}
};

当您在代码中创建一个新节点时，C++ 会为该节点分配一 block 内存，但不会清除它。所以 l、r 和 p 的值将是那里的任何值。
在您的算法中，测试:if (!cur->r) & (!cur->l) 当前失败，因为节点中有未初始化的垃圾，而不是 NULL.
因此，当您尝试插入第二个节点时，算法会认为根的右侧有一个有效节点。并尝试读取那里的内存和那里的值，即你看到的垃圾 x。根据垃圾的值(value)，对于某些运行代码的人来说，它也可能会崩溃 :)

此外，我 99.9% 确定 Node* cur 应该是指向树中节点的指针，而不是新节点，因此: 节点* cur = new Node(); cur->v = root->v; 是错误的，应该是 Node* cur = root;

正确的初始化 - 在 C++11 中你可以这样做:

struct Node {
    Node* l = nullptr;
    Node *r = nullptr;
    Node *p = nullptr;
    int v   = 0;
    Node() {}
    Node(int _v, Node* _p) : v(_v), p(_p) {}
};

否则

struct Node {
    Node* l;
    Node *r;
    Node *p;
    int v;
    Node() : l(NULL), r(NULL), p(NULL), v(0){}
    Node(int _v, Node* _p) : l(NULL), r(NULL), p(_p), v(_v) {}
};

您应该按照定义它们的相同顺序初始化类的成员。

现在代码中还有很多其他的问题:

树似乎分配了很多节点但不释放任何内存。 (最简单的方法是对 l 和 r 以及根节点使用 unique_ptr)

tree是子节点的拥有者吗？还是应该是Node拥有并左右分配？ (如果您对左右使用 std::unique_ptr 则消失)

您没有按照定义的顺序初始化成员。这可能会导致各种错误。 (因为编译器在不告诉你的情况下重新排序初始化)

Node 和 Tree 处理原始指针但不定义适当的 operator=，复制 ctor(或删除它们)(如果使用 unique_ptr 则消失)

Tree 缺少一个 dtor 来清理分配的内存(如果你使用 unique_ptr 就会消失)