數(shù)據(jù)結(jié)構(gòu)與算法

第七章搜索結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)電子教案1靜態(tài)搜索表二叉搜索樹最優(yōu)二叉搜索樹AVL樹第七章搜索結(jié)構(gòu)2搜索(Search)的概念靜態(tài)搜索表所謂搜索，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。搜索的結(jié)果通常有兩種可能：搜索成功，即找到滿足條件的數(shù)據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中的位置,還可給出該對(duì)象中的具體信息。搜索不成功，或搜索失敗。作為結(jié)果，應(yīng)報(bào)告一些信息,如失敗標(biāo)志、位置等。3通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象(或記錄)組成。在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的環(huán)境。靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。靜態(tài)搜索表

4動(dòng)態(tài)環(huán)境，為保持較高的搜索效率,搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。

動(dòng)態(tài)搜索表在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)元素的存放地址。搜索算法根據(jù)給定值k，在數(shù)組中進(jìn)行搜索。直到找到k在數(shù)組中的存放位置或可確定在數(shù)組中找不到

k為止。

靜態(tài)搜索表5數(shù)據(jù)表與搜索表的類定義

#include<iostream>#include<cassert>usingnamespacestd;template<classE,classK>

classdataList;

//

前視定義template<classE,classK>classdataNode{ //

數(shù)據(jù)表中結(jié)點(diǎn)類的定義

friendclassdataList<E,K>;//

聲明友元類private:6

Kkey; //

關(guān)鍵碼域

Eother; //

其他域，視問題而定public:

dataNode(

)

{

}

//

構(gòu)造函數(shù)

KgetKey(

)const{returnkey;} //

讀取關(guān)鍵碼voidsetKey(const

Kx){key=x;}//

修改關(guān)鍵碼};template<classE,classK>classdataList{ //

數(shù)據(jù)表類定義protected:7

dataNode<E,K>*Element;//

數(shù)據(jù)表存儲(chǔ)數(shù)組intArraySize,CurrentSize;//

數(shù)組長度和元素個(gè)數(shù)public:

dataList(intsz):ArraySize(sz),

CurrentSize(0){

Element=newdataNode<E,K>[sz];

assert(Element!=NULL);}

dataList(dataList<E,K>&R);//

復(fù)制構(gòu)造函數(shù)virtual~dataList(

){delete[

]

Element;}

//

析構(gòu)函數(shù)

8virtualintLength()const{returnCurrentSize;}virtualKgetKey(constinti)const{

//

提取第i（0開始）元素值

assert(i>=0

&&

i<CurrentSize);

returnElement[i].key;}virtualvoidsetKey(const

Kx,constinti){

//

修改第i（0開始）元素值assert(i>=

0

&&

i<CurrentSize);

Element[i].key=x;}9

virtualboolInsert(constdataNode<E,K>&e1);

//

插入

virtualboolRemove(constKx,E&e1);

//

刪除

voidoutput()const; //

輸出

voidinput(); //

輸入

};template<classE,classK>booldataList<E,K>::Insert( const

dataNode<E,K>&e1){//

在dataList的尾部插入新元素,若插入失敗函數(shù)返//

回false,否則返回true.10

if(CurrentSize==ArraySize)returnfalse;

Element[CurrentSize]=e1; //插入在尾端

CurrentSize++;returntrue;}template<classE,classK>booldataList<E,K>::Remove(constKx,E&e1){//在dataList中刪除關(guān)鍵碼為x的元素,通過e1返回。//用尾元素填補(bǔ)被刪除元素。

if(CurrentSize==0)returnfalse;inti;for(i=0;i<CurrentSize&&Element[i].key!=x;i++);//在表中順序?qū)ふ?1if(i==CurrentSize)returnfalse; //

未找到

e1=Element[i].other;//

找到,保存被刪元素的值

Element[i]=Element[CurrentSize-1];//

填補(bǔ)

CurrentSize--;returntrue;}template<classE,classK>voiddataList<E,K>::output(

)

const{

cout

<<"數(shù)組中的元素為："<<endl;

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

cout<<Element[i].key<<'';

cout<<endl;12

cout<<"元素個(gè)數(shù):

"<<CurrentSize<<endl;}template<classE,classK>voiddataList<E,K>::input(

){

cout<<"輸入存儲(chǔ)數(shù)組當(dāng)前長度:

"; cin>>CurrentSize;

cout<<"輸入數(shù)組元素的關(guān)鍵碼:\n";for(inti=0;i<CurrentSize;i++){

cout<<"元素

"<<i+1<<":"; cin>>

Element[i].key;}}13順序搜索主要用于在線性表中搜索。設(shè)若表中有CurrentSize個(gè)元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值x進(jìn)行比較若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與x相等的元素，則搜索失敗。給出失敗信息(這里用-1表示)。順序搜索（SequentialSearch）

14一般的順序搜索算法在第二章已經(jīng)討論過，本章介紹一種使用“監(jiān)視哨”的順序搜索方法。設(shè)在數(shù)據(jù)表dataList中順序搜索關(guān)鍵碼與給定值x相等的數(shù)據(jù)元素，要求數(shù)據(jù)元素在表中從下標(biāo)0開始存放,下標(biāo)為CurrentSize的元素作為控制搜索過程自動(dòng)結(jié)束的“監(jiān)視哨”使用。若搜索成功，則函數(shù)返回該元素在表中序號(hào)Location（下標(biāo)）,若搜索失敗，則函數(shù)返回-1。15順序搜索表類

constintdefaultSize=100;template<classE,classK>classSearchList:publicdataList<E,K>{public:

SearchList(intsz=defaultSize)

:dataList(sz){ } intSeqSearch(constK

x)const;

//順序搜索

intSeqSearch(constKx,intloc)const;

//遞歸搜索};16使用監(jiān)視哨的順序搜索算法

template<classE,classK>intSearchList<E,K>::SeqSearch(constKx)const{

Element[CurrentSize].setKey(x);

//

監(jiān)視哨 inti=0;while(Element[i++].getKey()!=x); //從前向后順序搜索return(i==CurrentSize?-1:i);}constintSize=10;voidmain(void){17dataList<int,int>L1(Size); //

定義搜索表L1intTarget;intLoc;

L1.input();L1.output();

//

(修改教材)cout<<"輸入要查找的關(guān)鍵碼

:";cin>>Target; //

輸入要搜索的數(shù)據(jù)

if((Loc=L1.SeqSearch(Target))

>=0)cout<<"找到待查元素位置在："<<Loc

+

1

<<endl; //

搜索成功else

cout<<"沒有找到待查元素！"<<endl;

//

搜索不成功}18設(shè)數(shù)據(jù)表中有n

個(gè)元素，搜索第i

個(gè)元素的概率為pi，搜索到第i

個(gè)元素所需比較次數(shù)為ci，則搜索成功的平均搜索長度:在順序搜索并設(shè)置“監(jiān)視哨”情形：

ci=i+1,i=0,1,,n-1，因此順序搜索的平均搜索長度19一般表中各個(gè)元素的搜索概率不同，如果按搜索的概率從高到低排列表中的元素，從有序順序表的情況可知，可以得到高的搜索效率。在等概率情形，pi=1/n,i=1,2,,n。搜索成功的平均搜索長度為：在搜索不成功情形，ASLunsucc

=n+1。20采用遞歸方法搜索值為x的元素，每遞歸一層就向待查元素逼近一個(gè)位置，直到到達(dá)該元素。假設(shè)待查元素在第i（0≤i<n）個(gè)位置，則算法遞歸深度達(dá)i（0～i）。102030405060i=1搜索

30102030405060i=2102030405060i=3遞歸順序搜索的遞歸算法21順序搜索的遞歸算法template<classE,classK>intdataList<E,K>::SeqSearch(constKx,

intloc)const{//

在數(shù)據(jù)表Element[0…n-1]中搜索其關(guān)鍵碼與給//

定值匹配的對(duì)象,函數(shù)返回其表中位置。參數(shù)

loc//是在表中開始搜索位置

if(loc>=CurrentSize)return

-1;

//

失敗

elseif(Element[loc].getKey()==x)//

搜索成功

returnloc;elsereturn

SeqSearch(x,loc+1);

//

遞歸搜索}22template<classE,classK>class

SortedList:publicdataList<E,K>{public:SortedList(intsz=100):dataList(sz){

}

intSearch(constKx)const; //順序搜索

intBinarySearch(constKx)const;//

折半搜索intBinarySearch(constKx,intlow, inthigh)const;//

遞歸折半搜索};有序順序表的類定義23基于有序順序表的順序搜索算法template<classE,classK>intSortedList<E,K>::SeqSearch(constKx)const{//順序搜索關(guān)鍵碼為x的數(shù)據(jù)對(duì)象 for(inti=0;i<CurrentSize;i++) if(Element[i].getKey()==x)returni;//成功 elseif(Element[i].getKey()>x)break;//失敗 return-1;}24有序順序表順序搜索的時(shí)間代價(jià)衡量一個(gè)搜索算法的時(shí)間效率的標(biāo)準(zhǔn)是：在搜索過程中關(guān)鍵碼平均比較次數(shù)，也稱為平均搜索長度ASL(AverageSearchLength)，通常它是搜索表中元素總數(shù)n的函數(shù)。設(shè)搜索第i

個(gè)元素的概率為pi,搜索到第i

個(gè)元素所需比較次數(shù)為ci,則搜索成功的平均搜索長度:25在順序搜索情形，搜索第i(0≤i<n)個(gè)元素需要比較i

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

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

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

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

Element[mid].key<x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。如果搜索區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要搜索的對(duì)象，則搜索失敗。29搜索成功的例子-101346810126012345678搜索給定值lowmidhigh6

6810125678lowmidhigh665lowmidhigh630搜索失敗的例子-101346810125012345678搜索給定值lowmidhigh5

6810125678lowmidhigh655lowmidhigh531template<classE,classK>intSortedList<E,K>::BinarySearch(constKx,

intlow,

inthigh)const{//折半搜索遞歸算法

intmid=-1;//

元素序號(hào)從

0

開始

if(low<=high){

mid=(low+high)/2;

if(Element[mid].getKey()<x)

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

elseif(Element[mid].getKey()>x)

mid=BinarySearch(x,low,mid-

1);

}

returnmid;}32template<classE,classK>intSortedList<E,K>::BinarySearch(constKx)const{

//折