0

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

在《算法导论》，第二版，p。501-502，描述了不相交集的链表表示，其中每个列表成员维护以下三个字段：

  • 集合成员
  • 指向next对象的指针
  • 指向第一个对象（集合representative）的指针。

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

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

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

4

2 回答 2

0

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

据我了解，数据结构类似于：

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;
}
于 2010-06-27T22:59:55.717 回答
0 
why not drop the Linked List object entirely and use that fourth field to point directly to the tail?

可以从路径压缩中获得洞察力。那里的所有元素都应该指向列表的头部。如果它没有发生，那么 find-set 操作会执行此操作（通过更改 p[x] 并返回它）。你同样谈到尾巴。因此，如果只有实现这样的功能，我们才能使用它。

于 2013-07-26T08:10:43.287 回答