Class 成员函数正常工作，但在作为另一个 class 的数据成员调用时陷入死循环

Question

我写了一个树结构，并做了一个基本的搜索功能来寻找树中的节点。树本身使用哨兵节点来标记所有端点（根的父节点，叶子的子节点），并且搜索简单地遍历节点，直到找到匹配项或命中哨兵节点。当我在树的实例上调用搜索功能时，它工作正常，但是当树是另一个 class 的数据成员时，它会卡住。在下面的代码中，"t.search(1)" 有效，但 "embedded_tree.t.search(1)" 陷入无限循环。

我已经将其缩小到这样一个事实，即当调用 embedded_tree.t.search() 时，“&sentinel”的内容正确地指向了 sentinel 节点，但似乎是一个新指针，因为它不等同于 root、sentinel.parent 和 sentinel.child 的内容。从这里我被卡住了，我不确定如何调用它，以便 &sentinel 匹配构建树时创建的指针。

#include <iostream>

struct NODE {
    int key;
    NODE* parent;
    NODE* child;
    NODE() : key(0), parent(NULL), child(NULL) {};
};

struct TREE {
    NODE sentinel;
    NODE* root;

    TREE()
    {
        sentinel = *new NODE;
        sentinel.parent = &sentinel;
        sentinel.child = &sentinel;
        root = &sentinel;
    }

    NODE* search(int k)
    {
        NODE* x = root;
        while (x != &sentinel)
        {
            if (x->key == k) return x;
            x = x->child;
        }
        return &sentinel;
    }
};

struct A {
    TREE t;

    A() : t(*new TREE()) {};
};

int main()
{
    TREE t;
    t.search(1);

    A embedded_tree;
    embedded_tree.t.search(1);
}

Answer 1

您将动态内存分配与堆栈分配混淆了。当你做

sentinel = *new NODE

不好的事情发生了。在堆栈上为 NODE sentinel 分配内存，然后在 new 运算符中为 NODE 分配内存，然后分配给 sentinel 变量，并在 new 运算符中创建内存丢失了。你应该重写你的代码来使用指针，并添加析构函数，像这样

#include <iostream>

struct NODE {
    int key;
    NODE* parent;
    NODE* child;
    NODE() : key(0), parent(NULL), child(NULL) {};
};

struct TREE {
    NODE* sentinel;
    NODE* root;

    TREE()
    {
        sentinel = new NODE;
        sentinel->parent = sentinel;
        sentinel->child = sentinel;
        root = sentinel;
    }

    ~TREE() {
        if (NULL != sentinel) {
            delete sentinel;
            sentinel = NULL;
            root = NULL;
        }
    }

    NODE* search(int k)
    {
        NODE* x = root;
        while (x != sentinel)
        {
            if (x->key == k) return x;
            x = x->child;
        }
        return sentinel;
    }


};

struct A {
    TREE* t;

    A() : t(new TREE()) {};
    ~A() {
        if (NULL != t) {
            delete t;
            t = NULL;
        }

    }
};

int main()
{
    TREE t;
    t.search(1);

    A embedded_tree;
    embedded_tree.t->search(1);
}

但是，既然我们在谈论 C++，我建议您在熟悉手动内存管理之后再看看智能指针和容器。

Class 成员函数正常工作，但在作为另一个 class 的数据成员调用时陷入死循环

Class member function works normally, but gets stuck in an infinite loop when called as a data member of another class

c++

tree

loops

infinite