集合及运算

可以用树表示集合，树的结点代表集合的元素

• 存储结构

这里采用数组的存储形式

#define ElementType int
typedef struct SetNode
{
	ElementType data;
	ElementType parent;
}SetType;
int size=0;

• 创建集合

因为创建不是要讨论的核心，为了方便，这里采用了暴力的创建方法
为了区分根结点以及哪个根结点更大，这里用根结点的parent标识，例如：根结点r1有3个孩子，则r1的parent就是-4（是负数就是根结点）

void CreateSet(SetType* s)
{
	
	s[0].data=1;s[0].parent=-3; 
	s[1].data=2;s[1].parent=1; 
	s[2].data=4;s[2].parent=1; 
	s[3].data=3;s[3].parent=-4; 
	s[4].data=8;s[4].parent=3; 
	s[5].data=7;s[5].parent=3; 
	s[6].data=5;s[6].parent=3;
	size=7;
}

• 查找某个元素的根结点，返回根结点的下标

先找到查找元素的下标i
如果它的父结点大于0，说明不是根结点，递归找父结点的根结点，小于0，则找到了根结点，返回根结点的下标

ElementType Find(SetType* s,ElementType x)
{
	int i;
	for(i=0;i<size && s[i].data!=x;i++ );
	if(i>=size) return -1;//没找到
	if(s[i].parent>0)	return Find(s,s[i].parent);
	else return i;
}

• 合并两个集合

将元素少的 根结点（r1）并在另一个根结点（r2）上
r2.parent等于两个根结点的parent之和
r1的parent等于r2的data

void Union(SetType* s,ElementType root1,ElementType root2)
{
	if(s[root1].parent<s[root2].parent)
	{
		s[root1].parent+=s[root2].parent;
		s[root2].parent=s[root1].data;
	}
	else
	{
		s[root2].parent+=s[root1].parent;
		s[root1].parent=s[root2].data;
	}
}

• 输出和主函数（用来测试）

void PrintSet(SetType* s)
{
	
	for(int i=0;i<size;i++)
	{
		printf("%d---->%d\n",s[i].data,s[i].parent);
	}
}
int main(int argc, char** argv) {
	SetType s[10];
	CreateSet(s);
	PrintSet(s);
	printf("----------find-------------\n");
	printf("%d\n",Find(s,7));
	printf("----------Union-------------\n");
	Union(s,0,3);
	PrintSet(s);
	return 0;
}

• 运行结果