《集合與字典》ppt課件

《《集合與字典》ppt課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第六章集合與字典趙建華南京大學(xué)計算機系內(nèi)容集合及其表示并查集與等價類字典跳表散列集合的基本概念具有某種共同性質(zhì)”的若干不同的對象合在一起構(gòu)成集合。在算法與數(shù)據(jù)結(jié)構(gòu)中所遇到的集合中所有成員具有相同的數(shù)據(jù)類型。例如：colour={red,orange,yellow,green,black,blue,purple,white}一些說明作為數(shù)據(jù)結(jié)構(gòu)中的集合在概念上講，元素之間是無序的。但是可能為了效率，在實現(xiàn)中將元素之間的某個序關(guān)系和元素的存儲方式對應(yīng)起來；不同的表示方法：保存實際數(shù)據(jù)值保存下標(biāo)或者reference在父集中存放指示信息，表示是否在

2、子集合內(nèi)。允許相同元素多次出現(xiàn)的稱為多重集合或者包。集合的運算還包括：判斷一個元素是否在集合中集合是否為空A是否為B的子集以及添加/刪除元素等操作遍歷所以元素求滿足某個條件的所有元素組成的子集A?B或A+BA?B或A?BA-BAAABBB集合（Set）的抽象數(shù)據(jù)類型templateclassSet{public:virtualSet()=0;//構(gòu)造函數(shù)virtualmakeEmpty()=0;//置空集合virtualbooladdMember(constTx)=0;virtualbooldelMember(constTx)

3、=0;virtualSetintersectWith(Set&R)=0;//集合的交運算virtualSetunionWith(Set&R)=0;//集合的并運算virtualSetdifferenceFrom(Set&R)=0;//集合的差運算virtualboolContains(Tx)=0;virtualboolsubSet(Set&R)=0;virtualbooloperator==(Set&R)=0;//判集合是否相等};集合的位向量實現(xiàn)當(dāng)集合是全集合{0,1,2,…,n}的一個子集，

4、且n是不大的整數(shù)時，可用位(0,1)向量來實現(xiàn)集合。對于每個i，有一個二進位；取值1或0分別表示在集合與不在集合中。如果n小于32，可以直接用32位整數(shù)表示；否則可以使用整數(shù)數(shù)組表示。當(dāng)全集合是由有限個可枚舉的成員組成時，可建立全集合成員與整數(shù)0,1,2,…的一一對應(yīng)關(guān)系，然后用位向量來表示該集合的子集。如果全集用數(shù)組表示，那么其子集也可以用位向量表示。但是，此時需要保證全集不改變。位向量集合的類定義#include#includeconstintDefaultSize=50;classbitSet

5、{//用位向量來存儲集合元素,集合元素的范圍在0到//setSize-1之間。數(shù)組采用16位無符號短整數(shù)實現(xiàn)intsetSize;//集合大小intvecterSize;//位數(shù)組大小unsignedshort*bitVector;//bitVector[i]的第j位為0/1表示第i*16+j個元素是否在此集合內(nèi)。位向量集合的類定義（二）public:bitSet(intsz=DefaultSize);//構(gòu)造函數(shù)bitSet(constbitSet&R);//復(fù)制構(gòu)造函數(shù)～bitSet(){delete[]bitVector;}//析構(gòu)函數(shù)

6、intgetMember(constintx);//取集合元素xvoidputMember(constintx,intv);//改集合元素xvoidmakeEmpty(){//置空集合for(inti=0;i&operator=(constbitSet&R);bitSetoperator+(constb

7、itSet&R);bitSetoperator*(constbitSet&R);bitSetoperator-(constbitSet&R);boolContains(constintx);boolsubSet(bitSet&R);//判this是否R的子集booloperator==(bitSet&R);//判集合this與R相等friendistream&operator>>(istream&in,bitSet&R);//輸入friendostream&operator<<(ostream&out,bitSet&R);//輸出

8、}構(gòu)造函數(shù)的實現(xiàn)bitSet::bitSet(intsz):setSize(sz){//構(gòu)造函數(shù)assert(setSize>0);//檢查參數(shù)的合理性vector