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

可以標識一個數據元素。

主關鍵碼：能唯一確定一個數據元素的關鍵碼。次關鍵碼：不能唯一確定一個數據元素的關鍵碼。查找表查找表是一種以集合為邏輯結構、以查找為核心的數據結構。查找表的基本操作：建表、查找、讀表元、插入與刪除靜態查找表：指一經建立就基本保持不變的查找表，

主要操作是檢索。動態查找表：經常需要改動的查找表，常進行插入刪除操作。平均查找長度查找是給定一個值key，在查找表中找出關鍵碼

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

否則查找失敗（主關鍵字）。查找效率的標準是指查找過程中和關鍵碼的平均比較次數，即平均查找長度ASL，定義為：5-1線性表查找表結構將數據元素組織為一個線性表，可以是基于數組的

順序存儲或以線性鏈表存儲TypedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;首先，關鍵碼類型和數據元素類型約定如下描述：typedefstruct{ElemType*data;intlength;}SeqTable;靜態查找表的順序存儲結構描述如下：靜態查找表的鏈式存儲結構及其結點類型描述如下：typedefstructnode{ElemTypedata;structnode*next;}NodeType;順序查找基本思想是從查找表的一端開始順序掃描，將查找表中

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

當掃描結束時，還未找到關鍵碼等于給定值的元素，

則查找失敗。順序查找算法結束時，返回查找成功或失敗的標志，

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

又適合于鏈式存儲的靜態查找。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]，則比較次數c1=n；若找到的是第i個元素data[i]，則比較次數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)優點是算法簡單且適應面廣，無論查找表中元素是否有序均可使用。

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

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

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

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

部分中繼續進行二分法查找。這樣，經過一次比較就縮

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

索失敗。效率較高的查找方法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;}若表中元素個數n為：有則最大檢索長度為j;若則最大檢索長度為j+1，所以設檢索每個元素的概率相同，則平均檢索長度為：T(n)=O(log2n)插值查找類似于查英文字典的方法，在查找一個C開頭的

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

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

可用此查找方法基本思想：對于表長為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個數據元素查找表分為m個子表，

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

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

散列函數使每個關鍵碼都和結構中存儲位置對應,

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

按關鍵碼計算元素的存儲位置，并按此存放；

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

將kx與地址單元中元素關鍵碼進行比較，

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

key1和key2稱為同義詞。

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

發生碰撞時，同義詞可以存放在基本區域中未被占用

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

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

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

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

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

Keyh(key)0003194263260007183097090006294436430007586157150009196979970003103293296.折疊法

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

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

364

587

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

58|2422|241

移位折疊相加移位相加

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

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

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

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

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

或檢索到關健碼為key的元素或檢索到達一個空單元。Hi=(Hash(key)+di)MODmi=1,2,…,k(k≤m-1)其中：m為表長，di為增量序列，可有多種取法；di=1,2,3,…,m-1,di=i稱線性探查序列；①線性探查法由線性探查序列,解決碰撞,稱為線性探查法。關鍵碼集：{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③雙哈希函數探測法di=i*ReHash(key),ReHash(key)是另一個散列函數，

稱雙散列探查序列；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２.拉鏈法設基本區域長度為m，建立m條鏈表，將所有關鍵字

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

個基本區域地址中沒有存放查找表元素，則對應的

鏈表為空鏈表；

發生沖突的同組同義詞存放在同一條鏈表中。給定元素的關鍵碼為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}結點類型：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.建立一個公共溢出區基本表溢出表5-4動態查找表二叉排序樹查找表采用二叉排序樹作為存儲結構，既有較高的查找效率，

又具有鏈式存儲時元素插入、刪除操作的靈活性。二叉排序樹的定義二叉排序樹(BinarySortTree)或者是一棵空二叉樹；或者具有下列性質的二叉樹：(1).若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

(2).若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；((3).它的左右子樹也分別為二叉排序樹。6355425890706310456783一棵二叉排序樹二叉排序樹的查找過程(1)若查找樹為空，查找失敗。(2)查找樹為非空，將給定值kx與查找樹的根結點關鍵碼比較；(3)若相等，查找成功，結束，否則有以下兩種情況：①當小于根結點關鍵碼，查找將在左子樹上進行，轉(1)；②當大于根結點關鍵碼，查找將在右子樹上進行，轉(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;}

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

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

(2).如果二叉排序樹為非空，則將新結點的關鍵碼與根結點的關鍵碼比較，若相等表示該結點已在二叉排序樹中；若小于根結點的關鍵碼，則將新結點插入到根結點的左子樹中；否則，插入到根結點的左子樹中。(3).子樹中的插入過程和樹中的插入過程相同，如此進行下去，直到找到該結點，或者直到新結點成為葉子結點為止。635542589070631045678343二叉排序樹插入一個結點的算法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;

}

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

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

只需用子樹根結點代替p結點。

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

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

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

再用(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;}在二叉排序樹上查找關鍵字實際上是走了一條從根結點

到某個結點的路徑的過程，比較的次數等于路徑長度加1。

因此，比較的次數不超過樹的深度。但是具有n個結點的

二叉樹可以有不同的形態，因此，對于不同形態的二叉

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

最壞的情況下蛻變為單支樹，此時的平均查找長度為（n+1)/2。平衡二叉樹（AVL樹）平衡二叉樹的定義是一棵空樹或是具有下列性質的二叉排序樹：

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

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

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

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

首先在根結點的關鍵碼集合中進行檢索，若key==ki

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

和ki+1

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

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

1,p

1,k2,p

2,…,k