2

这是我试图解决的家庭作业问题，只需要有人看看并告诉我我做对了还是磨损了..

动态集合运算 UNION 以两个不相交的集合 S1 和 S2 作为输入，它返回一个由 S1 和 S2 的所有元素组成的集合 S = S1 U S2。集合 S1 和 S2 通常被操作破坏。展示如何使用合适的列表数据结构在 O(1) 时间内支持 UNION

我正在考虑有两个可以在恒定时间内完成的链接列表，但为此我们需要记住指向列表的第一个（头）和最后一个（尾）元素的指针。结构节点{字符*字；结构节点*下一个；} 结构集{ 结构节点* 头；结构节点*尾；对于每个带有头指针的列表，我们还将保留一个尾指针。支持 O(1) 时间内的联合操作：假设我们有两个集合 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;
            }

我的方法是否朝着正确的方向发展？

4

3 回答 3

1

万一我们手头没有尾指针（实际上是链表的常见情况......），我们不能在 O(1) 中合并两个列表，因为我们必须遍历其中一个列表才能获得它尾指针，它需要 O(n)。

在这种情况下，手头只有两个头指针，“合适的列表数据结构”必须是一个双循环链表。我们断开LIST_1 的头元素和它的下一个元素之间的链接，并断开LIST_2 的头元素和它的上一个元素之间的链接。然后我们连接两个头部元素并连接其他两个元素。因此，我们得到了另一个双循环链表，并且保留了“指针流”（这就是为什么我们不应该断开 LIST_2 的头元素与其下一个元素的连接）。

于 2016-01-07T05:39:20.043 回答
0

是的，这就是我会采取的相同方法。

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
于 2013-10-05T17:26:02.867 回答
0

在您提到的问题中，我们可以使用任何合适的列表数据结构（您给出的答案也考虑了指向尾部的指针，除非您想使用 O( 1）通常我们在谈论链表时只考虑头节点的概念）因此我们将使用双循环链表。现在我们必须加入 2 个集合，以便我们可以执行以下操作以在 O(1) 中实现它

(headS1->prev)->next = headS2;
temp = headS1->prev;
(headS2->prev)->next = headS1 ;
headS1->prev = headS2->prev ;
headS2->prev = temp;
于 2018-10-15T22:23:58.497 回答