不相交集的链表表示 - 算法简介文本中的遗漏？

Question

成功解决了我的上一个 CLRS 问题， 这是另一个：

算法简介，第二版，第 12 页。 501-502，描述了不相交集合的链表表示，其中每个列表成员维护以下三个字段：

• 将成员
• 指针设置为下一个对象
• 指针返回到第一个对象（集合代表）。

尽管链表可以仅使用单个“链接”对象类型来实现，但教科书显示了一个辅助“链表”对象，其中包含指向“头”链接和“尾”链接的指针。拥有指向“尾部”的指针有利于Union(x, y)操作，因此不需要遍历较大集合x中的所有链接来开始将较小的集合 y 的链接附加到它。

然而，为了获得对尾部链接的引用，似乎每个链接对象都需要维护一个第四字段：对链接列表辅助对象本身的引用。在这种情况下，为什么不完全删除链接列表对象并使用第四个字段直接指向尾部呢？

您认为这是文本中的遗漏吗？

Answer 1

我刚刚打开文本，教科书的描述对我来说似乎很好。

据我了解，数据结构是这样的：

struct Set {
    LinkedListObject * head;
    LinkedListObject * tail;
};

struct LinkedListObject {
    Value set_member;
    Set *representative;
    LinkedListObject * next;
};

教科书没有谈到我的书（第二版）中的任何“辅助”链表结构。你能贴出相关段落吗？

建立一个联盟会是这样的：

// No error checks.
Set * Union(Set *x, Set *y) {

    x->tail->next = y->head;    
    x->tail = y->tail;

    LinkedListObject *tmp = y->head;

    while (tmp) {

        tmp->representative = x;
        tmp = tmp->next;

    }
    return x;
}

Answer 2

why not drop the Linked List object entirely and use that fourth field to point directly to the tail?

可以从路径压缩中获得见解。所有元素都应该指向列表的头部。如果没有发生，则查找集操作会执行此操作（通过更改 p[x] 并返回它）。你同样谈论尾巴。所以只有实现了这样的功能我们才能使用它。