數(shù)據(jù)結(jié)構(gòu)第五章查找

查找是為了得到某個信息而進行的工作，也稱檢索基本概念與術(shù)語靜態(tài)查找表動態(tài)查找表哈希表查找基本概念關(guān)鍵碼關(guān)鍵碼是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值，用它

可以標(biāo)識一個數(shù)據(jù)元素。

主關(guān)鍵碼：能唯一確定一個數(shù)據(jù)元素的關(guān)鍵碼。次關(guān)鍵碼：不能唯一確定一個數(shù)據(jù)元素的關(guān)鍵碼。查找表查找表是一種以集合為邏輯結(jié)構(gòu)、以查找為核心的數(shù)據(jù)結(jié)構(gòu)。查找表的基本操作：建表、查找、讀表元、插入與刪除靜態(tài)查找表：指一經(jīng)建立就基本保持不變的查找表，

主要操作是檢索。動態(tài)查找表：經(jīng)常需要改動的查找表，常進行插入刪除操作。平均查找長度查找是給定一個值key，在查找表中找出關(guān)鍵碼

等于key的元素，如果找到，則查找成功；

否則查找失?。ㄖ麝P(guān)鍵字）。查找效率的標(biāo)準(zhǔn)是指查找過程中和關(guān)鍵碼的平均比較次數(shù)，即平均查找長度ASL，定義為：5-1線性表查找表結(jié)構(gòu)將數(shù)據(jù)元素組織為一個線性表，可以是基于數(shù)組的

順序存儲或以線性鏈表存儲TypedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;首先，關(guān)鍵碼類型和數(shù)據(jù)元素類型約定如下描述：typedefstruct{ElemType*data;intlength;}SeqTable;靜態(tài)查找表的順序存儲結(jié)構(gòu)描述如下：靜態(tài)查找表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其結(jié)點類型描述如下：typedefstructnode{ElemTypedata;structnode*next;}NodeType;順序查找基本思想是從查找表的一端開始順序掃描，將查找表中

元素的關(guān)鍵碼同給定的值比較，如果相等，則查找成功；

當(dāng)掃描結(jié)束時，還未找到關(guān)鍵碼等于給定值的元素，

則查找失敗。順序查找算法結(jié)束時，返回查找成功或失敗的標(biāo)志，

若查找成功，指出找到元素的位置，否則，給出失敗信息。順序查找既適合于順序存儲的靜態(tài)查找表，

又適合于鏈?zhǔn)酱鎯Φ撵o態(tài)查找。typedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;typedefstruct{ElemType*elem;intlength;}SeqTable;順序查找算法intS_Search(SeqTable*t,KeyTypekx){inti;t->elem[0]=kx;for(i=t->length;t->elem[i].key!=kx;i--);returni;}

intseqSearch(SeqTable*t,KeyTypekx,int*p){inti；

for(i=0；i<t->length；i++)if(t->elem[i].key==kx){*p=i；return(1)；}*p=i；

return(0)；}若找到的是第一個元素data[1]，則比較次數(shù)c1=n；若找到的是第i個元素data[i]，則比較次數(shù)ci=n-i+1；在不考慮檢索失敗的情況下，順序檢索的平均檢索長度為

ASL=1*pn+2*pn-1+…+n*p1=(1+2+…+n)/n(pi=1/n)=(n+1)/2T（n)=O(n)優(yōu)點是算法簡單且適應(yīng)面廣，無論查找表中元素是否有序均可使用。

缺點是平均檢索長度較大，特別是當(dāng)n很大時，檢索效率較低。有序表的查找二分查找基本思想是設(shè)查找表中的元素從小到大有序，首先將

給定值key與表中間位置上元素的關(guān)鍵碼比較，如果相

等，則檢索成功；否則，若key小，則在查找表前半部

分中繼續(xù)進行二分法查找，若key大，則在查找表后半

部分中繼續(xù)進行二分法查找。這樣，經(jīng)過一次比較就縮

小一半的查找區(qū)間，如此進行下去，直到檢索成功或檢

索失敗。效率較高的查找方法71418212329313538424649520123456789101112lowmidhighhighmidhighmidlowmidstatusBinSearch(SeqTablet,KeyTypekx){intlow,high,mid;intflag;low=0;high=t->length-1;while(low<=high){mid=(low+high)/2;if(kx<t->elem[mid])high=mid-1;elseif(kx>t->elem[mid])low=mid+1;else{flag=mid;break;}}returnflag;}若表中元素個數(shù)n為：有則最大檢索長度為j;若則最大檢索長度為j+1，所以設(shè)檢索每個元素的概率相同，則平均檢索長度為：T(n)=O(log2n)插值查找類似于查英文字典的方法，在查找一個C開頭的

英文單詞時，從字典中間的一頁開始，這就是

插值查找的基本思想。查找表順序存儲，數(shù)據(jù)元素的關(guān)鍵字在查找表中均勻分布。mid=low+kx-t.data[low].keyt.data[high].key-t.data[low].key(high-low)時間效率為T(n)=O(log2n)斐波納契查找（黃金分割法）斐波納契數(shù)列定義：設(shè)n個數(shù)據(jù)元素的有序表，且n正好是某個斐波納契數(shù)。

可用此查找方法基本思想：對于表長為F(k)-1的有序表，以相對low

偏移量F(k-1)-1取中點，即mid=low+F(k-1)-1,對表進

行分割，則左子表表長為F(k-1)-1，右子表表長為

F(k)-1-F(k-1)-1＝F(k-2)-1。

一直分割到查找成功或查找失敗。分塊查找分塊檢查找（索引順序查找），

是順序查找的一個改進方法。索引表的整個表分成三個子表，對每個子表建立一個索引項，

其中包括兩項內(nèi)容：關(guān)鍵字項(其值為該子表內(nèi)的最大關(guān)鍵字)

和指針項(指示該子表的第一個記錄在表中的位置)。

索引表按關(guān)鍵字有序，表或者有序或者分塊有序。

分塊有序指的是后一個子表中所有記錄的關(guān)鍵字均

大于前一個子表中的最大關(guān)鍵字。設(shè)n個數(shù)據(jù)元素查找表分為m個子表，

分塊檢索的平均檢索長度為5-2哈希表查找哈希表查找法即散列法又稱為雜湊法或關(guān)鍵碼—地址轉(zhuǎn)換法。

用散列法表示的查找表稱為（哈希表）散列表。

散列函數(shù)使每個關(guān)鍵碼都和結(jié)構(gòu)中存儲位置對應(yīng),

這樣的一個對應(yīng)關(guān)系稱為散列(哈希Hash)函數(shù)。關(guān)鍵碼存儲地址h22113251527618412010012345678910例{18,27,1,20,22,6,10,13,41,15,25}h(key)=keymod11哈希表與哈希方法哈希表與哈希方法：選取某個函數(shù)，依該函數(shù)

按關(guān)鍵碼計算元素的存儲位置，并按此存放；

查找時，由同一個函數(shù)對給定值kx計算地址，

將kx與地址單元中元素關(guān)鍵碼進行比較，

確定查找是否成功。若key1≠key2，有h(key1)=h(key2)，這種現(xiàn)象稱為沖突（碰撞）。

key1和key2稱為同義詞。

h(key)的值域所對應(yīng)的地址空間稱為基本區(qū)域。

發(fā)生碰撞時，同義詞可以存放在基本區(qū)域中未被占用

的單元，也可以存放到另外的區(qū)域中負載因子：

其中α>1時沖突不可避免。

(1)構(gòu)造好的哈希函數(shù)哈希方法的兩個問題：(2)制定解決沖突的方案所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度。轉(zhuǎn)制換出來的地址要大致均勻分布，減少空間浪費。常用的哈希函數(shù)1.直接定址法取關(guān)鍵碼的某個線性函數(shù)值為哈希函數(shù)。Hash(key)=a.key+b例：{100,300,500,700,800,900}1003005007008009000123456789Hash(key)=1/100*key2.除余法除余法是取關(guān)鍵碼被某個不大于散列表長度m的

數(shù)P除后所得余數(shù)為散列地址。數(shù)p的選取，一般

可選P為小于基本區(qū)域長度m的最大素數(shù)比較好。22113251527618412010012345678910例{18,27,1,20,22,6,10,13,41,15,25}h(key)=keymod113.乘余取整法Hash(key)=取上式的整數(shù)部分作為哈希地址。a一般取值為：4.中平方法先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。例如，關(guān)鍵碼key=4731(4731)2=22382361h(key)=3825.數(shù)字分析法數(shù)字分析法是關(guān)鍵碼位數(shù)比存儲區(qū)的地址碼的位數(shù)多,這時可以對關(guān)鍵碼的各位進行分析,丟掉分布不均勻的位留下均勻位作為地址。例如:對下列關(guān)鍵碼集合進行關(guān)鍵碼到地址的轉(zhuǎn)換。關(guān)鍵碼是9位的，地址是3位的，需要經(jīng)過分析丟掉6位。

Keyh(key)0003194263260007183097090006294436430007586157150009196979970003103293296.折疊法

折疊法是將關(guān)鍵碼分割成倍數(shù)相等的幾部分，最后一部分的倍數(shù)可以短點，將這幾部分疊加求和，取后幾位為哈希地址。例：key=25346358705移位疊加法：將各部分的最后一位對齊相加；間界疊加法：從一端向另一端沿各部分分界來回折疊，

最后一位對齊相加。分割：25346358705253463587+051308253

364

587

50+1254Hash(key)=308Hash(key)=254例如，關(guān)鍵碼為key=582422241，要求轉(zhuǎn)換為4位的地址碼。

58|2422|241

移位折疊相加移位相加

855814224124222422110642721h1(key)=1064h2(key)=2721折疊法是將關(guān)鍵碼分割成幾部分，其中一部分的長度

等于地址碼的長度，再加上其余部分，舍棄進位作為地址。++補充：處理沖突的方法1.開放定址法開放定址法解決碰撞的方法是在基本區(qū)域內(nèi)形成

一個探查序列，沿探查序列進行檢索，直到找

到該元素或碰到一個未被占用的地址為止。

插入時，直到找到一個空單元；檢索時，

或檢索到關(guān)健碼為key的元素或檢索到達一個空單元。Hi=(Hash(key)+di)MODmi=1,2,…,k(k≤m-1)其中：m為表長，di為增量序列，可有多種取法；di=1,2,3,…,m-1,di=i稱線性探查序列；①線性探查法由線性探查序列,解決碰撞,稱為線性探查法。關(guān)鍵碼集：{47,7,29,11,16,92,22,8,3}哈希表長為11，

Hash(key)=keymod11477012345678910291116922283②二次探測法di=12,-12,22,-22,…,k2,-k2(k≤m/2)稱為二次探查序列；801234567891016{47,7,29,11,16,92,22,8,3}477291192223③雙哈希函數(shù)探測法di=i*ReHash(key),ReHash(key)是另一個散列函數(shù)，

稱雙散列探查序列；Hi=(Hash(key)+i*ReHash(key))MODm例如:K={18,73,10,05,68,99,27,41,51,32,25},Hash(key)=key%13，ReHash(key)=key%11+11873100123456789101112568992741513225２.拉鏈法設(shè)基本區(qū)域長度為m，建立m條鏈表，將所有關(guān)鍵字

為同義詞的記錄存儲在同一條線性鏈表中。如果某

個基本區(qū)域地址中沒有存放查找表元素，則對應(yīng)的

鏈表為空鏈表；

發(fā)生沖突的同組同義詞存放在同一條鏈表中。給定元素的關(guān)鍵碼為key，首先計算出h(key)，

即確定是在第h(key)條鏈表中，

在鏈表中進行插入及檢索操作。K={18,73,10,05,68,99,27,41,51,32,25}，h(key)=key%13{5,8,10,5,3,8,1,2,12,6,12}結(jié)點類型：typedefstructNode{keytypedey;…

structNode*next;

}NodeType;哈希表：typedefNodeType*OpenHash[m];#definem…intCreateHashT(OpenHashl_t;DataType*eptr){intI;intd,finished;for(i=0;i<m;i++)l_t[i]=NULL;for(;eptr->key!=0;eptr++){d=Hash(eptr->key);finished=MovElemToHashT(eptr,l_t,d);if(!finished)break;}returnfinished;}3.建立一個公共溢出區(qū)基本表溢出表5-4動態(tài)查找表二叉排序樹查找表采用二叉排序樹作為存儲結(jié)構(gòu)，既有較高的查找效率，

又具有鏈?zhǔn)酱鎯r元素插入、刪除操作的靈活性。二叉排序樹的定義二叉排序樹(BinarySortTree)或者是一棵空二叉樹；或者具有下列性質(zhì)的二叉樹：(1).若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

(2).若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；((3).它的左右子樹也分別為二叉排序樹。6355425890706310456783一棵二叉排序樹二叉排序樹的查找過程(1)若查找樹為空，查找失敗。(2)查找樹為非空，將給定值kx與查找樹的根結(jié)點關(guān)鍵碼比較；(3)若相等，查找成功，結(jié)束，否則有以下兩種情況：①當(dāng)小于根結(jié)點關(guān)鍵碼，查找將在左子樹上進行，轉(zhuǎn)(1)；②當(dāng)大于根結(jié)點關(guān)鍵碼，查找將在右子樹上進行，轉(zhuǎn)(1)；typedefstructNode{KeyTypekey;structNode*lchild,*rchild;}BinTNode,*BiTree;intBSTSearch(BinTNode*T,BinTNode*C,BinTNode*F,

KeyTypex)

{intflag;C=T;flag=0;while(C)

if(x>C->key){F=C;C=C->rchild;}

elseif(x<C->key){F=C;C=C->lchild;}

else{flag=1;break;}returnflag;}

二叉排序樹查找算法假設(shè)二叉排序樹共有n個結(jié)點，高度是h()，

算法的執(zhí)行時間代價最壞為O(h)。二叉排序樹的插入操作和構(gòu)造一棵二叉排序樹在二叉排序樹中插入新結(jié)點，要保證插入后仍是二叉排序樹。插入新結(jié)點的方法是：(1).如果二叉排序樹為空，則新結(jié)點為根結(jié)點。

(2).如果二叉排序樹為非空，則將新結(jié)點的關(guān)鍵碼與根結(jié)點的關(guān)鍵碼比較，若相等表示該結(jié)點已在二叉排序樹中；若小于根結(jié)點的關(guān)鍵碼，則將新結(jié)點插入到根結(jié)點的左子樹中；否則，插入到根結(jié)點的左子樹中。(3).子樹中的插入過程和樹中的插入過程相同，如此進行下去，直到找到該結(jié)點，或者直到新結(jié)點成為葉子結(jié)點為止。635542589070631045678343二叉排序樹插入一個結(jié)點的算法IntInsertNode(BinTNode*T,KeyTypex){BinTNode*p,*q,*s;intflag=0;p=*t;if(!BSTSearch(T,q,p,x)){s=newBinTNode;s->key=kx;s->lchild=s->rchild=NULL;flag=1;if(!p)T=s;else{if(x>p->key)p->rchild=s;elsep->lchild=s;

}

}returnflag;

}

例如：已知關(guān)鍵碼集合K={18,73,10,05,68,99,27,41,51,32,25}，寫出二叉排序樹的構(gòu)造過程1873100568992741513225StatusCreatBST(BinTNode*T){KeyTypex;T=NULL;cin>>x;while(x!=-1){InsertNode(T,x);cin>>x;}returnsuccess;}二叉排序樹的刪除操作在二叉排序樹中刪除一個指定結(jié)點，刪除結(jié)點后的二叉樹

還是一棵二叉排序樹。設(shè)待刪除結(jié)點為p，其雙親結(jié)點為f，分以下三種情況：(1)p是葉結(jié)點。(2)p是單分支結(jié)點，即只有左子樹pl或右子樹pr,

只需用子樹根結(jié)點代替p結(jié)點。

(3)p有左右子樹時,按中序遍歷保持有序進行調(diào)整。FPfpPL兩種調(diào)整方法：①直接令p結(jié)點的右孩子p1為f相應(yīng)的子樹，將p的

原左子樹pL作為以pr為根的子樹中序遍歷的第一

個結(jié)點的左子樹。②用p結(jié)點的直接后繼pr(或直接前驅(qū))替換p結(jié)點。

再用(2)方法刪去pr。FPfpPLP1P2PJPRS1S2SJSRFPpPLP1P2PJPRS1S2SJSRfPR二叉排序樹刪除算法intDeleteNode(BinTNode*T,KeyTypex)

{BinTNode*p,*q,*s,*f;intflag=0;p=T;if(BSTSearch(T,q,p,x))

if(q){if(q->lchild==NULL&&q->rchild==NULL){if(p){if(p->lchild==q)p->lchild=NULL;elsep->rchild=NULL;}elseT=NULL;free(q);}elseif(q->lchild==NULL){if(p){if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elseT=q->rchild;free(q);}elseif(q->rchild==NULL){if(p){if(p->lchild==q)p->lchild=q->lchild;elsep->rchild=q->lchild;}

elseT=q->lchild;free(q);}else{child=q->rchild;while(child->lchild)child=child->lchild;child->lchild=q->lchild;if(p){if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elseT=q->rchild;free(q);}returnsuccess;}returnfailure;}在二叉排序樹上查找關(guān)鍵字實際上是走了一條從根結(jié)點

到某個結(jié)點的路徑的過程，比較的次數(shù)等于路徑長度加1。

因此，比較的次數(shù)不超過樹的深度。但是具有n個結(jié)點的

二叉樹可以有不同的形態(tài)，因此，對于不同形態(tài)的二叉

排序樹，其平均查找長度也是不同的。

最壞的情況下蛻變?yōu)閱沃洌藭r的平均查找長度為（n+1)/2。平衡二叉樹（AVL樹）平衡二叉樹的定義是一棵空樹或是具有下列性質(zhì)的二叉排序樹：

它的左子樹和右子樹都是平衡二叉樹，且左子樹和

右子樹高度之差的絕對值不超過1.72418530607891426550477241853060789142非平衡二叉樹平衡二叉樹3-30000000002-2011-101平衡因子：結(jié)點左右子樹高度之差的數(shù)字稱為結(jié)點的平衡因子在平衡二叉樹上插入或刪除結(jié)點后，得進行平衡調(diào)整左單旋轉(zhuǎn)（RR型）aBhDhEhcxaBhDhEhcx27510-1BA27510-1BA73-2735100BA27051270-1BA1007341099730BA510274101000-10990-1-1-2acDhEhBhxacDhEhBhx右單旋轉(zhuǎn)（LL型）271001BA271001BA052271000BA050512701BA10005180003011251270BA1000518003010先左后右雙向旋轉(zhuǎn)（LR型）先右后左雙向旋轉(zhuǎn)（RL型）B樹和B＋樹B樹和B＋樹用于外存文件的索引。

一棵m階的B樹，或為空樹，或是滿足下列特性的m叉樹：（1）樹中每個結(jié)點至多有m棵子樹；（2）除根之外的所有分支結(jié)點至少有m/2棵子樹；（3）若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹；（4）有j個子女的非葉結(jié)點中恰好有j-1個關(guān)鍵碼，且按遞增順序排列，結(jié)點中包含的信息為

(p0,k1,p1,k2,…,kj-1,pj)B樹的定義其中ki(i=1,..,j-1)為關(guān)鍵碼，且ki<ki+1(i=1,…,j-2);pi(i=0,…,j-1)為指向子樹根結(jié)點的指針，且pi-1所指子樹中所有結(jié)點的關(guān)鍵碼均小于ki(i=1,…,j-1),pj-1所指子樹中所有結(jié)點的關(guān)鍵碼均大于kj-1,j（m/2<=j<=m-1）為關(guān)鍵碼的個數(shù)。（5）所有葉子結(jié)點都在同一層上，實際上這些結(jié)點不存在。當(dāng)m=2時，m階B樹實際上就是二叉排序樹。所以m階B樹是二叉排序樹的推廣。其查找過程和二叉排序樹類似，它是一個沿指針查找結(jié)點和在結(jié)點的關(guān)鍵碼中進行順序查找交叉進行的過程。實際應(yīng)用中，m和內(nèi)外存交換的單位有關(guān)，一般，m=1024B樹主要用于文件的索引。結(jié)點類型可以如下說明：#definem 3typedefstructBTNode{int keyNum; /*關(guān)鍵字個數(shù)*/structBTNode*parent; /*指向父結(jié)點*/KeyType key[m+1];/*關(guān)鍵字向量*/structBTNode*ptr[m+1];/*子樹指針向量*/Record *recPtr[m+1]/*指向文件中的記錄號*/}NodeType;1、B樹的檢索keykiki+1pi

首先在根結(jié)點的關(guān)鍵碼集合中進行檢索，若key==ki

，則檢索成功；否則，key一定在ki

和ki+1

之間（存在某個i），沿pi繼續(xù)查找，重復(fù)上述過程，直到檢索成功，或pi為空，檢索失敗。B樹的運算性能分析在B樹是進行查找包含兩種基本操作：（1）在B樹中找結(jié)點；（2）在結(jié)點中找關(guān)鍵字。由于B樹通常存儲在磁盤上，因此前一操作是在磁盤上進行的，而后一操作是在內(nèi)存中進行的，即在磁盤上找到指針p所指結(jié)點后，先將結(jié)點中信息讀入內(nèi)存，然后查詢。而在磁盤上進行操作比在內(nèi)存中操作慢得多，因此在磁盤上進行查找的次數(shù)，即待查關(guān)鍵字所在結(jié)點在B樹是的層次數(shù)，是決定B樹查找效率的關(guān)鍵因素?，F(xiàn)在考慮最壞的情況：含n個關(guān)鍵字的m階B樹的最大深度 為logm/2(n+1)/2+12.B樹的插入深度為h的m階B樹，新結(jié)點一般插入到h層，首先檢索到第h層，確定插入結(jié)點位置。（1）若被插入結(jié)點中關(guān)鍵碼個數(shù)小于m-1，則插入。（2）若被插入結(jié)點中關(guān)鍵碼個數(shù)等于m-1，則引起結(jié)點“分裂”?？扇缦聦崿F(xiàn)“分裂”：假設(shè)*p結(jié)點中含有信息為：

m,p0,(k1,p1),…,(km,pm)將*p分裂為*p和*p’兩個結(jié)點，分別含有信息為：*p：m/2－1,p0,(k1,p1),…(km/2－1,pm/2－1)*p’：(m-m/2,pm/2,(km/2+1,pm/2+1),…(km,pm)把關(guān)鍵字km/2和指針*p’一起插入到*p的雙親結(jié)點中。3.B樹的刪除在深度為h的m階B樹中刪除一個關(guān)鍵碼，首先檢索到該關(guān)鍵碼所在的結(jié)點,然后根據(jù)不同情況進行刪除。（1)若結(jié)點在第h層，且關(guān)鍵碼數(shù)目大于m/2-1，則只需從該結(jié)點中刪去該關(guān)鍵碼ki。（2）若結(jié)點在第h層，且關(guān)鍵碼數(shù)目等于m/2-1，該結(jié)點左兄弟（或右兄弟）結(jié)點中的關(guān)鍵碼數(shù)目大于m/2－1，則需調(diào)整被刪除關(guān)鍵碼的結(jié)點，兄弟結(jié)點，以及父結(jié)點中的信息。方法：設(shè)父結(jié)點中的信息為：（p0,k1,p1,k2,p2,…,kxpx),由pi指向被刪除關(guān)鍵碼的結(jié)點，其的信息為：（p0,k

1,p

1,k2,p

2,…,k