Я только что написал это, если кому-то все еще интересно. Я выполнял CLRS гл. 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;
}