我正在尝试在 Cormen 等人的《算法简介》中进行此练习，该练习与分离集数据结构有关：
假设我们要添加操作PRINT-SET(x)，给定
一个节点x并打印所有成员x已设置，按任何顺序。展示如何
我们可以只向不相交集中的每个节点添加一个属性
森林所以PRINT-SET(x) takes 时间与成员数量呈线性关系
的x's set，以及其他操作的渐近运行时间
没有变化。假设我们可以在 O(1) 内打印集合中的每个成员
时间。
现在，我很确定所需的属性是尾指针，这样它就可以跟踪孩子们。
由于不相交集合结构已经具有父属性，find-set(x)可以轻松打印出朝一个方向移动的节点。但现在有了尾指针，我们也可以朝另一个方向走。
但是，我不确定如何编写算法来做到这一点。如果有人可以用伪代码帮助我，我将不胜感激。
每个节点应该有一个next指向其所在集合中下一个节点的指针。集合中的节点应形成一个循环链表.
当单例集第一次创建时，节点的next指针指向自身。
当您将集合与节点合并时X并用节点设置Y（并且您已经通过标准化为集合代表来检查这些集合是否不同），您可以合并循环链表，只需交换即可完成X.next and Y.next;所以这是一个O(1)手术。
列出包含节点的集合中的所有元素X，遍历从 开始的循环链表X.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
