Liny_@NotePad

沉迷ACG中

离散集合的find与union操作

 @ _ @

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define Type int
  5. #define N 100
  6.  
  7. typedef struct Tree_node {
  8.         struct Tree_node*  parent;
  9.         int rank;
  10.         Type value;
  11. }NODE;
  12.  
  13. NODE* find(NODE *xp){
  14.         NODE *wp, *yp = xp, *zp = xp;
  15.         while(yp->parent){
  16.                 yp = yp->parent;
  17.         }
  18.         while(zp->parent){
  19.                 wp = zp->parent;
  20.                 zp->parent = yp;
  21.                 zp = wp;
  22.         }
  23.         return yp;
  24. }
  25.  
  26. NODE* unionTree(NODE *xp, NODE *yp){
  27.         NODE *up, *vp;
  28.         up = find(xp);
  29.         vp = find(yp);
  30.         if(up->rank<=vp->rank){
  31.                 up->parent = vp;
  32.                 if(up->rank == vp->rank){
  33.                         vp->rank ++;
  34.                 }
  35.                 up = vp;
  36.         }else{
  37.                 vp->parent = up;
  38.         }
  39.         return up;
  40. }
  41.  
  42. NODE* createNode(Type value, NODE* parent = NULL){
  43.         NODE* p = new NODE;
  44.         if(parent){
  45.                 p->rank = parent->rank + 1;
  46.         }else{
  47.                 p->rank = 1;
  48.         }
  49.         p->parent = parent;
  50.         p->value = value;
  51.         return p;
  52. }
  53.  
  54. int main(){
  55.         NODE* A[N];
  56.  
  57.         /* 建立集合{1,2,3,4} */
  58.         A[4] = createNode(4);   
  59.         A[3] = createNode(3,A[4]);     
  60.         A[2] = createNode(2,A[4]);
  61.         A[1] = createNode(1,A[2]);
  62.        
  63.        
  64.  
  65.         /* 建立集合{5,6,7,8} */
  66.         A[8] = createNode(8);   
  67.         A[7] = createNode(7,A[8]);     
  68.         A[6] = createNode(6,A[8]);
  69.         A[5] = createNode(5,A[6]);
  70.  
  71.         /*      合并两集合 */
  72.         unionTree(A[1],A[5]);
  73.  
  74.         /* 遍历集合 */
  75.         for(int i = 1; i<=8; i++){
  76.                 cout<<"结点"<<(A[i]->value)<<" ";
  77.                 if(A[i]->parent)cout<<"父结点"<<(A[i]->parent->value);
  78.                 else cout<<"该结点为根结点";
  79.                 cout<<endl;
  80.         }
  81.  
  82.         return 0;
  83. }

【算法】与【数据结构】 离散集合 find union Comments(0) 2009年3月10日 21:59