我有一个对象数组,每个对象都有一个权重值,一些对象附加到另一个成为其父对象的对象。我需要将所有子对象的权重添加到父对象,还必须将附加到子对象的对象的权重等添加到父对象。
这是我迄今为止最好的方法,但不知何故最终根本没有改变 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);
}
}
}
最佳答案
您要实现的是后序、深度优先的树遍历。您恰好以带有子到父引用的数组形式获取树。
缺少父子引用会降低该过程的效率,但它仍然可行。
纯粹将其视为结构问题(暂时避免代码,以避免对您的代码做出假设),您正在查看一个递归调用,给定数组和“根”的索引:
- 找到以您的根为父节点的所有节点。
- 以这些节点中的每一个作为新根进行递归。
- 返回根的权重加上每个子节点的返回值(如果有的话)。
如果你的起始数组不能保证没有循环依赖,那么你还想传递当前访问节点的“链”,这样你就可以在你第二次访问一个节点时返回在同一个分支中。
要查找子节点,您只需每次遍历整个数组即可。这会给你一个 N^2 的整体效率,这是非常痛苦的,但它也是最容易理解的方法,所以它是一个很好的起点。了解其工作原理后,您就可以改进性能(例如在开始时进行单次传递以映射父子关系,这将使遍历本身更快)。
关于c++ - 在 C++ 中,如何找到直接或间接链接到数组特定元素的数组的所有元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35709511/