集合與字典一

集合及其表示集合是成員(元素)的一個群集。集合中的成員可以是原子(單元素)，也可以是集合。集合的成員必須互不相同(注：多重集合multiset允許重復(fù)元素)。在算法與數(shù)據(jù)結(jié)構(gòu)中所遇到的集合，其單元素通常是整數(shù)、字符、字符串或指針，且同一集合中所有成員具有相同的數(shù)據(jù)類型。例：colour={red,orange,yellow,green,black,blue,purple,white}

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

或

A+B

AB

或

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

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

virtualbooladdMember(constTx)=0;第4頁,共34頁，2024年2月25日，星期天

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

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

//集合的并運算

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

//集合的差運算

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

//判集合是否相等};第5頁,共34頁，2024年2月25日，星期天用位向量實現(xiàn)集合抽象數(shù)據(jù)類型當集合是全集合{0,1,2,…,n}的一個子集，且n是不大的整數(shù)時，可用位(0,1)向量來實現(xiàn)集合。當全集合是由有限個可枚舉的成員組成時，可建立全集合成員與整數(shù)0,1,2,…的一一對應(yīng)關(guān)系，用位向量來表示該集合的子集。一個二進位兩個取值1或0，分別表示在集合與不在集合。第6頁,共34頁，2024年2月25日，星期天thisRtemp011100001100010010101001110101110thisRtemp011100001100010010101000100000010thisRtemp011100001100010010101001010000100集合的并集合的交集合的差第7頁,共34頁，2024年2月25日，星期天template<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; };thisR001110101100011100101011000110101

第8頁,共34頁，2024年2月25日，星期天thisR001

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; //對應(yīng)位全部相等};第9頁,共34頁，2024年2月25日，星期天用帶表頭結(jié)點的有序鏈表表示集合firstfirst081723354972用有序鏈表實現(xiàn)集合抽象數(shù)據(jù)類型用有序鏈表來表示集合時，鏈表中的每個結(jié)點表示集合的一個成員。各結(jié)點所表示的成員e0,e1,…,en

在鏈表中按升序排列，即e0<e1<…<en。集合成員可以無限增加。因此，用有序鏈表可以表示無窮全集合的子集。第10頁,共34頁，2024年2月25日，星期天集合的有序鏈表類的定義template<classT>structSetNode{ //集合的結(jié)點類定義

Tdata; //每個成員的數(shù)據(jù)

SetNode<T>*link; //鏈接指針

SetNode():link(NULL); //構(gòu)造函數(shù)

SetNode(constT&x,SetNode<T>*next=NULL)

:data(x),link(next); //構(gòu)造函數(shù)

};template<classT>classLinkedSet{ //集合的類定義第11頁,共34頁，2024年2月25日，星期天private:

SetNode<T>*first,*last; //有序鏈表表頭指針,表尾指針public:

LinkedSet(){first=last=newSetNode<T>;}

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

～LinkedSet(){makeEmpty();deletefirst;} voidmakeEmpty(); //置空集合

booladdMember(constT&x);booldelMember(constT&x);

LinkedSet<T>&operator=(LinkedSet<T>&R);

LinkedSet<T>operator+(LinkedSet<T>&R);第12頁,共34頁，2024年2月25日，星期天

LinkedSet<T>operator*(LinkedSet<T>&R);

LinkedSet<T>operator-

(LinkedSet<T>&R);boolContains(constTx); //判x是否集合的成員

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

boolMin(T&x); //返回集合最小元素的值

boolMax(T&x); //返回集合最大元素的值

boolsubSet(bitSet<T>&R); //判this是否R的子集};第13頁,共34頁，2024年2月25日，星期天等價關(guān)系與等價類(EquivalenceClass)等價類與并查集在求解實際應(yīng)用問題時常會遇到等價類問題。從數(shù)學(xué)上看，等價類是對象（或成員）的集合，在此集合中所有對象應(yīng)滿足等價關(guān)系。若用符號“

”表示集合上的等價關(guān)系，則對于該集合中的任意對象x,y,z，下列性質(zhì)成立：自反性：x

x(即等于自身)。對稱性：若x

y,則y

x。傳遞性：若x

y且y

z,則x

z。第14頁,共34頁，2024年2月25日，星期天因此，等價關(guān)系是集合上的一個自反、對稱、傳遞的關(guān)系?！跋嗟取?=)就是一種等價關(guān)系，它滿足上述的三個特性。一個集合S中的所有對象可以通過等價關(guān)系劃分為若干個互不相交的子集S1,S2,S3,…，它們的并就是S。這些子集即為等價類。以下哪些是等價關(guān)系？室友、夫妻、師生、兄弟第15頁,共34頁，2024年2月25日，星期天給定集合S={0,1,2,3,4,5,6,7,8,9,10,11},及如下等價對:

0

4,3

1,6

10,8

9,7

4,6

8,3

5,2

11,11

0進行歸并的過程為：初始{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}第16頁,共34頁，2024年2月25日，星期天

{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}第17頁,共34頁，2024年2月25日，星期天并查集(Union-FindSets)并查集支持以下三種操作：

Union(Root1,Root2)

//合并操作

Find(x)

//查找操作

UFSets(s)

//構(gòu)造函數(shù)對于并查集來說，每個集合用一棵樹表示。為此，采用樹的雙親表示作為集合存儲表示。集合元素的編號從0到n-1。其中n是最大元素個數(shù)。第18頁,共34頁，2024年2月25日，星期天在雙親表示中，第i

個數(shù)組元素代表包含集合元素i的樹結(jié)點。初始時，根結(jié)點的雙親為-1，其絕對值表示集合中的元素個數(shù)。在同一棵樹上所有結(jié)點所代表的集合元素在同一個子集合中。第19頁,共34頁，2024年2月25日，星期天設(shè)S1={0,6,7,8},S2={1,4,9},S3={2,3,5}為簡化討論，忽略實際的集合名，僅用表示集合的樹的根來標識集合。集合名指針0

S11

S22

S30427681935-4000-3-34422第20頁,共34頁，2024年2月25日，星期天初始時,用構(gòu)造函數(shù)UFSets(s)

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

尋找集合元素i

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

將它們合并到一個集合中。下標parent-1-1-1-1-1-1-1-1-1-10123456789第21頁,共34頁，2024年2月25日，星期天S1下標parent集合S1,S2和S3的雙親表示-4

4

-3

2

-3

200040123456789S2S30768000-4419-344235-322第22頁,共34頁，2024年2月25日，星期天S1

S2的可能的表示方法下標parent集合S1

S2

和

S3的雙親表示-7

4

-320

2000

4012345678907684194190876-7-7000044444000第23頁,共34頁，2024年2月25日，星期天字典（Dictionary）

字典是一些元素的集合，每個元素有一個稱作關(guān)鍵碼（key）的域，不同元素的關(guān)鍵碼互不相同。在討論字典抽象數(shù)據(jù)類型時，把字典定義為<名字-屬性>對的集合。根據(jù)問題的不同，可以為名字和屬性（信息）賦予不同的含義。第24頁,共34頁，2024年2月25日，星期天例如，在圖書館檢索目錄中，名字是書名，屬性是索書號及作者等信息；在計算機活動文件表中，名字是文件名，屬性是文件地址、大小等信息。一般來說，有關(guān)字典的操作有如下幾種：確定一個指定的名字是否在字典中；搜索出該名字的屬性；修改該名字的屬性；插入一個新的名字及其屬性；刪除一個名字及其屬性。第25頁,共34頁，2024年2月25日，星期天字典的抽象數(shù)據(jù)類型

constintDefaultSize=26;template<className,classAttribute>classDictionary{//對象:一組<名字-屬性>對,其中,名字是唯一的public:

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

boolMember(Namename);

//判name是否在字典中

Attribute*Search(Namename);

//在字典中搜索關(guān)鍵碼與name匹配的表項

第26頁,共34頁，2024年2月25日，星期天voidInsert(Namename,Attributeattr);

//若name在字典中,則修改相應(yīng)<name,Attr>對

//的attr項;否則插入<name,Attr>到字典中

voidRemove(Namename);

//若name在字典中,則在字典中刪除相應(yīng)的

//<name,Attr>對};用文件記錄（record）或表格的表項（entry）來表示單個元素時，用二元組：

（關(guān)鍵碼key，記錄或表項位置指針adr）構(gòu)成搜索某一指定記錄或表項的索引項。第27頁,共34頁，2024年2月25日，星期天字典的線性表描述

字典可以保存在線性序列(e1,e2,…)中，其中ei是字典中的元素，其關(guān)鍵碼從左到右依次增大。為了適應(yīng)這種描述方式，可以定義有序順序表和有序鏈表。用有序鏈表來表示字典時，鏈表中的每個結(jié)點表示字典中的一個元素，各個結(jié)點按照結(jié)點中保存的數(shù)據(jù)值非遞減鏈接，即e1≤e2≤…。因此，在一個有序鏈表中尋找一個指定元素時，一般不用搜索整個鏈表。第28頁,共34頁，2024年2月25日，星期天跳表（skiplist）由前面討論可知，在一個有序順序表中進行折半搜索，時間效率很高。但是在有序鏈表中進行搜索，只能順序搜索，需要執(zhí)行O(n)次關(guān)鍵碼比較。如果在鏈表中部結(jié)點中增加一個指針，則比較次數(shù)可以減少到n/2+1。在搜索時，首先用要搜索元素與中間元素進行比較，如果要搜索元素小于中間元素，則僅需搜索鏈表的前半部分，否則只要在鏈表的后半部分進行比較即可。第29頁,共34頁，2024年2月25日，星期天跳表的結(jié)構(gòu)(a)帶有表頭結(jié)點和表尾結(jié)點的有序鏈表(b)在鏈表中部增加一個鏈接指針(c)在前半部分和后半部分中部各增加一個鏈接指針102030405060701020304050607010203040506070第30頁,共34頁，2024年2月25日，星期天在上面跳表的例子中有三條鏈：0級鏈就是圖(a)中的初始鏈表，包括了所有7個元素。1級鏈包括2、4、6三個元素。2級鏈