數(shù)據(jù)結(jié)構(gòu)6集合與字典課件

第六章集合與字典本章要點：集合的基本概念及表示方法利用并查集實現(xiàn)集合的方法字典跳表散列

1第六章集合與字典本章要點：1集合及其表示集合基本概念集合是成員(對象或元素)的一個群集。集合中的成員可以是原子(單元素)，也可以是集合。集合的成員必須互不相同。在算法與數(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”}2集合及其表示集合基本概念2集合中的成員一般是無序的，沒有先后次序關(guān)系。但在表示它時，常常寫在一個序列里。我們常設(shè)定集合中的單元素具有線性有序關(guān)系，此關(guān)系可記作“<”，表示“優(yōu)先于”。若a,b是集合中的兩個單元素，則a<b,a==b,a>b三者必居其一；若a,b,c是集合中的三個單元素，且a>b,b>c，則a>c。(傳遞性)整數(shù)、字符和字符串都有一個自然的線性順序。而指針也可以依據(jù)其在序列中安排的位置給予一個線性順序。集合操作有求集合的并、交、差、判存在等。3集合中的成員一般是無序的，沒有先后次序關(guān)系。但在表示它時，常集合運算的文氏(Venn)圖用位向量實現(xiàn)集合抽象數(shù)據(jù)類型當(dāng)集合是全集合{0,1,2,…,n}的一個子集，且n是不大的整數(shù)時，可用位(0,1)向量來實現(xiàn)集合。當(dāng)全集合是由有限的可枚舉的成員組成的集合時，可建立全集合成員與整數(shù)0,1,2,…的一一對應(yīng)關(guān)系，用位向量來表示該集合的子集4集合運算的文氏(Venn)圖用位向量實現(xiàn)集合抽象數(shù)據(jù)類型4集合的位向量(bitVector)類的定義#include<assert.h>constint

DefaultSize=100;classSet{private:int*bitVector;

int

MaxSize;public:

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

void

MakeEmpty(){for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=0;

}

5集合的位向量(bitVector)類的定義#include

intAddMember(constintx);

int

DelMember(constintx);

Set&operator=(Set

&right);

Set&operator+(Set

&

right);

Set&operator*(Set

&

right);Set&operator

-(Set

&

right);

int

Contains(constint

x);

int

SubSet(Set

&

right);

intoperator==(Set

&right);};6intAddMember(constintx)用位向量實現(xiàn)集合時部分操作的實現(xiàn)構(gòu)造函數(shù)Set::Set(int

MaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0);

bitVector=newint[MaxSize];

assert(bitVector!=0);for(int

i=0;

i<MaxSize;

i++)bitVector[i]=0;}7用位向量實現(xiàn)集合時部分操作的實現(xiàn)構(gòu)造函數(shù)7插入元素XintSet::Addmember(constint

x){

assert(x>=0&&

x<MaxSize);

if(!bitVector[x]){

bitVector[x]=1;

return1;

}

return0;}刪除元素Xint

Set::DelMember(constint

x){

assert(x>=0&&

x<MaxSize);

if(bitVector[x]){

bitVector[x]=0;

return1;

}

return0; }8插入元素X8集合復(fù)制Set&

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;}9集合復(fù)制9集合交運算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&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&!right.bitVector[i];return*this;}10集合交運算10判斷元素X是否在集合中int

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;}11判斷元素X是否在集合中11若This集合是right的子集則返回1否則為0int

Set::SubSet(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;i++)

if(bitVector[i]!＝right.bitVector[i])

return0;

return1;

}12若This集合是right的子集則返回1否則為012使用示例

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}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,兩集合不等13使用示例13用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型用帶表頭結(jié)點的有序鏈表表示集合用有序鏈表來表示集合時，鏈表中的每個結(jié)點表示集合的一個成員。各結(jié)點所表示的成員e0,e1,…,en

在鏈表中按升序排列，即e0<e1<…<en。在一個有序鏈表中尋找一個集合成員時，一般不用搜索整個鏈表，搜索效率可以提高很多。集合成員可以無限增加。因此，用有序鏈表可以表示無窮全集合的子集。14用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型用帶表頭結(jié)點的有序鏈表表示集集合的有序鏈表類的定義template<classType>classSetList;template<classType>classSetNode{ friendclassSetList<Type>;public:SetNode(constType&item):data(item),link(NULL); private:Typedata; SetNode<Type>*link;};template<classType>classSetList{private:SetNode<Type>*first,*last;public:15集合的有序鏈表類的定義template<classTypSetList();voidMakeEmpty();intAddMember(constType&x);intDelMember(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);intContains(constType&x);

intoperator==(SetList<Type>&right); Type&Min(); Type&Max(); }16SetList();16

集合的搜索、加入和刪除操作template<classType>判斷X是否為集合成員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;}17集合的搜索、加入和刪除操作17將X插入到集合中template<classType>intSetList<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=newSetNode(x);s→link=p;q→link=s;if(p==NULL)last=s; return1;}18將X插入到集合中18刪除集合中的Xtemplate<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; deletep;return1;}elsereturn0;}19刪除集合中的X19用有序鏈表表示集合時的幾個重載函數(shù)template<classType>復(fù)制集合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; }20用有序鏈表表示集合時的幾個重載函數(shù)20template<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;}else21template<classType>集合并{pc→link=newSetNode<Type>(pb→data);pb=pb→link;}pc=pc→link;}if(pa!=NULL)pc→link=pa;else{while(pb!=NULL){pc→link=newSetNode<Type>(pb→data);pc=pc→link;pb=pb→link;}pc→link=NULL;last=pc;}return*this;}22{pc→link=newSetNode<Type>template<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;deletepa;pa=pc→link;} elsepb=pb→link;}23template<classType>集合交23

while(pa!=NULL){pc→link=pa→link;deletepa;pa=pc→link;}last=pc;return*this;}24while(pa!=NULL){24template<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→link;deletepa;pa=pc→link;pb=pb→link;}elseif(pa→data<pb→data) {pc=pc→link;pa=pa→link;}elsepb=pb→link;}if(pa==NULL)last=pc;return*this;}25template<classType>判斷集合相等template<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;}26判斷集合相等26并查集(Union-FindSets)把每一個對象看作是一個單元素集合，然后按一定順序?qū)儆谕坏葍r類的元素所在的集合合并。在此過程中將反復(fù)地使用一個搜索運算，確定一個元素在哪一個集合中。能夠完成這種功能的集合就是并查集。它支持以下三種操作：

Union(Root1,Root2)

//并操作；要求兩個集合互不相交

Find(x)

//搜索操作；

UFSets(s)

//構(gòu)造函數(shù)。27并查集(Union-FindSets)把每一個對象看作是

對于并查集來說，每個集合用一棵樹表示。集合中每個元素的元素名分別存放在樹的結(jié)點中，此外，樹的每一個結(jié)點還有一個指向其雙親結(jié)點的指針。為此，需要有兩個映射：集合元素到存放該元素名的樹結(jié)點間的對應(yīng)；集合名到表示該集合的樹的根結(jié)點間的對應(yīng)。設(shè)S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}28對于并查集來說，每個集合用一棵樹表示。282929為簡化討論，忽略實際的集合名，僅用表示集合的樹的根來標(biāo)識集合。如果我們確定了元素i在根為j的樹中，而且j有一個指向集合名字表中第k項的指針，則集合名即為name[k]。為此，采用樹的雙親表示作為集合存儲表示。集合元素的編號從0到n-1。其中n是最大元素個數(shù)。在雙親表示中，第i個數(shù)組元素代表包含集合元素i的樹結(jié)點。根結(jié)點的雙親為-1，表示集合中的元素個數(shù)。為了區(qū)別雙親指針信息(0)，集合元素個數(shù)信息用負(fù)數(shù)表示。30為簡化討論，忽略實際的集合名，僅用表示集合的樹的根來標(biāo)識集合3131constintDefaultSize=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;};32constintDefaultSize=10;32UFSets::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}33UFSets::UFSets(ints){Find和Union操作性能不好。假設(shè)最初n個元素構(gòu)成

n棵樹組成的森林，parent[i]=-1。做處理Union(n-2,n-1),…,Union(1,2),Union(0,1)后，將產(chǎn)生如圖所示的退化的樹。執(zhí)行一次Union操作所需時間是O(1)，n-1次Union操作所需時間是O(n)。若再執(zhí)行Find(0),Find(1),…,Find(n-1),

若被搜索的元素為i，完成Find(i)

操作需要時間為O(i)，完成n次搜索需要的總時間將達(dá)到34Find和Union操作性能不好。假設(shè)最初n個元素構(gòu)成執(zhí)Union操作的加權(quán)規(guī)則為避免產(chǎn)生退化的樹，改進(jìn)方法是先判斷兩集合中元素的個數(shù)，如果以i為根的樹中的結(jié)點個數(shù)少于以j為根的樹中的結(jié)點個數(shù)，即parent[i]>parent[j]，則讓j成為

i的雙親，否則，讓i成為j的雙親。此即Union的加權(quán)規(guī)則。parent[0](==-4)<parent[4](==-3)35Union操作的加權(quán)規(guī)則為避免產(chǎn)生退化的樹，改進(jìn)方法是先判斷void

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é)點數(shù)多

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

else{

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

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

}}36voidUFSets::36使用加權(quán)規(guī)則得到的樹37使用加權(quán)規(guī)則得到的樹37字典及其抽象數(shù)據(jù)類型考慮的問題是數(shù)據(jù)的存儲和檢索（查詢），就像在新華字典里字詞的組織和查找一個字的相關(guān)解釋等?存儲和檢索是計算過程中最重要的基本操作?本章主要討論基于關(guān)鍵碼的數(shù)據(jù)存儲和檢索，需要根據(jù)某些線索找出相關(guān)的數(shù)據(jù)?支持這種操作的數(shù)據(jù)結(jié)構(gòu)，通常稱為字典或查找表?不是介紹一種結(jié)構(gòu)，而是介紹計算中最重要的一種問題的許多不同解決方式，以及各種相關(guān)性質(zhì)?將用到前面討論過的許多結(jié)構(gòu)。包括各種線性結(jié)構(gòu)、樹性結(jié)構(gòu)及其各種組合，涉及在這些結(jié)構(gòu)上操作的許多算法38字典及其抽象數(shù)據(jù)類型考慮的問題是數(shù)據(jù)的存儲和檢索（查詢），抽象模型設(shè)有關(guān)鍵碼集合KEY和值（或稱屬性）集合VALUE關(guān)聯(lián)(Association)是二元組（k,v）∈KEYxVALIUE字典：以關(guān)聯(lián)為元素的有窮集合（key不相同）關(guān)鍵碼到值的有窮函數(shù)：key->value主要字典操作：?檢索(search)?插入元素(insert)?刪除元素(delete)?修改某key對應(yīng)的值p269字典的抽象數(shù)據(jù)結(jié)構(gòu)39抽象模型設(shè)有關(guān)鍵碼集合KEY和值（或稱屬性）集合VALUE3最主要也是使用最頻繁的操作是檢索（也稱查找）檢索效率是字典實現(xiàn)中最重要的考慮因素靜態(tài)字典：建立后保持不變的字典動態(tài)字典：內(nèi)容經(jīng)常動態(tài)變動的字典靜態(tài)字典的基本操作就是檢索。實現(xiàn)中主要考慮檢索效率動態(tài)字典除檢索外還有插入和刪除，實現(xiàn)中還需要考慮：?插入刪除操作的效率?插入刪除可能導(dǎo)致字典結(jié)構(gòu)變化，動態(tài)變化中能否保證檢索效率？（使字典性能不隨操作的進(jìn)行而逐漸惡化）40最主要也是使用最頻繁的操作是檢索（也稱查找）40?存儲和檢索是計算機(jī)信息處理中最基本的工作?字典就是實現(xiàn)存儲和檢索的結(jié)構(gòu)?需要存儲和檢索的信息有許多具體情況，因此要考慮各種不同的字典實現(xiàn)技術(shù)。?這里的基本問題是空間利用率和操作效率檢索效率的評價標(biāo)準(zhǔn)：檢索過程中關(guān)鍵碼的平均比較次數(shù)，即平均檢索長度ASL（averagesearchlength），定義為：ASL=Σni=1picici和pi分別為元素i的檢索長度和概率。若各元素的檢索概率相等，就有pi=1/n。ASL=1/nΣci。字典的組織方法很多，如：順序、跳表、散列、二叉樹和B樹等。41?存儲和檢索是計算機(jī)信息處理中最基本的工作41線性表表示線性表可以保存信息，因此可以作為字典的實現(xiàn)基礎(chǔ)關(guān)聯(lián)在線性表里順序排列，形成關(guān)聯(lián)的序列檢索就是在線性表里查找關(guān)鍵碼合適的元素數(shù)據(jù)元素的插入刪除都是很平常的線性表操作順序表表示鏈表表示（p270）42線性表表示線性表可以保存信息，因此可以作為字典的實現(xiàn)基礎(chǔ)順序檢索算法/*在字典中順序檢索關(guān)鍵碼為key的元素*/intseqSearch(SeqDic*pdic,KeyTypekey,int*position){inti;for(i=0;i<pdic->n;i++)/*從頭開始向后掃描*/if(pdic->element[i].key==key){*position=i;returnTRUE;/*檢索成功*/}*position=-1;returnFALSE;/*檢索失敗*/}失敗時由position設(shè)置一個特殊值。43順序檢索算法/*在字典中順序檢索關(guān)鍵碼為key的元素*/43平均檢索長度分析ASL=1*p1+2*p2+…+n*pn=(1+2+…+n)/n(pi=1/n時)=(n+1)/2=O(n)優(yōu)點：數(shù)據(jù)結(jié)構(gòu)和算法簡單，元素是否有序均可使用缺點：平均檢索長度大，n很大時檢索耗時太多不適合動態(tài)變化頻繁的字典刪除元素需順序檢索，O(n)，可能大量移動數(shù)據(jù)插入元素（關(guān)聯(lián)）時可保存在已有元素之后，O(1)操作；若要防止出現(xiàn)重復(fù)關(guān)鍵碼，就需要檢查所有元素，O(n)動態(tài)變化中字典的檢索效率不變（已經(jīng)是最低效的）44平均檢索長度分析44二分法檢索算法如果字典元素之間有關(guān)系，就可能利用它加快檢索速度。最常見的關(guān)系是關(guān)鍵碼有序，這時將元素按序排列（從小到大或從大到?。┡帕?，就可以快速檢索（二分法）二分法檢索基本過程（假設(shè)元素按關(guān)鍵碼升序排列）：1.初始時，考慮范圍是整個字典（順序表）2.取考慮范圍中位于中間的元素，用這個元素的關(guān)鍵碼與檢索關(guān)鍵碼比較。如果相等則檢索結(jié)束；否則3.如果檢索關(guān)鍵碼較大，把檢索范圍改為位置高的一半；如果檢索關(guān)鍵碼較小，把檢索范圍改為低一半4.如果范圍里已經(jīng)無元素，檢索失敗結(jié)束，否則回到245二分法檢索算法45/*在字典中用二分法檢索關(guān)鍵碼為key的元素*/intbiSearch(SeqDic*pdic,KeyTypekey,int*position){intlow=0,high=pdic->n-1,mid;while(low<=high){mid=(low+high)/2;/*當(dāng)前檢索的中間位置*/if(pdic->element[mid].key==key){/*檢索成功*/*position=mid;returnTRUE;}elseif(pdic->element[mid].key>key)high=mid-1;/*要檢索的元素在左半?yún)^(qū)*/elselow=mid+1;/*要檢索的元素在右半?yún)^(qū)*/}*position=-1;returnFALSE;/*檢索失敗*/}46/*在字典中用二分法檢索關(guān)鍵碼為key的元素*/46分析每次比較將范圍縮小一半，第i次可能比較的元素個數(shù)∶比較次數(shù)可能比較的元素個數(shù)11=2022=2134=22┇┇n2j-1若元素個數(shù)n剛好為20+21+……+2j-1=2j-1則最大檢索長度為j；若2j-1<n≤2j+1-1，則最大檢索長度為j+1。所以，二分法的最大檢索長度為log2(n+1)47分析47二分法檢索（排序順序字典）：–優(yōu)點是檢索速度快，O(logn)–插入時需要維護(hù)元素順序，O(n)操作（檢索插入位置可以用二分法，O(logn)）–刪除可用二分法查找元素，但需移動后面元素，O(n)–只能用于元素按關(guān)鍵碼排序的字典，只適合順序存儲結(jié)構(gòu)總結(jié)：排序表實現(xiàn)字典，檢索效率高。為保持元素順序，插入刪除操作效率低。因此不適合用于實現(xiàn)大的動態(tài)字典48二分法檢索（排序順序字典）：48跳表在一個使用有序鏈表描述的具有n個元素的字典中進(jìn)行搜索，至多需進(jìn)行n次比較。如果在鏈中部節(jié)點加一個指針，則比較次數(shù)可以減少到n/2+1。搜索時，首先將欲搜索元素與中間元素進(jìn)行比較。如果欲搜索的元素較小，則僅需搜索鏈表的左半部分，否則，只要在鏈表右半部分進(jìn)行比較即可。49跳表在一個使用有序鏈表描述的具有n個元素的字典中進(jìn)行搜索，5050通常0級鏈包括n個元素，1級鏈包括n/2個元素，2級鏈包括n/4個元素，而每2i個元素有一個i級鏈指針。當(dāng)且僅當(dāng)一個元素在0～i級鏈上，但不在i+1級（若該鏈存在）鏈上時，我們就說該元素是i級鏈元素。在圖中，40是2級鏈上唯一的元素而75是1級鏈元素。20、30、60、80是0級鏈元素。圖所示的結(jié)構(gòu)為跳表（skiplist）。在該結(jié)構(gòu)中有一組有層次的鏈。0級鏈?zhǔn)前性氐挠行蜴湵恚?級鏈?zhǔn)?級鏈的一個子集。i級鏈所包含的元素是i-1級鏈的子集。圖中，i級鏈上所有的元素均在i-1級鏈上。51通常0級鏈包括n個元素，1級鏈包括n/2個元素，2級鏈跳表的插入和刪除在圖中可以看到，一個指針的元素有n/2個，兩個指針的元素有n/4個，三指針的元素有n/8，有i指針的元素有n/2i個。他們處在i級的鏈上。在進(jìn)行插入和刪除時，要想保持跳表結(jié)構(gòu)，必須耗時O(n)。跳表是用空間+插入和刪除上的時間來換取搜索上的時間。這是一種處理方法，但不是很好。52跳表的插入和刪除在圖中可以看到，一個指針的元素有n/2個，兩散列(Hashing)前面講的字典數(shù)據(jù)結(jié)構(gòu)（算法）中，元素的存儲位置與元素的關(guān)鍵碼之間不存在直接對應(yīng)關(guān)系，因此查找關(guān)鍵碼需要一系列的比較。搜索的效率取決于比較的次數(shù)。散列表與散列方法

散列方法在表項的存儲位置與它的關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash(),使每個關(guān)鍵碼與結(jié)構(gòu)中的唯一存儲位置相對應(yīng)：

Address=Hash(Rec.key)53散列(Hashing)前面講的字典數(shù)據(jù)結(jié)構(gòu)（算法）中，元素的散列方法：在存放表項時，通過相同函數(shù)計算存儲位置，并按此位置存放，這種方法稱為散列方法。

散列函數(shù)：在散列方法中使用的函數(shù)。

散列表：按上述方法構(gòu)造出來的表稱為散列表。

通常關(guān)鍵碼集合比散列表地址集合大的多，因此有可能經(jīng)過散列函數(shù)的計算，把不同的關(guān)鍵碼映射到同一個散列地址上。稱這些散列地址相同的不同關(guān)鍵碼為同義詞。

54散列方法：在存放表項時，通過相同函數(shù)計算存儲位置，并按此位置對于散列方法需要討論兩個問題

(1)對于給定的一個關(guān)鍵碼集合，選擇一個計算簡單且地址分布比較均勻的散列函數(shù)，避免或盡量減少沖突。

(2)擬訂解決沖突的方案。

散列函數(shù)

構(gòu)造散列函數(shù)應(yīng)注意以下幾個問題：

(1)散列函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址，其值域必須在1～m-1之間。

(2)散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中。

(3)散列函數(shù)應(yīng)是簡單的。55對于散列方法需要討論兩個問題

(1)對于給定的一1.直接定址法

此類方法取關(guān)鍵碼的某個線形函數(shù)值作為散列地址：

Hash(key)=a*key+b{其中a,b為常數(shù)}

這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突。但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同，這種要求一般很難實現(xiàn)。

561.直接定址法

此類方法取關(guān)鍵碼的某個線形函數(shù)2.數(shù)字分析法

設(shè)有n個d位數(shù)，每一位可能有r種不同的符號。這r種不同的符號在各位上出現(xiàn)的頻率不一定相同?？筛鶕?jù)散列表的大小，選取其中各種符號分布均勻的若干位作為散列地址。計算各位數(shù)字中符號分布均勻度

其中，表示第I個符號在第k位上出現(xiàn)的次數(shù)，n/r表示各種符號在n個數(shù)中均勻出現(xiàn)的期望值。計算值越小，表明在該位各種符號分布的越均勻。572.數(shù)字分析法

設(shè)有n個d位數(shù)，每一位可能有r3.除留余數(shù)法

設(shè)散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或等于m的質(zhì)數(shù)p，或選取一個不含有小于20的質(zhì)因子的合數(shù)作為除數(shù)。這樣的散列函數(shù)為：

hash(key)=key%pp≤m

其中，“%”是整數(shù)除法取余的運算，要求這時的質(zhì)數(shù)p不是接近2的冪。583.除留余數(shù)法

設(shè)散列表中允許的地址數(shù)為m，取4.平方取中法

先計算構(gòu)成關(guān)鍵碼的表示符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。在平方取中法中，一般取散列地址為2的某次冪。594.平方取中法

先計算構(gòu)成關(guān)鍵碼的表示符的內(nèi)碼5.折疊法

有兩種方法：

(1)移位法----把各部分的最后一位對齊相加。

(2)分界法----各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當(dāng)作散列地址。605.折疊法

有兩種方法：

(1)移位法----把各部分處理沖突的閉散列方法

若設(shè)散列表有m個地址，將其改為m個桶。其桶號與散列地址一一對應(yīng)。每個桶可存放s個表項。如果對不同的關(guān)鍵碼用散列函數(shù)計算得到同一個散列地址，就產(chǎn)生了沖突，它們可以放到桶內(nèi)的不同位置，只有當(dāng)桶內(nèi)所s個表項都放滿后才會產(chǎn)生沖突。

61處理沖突的閉散列方法

若設(shè)散列表有m個地址，將其改處理沖突的一種常用的方法就是閉散列，也叫開地址法。所有的桶都直接放在散列表數(shù)組中。因此，每一個桶只有一個表項。如果在存放表項時發(fā)現(xiàn)，該位置已被別的表項占據(jù)，則在整個表中查找新的位置，如果表未被裝滿，則在允許的范圍內(nèi)必定有新的位置。查找的主要方法有3種。

1.線形探測法

方法為：一旦發(fā)生沖突，在表中順序向后尋找“下一個”空桶Hi的遞推公式為:Hi=(Hi-1+1)%mi=1,2,….,m-1或

Hi=(H0+I)%mI=1,2,….,m-162處理沖突的一種常用的方法就是閉散列，也叫開地址法。所有的桶都實例:已知關(guān)鍵碼Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly

散列函數(shù)為:Hash(x)=ord(x)-ord(‘a(chǎn)’)

可得:Hash(Burke)=1,Hash(Ekers)=4,Hash(Broad)=1,

Hash(Blum)=1,Hash(Attlee)=0,Hash(Alton)=0,

Hash(Hecht)=7,Hash(Ederly)=4

01234567AttleBurkBroaBlumEkerAltoEderHech63實例:已知關(guān)鍵碼Burke,Ekers,Broad,Blum二次探查法

線形探查法容易產(chǎn)生“堆積”的問題,即不同探查序列的關(guān)鍵碼占據(jù)可利用的空桶,使得為尋找某一關(guān)鍵碼需要經(jīng)歷土同的探查序列的元素,導(dǎo)致搜索時間增加.

使用二次探查法,在表中尋找“下一個”空桶的公式為:

Hi=(H0+i2)%m,Hi=(H0-i2)%m,I=1,2,3,…,(m-1)/2

式中H0=hash(x)是通過某一個散列函數(shù)hash()對表項的關(guān)鍵碼x進(jìn)行計算得到的桶號,它是一個非負(fù)整數(shù).m是表的大小,它應(yīng)是64二次探查法

線形探查法容易產(chǎn)生“堆積”的問題,一個值為4k+3的質(zhì)數(shù),其中k是一個整數(shù).

實例:若設(shè)表的長度為Tablesize=31,根據(jù)線形探查結(jié)果利用二次探查法所得到的結(jié)果為:

01234567BlumBurkBroaEkerEderlHech2122232425262730AltonAttle設(shè)散列表的桶數(shù)為m,待查表項的關(guān)鍵碼為x,第一次通過散列函數(shù)計算出來的桶號為H0=hash(x).當(dāng)發(fā)生沖突時,第i-1次和第i次次計算出來的“下一個”桶號為:65一個值為4k+3的質(zhì)數(shù),其中k是一個整數(shù).

實例:若設(shè)表的長將上述兩式相加可以得到:從上述式子可以知道,只要知道上一次桶號Hi-1就可以知道下一個桶號Hi.66將上述兩式相加可以得到:從上述式子可以知道,只要知道上一次桶3.雙散列法

使用散列方法時,需要使用兩個散列函數(shù).第一個散列函數(shù)Hash()按表項的關(guān)鍵碼key計算表項所在的桶號.一旦發(fā)生沖突,利用第二個散列函數(shù)ReHash()計算該表項“下一個”桶的移位量.處理沖突的開散列方法----鏈地址法

鏈地址法處理沖突的方法是,將通過散列函數(shù)計算出來地址相同的關(guān)鍵碼通過鏈表鏈接起來,各鏈表表頭結(jié)點組成一個向量.向量的元素個數(shù)與桶數(shù)一致表頭.673.雙散列法

使用散列方法時,需要使用兩個散列第六章集合與字典本章要點：集合的基本概念及表示方法利用并查集實現(xiàn)集合的方法字典跳表散列

68第六章集合與字典本章要點：1集合及其表示集合基本概念集合是成員(對象或元素)的一個群集。集合中的成員可以是原子(單元素)，也可以是集合。集合的成員必須互不相同。在算法與數(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”}69集合及其表示集合基本概念2集合中的成員一般是無序的，沒有先后次序關(guān)系。但在表示它時，常常寫在一個序列里。我們常設(shè)定集合中的單元素具有線性有序關(guān)系，此關(guān)系可記作“<”，表示“優(yōu)先于”。若a,b是集合中的兩個單元素，則a<b,a==b,a>b三者必居其一；若a,b,c是集合中的三個單元素，且a>b,b>c，則a>c。(傳遞性)整數(shù)、字符和字符串都有一個自然的線性順序。而指針也可以依據(jù)其在序列中安排的位置給予一個線性順序。集合操作有求集合的并、交、差、判存在等。70集合中的成員一般是無序的，沒有先后次序關(guān)系。但在表示它時，常集合運算的文氏(Venn)圖用位向量實現(xiàn)集合抽象數(shù)據(jù)類型當(dāng)集合是全集合{0,1,2,…,n}的一個子集，且n是不大的整數(shù)時，可用位(0,1)向量來實現(xiàn)集合。當(dāng)全集合是由有限的可枚舉的成員組成的集合時，可建立全集合成員與整數(shù)0,1,2,…的一一對應(yīng)關(guān)系，用位向量來表示該集合的子集71集合運算的文氏(Venn)圖用位向量實現(xiàn)集合抽象數(shù)據(jù)類型4集合的位向量(bitVector)類的定義#include<assert.h>constint

DefaultSize=100;classSet{private:int*bitVector;

int

MaxSize;public:

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

void

MakeEmpty(){for(int

i=0;

i<MaxSize;

i++)

bitVector[i]=0;

}

72集合的位向量(bitVector)類的定義#include

intAddMember(constintx);

int

DelMember(constintx);

Set&operator=(Set

&right);

Set&operator+(Set

&

right);

Set&operator*(Set

&

right);Set&operator

-(Set

&

right);

int

Contains(constint

x);

int

SubSet(Set

&

right);

intoperator==(Set

&right);};73intAddMember(constintx)用位向量實現(xiàn)集合時部分操作的實現(xiàn)構(gòu)造函數(shù)Set::Set(int

MaxSetSize):

MaxSize(MaxSetSize){

assert(MaxSize>0);

bitVector=newint[MaxSize];

assert(bitVector!=0);for(int

i=0;

i<MaxSize;

i++)bitVector[i]=0;}74用位向量實現(xiàn)集合時部分操作的實現(xiàn)構(gòu)造函數(shù)7插入元素XintSet::Addmember(constint

x){

assert(x>=0&&

x<MaxSize);

if(!bitVector[x]){

bitVector[x]=1;

return1;

}

return0;}刪除元素Xint

Set::DelMember(constint

x){

assert(x>=0&&

x<MaxSize);

if(bitVector[x]){

bitVector[x]=0;

return1;

}

return0; }75插入元素X8集合復(fù)制Set&

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;}76集合復(fù)制9集合交運算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&

right){

assert(MaxSize==right.MaxSize);

for(inti=0;

i<MaxSize;

i++)

bitVector[i]=bitVector[i]&&!right.bitVector[i];return*this;}77集合交運算10判斷元素X是否在集合中int

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;}78判斷元素X是否在集合中11若This集合是right的子集則返回1否則為0int

Set::SubSet(Set&

right){

assert(MaxSize==right.MaxSize);

for(int

i=0;

i<MaxSize;i++)

if(bitVector[i]!＝right.bitVector[i])

return0;

return1;

}79若This集合是right的子集則返回1否則為012使用示例

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}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,兩集合不等80使用示例13用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型用帶表頭結(jié)點的有序鏈表表示集合用有序鏈表來表示集合時，鏈表中的每個結(jié)點表示集合的一個成員。各結(jié)點所表示的成員e0,e1,…,en

在鏈表中按升序排列，即e0<e1<…<en。在一個有序鏈表中尋找一個集合成員時，一般不用搜索整個鏈表，搜索效率可以提高很多。集合成員可以無限增加。因此，用有序鏈表可以表示無窮全集合的子集。81用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型用帶表頭結(jié)點的有序鏈表表示集集合的有序鏈表類的定義template<classType>classSetList;template<classType>classSetNode{ friendclassSetList<Type>;public:SetNode(constType&item):data(item),link(NULL); private:Typedata; SetNode<Type>*link;};template<classType>classSetList{private:SetNode<Type>*first,*last;public:82集合的有序鏈表類的定義template<classTypSetList();voidMakeEmpty();intAddMember(constType&x);intDelMember(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);intContains(constType&x);

intoperator==(SetList<Type>&right); Type&Min(); Type&Max(); }83SetList();16

集合的搜索、加入和刪除操作template<classType>判斷X是否為集合成員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;}84集合的搜索、加入和刪除操作17將X插入到集合中template<classType>intSetList<Type>::AddMember(constType&x){SetNode<Type>*p=first→link,*q=first;wh