第六章集合與字典(一)

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

集合基本概念2集合中的成員一般是無序的，但在表示它時(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)成的集合屬于后者。3AB

或

A+B

AB

或

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

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

virtualbool

addMember(constTx)=0;4

virtualbool

delMember(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)算

virtualbool

Contains(Tx)=0;virtualbool

subSet(Set<T>&R)=0;virtualbooloperator==(Set<T>&R)=0;

//判集合是否相等};5用位向量實(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，分別表示在集合與不在集合。6thisRtemp011100001100010010101001110101110thisRtemp011100001100010010101000100000010thisRtemp011100001100010010101001010000100集合的并集合的交集合的差7template<classT>bool

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

assert(setSize==R.setSize);for(int

i=0;i<vectorSize;i++)//按位判斷

if(bitVector[i]&!R.bitVector[i])returnfalse; returntrue; };thisR0011101011000111001010110001101018thisR001

1

0000110001

0

0101010itemplate<classT>bool

bitSet<T>::operator==(bitSet<T>&R){//判集合this與R相等

if(vectorSize!=R.vectorSize)returnfalse;for(int

i=0;i<vectorSize;i++)if(bitVector[i]!=R.bitVector[i])returnfalse;returntrue; //對(duì)應(yīng)位全部相等};9用帶表頭結(jié)點(diǎn)的有序鏈表表示集合firstfirst081723354972用有序鏈表實(shí)現(xiàn)集合抽象數(shù)據(jù)類型用有序鏈表來表示集合時(shí)，鏈表中的每個(gè)結(jié)點(diǎn)表示集合的一個(gè)成員。各結(jié)點(diǎn)所表示的成員e0,e1,…,en

在鏈表中按升序排列，即e0<e1<…<en。集合成員可以無限增加。因此，用有序鏈表可以表示無窮全集合的子集。10集合的有序鏈表類的定義template<classT>struct

SetNode{ //集合的結(jié)點(diǎn)類定義

Tdata; //每個(gè)成員的數(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{ //集合的類定義11private:

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

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

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

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

bool

addMember(constT&x);

bool

delMember(constT&x);

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

LinkedSet<T>operator+(LinkedSet<T>&R);12

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

LinkedSet<T>operator-

(LinkedSet<T>&R);

bool

Contains(constTx); //判x是否集合的成員

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

bool

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

bool

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

bool

subSet(bitSet<T>&R); //判this是否R的子集};13等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)等價(jià)類與并查集在求解實(shí)際應(yīng)用問題時(shí)常會(huì)遇到等價(jià)類問題。從數(shù)學(xué)上看，等價(jià)類是對(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。14因此，等價(jià)關(guān)系是集合上的一個(gè)自反、對(duì)稱、傳遞的關(guān)系?！跋嗟取?=)就是一種等價(jià)關(guān)系，它滿足上述的三個(gè)特性。一個(gè)集合S中的所有對(duì)象可以通過等價(jià)關(guān)系劃分為若干個(gè)互不相交的子集S1,S2,S3,…，它們的并就是S。這些子集即為等價(jià)類。以下哪些是等價(jià)關(guān)系？室友、夫妻、師生、兄弟15給定集合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}16

{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并查集

(Union-FindSets)并查集支持以下三種操作：

Union(Root1,Root2)

//合并操作

Find(x)

//查找操作

UFSets(s)

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

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

S11

S22

S30427681935-4000-3-3442220初始時(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

-1012345678921S1下標(biāo)parent集合S1,S2和S3的雙親表示-4

4

-3

2

-3

200040123456789S2S30768000-4419-344235-32222S1

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

S2

和

S3的雙親表示-7

4

-320

2000

4012345678907684194190876-7-700004444400023字典（Dictionary）

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

constint

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

Dictionary(int

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

bool

Member(Namename);

//判name是否在字典中

Attribute*Search(Namename);

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

26

voidInsert(Namename,Attributeattr);

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

//的attr項(xiàng);否則插入<name,Attr>到字典中

voidRemove(Namename);

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

//<name,Attr>對(duì)};用文件記錄（record）或表格的表項(xiàng)（entry）來表示單個(gè)元素時(shí)，用二元組：

（關(guān)鍵碼key，記錄或表項(xiàng)位置指針adr）構(gòu)成搜索某一指定記錄或表項(xiàng)的索引項(xiàng)。27字典的線性表描述

字典可以保存在線性序列(e1,e2,…)中，其中ei

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

搜索時(shí)間代價(jià)為O(log2n)。31圖(c)就是跳表，有一組分層的鏈，0級(jí)鏈?zhǔn)前性氐挠行蜴湵恚衝個(gè)元素。0級(jí)鏈的第21,221,321,個(gè)結(jié)點(diǎn)鏈接起來形成1級(jí)鏈，故1級(jí)鏈?zhǔn)?級(jí)鏈的子集。1級(jí)鏈的第22,222,322,個(gè)結(jié)點(diǎn)鏈接起來形成2級(jí)鏈，依此類推，第i級(jí)鏈所包含的元素是第i-1級(jí)鏈的子集。一個(gè)有n個(gè)元