第七章-集合與搜索-C++數(shù)據(jù)結(jié)構(gòu)-教學(xué)課件

集合及其表示等價(jià)類與并查集靜態(tài)搜索表二叉搜索樹(shù)最優(yōu)二叉搜索樹(shù)AVL樹(shù)小結(jié)第七章集合與搜索集合及其表示第七章集合與搜索1集合基本概念集合及其表示集合是成員(對(duì)象或元素)的一個(gè)群集。集合中的成員可以是原子(單元素)，也可以是集合。集合的成員必須互不相同。在算法與數(shù)據(jù)結(jié)構(gòu)中所遇到的集合，其單元素通常是整數(shù)、字符、字符串或指針，且同一集合中所有成員具有相同的數(shù)據(jù)類型。colour={red,orange,yellow,green,black,blue,purple,white}name={“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”}集合基本概念集合及其表示集合是成員(對(duì)象或元素)的一個(gè)群集。2集合中的成員一般是無(wú)序的，沒(méi)有先后次序關(guān)系。但在表示它時(shí)，常常寫(xiě)在一個(gè)序列里。我們常設(shè)定集合中的單元素具有線性有序關(guān)系，此關(guān)系可記作“<”，表示“優(yōu)先于”。若a,b是集合中的兩個(gè)單元素，則a<b,a==b,a>b三者必居其一；若a,b,c是集合中的三個(gè)單元素，且a>b,b>c，則a>c。(傳遞性)整數(shù)、字符和字符串都有一個(gè)自然的線性順序。而指針也可以依據(jù)其在序列中安排的位置給予一個(gè)線性順序。集合操作有求集合的并、交、差、判存在等。集合中的成員一般是無(wú)序的，沒(méi)有先后次序關(guān)系。但在表示它時(shí)，常3集合運(yùn)算的文氏(Venn)圖集合(Set)的抽象數(shù)據(jù)類型Template<classType>class

Set{

Set(intMaxSetSize):MaxSize(MaxSetSize);

void

MakeEmpty(Set

&s);

int

AddMember(Set

&s,constTypex);

intDelMember(Set

&s,constType

&x);集合運(yùn)算的文氏(Venn)圖集合(Set)的抽象數(shù)據(jù)類型Te4

void

Assign

(Set&s1,

Set&s2

);

void

Union

(Set&s1,

Set&s2

);

voidIntersection

(Set&s1,

Set&s2

);

void

Difference

(Set&s1,

Set&s2

);

int

Contains(Set

&s,constType

&

x);

intEqual(Set

&s1,Set&s2);

int

SubSet(Set

&s1,Set&s2

);}voidAssign(Set&s1,Se5用位向量實(shí)現(xiàn)集合抽象數(shù)據(jù)類型集合的位向量(bitVector)類的定義#include<assert.h>constint

DefaultSize=100;classSet{

當(dāng)集合是全集合{0,1,2,…,n}的一個(gè)子集，且n是不大的整數(shù)時(shí)，可用位(0,1)向量來(lái)實(shí)現(xiàn)集合。當(dāng)全集合是由有限的可枚舉的成員組成的集合時(shí)，可建立全集合成員與整數(shù)0,1,2,…的一一對(duì)應(yīng)關(guān)系，用位向量來(lái)表示該集合的子集。用位向量實(shí)現(xiàn)集合抽象數(shù)據(jù)類型集合的位向量(bitVecto6private:int*bitVector;

int

MaxSize;public:

Set(intMaxSetSize=DefaultSize);~Set(){delete[]bitVector;}

void

MakeEmpty(){for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=0;

}

intAddMember(constintx);

int

DelMember(constintx);

Set&operator=(Set

&right);

private:7

Set&operator+(Set

&

right);

Set&operator*(Set

&

right);Set&operator

-(Set

&

right);

int

Contains(constint

x);

int

SubSet(Set

&

right);

intoperator==(Set

&right);};使用示例

Sets1,s2,s3,s4,s5;

intindex,equal;

//構(gòu)造集合

for(int

k=0;

k<10;

k++)//集合賦值

{

s1.AddMember(k);

s2.AddMember(k+7);}

//s1:{0,1,2,…,9},s2:{7,8,9,…,16}Set&operator+(Set&ri8

s3=s1+s2;//求s1與s2的并{0,1,…,16}

s4=s1*s2;//求s1與s2的交{

7,8,9}

s5=s1-

s2;//求s1與s2的差{0,1,2,3,4,5,6}

index=s1.SubSet(s4);//求s4在s1中首次匹配

cout<<index<<endl;//位置，index=7

equal=s1==s2;

//集合s1與s2比較相等

cout<<equal<<endl;

//equal為0,兩集合不等用位向量實(shí)現(xiàn)集合時(shí)部分操作的實(shí)現(xiàn)Set::Set(int

MaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0);

bitVector=newint[MaxSize];

assert(bitVector!=0);

s3=s1+s2;//求s1與s2的9for(int

i=0;

i<MaxSize;

i++)bitVector[i]=0;}intSet::Addmember(constint

x){

assert(x>=0&&

x<MaxSize);

if(!bitVector[x]){

bitVector[x]=1;

return1;

}

return0;}int

Set::DelMember(constint

x){

assert(x>=0&&

x<MaxSize);

if(bitVector[x]){

bitVector[x]=0;

return1;

}

return0; }for(inti=0;i<MaxSi10Set&

Set::operator=(Set&

right){

assert(MaxSize==right.MaxSize);for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=right.bitVector[i]; return*this;}Set&

Set::operator+(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]||right.bitVector[i];return*this;}Set&Set::operator=(Set&11Set&

Set::operator*(Set

&right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&

right.bitVector[i];return*this;}Set&

Set::operator

-(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&!right.bitVector[i];return*this;}

Set&Set::operator*(Set&12int

Set::Contains(constint

x){

assert(x>=0&&x<MaxSize);

returnbitVector[x]; }intSet::operator

==(Set&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;i++)

if(bitVector[i]!=right.bitVector[i])return0;

return1;}int

Set::SubSet(Set&

right){

assert(MaxSize==right.MaxSize);intSet::Contains(constin13

for(int

i=0;

i<MaxSize;i++)

if(bitVector[i]&&!right.bitVector[i])return0;

return1;

}用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型用帶表頭結(jié)點(diǎn)的有序鏈表表示集合for(inti=0;i<MaxSiz14用有序鏈表來(lái)表示集合時(shí)，鏈表中的每個(gè)結(jié)點(diǎn)表示集合的一個(gè)成員。各結(jié)點(diǎn)所表示的成員e0,e1,…,en

在鏈表中按升序排列，即e0<e1<…<en。在一個(gè)有序鏈表中尋找一個(gè)集合成員時(shí)，一般不用搜索整個(gè)鏈表，搜索效率可以提高很多。集合成員可以無(wú)限增加。因此，用有序鏈表可以表示無(wú)窮全集合的子集。集合的有序鏈表類的定義template<classType>classSetList;

用有序鏈表來(lái)表示集合時(shí)，鏈表中的每個(gè)結(jié)點(diǎn)表示集合的一個(gè)成員。15template<classType>

classSetNode{ friendclassSetList<Type>;public:

SetNode(constType&item):

data(item),link(NULL); private:

Typedata;

SetNode<Type>*link;};template<classType>class

SetList

{private:

SetNode<Type>*first,*last;public:template<classType>classSe16SetList();

void

MakeEmpty();

intAddMember(constType&

x);int

DelMember(constType&

x);

SetList<Type>&operator=(SetList<Type>&

right);

SetList<Type>&operator+(SetList<Type>&

right);

SetList<Type>&operator*(SetList<Type>&

right);

SetList<Type>&operator-(SetList<Type>&

right);int

Contains(constType&x);

SetList();17int

operator

==(SetList<Type>&

right);

Type&

Min();

Type&

Max(); }集合構(gòu)造函數(shù)template<classType>voidSetList<Type>::SetList(){

SetNode<Type>*first=*last=

new

SetNode<Type>(0);

}intoperator==(SetList<18集合的搜索、加入和刪除操作template<classType>intSetList<Type>::Contains(constType&

x){

SetNode<Type>*temp=first→link;

while(temp!=NULL

&&

temp→data<x)

temp=temp→link;

if(temp!=NULL

&&

temp→data==x)

return1;

elsereturn0;}集合的搜索、加入和刪除操作19template<classType>int

SetList<Type>::AddMember(constType&x){SetNode<Type>*p=first→link,*q=first;while(p!=NULL

&&

p→data<x)

{q=p;

p=p→link;

}

if(p!=NULL&&p→data==x)return0;

SetNode<Type>*s=new

SetNode(x);

s→link=p;

q→link=s;

if(p==NULL)last=s;

return1;}template<classType>intSetL20template<classType>intSetList<Type>::DelMember(constType&

x){

SetNode<Type>*p=first→link,*q=first;

while(p!=NULL&&

p→data<x)

{

q=p;

p=p→link;

}

if(p!=NULL

&&

p→data==x){

q→link=p→link;

if(p==last)last

=q;

delete

p;

return1;}

elsereturn0;}template<classType>intSetL21用有序鏈表表示集合時(shí)的幾個(gè)重載函數(shù)template<classType>SetList<Type>&SetList<Type>::operator=(SetList<Type>&

right){

SetNode<Type>*pb=right.first→link;

SetNode<Type>*pa=first=newSetNode<Type>;

while(pb!=NULL){

pa→link=new

SetNode<Type>(pb→data);

pa=pa→link;

pb=pb→link;

}

pa→link=NULL;

last=pa;return*this; }用有序鏈表表示集合時(shí)的幾個(gè)重載函數(shù)22template<classType>SetList<Type>&

SetList<Type>::operator+(SetList<Type>&right){

SetNode<Type>*pb=right.first→link;

SetNode<Type>*pa=first→link;

SetNode<Type>*pc=first;

while(pa!=NULL

&&

pb!=NULL){if(pa→data==pb→data)

{pc→link=pa;

pa=pa→link;

pb=pb→link;

}

elseif(pa→data<pb→data)

{

pc→link=pa;

pa=pa→link;

}

elsetemplate<classType>23

{pc→link=new

SetNode<Type>(pb→data);

pb=pb→link;

}pc=pc→link;}if(pa!=NULL)pc→link=pa;else{while(pb!=NULL){

pc→link=new

SetNode<Type>(pb→data);pc=pc→link;

pb=pb→link;

}pc→link=NULL;

last=pc;}return*this;}{pc→link=newSetN24template<classType>SetList<Type>&

SetList<Type>::operator*(SetList<Type>&right){

SetNode<Type>*pb=right.first→link;

SetNode<Type>*pa=first→link;

SetNode<Type>*pc=first;

while(pa!=NULL

&&

pb!=NULL){

if(pa→data==pb→data)

{pc=pc→link;

pa=pa→link;

pb=pb→link;

}

elseif(pa→data<pb→data)

{

pc→link=pa→link;

delete

pa;

pa=pc→link;

}

else

pb=pb→link;

}

template<classType>25while(pa!=NULL){

pc→link=pa→link;

delete

pa;

pa=pc→link;

}

last=pc;return*this;}template<classType>SetList<Type>&

SetList<Type>::operator

-(SetList<Type>&right){

SetNode<Type>*pb=right.first→link;

SetNode<Type>*pa=first→link;

while(pa!=NULL){26

SetNode<Type>*pc=first; while(pa!=NULL

&&pb!=NULL){

if(pa→data==pb→data)

{

pc→link=pa→link;

delete

pa;

pa=pc→link;

pb=pb→link;

}elseif(pa→data<pb→data)

{

pc=pc→link;

pa=pa→link;

}

else

pb=pb→link;

}

if(pa==NULL)last=pc;return*this;}SetNode<Type>*pc=first;27template<classType>intSetList<Type>::operator==(SetList<Type>&

right){SetNode<Type>*pb=right.first→link;

SetNode<Type>*pa=first→link;

while(pa!=NULL

&&

pb!=NULL)

if(pa→data==pb→data)

{pa=pa→link;

pb=pb→link;

}elsereturn0;

if(pa!=NULL

||

pb!=NULL)return0;

return1;}template<classType>intSetL28等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)等價(jià)類與并查集在求解實(shí)際應(yīng)用問(wèn)題時(shí)常會(huì)遇到等價(jià)類問(wèn)題。從數(shù)學(xué)上看，等價(jià)類是一個(gè)對(duì)象(或成員)的集合，在此集合中所有對(duì)象應(yīng)滿足等價(jià)關(guān)系。若用符號(hào)“”表示集合上的等價(jià)關(guān)系，那么對(duì)于該集合中的任意對(duì)象x,y,

z，下列性質(zhì)成立：自反性：xx(即等于自身)。對(duì)稱性：若x

y,則y

x。傳遞性：若x

y且y

z,則x

z。因此，等價(jià)關(guān)系是集合上的一個(gè)自反、對(duì)稱、傳遞的關(guān)系。等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)等價(jià)類29

“相等”(=)就是一種等價(jià)關(guān)系，它滿足上述的三個(gè)特性。一個(gè)集合S

中的所有對(duì)象可以通過(guò)等價(jià)關(guān)系劃分為若干個(gè)互不相交的子集S1,S2,S3,…，它們的并就是

S。這些子集即為等價(jià)類。確定等價(jià)類的方法分兩步走。第一步，讀入并存儲(chǔ)所有的等價(jià)對(duì)(i,j)；第二步，標(biāo)記和輸出所有的等價(jià)類?！跋嗟取?=)就是一種等價(jià)關(guān)系，它滿足上述的三個(gè)特30void

equivalence(){

初始化;

while等價(jià)對(duì)未處理完

{讀入下一個(gè)等價(jià)對(duì)

(i,j);存儲(chǔ)這個(gè)等價(jià)對(duì)

;}

輸出初始化;

for(尚未輸出的每個(gè)對(duì)象)

輸出包含這個(gè)對(duì)象的等價(jià)類

;}給定集合

S={0,1,2,3,4,5,6,7,8,9,10,11},及如下等價(jià)對(duì):

0

4,3

1,6

10,8

9,7

4,

6

8,3

5,2

11,11

0voidequivalence(){給定集合S=31初始

{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}0

4

{0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}3

1

{0,4},{1,3},{2},{5},{6},{7},{8},{9},{10},{11}6

10{0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}

8

9

{0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}7

4

{0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}6

8

{0,4,7},{1,3},{2},{5},{6,8,9,10},{11}3

5

{0,4,7},{1,3,5},{2},{6,8,9,10},{11}2

11{0,4,7},{1,3,5},{2,11},{6,8,9,10}11

0{0,2,4,7,11},{1,3,5},{6,8,9,10}初始{0},{1},{2},{3},{4},{5},{6}32確定等價(jià)類的鏈表方法

設(shè)等價(jià)對(duì)個(gè)數(shù)為m，對(duì)象個(gè)數(shù)為n。一種可選的存儲(chǔ)表示為單鏈表?？蔀榧系拿恳粚?duì)象建立一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，并建立一個(gè)一維的指針數(shù)組seq[n]作為各單鏈表的表頭結(jié)點(diǎn)向量。seq[i]是第i個(gè)單鏈表的表頭結(jié)點(diǎn)，第i個(gè)單鏈表中所有結(jié)點(diǎn)的data域存放在等價(jià)對(duì)中與i等價(jià)的對(duì)象編號(hào)。

當(dāng)輸入一個(gè)等價(jià)對(duì)(i,j)后，就將集合元素i鏈入第j個(gè)單鏈表，且將集合元素j鏈入第i個(gè)單鏈表。在輸出時(shí)，設(shè)置一個(gè)布爾數(shù)組out[n]，用out[i]標(biāo)記第i個(gè)單鏈表是否已經(jīng)輸出。

確定等價(jià)類的鏈表方法設(shè)等價(jià)對(duì)個(gè)數(shù)為m，對(duì)象個(gè)數(shù)為n。33void

equivalence(){

讀入n;

將seq

初始化為

0

且將

out

初始化為

False;

while等價(jià)對(duì)未處理完

{

讀入下一個(gè)等價(jià)對(duì)(i,j);

將

j

鏈入

seq[i]鏈表;將i

鏈入

seq[j]鏈表;

}

for(i=0;i<n;i++) //檢測(cè)所有對(duì)象

if(out[i]==False){//若對(duì)象i未輸出

out[i]=True;//對(duì)象i做輸出標(biāo)志

輸出包含對(duì)象i的等價(jià)類;

}}voidequivalence(){34算法的輸出從編號(hào)i=0的對(duì)象開(kāi)始，對(duì)所有的對(duì)象進(jìn)行檢測(cè)。在i=0時(shí)，循第0個(gè)單鏈表先找出形式為(0,j)的等價(jià)對(duì)，把0和j作為同一個(gè)等價(jià)類輸出。再根據(jù)等價(jià)關(guān)系的傳遞性，找所有形式為(j,k)的等價(jià)對(duì)，把k也納入包含0的等價(jià)類中輸出。如此繼續(xù)，直到包含0的等價(jià)類完全輸出為止。接下來(lái)再找一個(gè)未被標(biāo)記的編號(hào)，如i=1，該對(duì)象將屬于一個(gè)新的等價(jià)類，我們?cè)儆蒙鲜龇椒▌澐帧?biāo)記和輸出這個(gè)等價(jià)類。在算法中使用了一個(gè)棧。每次輸出一個(gè)對(duì)象編號(hào)時(shí)，都要把這個(gè)編號(hào)進(jìn)棧，記下以后還要檢測(cè)輸出的等價(jià)對(duì)象的單鏈表。算法的輸出從編號(hào)i=0的對(duì)象開(kāi)始，對(duì)所有的對(duì)象進(jìn)行檢35輸入所有等價(jià)對(duì)后的seq數(shù)組及各單鏈表的內(nèi)容輸入所有等價(jià)對(duì)后的seq數(shù)組及各單鏈表的內(nèi)容36等價(jià)類鏈表的定義enum

Boolean

{False,True

};

class

ListNode

{ //定義鏈表結(jié)點(diǎn)類

friendvoidequivalence();

private:

intdata; //結(jié)點(diǎn)數(shù)據(jù)

ListNode*link; //結(jié)點(diǎn)鏈指針

ListNode(intd){

data=d;link=NULL;}

};

typedefListNode*ListNodePtr;等價(jià)類鏈表的定義37建立等價(jià)類算法(輸入等價(jià)對(duì)并輸出等價(jià)類)每當(dāng)一個(gè)對(duì)象的單鏈表檢測(cè)完，就需要從棧中退出一個(gè)指針，以便繼續(xù)輸出等價(jià)類中的其它對(duì)象。如果棧空，說(shuō)明該等價(jià)類所有對(duì)象編號(hào)都已輸出，再找一個(gè)使得out[i]==False的最小的i，標(biāo)記并輸出下一個(gè)等價(jià)類。void

equivalence(){

ifstream

inFile("equiv.in",

ios::in);

//輸入文件

if(!inFile){

cout

<<“不能打開(kāi)輸入文件"<<

endl;exit(1);}int

i,j,n;建立等價(jià)類算法(輸入等價(jià)對(duì)并輸出等價(jià)類)voidequi38

inFile>>n; //讀入對(duì)象個(gè)數(shù)seq=

new

ListNodePtr[n];

out=

new

Boolean[n];//初始化seq和out

for(i=0;i<n;i++)

{seq[i]=0;

out[i]=False;

}inFile>>i>>j; //輸入等價(jià)對(duì)(i,j)

while(inFile.good()){ //輸入文件結(jié)束轉(zhuǎn)出循環(huán)

x=

newListNode(j);//創(chuàng)建結(jié)點(diǎn)j

x→link=seq[i];

seq[i]=x;//鏈入第i個(gè)鏈表

y=

new

ListNode(i);//創(chuàng)建結(jié)點(diǎn)iy→link=seq[j];

seq[j]=y;//鏈入第j個(gè)鏈表

inFile>>i>>j; //輸入下一個(gè)等價(jià)對(duì)

}inFile>>n; //讀入對(duì)象個(gè)39

for

(i=0;i<n;i++)

if(out[i]==False)

{ //未輸出,需要輸出

cout<<endl

<<“Anewclass:”<<i;//輸出

out[i]=True; //作輸出標(biāo)記

ListNode*x=seq[i];

//取第i鏈表頭指針

ListNode*top=NULL;//棧初始化

while

(1)

{ //找類的其它成員

while(x)

{ //處理鏈表,直到x=0

j=x→data; //成員j

if(out[j]==False){//未輸出,輸出

cout

<<“,”<<j;

out[j]=True;

ListNode*y=x→link;x→link=top;top=x; //結(jié)點(diǎn)x進(jìn)棧for(i=0;i<n;i++)

40

x=y; //x進(jìn)到鏈表下一個(gè)結(jié)點(diǎn)

}

else

x=x→link;//已輸出過(guò),跳過(guò)

}

if

(top==NULL)break;//?？胀顺鲅h(huán)

else{x=seq[top→data];top=top→link;}

//棧不空,退棧,x是根據(jù)結(jié)點(diǎn)編號(hào)回//溯的另一個(gè)鏈表的頭指針

}

}

delete

[]

seq;

delete[]

out;}x=y; //x41并查集(Union-FindSets)建立等價(jià)類的另一種解決方案是先把每一個(gè)對(duì)象看作是一個(gè)單元素集合，然后按一定順序?qū)儆谕坏葍r(jià)類的元素所在的集合合并。在此過(guò)程中將反復(fù)地使用一個(gè)搜索運(yùn)算，確定一個(gè)元素在哪一個(gè)集合中。能夠完成這種功能的集合就是并查集。它支持以下三種操作：

Union(Root1,Root2)

//并操作；

Find(x)

//搜索操作；

UFSets(s)

//構(gòu)造函數(shù)。一般情形，并查集主要涉及兩種數(shù)據(jù)類型：集合名類型和集合元素的類型。并查集(Union-FindSets)建立等價(jià)類的另一種42

對(duì)于并查集來(lái)說(shuō)，每個(gè)集合用一棵樹(shù)表示。集合中每個(gè)元素的元素名分別存放在樹(shù)的結(jié)點(diǎn)中，此外，樹(shù)的每一個(gè)結(jié)點(diǎn)還有一個(gè)指向其雙親結(jié)點(diǎn)的指針。為此，需要有兩個(gè)映射：集合元素到存放該元素名的樹(shù)結(jié)點(diǎn)間的對(duì)應(yīng)；集合名到表示該集合的樹(shù)的根結(jié)點(diǎn)間的對(duì)應(yīng)。設(shè)S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}對(duì)于并查集來(lái)說(shuō)，每個(gè)集合用一棵樹(shù)表示。43利用并查集來(lái)解決等價(jià)問(wèn)題的步驟如下：利用UFSets操作,建立UFSets型集合this,集合中每一個(gè)元素初始化為0，各自形成一個(gè)單元素子集合,i=1,2,…,n。n是集合中元素個(gè)數(shù)。重復(fù)以下步驟,直到所有等價(jià)對(duì)讀入并處理完為止。讀入一個(gè)等價(jià)對(duì)[i][j];用Find(i),Find(j)搜索i、j所屬子集合的名字x和y;若x

y.用Union(x,y)或Union(y,x)將它們合并,前者的根在x；后者的根在y。利用并查集來(lái)解決等價(jià)問(wèn)題的步驟如下：利用UFSets操作,44為簡(jiǎn)化討論，忽略實(shí)際的集合名，僅用表示集合的樹(shù)的根來(lái)標(biāo)識(shí)集合。如果我們確定了元素i在根為j的樹(shù)中，而且j有一個(gè)指向集合名字表中第k項(xiàng)的指針，則集合名即為name[k]。為此，采用樹(shù)的雙親表示作為集合存儲(chǔ)表示。集合元素的編號(hào)從0到n-1。其中n是最大元素個(gè)數(shù)。在雙親表示中，第i個(gè)數(shù)組元素代表包含集合元素i的樹(shù)結(jié)點(diǎn)。根結(jié)點(diǎn)的雙親為-1，表示集合中的元素個(gè)數(shù)。為了區(qū)別雙親指針信息(0)，集合元素個(gè)數(shù)信息用負(fù)數(shù)表示。為簡(jiǎn)化討論，忽略實(shí)際的集合名，僅用表示集合的樹(shù)的根來(lái)標(biāo)識(shí)集合45S1S2的可能的表示方法下標(biāo)parent集合S1,S2和S3的雙親表示-14-12-1200040123456789S1S2的可能的表示方法下標(biāo)集合S1,S2和S3的雙46constintDefaultSize=10;class

UFSets{//并查集的類定義public:

UFSets(int

s=DefaultSize); ~UFSets(){

delete[]parent;}

constUFSets

&

operator=(UFSets

const&

Value);

void

Union(intRoot1,intRoot2);

intFind(int

x);

voidUnionByHeight(int

Root1,int

Root2); private:

int*parent;

intsize;};constintDefaultSize=10;47UFSets::UFSets(int

s){//構(gòu)造函數(shù)

size=s;

parent=newint[size+1];

for(int

i=0;

i<=size;

i++)parent[i]=-1;

}unsignedint

UFSets::Find(int

x){//搜索操作

if(parent[x]<=0)return

x;

elsereturnFind(parent[x]);}void

UFSets::Union(int

Root1,int

Root2){//并

parent[Root2]=Root1;//Root2指向Root1}UFSets::UFSets(ints){48Find和Union操作性能不好。假設(shè)最初n個(gè)元素構(gòu)成n棵樹(shù)組成的森林，parent[i]=-1。做處理Union(n-2,n-1),…,

Union(1,2),Union(0,1)后，將產(chǎn)生如圖所示的退化的樹(shù)。

執(zhí)行一次Union操作所需時(shí)間是O(1)，n-1次Union操作所需時(shí)間是O(n)。若再執(zhí)行Find(0),Find(1),…,Find(n-1),

若被搜索的元素為i，完成Find(i)操作需要時(shí)間為O(i)，完成n次搜索需要的總時(shí)間將達(dá)到Find和Union操作性能不好。假設(shè)最初n個(gè)元素構(gòu)成49為避免產(chǎn)生退化的樹(shù)，改進(jìn)方法是先判斷兩集合中元素的個(gè)數(shù)，如果以

i為根的樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)少于以

j為根的樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)，即parent[i]>parent[j]，則讓

j成為i的雙親，否則，讓i成為j的雙親。此即Union的加權(quán)規(guī)則。Union操作的加權(quán)規(guī)則parent[0](==-4)<parent[4](==-3)為避免產(chǎn)生退化的樹(shù)，改進(jìn)方法是先判斷兩集合中元素的個(gè)數(shù)，如果50void

UFSets::WeightedUnion(intRoot1,intRoot2){//按Union的加權(quán)規(guī)則改進(jìn)的算法

inttemp=parent[Root1]+parent[Root2];if(parent[Root2]<parent[Root1]){

parent[Root1]=Root2;//Root2中結(jié)點(diǎn)數(shù)多

parent[Root2]=temp;//Root1指向Root2}

else{

parent[Root2]=Root1;//Root1中結(jié)點(diǎn)數(shù)多

parent[Root1]=temp;//Root2指向Root1

}}voidUFSets::51

使用加權(quán)規(guī)則得到的樹(shù)使用加權(quán)規(guī)則得到的樹(shù)52使用并查集處理等價(jià)對(duì)，形成等價(jià)類的過(guò)程使用并查集處理等價(jià)對(duì)，形成等價(jià)類的過(guò)程53Union操作的折疊規(guī)則為進(jìn)一步改進(jìn)樹(shù)的性能，可以使用如下折疊規(guī)則來(lái)“壓縮路徑”。即：如果j是從i到根的路徑上的一個(gè)結(jié)點(diǎn)，且parent[j]

root[j]，則把parent[j]置為root[i]。Union操作的折疊規(guī)則為進(jìn)一步改進(jìn)樹(shù)的性能，可以使用如下折54int

UFSets::CollapsingFind(int

i){//使用折疊規(guī)則的搜索算法

for(intj=i;

parent[j]>=0;

j=parent[j]);

//讓j

循雙親指針走到根

while(i!=j)//換parent[i]到j(luò)

{int

temp=parent[i];

parent[i]=j;

i=temp;}

returnj;}

使用折疊規(guī)則完成單個(gè)搜索，所需時(shí)間大約增加一倍。但是，它能減少在最壞情況下完成一系列搜索操作所需的時(shí)間。intUFSets::CollapsingFind(55搜索(Search)的概念靜態(tài)搜索表

所謂搜索，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。搜索的結(jié)果通常有兩種可能：

搜索成功，即找到滿足條件的數(shù)據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中的位置，還可進(jìn)一步給出該對(duì)象中的具體信息。

搜索不成功，或搜索失敗。作為結(jié)果，也應(yīng)報(bào)告一些信息，如失敗標(biāo)志、失敗位置等。通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象(或記錄)組成。搜索(Search)的概念靜態(tài)搜索表所謂搜索，就是在數(shù)據(jù)集56在每一個(gè)對(duì)象中有若干屬性，其中應(yīng)當(dāng)有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。它稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，這樣，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的環(huán)境。

靜態(tài)環(huán)境，搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后不發(fā)生改變。靜態(tài)搜索表

動(dòng)態(tài)環(huán)境，為保持較高的搜索效率，搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。動(dòng)態(tài)搜索表在每一個(gè)對(duì)象中有若干屬性，其中應(yīng)當(dāng)有一個(gè)屬性，其值可唯一地標(biāo)57靜態(tài)搜索表template<classType>classdataList;template<classType>class

Node{friendclassdataList<Type>;public:

Node(constType&value):key

(value){}TypegetKey()const

{return

key;

}

void

setKey(Type

k){

key=k;

}private:

Type

key;

other;};靜態(tài)搜索表58template<classType>class

dataList{public:

dataList(int

sz=10):

ArraySize(sz),

Element(new

Node<Type>[sz]){}

virtual~dataList(){

delete[]Element;}

friendostream

&operator<<(ostream&

OutStream,

const

dataList<Type>

&OutList);

friendistream

&operator>>(istream&

InStream,dataList<Type>

&InList);protected:

Type*Element;

int

ArraySize,CurrentSize;};template<classType>classda59template<classType>class

searchList

:public

dataList<Type>{//作為派生類的靜態(tài)搜索表的類定義public:

searchList(intsz=10):

dataList<Type>(sz){}

virtual~searchList(){}

virtualint

Search(constType&

x)const;};template<classType>classse60template<classType>istream&operator>>(istream&

InStream,dataList<Type>

&

InList){//從輸入流對(duì)象InStream輸入數(shù)據(jù)到數(shù)據(jù)表InList

cout<<“輸入數(shù)組當(dāng)前大小

:”;

Instream>>InList.CurrentSize;cout<<“輸入數(shù)組元素值

:\n”;

for(int

i=0;

i<InList.CurrentSize;i++){cout<<“元素”<<i<<“:”;

InStream>>InList.Element[i];}return

InStream;}template<classType>istream61template<classType>ostream&operator<<(ostream&

OutStream,

const

dataList<Type>&

OutList){//將數(shù)據(jù)表OutList內(nèi)容輸出到輸出流對(duì)象OutStream

OutStream<<“數(shù)組內(nèi)容

:\n”;

for(int

i=0;

i<OutList.CurrentSize;i++)

OutStream<<OutList.Element[i]<<‘’;

OutStream<<endl;

OutStream<<“數(shù)組當(dāng)前大小

:”<<

OutList.CurrentSize<<endl;

return

OutStream;}template<classType>ostream62衡量一個(gè)搜索算法的時(shí)間效率的標(biāo)準(zhǔn)是：在搜索過(guò)程中關(guān)鍵碼的平均比較次數(shù)或平均讀寫(xiě)磁盤(pán)次數(shù)(只適合于外部搜索)，這個(gè)標(biāo)準(zhǔn)也稱為平均搜索長(zhǎng)度ASL(AverageSearchLength)，通常它是搜索結(jié)構(gòu)中對(duì)象總數(shù)n或文件結(jié)構(gòu)中物理塊總數(shù)n的函數(shù)。另外衡量一個(gè)搜索算法還要考慮算法所需要的存儲(chǔ)量和算法的復(fù)雜性等問(wèn)題。在靜態(tài)搜索表中，數(shù)據(jù)對(duì)象存放于數(shù)組中，利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)對(duì)象的存放地址。搜索算法根據(jù)給定值x，在數(shù)組中進(jìn)行搜索。直到找到x在數(shù)組中的存放位置或可確定在數(shù)組中找不到x為止。衡量一個(gè)搜索算法的時(shí)間效率的標(biāo)準(zhǔn)是：在搜索過(guò)程中關(guān)鍵碼的平均63順序搜索

(SequentialSearch)所謂順序搜索，又稱線性搜索，主要用于在線性結(jié)構(gòu)中進(jìn)行搜索。設(shè)若表中有CurrentSize個(gè)對(duì)象，則順序搜索從表的先端開(kāi)始，順序用各對(duì)象的關(guān)鍵碼與給定值x進(jìn)行比較，直到找到與其值相等的對(duì)象，則搜索成功，給出該對(duì)象在表中的位置。若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與x相等的對(duì)象，則搜索失敗。給出失敗信息。順序搜索(SequentialSearch)所謂順序搜索64template<classType>intsearchList<Type>::Search(constType&

x)const{//順序搜索的迭代算法，0號(hào)元素為監(jiān)視哨

Element[0].setKey(x);

int

i=CurrentSize;

while(Element[i].getKey()!=x)i--;

return

i;}template<classType>intearchList<Type>::Search(constType&

x,int&loc)const{//順序搜索的遞歸算法

if(loc>=CurrentSize)return

-1;

elseif(Element[loc].getKey()==

x)returnloc;elsereturn

Search(x,loc+1);}template<classType>intsear65constint

Size=10;main

(){//順序搜索的主過(guò)程searchList<float>

List1(Size);

float

Target;

intLocation;

cin>>List1;

cout<<List1;

//輸入/輸出數(shù)據(jù)表List1

cout<<“搜索浮點(diǎn)數(shù)

:”;

cin>>Target;

if((Location=List1.search(Target))!=0)

cout<<“找到下標(biāo)”<<Location<<endl;

else

cout<<“沒(méi)有找到.\n”;}constintSize=10;66順序搜索的平均搜索長(zhǎng)度

設(shè)搜索第

i個(gè)元素的概率為pi，搜索到第

i個(gè)元素所需比較次數(shù)為

ci，則搜索成功的平均搜索長(zhǎng)度:在順序搜索情形，ci=i+1,i=0,1,,n-1，因此在等概率情形，pi=1/n,

i=0,1,,n-1。

順序搜索的平均搜索長(zhǎng)度設(shè)搜索第i個(gè)元素的概率為pi，67基于有序順序表的折半搜索設(shè)n個(gè)對(duì)象存放在一個(gè)有序順序表中，并按其關(guān)鍵碼從小到大排好了序。采用對(duì)分搜索時(shí)，先求位于搜索區(qū)間正中的對(duì)象的下標(biāo)mid，用其關(guān)鍵碼與給定值x比較:

Element[mid].getKey()=x，搜索成功；

Element[mid].getKey()>x，把搜索區(qū)間縮小到表的前半部分，再繼續(xù)進(jìn)行對(duì)分搜索；

Element[mid].getKey()<x，把搜索區(qū)間縮小到表的后半部分，再繼續(xù)進(jìn)行對(duì)分搜索。每比較一次，搜索區(qū)間縮小一半。如果搜索區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要搜索的對(duì)象，則搜索失敗。基于有序順序表的折半搜索設(shè)n個(gè)對(duì)象存放在一個(gè)有序順序表中，并68搜索成功的例子 搜索失敗的例子搜索成功的例子 搜索失敗的例子69template<classType>class

orderedList

:public

dataList<Type>{//有序表的類定義,繼承了數(shù)據(jù)表public:

orderedList(intsz=10):

dataList<Type>(sz){}

virtual~orderedList(){}

virtualint

Search(constType&

x)const;};

template<classType>classor70temp