數(shù)據(jù)結(jié)構(gòu)ds-07(刪減部分13)

第七章搜索結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)電子教案本章的主要內(nèi)容是:搜索的基本概念線性表的搜索技術(shù)樹表的搜索技術(shù)散列表的搜索技術(shù)3所謂搜索，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象。搜索的結(jié)果通常有兩種可能：搜索成功搜索不成功

搜索(Search)的概念基本概念關(guān)鍵碼：可以標識一個記錄的某個數(shù)據(jù)項。鍵值：關(guān)鍵碼的值。主關(guān)鍵碼：可以唯一地標識一個記錄的關(guān)鍵碼。

次關(guān)鍵碼：不能唯一地標識一個記錄的關(guān)鍵碼。7.1概述50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972.92003.71979.92003.71990.4工作時間靜態(tài)搜索：不涉及插入和刪除操作的搜索。動態(tài)搜索：涉及插入和刪除操作的搜索。

7.1概述查找的基本概念靜態(tài)搜索適用于：搜索集合一經(jīng)生成，便只對其進行搜索，而不進行插入和刪除操作，或經(jīng)過一段時間的搜索之后，集中地進行插入和刪除等修改操作；動態(tài)搜索適用于：查找與插入和刪除操作在同一個階段進行，例如當查找成功時，要刪除查找到的記錄，當查找不成功時，要插入被查找的記錄。7.1概述基本概念搜索結(jié)構(gòu)：面向搜索操作的數(shù)據(jù)結(jié)構(gòu)，即搜索基于的數(shù)據(jù)結(jié)構(gòu)。查找結(jié)構(gòu)

查找方法

集合中元素之間不存在明顯的組織規(guī)律，不便查找。集合

線性表

樹表

散列表

本章討論的搜索結(jié)構(gòu)：線性表：適用于靜態(tài)搜索，主要采用順序搜索技術(shù)和折半搜索技術(shù)。樹表：適用于動態(tài)搜索，主要采用二叉排序樹的搜索技術(shù)。散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術(shù)。

7.1概述基本概念搜索算法的性能

搜索算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。7.1概述關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？平均搜索長度：將搜索算法進行的關(guān)鍵碼的比較次數(shù)的數(shù)學期望值定義為平均搜索長度，即：其中：n：問題規(guī)模，查找集合中的記錄個數(shù)；

pi：搜索第i個記錄的概率；ci：搜索第i個記錄所需的關(guān)鍵碼的比較次數(shù)。ASL?==niiicp1搜索算法的性能

7.1概述ASL?==niiicp1ci取決于算法；pi與算法無關(guān)，取決于具體應(yīng)用。如果pi是已知的，則平均查找長度只是問題規(guī)模的函數(shù)。在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)組元素的下標作為數(shù)據(jù)元素的存放地址。搜索算法根據(jù)給定值k，在數(shù)組中進行搜索。直到找到k在數(shù)組中的存放位置或可確定在數(shù)組中找不到

k為止。

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

#include<iostream.h>#include<assert.h>constintdefaultSize=100;template<classE,classK>classdataList; //數(shù)據(jù)表類的前視定義template<classE,classK>classdataNode{ //數(shù)據(jù)表中結(jié)點類的定義friendclassdataList<E,K>; private:

Kkey; //關(guān)鍵碼域

E

other; //其他域（視問題而定）

//聲明其友元類為dataListpublic:12

dataNode(constKx):key(x){} //構(gòu)造函數(shù)

KgetKey()const{returnkey;} //讀取關(guān)鍵碼

voidsetKey(Kx){key=x;} //修改關(guān)鍵碼};template<classE,classK>classdataList{ //數(shù)據(jù)表類定義protected:

dataNode<E,K>*Element; //數(shù)據(jù)表存儲數(shù)組

intArraySize,CurrentSize; //數(shù)組最大長度和當前長度13順序搜索主要用于在線性表中搜索。順序用各元素的關(guān)鍵碼與給定值x進行比較技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。7.1.2順序搜索（SequentialSearch）

順序查找（線性查找）基本思想：從線性表的一端向另一端逐個將關(guān)鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。

101524612354098550123456789i例：查找k＝35iii順序查找（線性查找）intSeqSearch1(intr[],intn,intk)//數(shù)組r[1]~r[n]存放查找集合{i=n;while(i>0&&r[i]!=k)i--;returni;}基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

改進的順序查找101524612354098550123456789i例：查找k＝35iii哨兵35查找方向基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

改進的順序查找101524612354098550123456789i例：查找k＝25ii25查找方向iiiiiiiintSeqSearch2(intr[],intn,intk)//數(shù)組r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}改進的順序查找

ASL==?=niicp1?+-=niiinp1)1(i=(n+1)/2=O(n)平均查找長度較大，特別是當待查找集合中元素較多時，查找效率較低。順序查找的缺點：對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；對表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。順序查找的優(yōu)點：算法簡單而且使用面廣。7.1.3基于有序順序表的折半搜索哨兵法當N很大時，搜索的效率很低。如果把順序表的元素按其關(guān)鍵碼從小到大排列，則可以采取效率更高的搜索算法。20折半搜索使用條件：線性表中的記錄必須按關(guān)鍵碼有序；必須采用順序存儲?；舅枷耄赫郯胨阉鲿r,先求位于搜索區(qū)間正中的對象的下標mid，用其關(guān)鍵碼與給定值x比較:Element[mid].key==x，搜索成功；

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

Element[mid].key<x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。例：查找值為14的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值為22的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>highintBinSearch1(intr[],intn,intk){//數(shù)組r[1]~r[n]存放查找集合low=1;high=n;while(low<=high){

mid=(low+high)/2;if(k<r[mid])high=mid-1;elseif(k>r[mid])low=mid+1;elsereturnmid;}return0;}折半查找——非遞歸算法intBinSearch2(intr[],intlow,inthigh,intk){//數(shù)組r[1]~r[n]存放查找集合if(low>high)return0;

else{mid=(low+high)/2;if(k<r[mid])returnBinSearch2(r,low,mid-1,k);elseif(k>r[mid])returnBinSearch2(r,mid+1,high,k);elsereturnmid;}}折半查找——遞歸算法有序順序表的折半搜索的判定樹

(10,20,30,40,50,60)1050======30<<<<<<>>>>>>204060(2*1+3*6)/7折半搜索性能分析若設(shè)n=2h-1，則描述折半搜索的判定樹是高度為h-1的滿二叉樹。

2h=n+1,h=log2｜

(n+1)︱。搜索成功：在表中查找任一記錄的過程，即是折半查找判定樹中從根結(jié)點到該記錄結(jié)點的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點在樹中的層數(shù)。搜索不成功：查找失敗的過程就是走了一條從根結(jié)點到外部結(jié)點的路徑，和給定值進行的關(guān)鍵碼的比較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)?？梢杂脷w納法證明課堂練習（多項選擇）：Ａ．采用鏈式存貯結(jié)構(gòu) Ｂ．記錄的長度≤128Ｃ．采用順序存貯結(jié)構(gòu)Ｄ．記錄按關(guān)鍵字遞增有序√√使用折半查找算法時，要求被查文件：307.2二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：所有結(jié)點的關(guān)鍵碼互不相同。左子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都小于根結(jié)點的關(guān)鍵碼。右子樹（如果非空）上所有結(jié)點的關(guān)鍵碼都大于根結(jié)點的關(guān)鍵碼。左子樹和右子樹也是二叉搜索樹。351545504025102030二叉搜索樹例結(jié)點左子樹上所有關(guān)鍵碼小于結(jié)點關(guān)鍵碼；右子樹上所有關(guān)鍵碼大于結(jié)點關(guān)鍵碼；（a）（b）練：下列2種圖形中，哪個不是二叉搜索樹？如果對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結(jié)點關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。二叉搜索樹的類定義#include<iostream.h>#include<stdlib.h>template<classE,classK>structBSTNode{ //二叉樹結(jié)點類

Edata; //數(shù)據(jù)域

BSTNode<E,K>*left,*right;//左子女和右子女BSTNode(){left=NULL;right=NULL;

}

BSTNode(constEd,BSTNode<E,K>*L=NULL,

BSTNode<E,K>*R=NULL){data=d;left=L;right=R;}～BSTNode(){} //析構(gòu)函數(shù)

voidsetData(Ed){data=d;} //修改

EgetData(){returndata;} //提取

booloperator<(constE&x)

//重載：判小于

{returndata.key<x.key;}

booloperator>(constE&x) //重載：判大于

{returndata.key>x.key;}booloperator==(constE&x) //重載：判等于

{returndata.key==x.key;}};template<classE,classK>classBST{ //二叉搜索樹類定義private:BSTNode<E,K>*root; //根指針

KRefValue; //輸入停止標志public:BST(){root=NULL;

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

BST(Kvalue); //構(gòu)造函數(shù)

～BST(){}; //析構(gòu)函數(shù)

boolSearch(constKx)const //搜索

{returnSearch(x,root)!=NULL;}

BST<E,K>&operator=(constBST<E,K>&R); //重載：賦值

voidmakeEmpty()

//置空

{makeEmpty(root);root=NULL;}voidPrintTree()const{PrintTree(root);}//輸出

EMin(){returnMin(root)->data;} //求最小

EMax(){returnMax(root)->data;} //求最大

boolInsert(constE&e1)

//插入新元素

{returnInsert(e1,root);}boolRemove(constKx){returnRemove(x,root);} //刪除含x的結(jié)點private:

BSTNode<E,K>* //遞歸：搜索

Search(constKx,BSTNode<E,K>*ptr);voidmakeEmpty(BSTNode<E,K>*&ptr); //遞歸：置空

voidPrintTree(BSTNode<E,K>*ptr)const; //遞歸：打印

BSTNode<E,K>* //遞歸：復制

Copy(constBSTNode<E,K>*ptr); BSTNode<E,K>*Min(BSTNode<E,K>*ptr);

//遞歸：求最小

BSTNode<E,K>*Max(BSTNode<E,K>*ptr);

//遞歸：求最大

boolInsert(constE&e1,BSTNode<E,K>*&ptr);

//遞歸：插入

boolRemove(constKx,BSTNode<E,K>*&ptr);

//遞歸：刪除};二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。二叉搜索樹的搜索算法在二叉搜索樹上進行搜索，是一個從根結(jié)點開始，遞歸進行比較判等的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x

的元素，搜索過程從根結(jié)點開始。如果根指針為NULL，則搜索不成功；否則用給定值

x

與根結(jié)點的關(guān)鍵碼進行比較：若給定值等于根結(jié)點關(guān)鍵碼，則搜索成功若小于根結(jié)點的關(guān)鍵碼，則搜索左子樹；否則。遞歸搜索根結(jié)點的右子樹。搜索45搜索成功搜索28搜索失敗351545504025102030template<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//私有遞歸函數(shù)：在以ptr為根的二叉搜索樹中搜//索含x的結(jié)點。若找到，則函數(shù)返回該結(jié)點的//地址，否則函數(shù)返回NULL值。

if(ptr==NULL)returnNULL;

elseif(x<ptr->data)returnSearch(x,ptr->left);elseif(x>ptr->data)returnSearch(x,ptr->right);elsereturnptr; //搜索成功};template<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//非遞歸函數(shù)：作為對比，在當前以ptr為根的二//叉搜索樹中搜索含x的結(jié)點。若找到，則函數(shù)返//回該結(jié)點的地址，否則函數(shù)返回NULL值。

if(ptr==NULL)returnNULL;

BSTNode<E,K>*temp=ptr;while(temp!=NULL){

if(x==temp->data)returntemp;

if(x<temp->data)

temp=temp->left;elsetemp=temp->right;}returnNULL;};搜索過程是從根結(jié)點開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個結(jié)點；搜索不成功，搜索指針將走到樹上某個結(jié)點的空子樹。設(shè)樹的高度為h，最多比較次數(shù)不超過h。二叉搜索樹的插入算法為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點，把新元素加到搜索操作停止的地方。35154550402510203028插入新結(jié)點28二叉搜索樹的插入每次結(jié)點的插入，都要從根結(jié)點出發(fā)搜索插入位置，然后把新結(jié)點作為葉結(jié)點插入。二叉搜索樹的插入算法template<classE,classK>boolBST<E,K>::Insert(constE&e1,BSTNode<E,K>*&ptr){

if(ptr==NULL){ //新結(jié)點作為葉結(jié)點插入

ptr=newBstNode<E,K>(e1); //創(chuàng)建新結(jié)點

if(ptr==NULL){cerr<<"Outofspace"<<endl;exit(1);} returntrue;}elseif(e1<ptr->data)Insert(e1,ptr->left);

elseif(e1>ptr->data)Insert(e1,ptr->right);

elsereturnfalse; //x已在樹中,不再插入};利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。

輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981template<classE,classK>BST<E,K>::BST(Kvalue){//輸入一個元素序列,建立一棵二叉搜索樹

Ex;

root=NULL;RefValue=value; //置空樹

cin>>x; //輸入數(shù)據(jù)

while(x.key!=RefValue){ //RefValue是一個輸入結(jié)束標志

Insert(x,root);cin>>x; //插入，再輸入數(shù)據(jù)

}};在二叉排序樹上刪除某個結(jié)點之后，仍然保持二叉排序樹的特性。分三種情況討論：被刪除的結(jié)點是葉子；被刪除的結(jié)點只有左子樹或者只有右子樹；被刪除的結(jié)點既有左子樹，也有右子樹。

二叉搜索樹的刪除情況1——被刪除的結(jié)點是葉子結(jié)點二叉搜索樹的刪除50302080908588403532503020809085403532操作：將雙親結(jié)點中相應(yīng)指針域的值改為空。情況2——被刪除的結(jié)點只有左子樹或者只有右子樹操作：將雙親結(jié)點的相應(yīng)指針域的值指向被刪除結(jié)點的左子樹（或右子樹）。q=pp=p->lchild（或p=p->rchild）；free(q)二叉搜索樹的刪除50302080908588403532503020908588403532qp8853788117940945刪除78在右子樹上找中序下第一個結(jié)點填補2365538188179409452365情況3：被刪結(jié)點左、右子樹都不為空，以其左子樹中的最大值結(jié)點（或右子樹中的最小值結(jié)點）替代之，再來處理這個結(jié)點的刪除問題。情況3——被刪除的結(jié)點既有左子樹也有右子樹二叉搜索樹的刪除50302080908588403532403020809085883532二叉搜索樹的刪除算法template<classE,classK>boolBST<E,K>::Remove(constKx,

BstNode<E,K>*&ptr){//在以ptr為根的二叉搜索樹中刪除含x的結(jié)點

BstNode<E,K>*temp;if(ptr!=NULL){if(x<ptr->data)Remove(x,ptr->left);

//在左子樹中執(zhí)行刪除

elseif(x>ptr->data)Remove(x,ptr->right);

//在右子樹中執(zhí)行刪除elseif(ptr->left!=NULL&&ptr->right!=NULL)

{//ptr指示關(guān)鍵碼為x的結(jié)點，它有兩個子女

temp=ptr->right;

//到右子樹搜尋中序下第一個結(jié)點

while(temp->left!=NULL)temp=temp->left;

ptr->data=temp->data;

//用該結(jié)點數(shù)據(jù)代替根結(jié)點數(shù)據(jù)

Remove(ptr->data,ptr->right);} else{ //ptr指示關(guān)鍵碼為x的結(jié)點有一個子女

temp=ptr; if(ptr->left==NULL)ptr=ptr->right;elseptr=ptr->left;deletetemp;returntrue;} } returnfalse;};注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。

二叉搜索樹性能分析對于有n個關(guān)鍵碼的集合，其關(guān)鍵碼有n!種不同排列，可構(gòu)成不同二叉搜索樹有

(棵)

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

123111132223323同樣3個數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達到最大。用樹的搜索效率來評價這些二叉搜索樹。為此，在二叉搜索樹中加入外結(jié)點，形成判定樹。外結(jié)點表示失敗結(jié)點，內(nèi)結(jié)點表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴充的二叉搜索樹。舉例說明。已知關(guān)鍵碼集合

{a1,a2,a3}=

{do,if,to}，對應(yīng)搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3?？赡艿亩嫠阉鳂淙缦滤尽oiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)在判定樹中

○表示內(nèi)部結(jié)點，包含了關(guān)鍵碼集合中的某一個關(guān)鍵碼；□表示外部結(jié)點，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。一棵判定樹上的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點上的搜索概率p[i]與搜索該結(jié)點時所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點所在層次)乘積之和：設(shè)各關(guān)鍵碼的搜索概率相等：p[i]=1/n搜索不成功的平均搜索長度ASLunsucc為樹中所有外部結(jié)點上搜索概率q[j]與到達外部結(jié)點所需關(guān)鍵碼比較次數(shù)c'[j](=l'[j])乘積之和：設(shè)外部結(jié)點搜索概率相等：q[j]=1/(n+1)：設(shè)樹中所有內(nèi)、外部結(jié)點的搜索概率都相等：

p[i]=1/3,1≤i≤3,q[j]=1/4,0≤

j≤3

圖(a):ASLsucc=1/3*3+1/3*2+1/3*1=6/3,

ASLunsucc=1/4*3*2+1/4*2+1/4*1=9/4。

圖(b):

ASLsucc=1/3*2*2+1/3*1=5/3,

ASLunsucc=1/4*2*4=8/4。圖(c):ASLsucc=1/3*1+1/3*2+1/3*3=6/3,

ASLunsucc=1/4*1+1/4*2+1/4*3*2=9/4。圖(d):ASLsucc=1/3*2+1/3*3+1/3*1=6/3,

ASLunsucc=1/4*2+1/4*3*2+1/4*1=9/4。(1)相等搜索概率的情形

圖(e):ASLsucc=1/3*1+1/3*3+1/3*2=6/3,

ASLunsucc=1/4*1+1/4*3*2+1/4*2=9/4。圖(b)的情形所得的平均搜索長度最小。一般把平均搜索長度達到最小的擴充的二叉搜索樹稱作最優(yōu)二叉搜索樹。在相等搜索概率的情形下，所有內(nèi)部、外部結(jié)點的搜索概率都相等，視它們的權(quán)值都為1。同時，第k層有2k-1個結(jié)點，k=1,2,。則有n個內(nèi)部結(jié)點的擴充二叉搜索樹的內(nèi)部路徑長度I至少等于序列

0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,…