c++ - 在 C++ 中，如何找到直接或间接链接到数组特定元素的数组的所有元素？

Question

我有一个对象数组，每个对象都有一个权重值，一些对象附加到另一个成为其父对象的对象。我需要将所有子对象的权重添加到父对象，还必须将附加到子对象的对象的权重等添加到父对象。

这是我迄今为止最好的方法，但不知何故最终根本没有改变 parent 的原始体重:

void showMasterClass::mass_manager(int parent)
{
    for (int n = 0; n < total_objects; n++)
    {
        object[n].setMass(object[n].getEmptyMass());
    }

    for (int n = 0; n < total_objects; n++)
    {
        if (object[n].getDockedTo() == parent)
        {
            object[parent].setMass(object[parent].getMass() + object[n].getMass());
            mass_manager_subroutine(n, parent);
    }
    }
}

void showMasterClass::mass_manager_subroutine(int objeto, int parent)
{
    for (int n = 0; n < total_objects; n++)
    {
        if (object[n].getDockedTo() == objeto)
        {
            object[parent].setMass(object[parent].getMass() + object[n].getMass());
            mass_manager_subroutine(n, parent);
        }
    }
}

Answer 1

您要实现的是后序、深度优先的树遍历。您恰好以带有子到父引用的数组形式获取树。

缺少父子引用会降低该过程的效率，但它仍然可行。

纯粹将其视为结构问题(暂时避免代码，以避免对您的代码做出假设)，您正在查看一个递归调用，给定数组和“根”的索引:

1. 找到以您的根为父节点的所有节点。
2. 以这些节点中的每一个作为新根进行递归。
3. 返回根的权重加上每个子节点的返回值(如果有的话)。

如果你的起始数组不能保证没有循环依赖，那么你还想传递当前访问节点的“链”，这样你就可以在你第二次访问一个节点时返回在同一个分支中。

要查找子节点，您只需每次遍历整个数组即可。这会给你一个 N^2 的整体效率，这是非常痛苦的，但它也是最容易理解的方法，所以它是一个很好的起点。了解其工作原理后，您就可以改进性能(例如在开始时进行单次传递以映射父子关系，这将使遍历本身更快)。