1

这不是家庭作业。

视觉上它看起来像一棵树，但所有叶子都是唯一的（在数据库中具有唯一的 ID）。它们之上的层次结构有些随意。每个复选框有 3 种状态：开、关和部分。叶子可以只检查或不检查。孩子的状态应该驱动父母的状态。单击复选框应该“切换”它，并向上或向下传播必要的更改。如果您单击部分选中的父级，它应该变为完全选中。每个孩子都有一个指向父母列表的指针（如果必须，我可以将其更改为一组）。每个父母都有一个按字母顺序排列的孩子列表。同时，出于展示的目的，这个结构是一棵树，我可以展开和折叠，如下图所示。

我确信这个算法之前已经被发明了。由于叶子的数量已经达到20,000，我确实关心实践中的表现。但是，我不会试图以代码简短易读为代价来榨取算法中的每一滴性能。

我认为原则上我应该走下来（如果有任何地方可以去）并确定所有应该更换的叶子。在那之后，我应该走上去。从这组叶子中，我应该找出一组可能受到影响的父母。然后将其过滤到需要更改的父级集，以及需要更改的值。然后将它们添加到集合中。然后我需要从这些节点上走并重复。在我有一组叶子和其他需要更改的节点以及它们的值之后，我将需要这样做......或类似的事情。基于矩阵的表示将过于昂贵。

我在C++using中一起破解这个东西MFC，但我的问题几乎与语言无关。但是，我更喜欢具体的实现而不是算法。一些语言，如 Python、Perl、Scala 可能有太现代的技巧。我会尝试坚持一些更传统的东西，比如 Java、C#（减去 LINQ）。

欢迎代码、链接、参考和问题。

替代文字

4

2 回答 2

1

“部分”状态是这里的一个问题。

如果您处于“部分”状态，并且孩子通过“未检查”，您应该也“未检查”还是保持“部分”状态？这需要查询所有其他孩子。我建议修改结构以保留 2 个数字而不是标志（对于非叶子）：

  • 孩子的数量（不直接离开）
  • 检查的孩子的数量（不直接离开）

当然，您需要在每次更新时保持它们的正确性。

为了正确更新它们，从孩子到父母的简单步行。如果您确保每个子级只有一个对其父级的引用（父级也是如此......），那么每次子级更改其状态时，都会更新其每个父级（从而更新每个父级）。

于 2010-11-30T14:01:56.197 回答
0

啊，我明白为什么这很复杂。您希望在将项目添加到“可能已更改”列表时对它们进行增量拓扑排序。这样，您只需在处理完元素后处理它们的子元素；这确保您只处理一次更改的元素，并且假设您有一个 DAG，您将不会遇到由于循环引用而无法处理任何元素的情况。

所以，一般算法是这样的：

  • 将所有变化的叶子子节点添加到要处理的节点集中。
  • 对于集合中没有要处理的子节点的每个节点：
    • 确定它的新状态。
    • 如果其状态发生变化，则将其父节点添加到要处理的节点集中。

困难的部分是“没有要处理的子节点的每个节点”。但这只是拓扑排序。

于 2010-11-29T21:39:50.890 回答