Massive Algorithms: CLRS 10.2-6 Union two lists

Exercises 10.2-6
The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation. Show how to support UNION in O(1) time using a suitable list data structure.

如果用链表实现，可以将第二个list连接到第一个list上.
https://github.com/amlord/CLRS/blob/master/Study_Alone/III-Data_Structures/Chapter_10-Elementary_Data_Structures/10.2-Linked_lists/Exercises/10.2-6/10.2-6.pdf

http://blog.csdn.net/lihenair/article/details/18046437

↓￣￣￣￣￣￣￣￣￣￣￣│

■■->a0->a1->....->an-1->an<-tailA

↓￣￣￣￣￣￣￣￣￣￣￣│

■■->b0->b1->....->bn-1->bn<-tailB

↓￣￣￣￣￣￣￣￣￣￣￣￣￣￣ |

■■->a0->a1->......->an-1->an ┐ |

| |

↓￣￣￣￣￣￣￣￣￣￣￣￣￣ |

b0->b1->......->bn-2->bn-1->bn---┘

↑

tailA

type struct node {
    ElemType v;
    struct node* next;
} Node;

struct List {
    Node* tail;
};

Node* p = tailA-next;

tailA->next = tailB->next->next;
tailB->next = p;free(p)

struct node{

char* word;

struct node* next;

}

struct Set{

struct node* head;

struct node* tail;

}

For every list beside with the head pointer we'll also keep a tail pointer.

Supporting union operation in O(1) time: Suppose we've two Sets S1 and 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;

}

Labels