引言集合是一個基本的數(shù)學(xué)概念。邏輯上，集合中元素間不存在固有的關(guān)系。

組織集合的方法很多。例如：集合可以用線性表、搜索樹、跳表和散列表表示。本章將討論集合的線性表表示，以及2種常用的搜索算法。第7章討論表示集合的多種搜索樹。第8章將介紹跳表和散列表表示的集合。第6章集合與搜索

DATASTRUCTURE數(shù)據(jù)結(jié)構(gòu)內(nèi)容提要

1.集合的基本概念

2.定義動態(tài)集ADT3.集合的表示形式

4.順序搜索

5.二分搜索6.1基本概念課堂提要第6章集合與搜索6.1基本概念6.2順序搜索6.3二分搜索(a)集合結(jié)構(gòu)(b)線性結(jié)構(gòu)(c)樹形結(jié)構(gòu)(d)圖結(jié)構(gòu)圖1-2四種基本的結(jié)構(gòu)關(guān)系1.集合（1）基本概念集合：在數(shù)學(xué)上，集合是不同對象的無序匯集。例如：集合{1,2,3}與{3,2,1}相同。元素：集合的對象。在集合中，每個元素僅出現(xiàn)一次。多重集：元素的無序匯集，其中每個元素可出現(xiàn)一次或多次。通常，用{}表示無序集。例如：集合{1,1,2,3}與{3,2,1,1}相同，但與{1,2.3}不同。6.1.1集合與搜索有序集：元素的匯集，其中每個元素可以出現(xiàn)一次或多次，并且出現(xiàn)次序是重要的。通常用()表示有序集。例如：(1,2,3)與(3,2,1)不同。（2）集合的運算數(shù)學(xué)意義上，集合運算主要有：求集合的并求集合的差求集合的交判斷兩集合是否相等2.動態(tài)集（1）動態(tài)集：在數(shù)據(jù)結(jié)構(gòu)意義上，集合通常是動態(tài)的，在集合中可以插入和刪除元素，因而稱為動態(tài)集。（2）集合元素定義Template<classK,classD>StructE{OperatorK()const{returnkey;}//使元素間的比較視為關(guān)鍵字間的比較Kkey;Ddata;}其中，K稱為關(guān)鍵字類型，應(yīng)為可比較大小的類型。key為關(guān)鍵字。除關(guān)鍵字外的其他數(shù)據(jù)項歸入data中。關(guān)鍵字：數(shù)據(jù)元素中用來標(biāo)識一個數(shù)據(jù)元素的某個數(shù)據(jù)項。主關(guān)鍵字:可以唯一標(biāo)識一個元素的關(guān)鍵字。次關(guān)鍵字:用以識別若干元素的關(guān)鍵字。本章中，若無特殊說明，都假定被搜索的關(guān)鍵字是主關(guān)鍵字。3.搜索運算當(dāng)信息量較少，整個集合元素都存放在內(nèi)存中，稱為表。否則，稱為文件。搜索運算是表和文件上的最典型運算。搜索：根據(jù)給定的某個值，在表中確定一個關(guān)鍵字值等于給定值的數(shù)據(jù)元素；若表中存在這樣的元素，則稱搜索成功，搜索結(jié)果可以返回整個數(shù)據(jù)元素，也可指示該元素在表中的地址；若表中不存在關(guān)鍵字等于給定值的元素，則稱搜索不成功（失?。?。4.搜索算法分類

按元素是否在內(nèi)存，分為：

內(nèi)搜索：對表的搜索

外搜索：對文件的搜索

按關(guān)鍵字的比較情況，分為：

基于關(guān)鍵字比較的搜索

此類搜索將在第7章介紹

基于計算地址的搜索

此類搜索將在第8章介紹6.1.2動態(tài)集ADTADT6.1動態(tài)集抽象數(shù)據(jù)類型ADTDynamicSet{

數(shù)據(jù):同類元素的有限匯集，其最大允許長度為MaxSetSize。元素由關(guān)鍵字標(biāo)識，集合的元素各不相同。

運算：

Create()：創(chuàng)建一個空集合。

Destroy()：撤消一個集合。

IsEmpty()：若集合空，則返回true，否則返回false。

IsFull()：若集合滿，則返回true，否則返回false。

Search(x)：在集合中搜索與x的關(guān)鍵字值相同的元素。如果存在該元素，則將其值賦給x，并且函數(shù)返回Success；否則返回NotPresent。

Insert(x):

在集合中搜索與x的關(guān)鍵字相同的元素。若集合中存在該元素，則將其值賦給x，函數(shù)返回Duplicate。否則，若集合已滿，則函數(shù)返回Overflow；若集合未滿，則在表中插入值為x的元素，函數(shù)返回Success。

Remove(x):

在集合中搜索與x的關(guān)鍵字值相同的元素。如果存在該元素，則將其值賦給x，并從集合中刪除之，函數(shù)返回Success；否則返回NotPresent。

}

程序6.1動態(tài)集的C++模板抽象類template<classT>classDynamicSet{public:virtualResultCode

Search(T＆x)const=0;virtualResultCode

Insert(T＆x)=0;virtualResultCode

Remove(T＆x)=0;virtualboolIsEmpty()const=0;virtualbool

IsFull()const=0;};其中，函數(shù)返回類型ResultCode為枚舉類型：Enum

ResultCode{Success,NotPresent,Duplicate,Overflow,Underflow}6.1.3集合的表示

組織集合的方法很多，組織的方法不同，實現(xiàn)搜索等運算的方法也不同，它直接影響運算的效率。集合可以用線性表、搜索樹、跳表和散列表表示。本章討論集合的線性表表示，重點討論在于順序表表示方式下的搜索算法。下一章將介紹集合的搜索樹表示；第八章將討論散列表的集合。

程序6.2順序表表示的動態(tài)集類template<classT>classListSet:public

DynamicSet<T>{public:

ListSet(int

mSize);~ListSet(){delete[]l;}

bool

IsEmpty()const{returnn==0};

bool

IsFull()const{returnn==maxSize};

ResultCode

Search(T＆x)const;

ResultCode

Insert(T＆x);

ResultCode

Remove(T＆x);

private:T*l;//指針l指向一個一維數(shù)組

int

maxSize;

intn;

……};6.2順序搜索

集合可以用線性表表示。如果線性表中元素已按關(guān)鍵字值的大小次序排列，則稱為有序表。否則為無序表。本節(jié)將分別討論無序表和有序表的順序搜索算法。課堂提要第6章集合與搜索6.1基本概念6.2順序搜索6.3二分搜索（41，25，28，33，36，15）搜索成功！33（41，25，28，33，36，15）搜索失?。?5

從頭開始檢查無序表，將指定元素x的關(guān)鍵字與表中元素的關(guān)鍵字比較，若相等，搜索成功；若搜索完整個表，不存在關(guān)鍵字值等于給定值的元素，搜索失敗。例如，在下表中分別搜索33和35。6.2.1無序表的順序搜索

程序6.3順序搜索無序表template<classT>ResultCode

ListSet<T>::Search(T&x)const{for(inti=0;i<n;i++)if(l[i]==x){x=l[i];returnSuccess;//搜索成功

}returnNotPresent;//搜索失敗}

一個有序表是一個線性表（a0,a1,…,an-1），并且表中元素的關(guān)鍵字值有如下關(guān)系：

ai.key

ai+1.key(0

i<n-1)其中，ai.key表示元素ai的某個指定的關(guān)鍵字域。一個有序表可視為一個已按關(guān)鍵字排序的有序集6.2.2有序表的順序搜索有序表的順序搜索算法

（21，25，28，33，36，45）搜索成功！33（21，25，28，33，36，45）搜索失敗！35

從頭開始檢查有序表，將指定元素x的關(guān)鍵字與表中元素的關(guān)鍵字比較，若相等，搜索成功；若搜索到某個元素關(guān)鍵字大于指定元素x時，搜索失敗。例如，在下表中分別搜索33和35。程序6.4順序搜索有序表template<classT>ResultCode

ListSet<T>::Search(T&x)const{for(inti=0;l[i]<x;i++);//當(dāng)l[i]的關(guān)鍵字值大等于x的關(guān)鍵字值時，退出循環(huán)if(l[i]==x){x=l[i];returnSuccess;//搜索成功}returnNotPresent;//搜索失敗}（21，25，28，33，36，45）

分析一個搜索算法的時間復(fù)雜度通常分成功搜索以及搜索失敗兩種情況加以討論。為了確定一個指定關(guān)鍵字值的記錄在表中的位置所需的關(guān)鍵字值之間的比較次數(shù)的期望值稱為搜索算法的平均搜索長度(averagesearchlengthASL)。

6.2.3平均搜索長度1.無序表順序搜索（1）成功搜索的平均搜索長度

計算算法的平均搜索時間，需要給定表中元素ai被搜索的概率pi，假定每個元素的搜索概率是相等的，即pi=1/n，則程序6.3中，搜索成功時的平均搜索長度為（2）搜索失敗的平均搜索長度該函數(shù)在搜索失敗的情況下，總要進行n次關(guān)鍵字值之間的比較。（21，25，28，33，36，45）2.有序表順序搜索（1）成功搜索的平均搜索長度程序6.4的搜索有序表函數(shù)中，搜索成功時的平均搜索長度大致與搜索無序表相同。（2）搜索失敗的時間復(fù)雜度在搜索失敗的情況下，程序6.4的平均搜索長度大約比程序6.3快一倍。（21，25，28，33，36，45）6.3二分搜索

本節(jié)將介紹線性表上的另一種搜索算法：二分搜索。課堂提要第6章集合與搜索6.1基本概念6.2順序搜索6.3二分搜索

查找TP391.4/3-841

查找TP391.4/3-841

二分搜索的基本思想是：設(shè)有一個長度為n的有序表（l0,l1,l2,…,ln-1），要求在表中搜索與給定元素x有相同關(guān)鍵字的元素。若n=0,搜索失??；若n>0，可將有序表分解成兩個子表?，F(xiàn)以元素am為分割點，將表分成(l0,l1,l2,…,lm-1)和(lm+1,…,ln-1)兩個表。將lm的關(guān)鍵字值與X的關(guān)鍵字值作比較。比較結(jié)果有三種可能性：

（1)X<lm:若關(guān)鍵字值為X的元素在表中，則必定在子表（l0,l1,…,lm-1）中，可以在子表中繼續(xù)進行二分搜索；

（2)X==lm:搜索成功；

（3)X>lm:

若關(guān)鍵字值為X的元素在表中，則必定在子表（lm+1,lm+2,…,ln-1）中，可以在子表中繼續(xù)進行二分搜索。6.3.1二分搜索算法(l0,l1,l2,…lm-1,lm,lm+1…,ln-1)X

由分割點的不同，可以得到不同的二分搜索方法。如：對半搜索、一致對半搜索、斐波那契搜索和插值搜索等。

對半搜索是二分搜索中的一種。分割點為表的中點元素。若當(dāng)前搜索的子表為（llow,llow+1,…,lhigh）則m=(low+high)/2其中，m、low和high均為元素在表中的序號，low表示表的左端，high表示表的右端。

6.3.2對半搜索對半搜索的算法思想：如果當(dāng)前的表不空，則x與l[m]比較。若兩者相等，則搜索成功，函數(shù)返回m；若x小于l[m]，則繼續(xù)查找左半部分子表[low,m-1];否則繼續(xù)查找右半部分子表[m+1,high].如果當(dāng)前搜索的表是空表，則搜索失敗，函數(shù)返回-1.[Low21303641525466728397]high52(1)key=6666[Low]high722130364152546672839721303641525466728397][54搜索成功！21303641525466728397][66

下標(biāo)0123456789[Low21303641525466728397]high52(2)key=3535[Low]high302130364152546672839721303641525466728397][36搜索失敗！21303641525466728397][

下標(biāo)0123456789程序6.5對半搜索的遞歸算法template<classT>

ResultCode

ListSet<T>::Search(T&x)const{

inti=BSearch(x,0,n-1);if(i==-1)returnNotPresent;x=l[i];returnSuccess;}template<classT>int

ListSet<T>::BSearch(T&x,int

low,int

high)const{//遞歸函數(shù)，實現(xiàn)對半搜索

if(low<=high){

intm=(low+high)/2;//對半分割

if(x<l[m])returnBSearch(x,low,m-1); elseif(x>l[m])returnBSearch(x,m+1,high); elsereturnm;//x＝＝l[m]，搜索成功

}return-1;//搜索失敗}low=0high=6{if(low<=high){intm=(low+high)/2;if(x<l[m])...BSearch(x,low,m-1)elseif(x>l[m])...BSearch(x,m+1,high);elsereturnm;}}0

1

2

34563720

34

455664x=453low=4high=6{if(low<=high){intm=(low+high)/2;if(x<l[m])...BSearch(x,low,m-1)elseif(x>l[m])...BSearch(x,m+1,high);elsereturnm;}}5low=4high=4{if(low<=high){intm=(low+high)/2;if(x<l[m])...BSearch(x,low,m-1)elseif(x>l[m])...BSearch(x,m+1,high);elsereturnm;}}4程序6.6對半搜索的迭代算法template<classT>ResultCode

ListSet<T>::Search(T&x)const{

int

m,low=0,high=n-1;while(low<=high){m=(low+high)/2;if(x<l[m])high=m-1; elseif(x>l[m])low=m+1;else{ x=l[m];returnSuccess;//搜索成功

}}returnNotPresent;//搜索失敗}6.3.3

二叉判定樹可以建立一棵二叉判定樹來模擬對半搜索執(zhí)行過程二叉判定樹:

（1）指定元素x的關(guān)鍵字值與表中元素l[m]的關(guān)鍵字值之間的一次比較操作，表現(xiàn)為二叉判定樹中的一個內(nèi)結(jié)點，用一個圓形結(jié)點表示，并用m標(biāo)識。如果x==l[m]，則算法在該結(jié)點處成功終止。（2）二叉判定樹的根結(jié)點，代表算法中首先與x比較的元素l[m]，用m標(biāo)識。（3）結(jié)點m的左孩子是當(dāng)x<l[m]時，算法接下去與x比較的元素下標(biāo)，其右孩子是當(dāng)x>l[m]時,算法接下去與x比較的元素下標(biāo)。

（4）如果根據(jù)算法，在x與l[m]比較之后有x<l[m]，且算法終止，那么，結(jié)點m的左孩子用一個方形結(jié)點表示，結(jié)點標(biāo)號為m－1。反之，在x與l[m]比較之后有x>l[m]，且算法終止，那么，結(jié)點m的右孩子用一個方形結(jié)點表示，結(jié)點標(biāo)號為m。方形結(jié)點稱為外結(jié)點。換句話說，如果算法在方形結(jié)點m處終止，這意味著：（a）當(dāng)0

m<n-1時，l[m]<x<l[m+1]之間；（b）當(dāng)m=-1時，x<l[0]；（c）當(dāng)m=n-1時，x>l[n-1]。（5）從根結(jié)點到每個內(nèi)結(jié)點的一條路徑代表成功搜索的一條比較路徑。如果搜索成功，則算法在內(nèi)結(jié)點處終止，否則算法在外結(jié)點處終止。

二叉判定樹的建立：(1)根結(jié)點：第一次比較的元素的結(jié)點(2)結(jié)點的序號：元素的下標(biāo)；(3)根結(jié)點左子樹的根結(jié)點：左邊子表第一次比較的元素的結(jié)點下標(biāo)；(4)根結(jié)點右子樹的根結(jié)點：右邊子表第一次比較的元素的結(jié)點下