I just wrote this if someone is still interested. I ran CLRS Chap 21.1
/****************************************************************** * PROGRAM: Implementation of Linked-list representation of disjoi-* * nted sets in C++ without weighted union optimization. * * makeset, find takes O(1), Union takes O(n). Testing * * code is in the main method. * * AUTHOR: Bo Tian (bt288 at cam.ac.uk) drop me an email if you * * have any questions. * * LICENSE: Creative Commons Attribution 3.0 Unported * * http://creativecommons.org/licenses/by/3.0/ * *******************************************************************/ #include <iostream> using namespace std; long NodeAddress[10] = {0}; int n=0; template<class T> class ListSet { private: struct Item; struct node { T val; node *next; Item *itemPtr; }; struct Item { node *hd, *tl; }; public: ListSet() { } long makeset(T a); long find (long a); void Union (long s1, long s2); }; template<class T> long ListSet<T>::makeset (T a) { Item *newSet = new Item; newSet->hd = new node; newSet->tl = newSet->hd; node *shd = newSet->hd; NodeAddress[n++] = (long) shd; shd->val = a; shd->itemPtr = newSet; shd->next = 0; return (long) newSet; } template<class T> long ListSet<T>::find (long a) { node *ptr = (node*)a; return (long)(ptr->itemPtr); } template<class T> void ListSet<T>::Union (long s1, long s2) { //change head pointers in Set s2 Item *set2 = (Item*) s2; node *cur = set2->hd; Item *set1 = (Item*) s1; while (cur != 0) { cur->itemPtr = set1; cur = cur->next; } //join the tail of the set to head of the input set (set1->tl)->next = set2->hd; set1->tl = set2->tl; delete set2; } int main () { ListSet<char> a; long s1, s2, s3, s4; s1 = a.makeset('a'); s2 = a.makeset('b'); s3 = a.makeset('c'); s4 = a.makeset('d'); cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl; cout<<a.find(NodeAddress[2])<<endl; a.Union(s1, s3); cout<<a.find(NodeAddress[2])<<endl; }
segfault
source share