0

私の最後のCLRSの質問で成功したので、ここに別の質問があります。

アルゴリズム入門、第2版、p。501-502では、互いに素な集合のリンクリスト表現が記述されており、各リストメンバーは次の3つのフィールドを維持しています。

  • セットメンバー
  • nextオブジェクトへのポインタ
  • 最初のオブジェクト（セット）に戻るポインタrepresentative。

リンクリストは、単一の「リンク」オブジェクトタイプのみを使用して実装できますが、教科書には、「ヘッド」リンクと「テール」リンクへのポインタを含む補助的な「リンクリスト」オブジェクトが示されています。「テール」へのポインタがあると操作が簡単になるため、小さいセットのリンクをそれに追加し始めるためにUnion(x, y)、大きいセットのすべてのリンクをトラバースする必要はありません。xy

ただし、テールリンクへの参照を取得するには、各リンクオブジェクトが4番目のフィールド（リンクリスト補助オブジェクト自体への参照）を維持する必要があるように思われます。その場合は、リンクリストオブジェクトを完全に削除し、その4番目のフィールドを使用してテールを直接ポイントしてみませんか？

これは本文の省略だと思いますか？

4

2 に答える 2

0

テキストを開いたところ、教科書の説明は私には問題ないようです。

私が理解していることから、データ構造は次のようなものです。

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

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

教科書は、私が持っている本（第2版）の「補助的な」リンクリスト構造については何も話していません。関連する段落を投稿できますか？

ユニオンを行うと、次のようになります。

// 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 に答える