algorithm - 動的集合演算 UNION は、2 つの互いに素な集合 S1 および S2 を入力として受け取ります

Question

これは私が解決しようとした宿題の質問です.

動的集合演算 UNION は、2 つの互いに素な集合 S1 と S2 を入力として受け取り、S1 と S2 のすべての要素からなる集合 S = S1 U S2 を返します。集合Ｓ１およびＳ２は、通常、操作によって破壊される。適切なリスト データ構造を使用して O(1) 時間で UNION をサポートする方法を示します

一定時間で実行できる 2 つのリンクされたリストを作成することを考えていますが、そのためには、リストの最初 (先頭) と最後 (末尾) の両方の要素へのポインターを覚えておく必要があります。struct node{ char* word; 構造体ノード* 次; } struct Set{ struct node* head; } struct node* テール; ヘッド ポインターの横にあるすべてのリストについて、テール ポインターも保持します。O(1) 時間でユニオン演算をサポート: 2 つのセット S1 と S2 があるとします。

   PSEUDO-CODE:
            node* Union(Set S1,Set S2){
                  S1.tail->next = S2.head;
                  S1.tail = S2.tail;
                  Remove S2 from the list of sets;
                  return S1;
            }

私のアプローチは正しい方向に向かっていますか？

Answer 1

ええ、それは私が取るのと同じアプローチです。

S1:
A1->A2->A3

S2:
B1->B2->B3

Tail node of S1 (A3) linked to head node of S2 (B1)

S1US2:
A1->A2->A3*->*B1->B2->B3