北京師范大學數(shù)據結構教學資料-第6章-集合與字典

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

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

或

A+B

AB

或

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

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

virtualbooladdMember(constTx)=0;4精選PPT

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

bitSet(intsz=DefaultSize); //構造函數(shù)

bitSet(constbitSet<T>&R); //復制構造函數(shù)～bitSet(){delete[]bitVector;} //析構函數(shù)

intgetMember(constTx); //取集合元素x7精選PPTvoidputMember(constTx,intv);//改集合元素xvoidmakeEmpty(){

//置空集合

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

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

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

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

bitSet<T>operator-

(constbitSet<T>&R);boolContains(constTx); //判x是否集合this的成員8精選PPTboolsubSet(bitSet<T>&R);//判this是否R的子集

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

friendistream&operator>>(istream&in,

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

friendostream&operator<<(ostream&out,

bitSet<T>&R); //輸出private:intsetSize; //集合大小

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

unsignedshort*bitVector; //存儲集合元素的位數(shù)組};9精選PPT使用示例Sets1,s2,s3,s4,s5;intindex,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}10精選PPT//s1:{0,1,2,3,4,5,6,7,8,9}

index=s1.SubSet(s4);//判斷s1是否為s4子集

cout<<index<<endl;

//結果，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,兩集合不等11精選PPT構造函數(shù)的實現(xiàn)template<classT>bitSet<T>::bitSet(intsz):setSize(sz){//構造函數(shù)

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

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

bitVector=newint[vectorSize]; //分配空間

assert(bitVector!=NULL); //檢查存儲分配是否成功

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

bitVector[i]=0; //初始化};12精選PPTtemplate<classT>bitSet<T>::bitSet(constbitSet<T>&R){//復制構造函數(shù)

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

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

bitVector=newint[vectorSize]; //分配空間

assert(bitVector!=NULL); //檢查存儲分配是否成功

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

//初始化

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

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

returnint((elem>>(15-id))&1); //取第id位的值};14精選PPTtemplate<classT>voidbitSet<T>::putMember(constTx,intv){//將值v送入集合元素xintad=x/16,id=x%16; //計算數(shù)組元素下標

unsignedshortelem=bitVector[ad];

//取x所在數(shù)組元素

unsignedshorttemp=elem>>(15-id);

//右移,該位移至末尾

elem=elem<<(id+1);

if(temp%2==0&&v==1)temp=temp+1; //根據v的值,修改該位

elseif(temp%2==1&&v==0)temp=temp-1;bitVector[ad]=(temp<<(15-id))|(elem>>(id+1));};15精選PPTthisRtemp011100001100010010101001110101110thisRtemp011100001100010010101000100000010thisRtemp011100001100010010101001010000100集合的并集合的交集合的差16精選PPTtemplate<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);17精選PPTif(getMember(x)==1){

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

temp.bitVector[i]=bitVector[i]|R.bitVector[i]; returntemp;//按位求"或",由第三個集合返回};template<classT>bitSet<T>bitSet<T>:://求集合this與R的交operator*(constbitSet<T>&R){ assert(vectorSize==R.vectorSize);bitSettemp(setSize);for(inti=0;i<vectorSize;i++)temp.bitVector[i]=bitVector[i]&R.bitVector[i]; returntemp;//按位求“與”,由第三個集合返回19精選PPT};template<classT>bitSet<T>bitSet<T>:: //求集合this與R的差operator-

(constbitSet<T>&R){ assert(vectorSize==R.vectorSize); bitSettemp(setSize);for(inti=0;i<vectorSize;i++)temp.bitVector[i]=bitVector[i]&!R.bitVector[i]; returntemp; //由第三個集合返回};20精選PPTtemplate<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; };thisR00111010110001110010101100011010121精選PPTthisR001

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; //對應位全部相等};22精選PPT用帶表頭結點的有序鏈表表示集合firstfirst081723354972用有序鏈表實現(xiàn)集合抽象數(shù)據類型用有序鏈表來表示集合時，鏈表中的每個結點表示集合的一個成員。各結點所表示的成員e0,e1,…,en

在鏈表中按升序排列，即e0<e1<…<en。集合成員可以無限增加。因此，用有序鏈表可以表示無窮全集合的子集。23精選PPT集合的有序鏈表類的定義template<classT>structSetNode{ //集合的結點類定義

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

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

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

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

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

};template<classT>classLinkedSet{ //集合的類定義24精選PPTprivate:

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

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

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

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

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

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

LinkedSet<T>operator+(LinkedSet<T>&R);25精選PPT

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的子集};26精選PPT集合的加入和刪除操作template<classT>boolLinkedSet<T>::addMember(constT&x){//把新元素x加入到集合之中

SetNode<T>*p

=first->link,*pre=first;while(p!=NULL&&p->data<x)

//循鏈掃描

{pre=p;p=p->link;} if(p!=NULL&&p->data==x)returnfalse;

//集合中已有此元素,不加入

SetNode<T>*s=newSetNode(x);//創(chuàng)建結點

s->link=p;pre->link=s; //鏈入27精選PPT

if(p==NULL)last=s;

//鏈到鏈尾時改鏈尾指針

returntrue;};template<classT>boolLinkedSet<T>::delMember(constT&x){//把集合中成員x刪去

SetNode<T>*p=first->link,*pre=first;while(p!=NULL&&p->data<x)

//循鏈掃描

{pre=p;p=p->link;} if(p!=NULL&&p->data==x){//找到,可刪

pre->link=p->link; //重新鏈接28精選PPT表示集合的幾個重載函數(shù)

if(p==last)last=pre;

//刪鏈尾時改尾指針

deletep;

//刪除含x結點

returntrue; }elsereturnfalse; //集合中無此元素};template<classT>LinkedSet<T>LinkedSet<T>::operator+(LinkedSet<T>&R){//求集合this與集合R的并29精選PPT

SetNode<T>*pb=R.first->link; //R掃描指針

SetNode<T>*pa=first->link; //this掃描指針

LinkedSet<T>temp; //創(chuàng)建空鏈表

SetNode<T>*p,*pc=temp.first; //結果存放指針

while(pa!=NULL&&pb!=NULL){if(pa->data==pb->data){ //兩集合共有

pc->link=newSetNode<T>(pa->data);

pa=pa->link;pb=pb->link;} elseif(pa->data<pb->data){ //this元素值小

pc->link=newSetNode<T>(pa->data);

pa=pa->link;30精選PPT}else{ //R集合元素值小

pc->link=newSetNode<T>(pb->data);

pb=pb->link;}

pc=pc->link;}if(pa!=NULL)p=pa; //this集合未掃完

elsep=pb; //或R集合未掃完

while(p!=NULL){ //向結果鏈逐個復制

pc->link=newSetNode<T>(p->data);

pc=pc->link;p=p->link;}31精選PPTpc->link=NULL;temp.last=pc;//鏈表收尾

returntemp;}；firstR.first08172349temp.first231735papbpc081723354932精選PPTboolLinkedSet<T>::operator==(LinkedSet<T>&R){

SetNode<T>*pb=R.first->link;

SetNode<T>*pa=first->link;while(pa!=NULL&&pb!=NULL)if(pa->data==pb->data) {pa=pa->link;pb=pb->link;}elsereturnfalse; //掃描途中不等時退出

if(pa!=NULL||pb!=NULL)returnfalse;

//鏈不等長時,返回0returntrue;};33精選PPT等價關系與等價類(EquivalenceClass)等價類與并查集在求解實際應用問題時常會遇到等價類問題。從數(shù)學上看，等價類是對象（或成員）的集合，在此集合中所有對象應滿足等價關系。若用符號“”表示集合上的等價關系，則對于該集合中的任意對象x,y,z，下列性質成立：自反性：xx(即等于自身)。對稱性：若x

y,則y

x。傳遞性：若x

y且y

z,則x

z。34精選PPT確定等價類的方法因此，等價關系是集合上的一個自反、對稱、傳遞的關系?！跋嗟取?=)就是一種等價關系，它滿足上述的三個特性。一個集合S中的所有對象可以通過等價關系劃分為若干個互不相交的子集S1,S2,S3,…，它們的并就是S。這些子集即為等價類。確定等價類的方法分兩步走：35精選PPT

讀入并存儲所有的等價對(i,j)；標記和輸出所有的等價類。

voidequivalence

(){

初始化; while(等價對未處理完){讀入下一個等價對

(i,j);

存儲這個等價對

;}

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

輸出包含這個對象的等價類

;}36精選PPT給定集合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}37精選PPT

{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}38精選PPT并查集(Union-FindSets)并查集支持以下三種操作：

Union(Root1,Root2)

//合并操作

Find(x)

//查找操作

UFSets(s)

//構造函數(shù)對于并查集來說，每個集合用一棵樹表示。為此，采用樹的雙親表示作為集合存儲表示。集合元素的編號從0到n-1。其中n是最大元素個數(shù)。39精選PPT在雙親表示中，第i

個數(shù)組元素代表包含集合元素i的樹結點。初始時，根結點的雙親為-1，表示集合中的元素個數(shù)。在同一棵樹上所有結點所代表的集合元素在同一個子集合中。為此，需要有兩個映射：集合元素到存放該元素名的樹結點間的對應；集合名到表示該集合的樹的根結點間的對應。40精選PPT設S1={0,6,7,8},S2={1,4,9},S3={2,3,5}為簡化討論，忽略實際的集合名，僅用表示集合的樹的根來標識集合。集合名指針0

S11

S22

S30427681935-4000-3-3442241精選PPT初始時,用構造函數(shù)UFSets(s)

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

尋找集合元素i

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

將它們合并到一個集合中。下標parent-1-1-1-1-1-1-1-1-1-1012345678942精選PPTS1下標parent集合S1,S2和S3的雙親表示-4

4

-3

2

-3

200040123456789S2S30768000-4419-344235-32243精選PPTS1

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

S2

和

S3的雙親表示-7

4

-3202000

4012345678907684194190876-7-700004444400044精選PPT用雙親表示實現(xiàn)并查集的類定義

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

UFSets(intsz=DefaultSize); //構造函數(shù) ～UFSets(){delete[]parent;} //析構函數(shù)

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

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

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

voidUnionByHeight(intRoot1,intRoot2);

//改進例程:壓縮高度的合并算法private:45精選PPTint*parent; //集合元素數(shù)組(雙親表示)intsize; //集合元素的數(shù)目};UFSets::UFSets(intsz){ //構造函數(shù)：sz是集合元素個數(shù)，雙親數(shù)組的范圍//為parent[0]～parent[size-1]。

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

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

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

//每個自成單元素集合};46精選PPT并查集操作的算法查找-5012301234Find(4)Find

(3)=3

Find(2)

=2

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

=-5<0

結束47精選PPT

-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]));};48精選PPTvoidUFSets::Union(intRoot1,intRoot2){//求兩個不相交集合Root1與Root2的并

parent[Root1]+=parent[Root2];

parent[Root2]=Root1;

//將Root2連接到Root1下面};Find和

Union操作性能不好。假設最初n個元素構成n棵樹組成的森林，parent[i]=-1。做處理Union(n-2,n-1),…,Union(1,2),Union(0,1)后，將產生退化的樹。49精選PPT合并-1-1-1-1-10234-3-503213341332202314Union(0,1)-23-41421234Union(1,2)Union(2,3)Union(3,4)50精選PPT執(zhí)行一次Union操作所需時間是O(1)，n-1次Union操作所需時間是O(n)。若再執(zhí)行Find(0),Find(1),…,Find(n-1),若被搜索的元素為i，完成Find(i)操作需要時間為O(i)，完成n

次搜索需要的總時間將達到

改進的方法按樹的結點個數(shù)合并按樹的高度合并壓縮元素的路徑長度51精選PPT按樹結點個數(shù)合并結點個數(shù)多的樹的根結點作根-1-1-1-1-101234-1-10-7256-5-222332013456233020562314Union(2,0)52精選PPTvoidUFSets::WeightedUnion(intRoot1,intRoot2){//按Union的加權規(guī)則改進的算法

inttemp=parent[Root1]+parent[Root2];if(parent[Root2]<parent[Root1]){

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

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

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

parent[Root1]=temp;//Root2指向Root1}};53精選PPT按樹高度合并高度高的樹的根結點作根-1-1-1-1-101234-1-10-3256-3-222332013456233020562314Union(2,0)54精選PPTUnion操作的折疊規(guī)則為進一步改進樹的性能，可以使用如下折疊規(guī)則來“壓縮路徑”。即：如果j

是從i

到根的路徑上的一個結點，且parent[j]root[j]，則把parent[j]置為root[i]。0067867819193535從i=5

壓縮路徑00000000777999-8-855精選PPTintUFSets::CollapsingFind(inti){//使用折疊規(guī)則的搜索算法

for(intj=i;parent[j]>=0;j=parent[j]);

//讓

j循雙親指針走到根

while(parent[i]!=j){

//換

parent[i]到

jinttemp=parent[i];

parent[i]=j;i=temp;}

returnj;} 56精選PPT字典（Dictionary）

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

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

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

boolMember(Namename);

//判name是否在字典中

Attribute*Search(Namename);

//在字典中搜索關鍵碼與name匹配的表項

59精選PPTvoidInsert(Namename,Attributeattr);

//若name在字典中,則修改相應<name,Attr>對

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

voidRemove(Namename);

//若name在字典中,則在字典中刪除相應的

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

（關鍵碼key，記錄或表項位置指針adr）構成搜索某一指定記錄或表項的索引項。60精選PPT字典的線性表描述

字典可以保存在線性序列(e1,e2,…)中，其中ei是字典中的元素，其關鍵碼從左到右依次增大。為了適應這種描述方式，可以定義有序順序表和有序鏈表。用有序鏈表來表示字典時，鏈表中的每個結點表示字典中的一個元素，各個結點按照結點中保存的數(shù)據值非遞減鏈接，即e1≤e2≤…。因此，在一個有序鏈表中尋找一個指定元素時，一般不用搜索整個鏈表。61精選PPT#include<iostream.h>#include“SeqList.h”constintdefaultSize=50;template<classE,classK>class

SortedList:publicSeqList{public:

intSearch(Kk1)const; //搜索

voidInsert(constKk1,E&e1); //插入

boolRemove(constK

k1,E&e1); //刪除};有序順序表的類定義62精選PPT基于有序順序表的順序搜索算法template<classE,classK>intSortedList<E,K>::Search(Kk1)const{//順序搜索關鍵碼為x的數(shù)據對象

for(inti=1;i<=n;i++)

if(data[i-1]==k1)returni;//成功

elseif(data[i-1]>k1)break;return0;

//順序搜索失敗,返回失敗信息};算法中的“==”和“>”都是重載函數(shù)，在定義E時定義它們的實現(xiàn)。63精選PPT有序順序表順序搜索的時間代價衡量一個搜索算法的時間效率的標準是：在搜索過程中關鍵碼平均比較次數(shù)，也稱為平均搜索長度ASL(AverageSearchLength)，通常它是字典中元素總數(shù)n的函數(shù)。設搜索第i

個元素的概率為pi,搜索到第i

個元素所需比較次數(shù)為ci,則搜索成功的平均搜索長度:64精選PPT在順序搜索情形，搜索第i(1≤i≤n)個元素需要比較i

次，假定按等概率搜索各元素：這與一般順序表情形相同。但搜索不成功時不需一直比較到表尾，只要發(fā)現(xiàn)下一個元素的值比給定值大，就可斷定搜索不成功。設一個有n

個表項的表，查找失敗的位置有n+1個，可以用判定樹加以描述。搜索成功時停在內結點，搜索失敗時停在外結點。65精選PPT例如，有序順序表(10,20,30,40,50,60)的順序搜索的分析（使用判定樹）105060======203040<<<<<<>>>>>>66精選PPT判定樹是一種擴充二叉樹。內結點代表順序表中已有的元素，外結點代表失敗結點，它表示在兩個相鄰已有元素值之間的值。假定表中所有失敗位置的搜索概率相同，則搜索不成功的平均搜索長度：時間代價為O(n)。為了加速搜索，在有序順序表的情形，可以采用折半搜索，它也稱二分搜索，時間代價可減到O(log2n)。67精選PPT基于有序順序表的折半搜索設n個元素存放在一個有序順序表中。折半搜索時,先求位于搜索區(qū)間正中的元素的下標mid，用其關鍵碼與給定值x比較:

data[mid].key==x，搜索成功；

data[mid].key>x，把搜索區(qū)間縮小到表的前半部分，繼續(xù)折半搜索；

data[mid].key<x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。如果搜索區(qū)間已縮小到一個對象，仍未找到想要搜索的對象，則搜索失敗。68精選PPT搜索成功的例子-101346810126012345678搜索給定值lowmidhigh66810125678lowmidhigh665lowmidhigh669精選PPT搜索失敗的例子-101346810125012345678搜索給定值lowmidhigh56810125678lowmidhigh655lowmidhigh570精選PPTtemplate<classE,classK>intSortedList<E,K>::BinarySearch(Kk1,

const

intlow,

const

inthigh)const{//折半搜索的遞歸算法，用到E的重載操作“<”和“>”

intmid=0; //元素序號從1開始

if(low<=high){

mid=(low+high)/2;

if(data[mid-1]<k1)//元素序號與下標差一

mid=BinarySearch(k1,mid+1,high);

elseif(data[mid-1]>k1) mid=BinarySearch(k1,low,mid-1);}returnmid;};71精選PPTtemplate<classE,classK>intSortedList<E,K>::BinarySearch(Kk1)const{

//折半搜索的迭代算法，用到E的重載操作“<”和“>”

inthigh=n,low=1,mid;//元素序號從1開始

while(low<=high){

mid=(low+high)/2;

if(data[mid-1]<k1)low=mid+1;

//右縮搜索區(qū)間

else

if(data[mid-1]>k1)high=mid-1;

//左縮搜索區(qū)間

elsereturnmid;//搜索成功

}

return0;//搜索失敗}72精選PPT分析有序順序表(10,20,30,40,50,60)的折半搜索算法性能的判定樹：1050======30<<<<<<>>>>>>204060ASLunsucc=(2*1+3*6)/7=20/7ASLsucc=(1+2*2+3*3)/6=14/6

73精選PPT判定樹也是擴充二叉樹，搜索成功時檢測指針停留在樹中某個內結點上。搜索不成功時檢測指針停留在某個外結點（失敗結點）上。3515455025102030搜索22搜索4574精選PPT折半搜索算法的性能分析若設n=2h-1，則描述折半搜索的判定樹是高度為h

的滿二叉樹。

2h=n+1,h=log2(n+1)第1層結點有1個,搜索第1層結點要比較1次;第2層結點有2個,搜索第2層結點要比較2次;…,第i(1≤i≤h)層結點有2i-1

個,搜索第i層結點要比較i次，…。假定每個結點的搜索概率相等，即pi

=1/n，則搜索成功的平均搜索長度為75精選PPT可以用歸納法證明這樣，由2h=n+1,h=log2(n+1)76精選PPT有序鏈表的類定義

#include<assert.h>template<classE,classK>structChainNode{ //鏈表結點類定義

Edata;

ChainNode<E,K>*link;

ChainNode():link(NULL){}; //構造函數(shù)

ChainNode(E&e1,//構造函數(shù)

ChainNode<E,K>*next=NULL)

:data(e1),link(next){};};77精選PPTtemplate<classE,classK>classSortedChain{ //有序鏈表類定義public:

SortedChain(){ //構造函數(shù)

first=newChainNode<E,K>;

assert(first!=NULL);};

～SortedChain(); //析構函數(shù)

ChainNode<E,K>*Search(K

k1); //搜索

voidInsert(constKk1,E&e1); //插入

boolRemove(constK

k1,E&e1); //刪除

78精選PPT

ChainNode<E,K>*Begin(){returnfirst->link;} //定位第一個

ChainNode<E,K>*Next(ChainNode<E,K>*current)const{ //定位下一個

if(current!=NULL)returncurrent->link;elsereturnNULL;}private:

ChainNode<E,K>*first; //鏈表的頭指針};79精選PPT搜索、插入與刪除算法template<classE,classK>ChainNode<E,K>*SortedChain<T>::Search(constK

k1)const{

ChainNode<E,K>*p=first->link;while(p!=NULL&&p->data<k1)p=p->link; //重載：元素判小于

if(p!=NULL&&p->data==k1)returnp; //重載：元素判等于

elsereturnNULL;};80精選PPTtemplate<classE,classK>voidSortedChain<E,K>::Insert(constK

k1,E&e1){

ChainNode<E,K>*p=first->link,*pre=first；

ChainNode<E,K>*newNode;while(p!=NULL&&p->data

<=k1)

//重載：元素判小于等于

{pre=p;p=p->link;} //尋找插入位置

if(p!=NULL&&p->data==k1)

p->data=e1;else{newNode=newChainNode<E,K>(e1);if(newNode==NULL){

81精選PPTcerr<<“存儲分配失??！”<<endl;exit(1);}

newNode->link=p;pre->link=newNode;}};template<classE,classK>boolSortedChain<E,K>::Remove(constK

k1,E&e1){ChainNode<E,K>*p=first->link,*pre=first；

while(p!=NULL&&p->data<k1)

82精選PPT {pre=p;p=p->link;} //尋找刪除位置

if(p!=NULL&&p->data==k1