ufsets.cpp

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#include "UFSets.h"
#include<iostream>
using namespace std;
UFSets::UFSets (int sz) {	
//构造函数：sz 是集合元素个数,双亲数组的范围
//为parent[0]~parent[size-1]。
     size = sz;			  //集合元素个数
     parent = new int[size];  //创建双亲数组
     for (int i = 0; i < size; i++) parent[i] = -1;	  
                                           //每个自成单元素集合
}

int UFSets::Find (int x) {
//函数搜索并返回包含元素x的树的根。
     if (parent[x] < 0) return x;   //根的parent[]值小于0  
     else return (Find (parent[x]));
}

void UFSets::Union (int Root1, int Root2) {
//求两个不相交集合Root1与Root2的并
     parent[Root1] += parent[Root2];
     parent[Root2] = Root1;
                     //将Root2连接到Root1下面
}

void UFSets :: 
WeightedUnion (int Root1, int Root2) {
//按Union的加权规则改进的算法
     int temp = parent[Root1] + parent[Root2];
     if (parent[Root2] < parent[Root1]) {
         parent[Root1] = Root2;     //Root2中结点数多
         parent[Root2] = temp;      //Root1指向Root2
    }
    else {  
         parent[Root2] = Root1;    //Root1中结点数多
         parent[Root1] = temp;      //Root2指向Root1
    }
}

int UFSets::CollapsingFind (int i) {
//使用折叠规则的搜索算法
    int j = i; 
	for (; parent[j] >= 0; j = parent[j]);
         //让 j 循双亲指针走到根
     while (parent[i] != j) {     //换 parent[i] 到 j
          int temp = parent[i];  
          parent[i] = j;  i = temp; 
    }
    return j;
}	

void UFSets::output(){
	for(int i=0;i<size;i++)
	{
		cout<<"结点"<<i<<" : ";
		if(parent[i]>=0)
			cout<<"父亲结点"<<parent[i]<<endl;
		else
			cout<<"是根结点，有 "<<(parent[i]*(-1)-1)<<"子女"<<endl;
	}
}