Ensemble disjoint comme liste chaînée

Question

Quelqu'un peut-il me diriger vers des informations sur des ensembles disjoints sous forme de liste chaînée? Je ne peux pas trouver de code sur ce sujet. Langue C++

Answer 1

Eh bien je pense que vous pouvez trouver des informations dans cette page de Wikipedia. Bien sûr, cette information est écrite en pseudo-code, mais n'est pas difficile à traduire.

Answer 2

Boost a une implémentation: http://www.boost.org/doc/libs/1_39_0/libs/disjoint_sets/disjoint_sets.html. Devinez c'est ce que vous cherchez.

Answer 3

Je viens d'écrire ceci, si quelqu'un est toujours intéressé. Je mettais en œuvre 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; 
}