Представление в виде связанного списка непересекающихся множеств - упущение в тексте «Введение в алгоритмы»?

Question

Имея успех с моим последним вопросом CLRS, вот еще один:

В Введение в алгоритмы , второе издание, с.501-502 описано представление связанного списка непересекающихся наборов, в котором каждый член списка поддерживает следующие поля три :

• элемент набора * указатель 1012 *
• на next объект
• указатель назад на первый объект (набор representative).

Хотя связанные списки могут быть реализованы с использованием только одного типа объекта «Ссылка»,учебник показывает вспомогательный объект «Связанный список», который содержит указатель на ссылку «заголовок» и ссылку «хвост».Наличие указателя на «хвост» облегчает операцию Union(x, y), поэтому нет необходимости проходить все ссылки в большем наборе x, чтобы начать добавлять к нему ссылки меньшего набора y.

Однако для получения ссылки на хвостовую ссылку может показаться, что каждый объект ссылки должен содержать четвертое поле : ссылку на сам вспомогательный объект связанного списка.В таком случае, почему бы не удалить объект Linked List целиком и использовать это четвертое поле, чтобы указать непосредственно на хвост?

Считаете ли вы это упущением в тексте?

Answer 1

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

Понимание может быть получено из сжатия пути.Там все элементы должны указывать на заголовок списка.Если этого не происходит, то это делает операция find-set (изменяя p [x] и возвращая это).Ты так же говоришь о хвосте.Так что, если такая функция реализована только тогда, мы можем использовать это.

Answer 2

Я только что открыл текст, и описание учебника мне кажется подходящим.

Из того, что я понимаю, структура данных выглядит примерно так:

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;
}