2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(11)

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

　　如果這個集合只有x自己,那么最父級代表元素當(dāng)然就是它自己

　　*/

　　intFindSet(int * p,int x)

　　{

　　int tmp,px=x;

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

　　px=p[px];

　　/*

　　路徑壓縮,可選,如果需要頻繁查詢,壓縮之后可以提高速度

　　即把從x到代表元素路徑上的所有的元素的父節(jié)點都表示為代表元素

　　*/

　　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 ;

　　}

　　/*

　　軟考程序員考試歷年真題重點題總結(jié)及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)