第六章集合與字典

第六章集合與字典

數(shù)據(jù)結(jié)構(gòu)電子教案1集合及其表示并查集與等價(jià)類散列第六章集合與字典2集合及其表示集合是成員(元素)的一個(gè)群集。集合中的成員可以是原子(單元素)，也可以是集合。集合的成員必須互不相同(數(shù)學(xué)中的要求)。在我們這門課中所遇到的集合，其元素通常是整數(shù)、字符、字符串或指針，且同一集合中所有成員具有相同的數(shù)據(jù)類型。例：colour={red,orange,yellow,green,black,blue,purple,white}

集合基本概念3集合中的成員一般是無序的，但在表示它時(shí)，常寫在一個(gè)序列里，便于某些操作。常設(shè)定集合中的元素之間具有線性有序關(guān)系，此關(guān)系可記作“<”，表示“優(yōu)先于”。整數(shù)、字符和串都有一個(gè)自然線性順序。指針也可依據(jù)其在序列中安排的位置給予一個(gè)線性順序。在某些集合中保存實(shí)際數(shù)據(jù)值，某些集合中保存標(biāo)示元素是否在集合中的指示信息。如學(xué)校開設(shè)的所有課程的編碼屬于前者，一個(gè)學(xué)期開設(shè)的課程構(gòu)成的集合屬于后者。4AB

或

A+B

AB

或

ABA-BAAABBB集合（Set）的抽象數(shù)據(jù)類型template<classT>classSet{public:virtualSet()=0; //構(gòu)造函數(shù)

virtualmakeEmpty()=0; //置空集合

virtualbooladdMember(constTx)=0;5

virtualbooldelMember(constTx)=0;virtualSet<T>intersectWith(Set<T>&R)=0; //集合的交運(yùn)算

virtualSet<T>unionWith(Set<T>&R)=0;

//集合的并運(yùn)算

virtualSet<T>differenceFrom(Set<T>&R)=0;

//集合的差運(yùn)算

virtualboolContains(Tx)=0;virtualboolsubSet(Set<T>&R)=0;virtualbooloperator==(Set<T>&R)=0;

//判集合是否相等};6用位向量實(shí)現(xiàn)集合抽象數(shù)據(jù)類型當(dāng)集合是全集合{0,1,2,…,n}的一個(gè)子集，且n是不大的整數(shù)時(shí)，可用位(0,1)向量來實(shí)現(xiàn)集合。當(dāng)全集合是由有限個(gè)可枚舉的成員組成時(shí)，可建立全集合成員與整數(shù)0,1,2,…的一一對(duì)應(yīng)關(guān)系，用位向量來表示該集合的子集。一個(gè)二進(jìn)位兩個(gè)取值1或0，分別表示在集合與不在集合。如果采用16位無符號(hào)短整數(shù)數(shù)組bitVector[]作為集合的存儲(chǔ)，就要考慮如何求出元素i在bitVector數(shù)組中的相應(yīng)位置。7集合的位向量(bitVector)類的定義#include<assert.h>#include<iostream.h>constintDefaultSize=50;template<classT>classbitSet{//用位向量來存儲(chǔ)集合元素,集合元素的范圍在0到//setSize-1之間。數(shù)組采用16位無符號(hào)短整數(shù)實(shí)現(xiàn)private:

int

setSize; //集合大小

int

vectorSize; //位數(shù)組大小

unsignedshort*bitVector; //存儲(chǔ)集合元素的位數(shù)組8

public:

bitSet(int

sz

=

DefaultSize);//構(gòu)造函數(shù)

bitSet(constbitSet<T>&R);//復(fù)制構(gòu)造函數(shù)

~bitSet(){delete[]bitVector;}//析構(gòu)函數(shù)

int

getMember(constTx); //取集合元素x

voidputMember(constTx,intv);//改集合元素xvoidmakeEmpty(){

//置空集合

for(inti=0;i<vectorSize;i++)bitVector[i]=0;} booladdMember(constTx); //加入新成員xbooldelMember(constTx); //刪除老成員x9

bitSet<T>&operator=(constbitSet<T>&R);

bitSet<T>operator+(constbitSet<T>&R);

bitSet<T>operator*(constbitSet<T>&R);

bitSet<T>operator-

(constbitSet<T>&R);

bool

Contains(constTx);

//判x是否集合this的成員

bool

subSet(bitSet<T>&R);//判this是否R的子集

booloperator==(bitSet<T>&R); //判集合this與R相等10

friendistream&operator>>(istream&in,

bitSet<T>&R); //輸入

friendostream&operator<<(ostream&out,

bitSet<T>&R); //輸出};11使用示例bitSet<T>s1,s2,s3,s4,s5;boolindex,equal;for(intk=0;k<10;k++)

{

//

集合賦值

s1.AddMember(k);

s2.AddMember

(k+7);}

//

s1:{0,1,2,…,9},s2:{7,8,9,…,16}s3=s1+s2;

//

求s1與s2的并

{0,1,…,16}s4=s1*s2;

//

求s1與s2的交

{7,8,9}

s5=s1-s2;

//

求s1與s2的差

{0,1,…,6}12

//

s1:{0,1,2,3,4,5,6,7,8,9}

index=s1.SubSet(s4);//

判斷s1是否為s4子集

cout<<index<<endl;

//

結(jié)果，index=0

//

s1:{0,1,2,3,4,5,6,7,8,9}//

s4:{7,8,9}

equal=s1

==

s2;

//

集合s1與s2比較相等

cout<<equal<<endl;

//

為0,兩集合不等13構(gòu)造函數(shù)的實(shí)現(xiàn)template<classT>bitSet<T>::bitSet(intsz):setSize(sz){//構(gòu)造函數(shù)

assert(setSize>0); //檢查參數(shù)的合理性

vectorSize=(setSize+15)>>4;//存儲(chǔ)數(shù)組大小

bitVector=newunsignedshort[vectorSize];assert(bitVector!=NULL); //檢查存儲(chǔ)分配是否成功

for(inti=0;i<vectorSize;i++)

bitVector[i]=0; //初始化}14template<classT>bitSet<T>::bitSet(constbitSet<T>&R){//復(fù)制構(gòu)造函數(shù)

setSize=R.setSize; //集合元素個(gè)數(shù)

vectorSize=R.vectorSize; //存儲(chǔ)數(shù)組大小

bitVector=newunsignedshort[vectorSize]; assert(bitVector!=NULL); //檢查存儲(chǔ)分配是否成功

for(inti=0;i<vectorSize;i++)

//初始化

bitVector[i]=R.bitVector[i]; }15映射函數(shù)的實(shí)現(xiàn)template<classT>intbitSet<T>::getMember(constTx){//讀取集合元素xintad=x/16,id=x%16;//計(jì)算數(shù)組元素下標(biāo)

unsignedshortelem=bitVector[ad]; //取x所在數(shù)組元素

returnint((elem>>(15-id))&1); //取第id位的值}16template<classT>voidbitSet<T>::putMember(constTx,intv){//

將值

v

送入集合元素

xintad=x/16,id=x%16;//

計(jì)算數(shù)組元素下標(biāo)unsignedshortelem=bitVector[ad];

//

取

x

所在數(shù)組元素

elem=elem>>(15-id);//

右移,

該位移至末尾if(elem%2==0&&v==1)bitVector[ad]|=((elem+1)<<(15

-

id)); elseif(elem%2==1&&v==0)

bitVector[ad]^=(1<<(15-id));}17template<classT>boolbitSet<T>::addMember(constTx){assert(x>=0&&x<setSize);if(getMember(x)==0){

putMember(x,1);returntrue;} returnfalse;}

template<classT>boolbitSet<T>::delMember(constTx){assert(x>=0&&x<setSize);18

if(getMember(x)==1){

putMember(x,0);returntrue;} returnfalse;}template<classT>bitSet<T>bitSet<T>:://求集合this與R的并operator+(constbitSet<T>&R){assert(vectorSize==R.vectorSize);bitSet<T>temp(setSize);19for(inti=0;i<vectorSize;i++)

temp.bitVector[i]=bitVector[i]|R.bitVector[i]; return

bitSet<T>(temp);//

由第三個(gè)集合返回}template<classT>bitSet<T>bitSet<T>:://

求集合

this

與

R

的交operator*(constbitSet<T>&R){ assert(vectorSize==R.vectorSize);bitSet<T>temp(setSize);for(inti=0;i<vectorSize;i++)temp.bitVector[i]=bitVector[i]&R.bitVector[i]; returnbitSet<T>(temp);//

由第三個(gè)集合返回20}template<classT>bitSet<T>bitSet<T>:: //

求集合

this

與

R

的差operator-

(constbitSet<T>&R){ assert(vectorSize==R.vectorSize); bitSet<T>temp(vectorSize);for(inti=0;i<vectorSize;i++)temp.bitVector[i]=bitVector[i]&~R.bitVector[i]; return

bitSet<T>(temp);//

由第三個(gè)集合返回}21template<classT>bitSet<T>&bitSet<T>::operator=(constbitSet<T>&R){//

重載= assert(vectorSize

==

R.vectorSize); for(inti=0;i<vectorSize;i++)

bitVector[i]

=R.bitVector[i]; return*this;}22thisRtemp011100001100010010101001110101110thisRtemp011100001100010010101000100000010thisRtemp011100001100010010101001010000100集合的并集合的交集合的差23template<classT>boolbitSet<T>::subSet(bitSet<T>&R){//判this是否R的子集

assert(setSize==R.setSize);for(inti=0;i<vectorSize;i++)//按位判斷

if(bitVector[i]&

~R.bitVector[i])returnfalse; returntrue; }thisR00111010110001110010100000000100024thisR001

1

0000110001

0

0101010itemplate<classT>boolbitSet<T>::operator==(bitSet<T>&R){//判集合this與R是否相等

if(vectorSize!=R.vectorSize)returnfalse;for(inti=0;i<vectorSize;i++)if(bitVector[i]!=R.bitVector[i])returnfalse;returntrue; //對(duì)應(yīng)位全部相等}25等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)等價(jià)類與并查集在求解實(shí)際應(yīng)用問題時(shí)常會(huì)遇到等價(jià)類問題。從數(shù)學(xué)上看，等價(jià)類是對(duì)象的集合，在此集合中所有元素之間都滿足等價(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。26確定等價(jià)類的方法因此，等價(jià)關(guān)系是集合上的一個(gè)自反、對(duì)稱、傳遞的關(guān)系?！跋嗟取?=)就是一種等價(jià)關(guān)系，它滿足上述的三個(gè)特性。一個(gè)集合S中的所有對(duì)象可以通過等價(jià)關(guān)系劃分為若干個(gè)互不相交的子集S1,S2,S3,…，它們的并就是S。這些子集即為等價(jià)類。確定等價(jià)類的方法分兩步走：27

讀入并存儲(chǔ)所有的等價(jià)對(duì)(i,j)；標(biāo)記和輸出所有的等價(jià)類。

voidequivalence

(){

初始化;while(等價(jià)對(duì)未處理完){讀入下一個(gè)等價(jià)對(duì)

(i,j);

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

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

輸出包含這個(gè)對(duì)象的等價(jià)類;}28給定集合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

0進(jìn)行歸并的過程為：初始{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}29(接上){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}30并查集(Union-FindSets)并查集支持以下三種操作：

Union(Root1,Root2)

//合并操作

Find(x)

//查找操作

UFSets(s)

//構(gòu)造函數(shù)對(duì)于并查集來說，每個(gè)集合用一棵樹表示。我們采用樹的雙親表示作為集合的存儲(chǔ)表示。集合元素的編號(hào)從0到n-1。其中n是最大元素個(gè)數(shù)。31在雙親表示中，第i

個(gè)數(shù)組元素代表包含集合元素i的樹結(jié)點(diǎn)。初始時(shí)，根結(jié)點(diǎn)的雙親為-1，其絕對(duì)值表示集合中的元素個(gè)數(shù)。在同一棵樹上所有結(jié)點(diǎn)所代表的集合元素在同一個(gè)子集合中。為此，需要有兩個(gè)映射：集合元素到存放該元素名的樹結(jié)點(diǎn)間的對(duì)應(yīng)；集合名到表示該集合的樹的根結(jié)點(diǎn)間的對(duì)應(yīng)。32設(shè)S1={0,6,7,8},S2={1,4,9},S3={2,3,5}為簡化討論，忽略實(shí)際的集合名，僅用表示集合的樹的根來標(biāo)識(shí)集合。集合名指針0

S11

S22

S30427681935-4000-3-3442233初始時(shí),用構(gòu)造函數(shù)UFSets(s)

構(gòu)造一個(gè)森林,每棵樹只有一個(gè)結(jié)點(diǎn),表示集合中各元素自成一個(gè)子集合。用Find(i)

尋找集合元素i

的根。如果有兩個(gè)集合元素i和j,Find(i)==Find(j),表明這兩個(gè)元素在同一個(gè)集合中。如果兩個(gè)集合元素i和j不在同一個(gè)集合中,可用Union(i,j)

將它們合并到一個(gè)集合中。下標(biāo)parent-1-1-1-1-1-1-1-1-1-1012345678934S1下標(biāo)parent集合S1,S2和S3的雙親表示-4

4

-3

2

-3

200040123456789S2S30768000-4419-344235-32235S1

S2的可能的表示方法下標(biāo)parent集合S1

S2

和

S3的雙親表示-7

4

-320

2000

4012345678907684194190876-7-700004444400036用雙親表示實(shí)現(xiàn)并查集的類定義

constintDefaultSize=10;classUFSets{//集合中的各個(gè)子集合互不相交public:

UFSets(intsz=DefaultSize);//構(gòu)造函數(shù)

~UFSets(){delete[]parent;}//析構(gòu)函數(shù)

UFSets&operator=(UFSets&R);//集合賦值

voidUnion(intRoot1,intRoot2); //子集合并

intFind(intx); //查找x的根

voidWeightedUnion(intRoot1,intRoot2);

//改進(jìn)例程:帶權(quán)的合并算法private:37

int*parent; //集合元素?cái)?shù)組(雙親表示)intsize; //集合元素的數(shù)目};UFSets::UFSets(intsz){ //構(gòu)造函數(shù)：sz是集合元素個(gè)數(shù)，雙親數(shù)組//的范圍為parent[0]～parent[size-1]。

size=sz; //集合元素個(gè)數(shù)

parent=newint[size];//創(chuàng)建雙親數(shù)組

for(inti=0;i<size;i++)parent[i]=-1;

//每個(gè)自成單元素集合}38并查集操作的算法查找-5012301234Find(4)Find

(3)=3

Find(2)

=2

Find(1)=1Find(0)=0

=-5<0

結(jié)束39

-5

0123parentParent[4]=3Parent[3]=2Parent[2]=1Parent[1]=0Parent[0]=-501234intUFSets::Find(intx){//函數(shù)搜索并返回包含元素x的樹的根。

if(parent[x]<0)returnx;//根的parent[]值小于0

elsereturn(Find(parent[x]));}40voidUFSets::Union(intRoot1,intRoot2){//

求兩個(gè)不相交集合

Root1

與

Root2

的并

Root1=Find(Root1); Root2=Find(Root2); if(Root1!=Root2){ parent[Root1]+=parent[Root2]; parent[Root2]=Root1;

//

將

Root2

連接到

Root1

下面

}}41Find和Union操作性能不好。假設(shè)最初n個(gè)元素構(gòu)成n棵樹組成的森林，parent[i]=-1。做處理Union(n-2,n-1),…,Union(1,2),Union(0,1)后，將產(chǎn)生退化的樹。42合并-1-1-1-1-10234-3-503213341332202314Union(0,1)-23-41421234