2011年软考程序员考试复习笔试知识点整理(11)2

 　　找到x所在集合的最父级代表元素

　　如果这个集合只有x自己,那么最父级代表元素当然就是它自己

　　*/

　　intFindSet(int * p,int x)

　　{

　　int tmp,px=x;

　　while(p[px]>=0) //找到x所在集合的代表元素

　　px=p[px];

　　/*

　　路径压缩,可选,如果需要频繁查询,压缩之后可以提高速度

　　即把从x到代表元素路径上的所有的元素的父节点都表示为代表元素

　　*/

　　while(p[x]>=0)

　　{

　　tmp=p[x];

　　p[x]=px;

　　x=tmp;

　　}

　　return px; //x元素所在集合的代表元素

　　}

　　/*

　　合并x和y所在的集合.

　　*/

　　voidUnionSet(int * p,int x,int y)

　　{

　　int tmp;

　　x=FindSet(p,x);

　　y=FindSet(p,y);

　　if(x==y)

　　return ;

　　tmp=p[x]+p[y];

　　if(p[x]>p[y]) //将小树合并到大树下

　　{

　　p[y]=tmp;

　　p[x]=y;

　　}

　　else

　　{

　　p[x]=tmp;

　　p[y]=x;

　　}

　　return ;

　　}

　　/*