1

我有这堂课：

class obj
{
public:

    obj()
        : parent(nullptr),
        depth(0)
    {   }

    obj* parent;
    list<obj> children;
    int depth;  // Used only for this example
};

为了填充我的数据结构，我使用如下递归函数：

void recursive(obj& parent)
{
    if(parent.depth == 1)
        return;

    obj son;
    son.parent = &parent;
    son.depth = parent.depth + 1;

    recursive(son);

    parent.children.push_back(son);
}

以这种方式为例：

obj root;
recursive(root);

如果您注意，您会看到递归函数中的测试是否是：

if(parent.depth == n)
    return;

使用n >= 2此代码将不起作用（root->son->son一旦退出递归函数，“孙子”父级的存储地址等将不是有效地址）。

解决此问题的一种方法是使用指针列表 ( list<obj*> children) 而不是值列表：

void recursive(obj& parent)
{
    if(parent.depth == 2)
        return;

    obj* son_ptr = new obj();
    son_ptr->parent = &parent;
    son_ptr->depth = parent.depth + 1;

    recursive(*son);

    parent.children.push_back(son_ptr);
}

是否有另一种方法可以完成相同的工作并将objs 存储在值列表中而不是指针列表中？

4

2 回答 2

4

在你开始创建更多的孩子之前，这不只是固定对象的地址吗？为此，首先将它们放入子列表中，然后递归...

void recursive(obj& parent, int n)
{
    if (parent.depth == n)
        return;

    obj son;
    son.parent = &parent;
    son.depth = parent.depth + 1;
    parent.children.push_back(son);

    recursive(parent.children.back(), n);
}
于 2012-07-04T22:36:40.597 回答
1

您可能会考虑在 s 中存储唯一 ID obj，这样 s 的实例obj不会定义表示对象的身份，而是定义其 ID。如果这样做，您可能会存储 ID 以链接相关obj的 s 而不是存储指针。

例如，您可以更改obj类以包含一个int字段id：

class obj {
public:
    obj()
        : parent(nullptr),
          depth(0)
    {
        // Not thread-safe; would need to get protected if multi-threaded
        id = nextId++;
    }

    static int nextId;

    int id;
    int parentId;
    list<int> childrenIds;

    int depth;  // Used only for this example
};

每当您构造一个新obj的来表示一个新的逻辑“事物”时，您都可以为该字段分配一个新的、唯一的值id。当您想在代表相关“事物”的 s 之间建立关系时obj，您可以 - 例如 - 使用parentId字段而不是parent指针字段：

void recursive(obj& parent)
{
    if (parent.depth == 1) {
        return;
    }

    obj son;
    son.parentId = parent.id;
    son.depth = parent.depth + 1;

    recursive(son);

    parent.childrenIds.push_back(son.id);
}

当您想要跟随链接时，这需要更多的工作：而不是跟随指向 parent 的指针obj，而是需要在您维护obj的一些全局obj列表中查找（搜索有parentId问题的）。

当然，这实际上取决于这些objs 真正代表什么，以及您要实现的更广泛的目标......

于 2012-07-04T22:03:52.297 回答