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

第九章查找9.1基本概念9.2靜態(tài)查找表9.3動(dòng)態(tài)查找表9.4哈希表

基本概念查找表：是由同一類(lèi)型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。靜態(tài)查找表：對(duì)查找表只作查詢(xún)或檢索操作動(dòng)態(tài)查找表：在對(duì)查找表進(jìn)行查找過(guò)程中加入插入和刪除操作查找：在一個(gè)含有眾多的數(shù)據(jù)元素(或記錄)的查找表中找出某個(gè)“特定的”數(shù)據(jù)元素(或記錄).關(guān)鍵字：是數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值,用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(或記錄).主關(guān)鍵字：某關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)記錄。次關(guān)鍵字：用以識(shí)別若干記錄的關(guān)鍵字影響查找效率的因素1.數(shù)據(jù)結(jié)構(gòu)(查找表的存儲(chǔ)結(jié)構(gòu))2.查找算法3.記錄的存放形式(有序,無(wú)序)典型的關(guān)鍵字類(lèi)型說(shuō)明和數(shù)據(jù)元素類(lèi)型說(shuō)明：

TypedeffloatKeyType;//實(shí)型

Typedef

int

KeyType;//整型

Typedefchar*KeyType;//字符串型數(shù)據(jù)元素類(lèi)型定義為：

typedef

struct{

KeyTypekey;//關(guān)鍵字域

……//其它域}ElemType;對(duì)兩個(gè)關(guān)鍵字的比較約定為如下的宏定義//對(duì)數(shù)據(jù)類(lèi)型關(guān)鍵字#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))…//對(duì)字符串型關(guān)鍵字#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)

9。2靜態(tài)查找表順序表的查找有序表的查找索引順序表的查找抽象類(lèi)型靜態(tài)查找表定義為：ADTStaticSearchTable{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類(lèi)型相同，可唯一數(shù)據(jù)元素的關(guān)鍵字?jǐn)?shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合基本操作P：Create(&ST,n);操作結(jié)果：構(gòu)造一個(gè)含n各數(shù)據(jù)元素的靜態(tài)查找表STDestroy(&ST);初始條件：靜態(tài)查找表ST存在操作結(jié)果：銷(xiāo)毀表STSearch(ST,key);初始條件：靜態(tài)查找表ST存在，key為和關(guān)鍵字類(lèi)型相同的給定值。操作結(jié)果：若ST中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”Traverse(ST,Visit());初始條件：靜態(tài)查找表ST存在，Visit識(shí)對(duì)元素操作的應(yīng)用函數(shù)操作結(jié)果：按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)visit()一次僅一次。一旦visit()失敗，則操作失敗。}ADTStaticSearchTable以順序表或線性鏈表表示靜態(tài)查找表。靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)：Typedef

struct{

ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分

//配，0號(hào)單元留空

intlength;//表長(zhǎng)度}SSTable;順序表的查找順序查找的查找過(guò)程從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個(gè)記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒(méi)有所查記錄，查找不成功。順序查找的缺點(diǎn)：平均查找長(zhǎng)度較大優(yōu)點(diǎn)：算法簡(jiǎn)單且適應(yīng)面廣

順序查找順序查找算法實(shí)現(xiàn)int

Search_Seq(SSTable

ST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0

ST.elem[0].key=key;//”哨兵“for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//從后往前找returni;//找不到時(shí)，i為0}//Search_Seq順序查找操作的性能分析平均查找長(zhǎng)度(AverageSearchLength)

為確定記錄在查找表中的位置,需要和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱(chēng)為查找算法在查找成功時(shí)的平均查找長(zhǎng)度.

對(duì)于n個(gè)記錄的表,查找成功時(shí)的平均查找長(zhǎng)度為ASL=∑i=1n

pici

pi:為查找表中第i個(gè)記錄的概率

ci:為查找到表中其關(guān)鍵字與給定值相等的第i個(gè)記錄時(shí),和給定值已經(jīng)進(jìn)行過(guò)比較的關(guān)鍵字個(gè)數(shù).順序查找平均查找長(zhǎng)度在順序查找過(guò)程中,ci取決于所查記錄在表中的位置.一般情況下ci=n-i+1假設(shè)每個(gè)記錄的查找概率相等即pi=1/n則在等概率下順序查找平均查找長(zhǎng)度為:ASLss=∑i=1n

pici

=1/n∑i=1n(n-i+1)ASLss

=(n+1)/2以有序表作為靜態(tài)查找表時(shí)。

折半查找的查找過(guò)程：先確定待查記錄所在的范圍(區(qū)間),然后逐步縮小范圍直到找到或找不到該記錄為止，一般折半查找都是以處于區(qū)間中間位置記錄的關(guān)鍵字和給定值比較，若相等，則查找成功若不等，則縮小范圍，直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或者查找區(qū)間的大小小于0時(shí)（表明查找不成功）為止。

有序表的查找折半查找算法

int

Search_Bin(SSTable

ST,KeyTypekey){//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0low=1;high=ST.length;//置區(qū)間初值while(low<=high){mid=(low+high)/2;if(EQ(key.ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key.ST.elem[mid].key)high=mid-1;//繼續(xù)在前半?yún)^(qū)間查找

elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間查找}

return0;//順序表中不存在待查元素}Search_Bin例：已知如下11個(gè)數(shù)據(jù)元素的有序表(關(guān)鍵字既為數(shù)據(jù)元素的值)：(05,13,19,21,37,56,64,75,80,88,92）現(xiàn)要查找關(guān)鍵字為21的數(shù)據(jù)元素,mid=(high+low)/2上界取整0513192137566475808892lowmidhighhighmidLowmid7581110924136圖9.2折半查找操作過(guò)程的判定樹(shù)折半查找操作的性能分析折半查找操作的過(guò)程可以用二叉樹(shù)表示折半查找操作的性能分析假設(shè)有序表的長(zhǎng)度n=2h-1,即h=log2(n+1),則描述折半查找的判定樹(shù)是深度為h的滿二叉樹(shù),樹(shù)中層次為1的結(jié)點(diǎn)有一個(gè),層次為2的結(jié)點(diǎn)有兩個(gè),…,層次為h的結(jié)點(diǎn)有2h-1.再假設(shè)pi=

1/n.ASLbs=∑i=1n

pici=1/n∑j=1h

j.2j-1=(n+1)/n.log2(n+1)-1ASLbs=log2(n+1)-1以索引順序表表示靜態(tài)查找表。分塊查找又稱(chēng)索引順序查找，是順序查找的一種改進(jìn)方法。此查找表中，除表本身外，尚需建立一個(gè)“索引表”分塊查找過(guò)程：先確定待查記錄所在的塊(子表)，然后在塊中順序查找例：下圖為一個(gè)表及其索引表索引順序表的查找224886159索引表最大關(guān)鍵字起始地址22128203324483860748653子表(R1,R2,..,R4)(R5,R6,…,R8)(R9,R10….,R12)分塊查找過(guò)程：先確定待查記錄所在的塊(子表)，然后在塊中順序查找

9.2動(dòng)態(tài)查找表二叉排序樹(shù)和平衡二叉樹(shù)B-樹(shù)和B+樹(shù)動(dòng)態(tài)查找表特點(diǎn)：表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成，既對(duì)于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。ADTDynamicSearchTable{

數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類(lèi)型相同，可唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字

數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合基本操作P：

InitDSTable(&DT);

操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT

DestroyDSTable(&DT);

初始條件：動(dòng)態(tài)查找表DT存在操作結(jié)果：銷(xiāo)毀動(dòng)態(tài)查找表DT

SearchDSTable(DT,key);

初始條件：動(dòng)態(tài)查找表DT存在，key為和關(guān)鍵字類(lèi)型相同的給定值操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”

InsertDSTable(&DT,e);初始條件：動(dòng)態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素操作結(jié)果：若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為0DeleteDSTable(&DT,key);

初始條件：動(dòng)態(tài)查找表DT存在，key為和關(guān)鍵字類(lèi)型相同的給定值操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之TraverseDSTable(DT,Visit());初始條件：動(dòng)態(tài)查找表DT存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)操作結(jié)果：按某種次序?qū)T的每個(gè)接點(diǎn)調(diào)用函數(shù)Visit()

一次且至多一次。一旦Visit()失敗，則操作失敗}ADTDynamicSearchTable二叉排序樹(shù)：或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：⑴若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；⑵若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值⑶它的左，右子樹(shù)也分別為二叉排序樹(shù)二叉排序樹(shù)及其平衡二叉樹(shù)45531006190782437312二叉排序樹(shù)圖二叉排序樹(shù)查找過(guò)程二叉排序樹(shù)查找過(guò)程：當(dāng)二叉排序樹(shù)不空時(shí)，首先將給定值和根結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功，否則將依據(jù)給定值和根接點(diǎn)的關(guān)鍵字之間的大小關(guān)系，分別在左子樹(shù)或右子樹(shù)上繼續(xù)查找例：查找關(guān)鍵字61的記錄如圖4553100619078243731261>4561>5361<10061=61查找成功查找右子樹(shù)繼續(xù)查找右子樹(shù)查找左子樹(shù)BiTree

SearchBST(BiTree

T,KeyTypekey){//在根指針T所指二叉排序樹(shù)種遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，則返回指向該數(shù)組元素結(jié)點(diǎn)地指針，否則返回空指針

if(!T)||EQ(key,T->data.key))return(T);//查找結(jié)束elseifLT(key,T->data.key)return(SearchBST(T->lchild.key));//在左子樹(shù)中繼續(xù)查找elsereturn(SearchBST(T->rchild,key));//在右子樹(shù)中查找}//SearchBST二叉排序樹(shù)查找算法插入過(guò)程：二叉排序樹(shù)的結(jié)構(gòu)通常不時(shí)一次生成的，而是在查找過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)二叉排序樹(shù)的插入例：查找的關(guān)鍵字序列為{45,24,53,45,12,24,90}則生成的二叉排序樹(shù)如圖：Φ空樹(shù)45插入4524插入2453插入5312插入1290插入90StatusSearchBST(BiTree

T,KeyType

key,BiTree

f,BiTree&p)}//在根指針T所指二叉排序樹(shù)中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE，否則指針p指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)并返回FALSE，指針f指向T的雙親，其初始調(diào)用值為NULLif(!T){p=f;returnFALSE;}//查找不成功elseifEQ(key,T->data.key){p=T;returnTRUE;}//查找成功elseifLT(key,T->data.key)

searchBST(T->lchild,key,T,p);//在左子樹(shù)中查找elseSearchBST(T->rchild,key,T,p);//在右子樹(shù)中查}//SearchBST二叉排序樹(shù)的插入算法StatusInsertBST(BiTree&T,ElemTypee){//當(dāng)二叉排序樹(shù)T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時(shí)，插入e并返回TRUE，否則返回FALSEif(!SearchBST(T,e.key,NULL,p){//查找不成功

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn)elseifLT(e.key,p->data.key)p->lchild=s;//被插結(jié)點(diǎn)*s為左孩子

elsep->rchild=s;//被插結(jié)點(diǎn)*s為右孩子

returnTRUE;}elsereturnFALSE;//樹(shù)中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入}//InsertBST二叉排序樹(shù)的刪除設(shè)在二叉排序樹(shù)上被刪結(jié)點(diǎn)為*p(指向結(jié)點(diǎn)的指針p),其雙親結(jié)點(diǎn)為*f（結(jié)點(diǎn)指針為f)，且不失一般性，可設(shè)*p是*f的左孩子刪除分三種情況：⑴若*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)，既PL和PR均為空樹(shù)。由于刪去葉子結(jié)點(diǎn)不破壞整棵樹(shù)的結(jié)構(gòu)，則只需修改其雙親結(jié)點(diǎn)的指針即可⑵若*p結(jié)點(diǎn)只有左子樹(shù)PL或者只有右子樹(shù)PR，此時(shí)只有令PL或

PR直接成為其雙親結(jié)點(diǎn)*f的左子樹(shù)即可。⑶若*p結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)均不空時(shí)，分兩種情況：方法一:是令*p的左子樹(shù)為*f的左子樹(shù)，而*p的右子樹(shù)為*s(p左孩子的最右孩子)的右子樹(shù)。方法二:是令*p的直接前驅(qū)s(p左孩子的最右孩子)替代*p,同時(shí)將s的左子樹(shù)作為其雙親的右子樹(shù).或者是令*p的直接后繼s(p右孩子的最左孩子)替代*p,同時(shí)將s的右子樹(shù)作為其雙親的左子樹(shù).FPfp以*f為根的子樹(shù)P1子樹(shù)P1PR子樹(shù)PR在二叉排序樹(shù)上刪除一個(gè)結(jié)點(diǎn)的算法StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序樹(shù)T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回TRUE；否則返回FALSEIf(!T)returnFALSE;//不存在關(guān)鍵字等于key的數(shù)據(jù)元素Else{ifEQ(key,T->data.key)Delete(T);//找到關(guān)鍵字等于key的數(shù)據(jù)元素elseifLT(key,T->data.key)

DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);returnTRUE;}}//DeleteBST如前述三種情況綜合所得刪除操作算法：VoidDelete(BiTree&P){//從二叉排序樹(shù)中刪除結(jié)點(diǎn)p,并重接它得左或右子樹(shù)

if(!p->rchild){//右子樹(shù)空則只需重接它的左子樹(shù)

q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只需重接它的右子樹(shù)

q=p;p=p->rchild;free(q);}從二叉排序樹(shù)中刪除結(jié)點(diǎn)pelse{//左右子樹(shù)均不空

q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}//轉(zhuǎn)左，然后向右到盡頭

p->data=s->data;//s指向被刪結(jié)點(diǎn)的“前驅(qū)”

if(q!=p)q->rchild=s->lchild;//重接*q的右子樹(shù)elseq->lchild=s->lchild;//重接*q的左子樹(shù)Deletes;}}//Delete二叉排序樹(shù)的查找分析在二叉排序樹(shù)上查找其關(guān)鍵字等于給定值的結(jié)點(diǎn)的過(guò)程,恰是走了一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑的過(guò)程,和給定值比較的關(guān)鍵字個(gè)數(shù)不超過(guò)樹(shù)的深度.因此,含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形狀有關(guān).最差情況:單枝樹(shù)ASL=(n+1)/2最好情況:平衡二叉樹(shù)ASL=log2(n+1)-1平衡二叉樹(shù):或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1.平衡因子（BF)：該結(jié)點(diǎn)的左子樹(shù)的深度減去它的右子樹(shù)的深度.平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是-1,0,和1.在構(gòu)造二叉排序樹(shù)的過(guò)程中,需要進(jìn)行”平衡化”處理,成為二叉平衡樹(shù)平衡二叉樹(shù)

-1-101001平衡二叉樹(shù)其中-1,0,1為平衡因子設(shè):a為二叉排序樹(shù)上插入結(jié)點(diǎn)而失去平衡的最小子樹(shù)的根結(jié)點(diǎn)的指針⑴單向右旋平衡處理(LL型平衡旋轉(zhuǎn))⑵單向左旋平衡處理(RR型平衡旋轉(zhuǎn))

⑶雙向旋轉(zhuǎn)(先左后右)平衡處理(LR型平衡旋轉(zhuǎn))⑷雙向旋轉(zhuǎn)(先右后左)平衡處理(RL型平衡旋轉(zhuǎn))插入結(jié)點(diǎn)失去平衡后進(jìn)行調(diào)整規(guī)律構(gòu)成的二叉排序樹(shù)為平衡樹(shù)方法：例：設(shè)關(guān)鍵字序列為(13,24,37,90,53),構(gòu)成平衡樹(shù)過(guò)程如下Φ132413133724(a)空樹(shù)(b)插入130(c)插入24-10(d)插入37-2-10371324000(e)向左逆時(shí)針右旋轉(zhuǎn)平衡1353903724-20-210(f)相繼插入90和531390533724(g)第一次向右順時(shí)針旋轉(zhuǎn)3713905324-10000(h)第二次向左逆時(shí)針旋轉(zhuǎn)平衡之B-樹(shù)的結(jié)構(gòu):一棵m階的B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M足下列特性的m叉樹(shù)：⑴樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)⑶除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)⑷所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,…,Kn,An)其中:Ki為關(guān)鍵字，且

Ki<Ki+1,Ai為指向子樹(shù)根結(jié)點(diǎn)的指針，n為關(guān)鍵字的個(gè)⑸所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息B-樹(shù)和B+樹(shù)

一棵4階的B-樹(shù)圖135199139127111118243783475364FFFFFFFFFFFFB-樹(shù)查找過(guò)程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過(guò)程B-樹(shù)結(jié)點(diǎn)類(lèi)型說(shuō)明：#definem3//B樹(shù)的階Typedef

struct

BTNode{

int

keynum;//結(jié)點(diǎn)大小

struct

BTNode*parent;//指向雙親結(jié)點(diǎn)

KeyTypeKey[m+1];//關(guān)鍵字向量，0號(hào)單元未用

struct

BTNode*ptr[m+1];//子樹(shù)指針向量

Record*recptr[m+1];//記錄指針向量}BTNode,*Btree;//B樹(shù)結(jié)點(diǎn)和B樹(shù)類(lèi)型Typedef

struct{

BTNode*pt;//指向找到的結(jié)點(diǎn)

inti;//1…m，在結(jié)點(diǎn)中的關(guān)鍵字序號(hào)

inttag;//1查找成功，0查找失敗}Result;//B樹(shù)的查找結(jié)果類(lèi)型B-樹(shù)查找算法實(shí)現(xiàn)ResultSearchBTree(Btree

T,KeyTypeK){//在n階B樹(shù)T上查找關(guān)鍵字K，返回結(jié)果(pt,i,tag).若查找成功，則tag=1.指針pt所指向結(jié)點(diǎn)第i個(gè)關(guān)鍵字等于K，否則tag=0，等于K的關(guān)鍵字應(yīng)插入在指針pt所指向結(jié)點(diǎn)中第i個(gè)和i+1個(gè)關(guān)鍵字之間P=T;q=NULL;found=FALSE;i=0;While(p&&!found){n=p->keynum;i=Search(p,K);//在p->key[1..keynum]中查找if(i>0&&p->key[i]==K)found=TRUE;//找到待查關(guān)鍵字else{q=p;p=p->ptr[i];}}if(found)return(p,i,1);//查找成功elsereturn(q,i,0);//查找不成功，返回K的插入位置信息}//SearchBTreeB-樹(shù)的查找分析在B-樹(shù)上進(jìn)行查找包含兩種操作:1.在B-樹(shù)中找結(jié)點(diǎn)(在磁盤(pán)上進(jìn)行)2.在結(jié)點(diǎn)中找關(guān)鍵字(在內(nèi)存中進(jìn)行)顯然.在磁盤(pán)上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找耗費(fèi)時(shí)間多的多.在磁盤(pán)上進(jìn)行查找次數(shù),即待查關(guān)鍵字所在結(jié)點(diǎn)在B-樹(shù)上的層次數(shù),是決定B-樹(shù)查找效率的主要因素.考慮最壞情況,即待查結(jié)點(diǎn)在B-樹(shù)中的最大層次數(shù),也就是,求含N個(gè)關(guān)鍵字的m階B-樹(shù)的最大深度是多少?

先討論深度為L(zhǎng)+1層的m階B-樹(shù)所具有的最少結(jié)點(diǎn)數(shù)

根據(jù)B-樹(shù)的定義:

第一層至少有1個(gè)結(jié)點(diǎn);第二層至少有2個(gè)結(jié)點(diǎn);第三層至少有2(m/2上取整)個(gè)結(jié)點(diǎn);........第L+1層至少有2(m/2上取整)L-1結(jié)點(diǎn)因?yàn)楹琋個(gè)關(guān)鍵字的m階B-樹(shù)中葉結(jié)點(diǎn)為N+1個(gè),因此有N+1>=2(m/2上取整)L-1

反之L<=log[m/2]((N+1)/2)+1也就是說(shuō),含N個(gè)關(guān)鍵字的m階B-樹(shù)上進(jìn)行查找時(shí),所涉及的結(jié)點(diǎn)數(shù)不超過(guò)log[m/2]((N+1)/2)+1B-樹(shù)的插入B-樹(shù)的生成是從空樹(shù)起，逐個(gè)插入關(guān)鍵字而得。由于B-樹(shù)結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)必須>=m/2-1，所以，每次插入一個(gè)關(guān)鍵字不是在樹(shù)中填加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中填加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m-1，則插入完成，否則要產(chǎn)生結(jié)點(diǎn)的“分裂”.如圖：B-樹(shù)的插入

在3階B-樹(shù)中進(jìn)行插入示例4524539037100617050312btabcdefgh一棵B-樹(shù)4524539030

37100617050312btabcdefgh插入30之后45245390263037100617050312btabcdefgh4524

30539037100617050312btabcdefgh26d插入26之后4524305390

371006170

8550312btabcd’efgh26d4524305370903710050312btabcd’efgh266185g’d45

702430btab53901003726312615085插如85之后e’cdd’efgg’hStatusInsertBTree(Btree&T,KeyTypeK,Btreeq,inti){//在m階B樹(shù)T上結(jié)點(diǎn)*q的key[i]與key[i+1]之間插入關(guān)鍵字k若引起結(jié)點(diǎn)過(guò)大，則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整，使T仍是m階B樹(shù)X=K;ap=NULL;finished=FALSE;While(q&&!finished){

Insert(q,i,x,ap);//將x和ap分別插入q->key[i]和q->ptr[i]之間if(q->keynum<m)finished=TRUE;//插入完成

在B-樹(shù)上插入關(guān)鍵字算法：else{//否則分裂結(jié)點(diǎn)qs=m/2+1;

splist(q,ap);x=q->key[s];//將q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新結(jié)點(diǎn)*apq=q->parent;if(q)i=Search(q,x);//在雙親結(jié)點(diǎn)*q中查找x的插入位置}//else}//whileif(!finished)//如果T是空樹(shù)或者根結(jié)點(diǎn)分裂為結(jié)點(diǎn)*q和*ap

newRoot(T,q,x,ap);//生成含(T,x,ap)的新的根結(jié)點(diǎn)*T,原T和ap為子樹(shù)的指針}//InsertBTreeB-樹(shù)的刪除刪除一個(gè)關(guān)鍵字：首先找到該關(guān)鍵字所在的結(jié)點(diǎn)，并從中刪除之，若該結(jié)點(diǎn)為最下層的非終端結(jié)點(diǎn)，且其中的關(guān)鍵字?jǐn)?shù)目不少于m/2，則刪除完成，否則要進(jìn)行“合并”結(jié)點(diǎn)的操作。假若所刪關(guān)鍵字為非終端結(jié)點(diǎn)中的Ki，則可以指針?biāo)缸訕?shù)中的最小關(guān)鍵字Y替代Ki，

然后在相應(yīng)的結(jié)點(diǎn)中刪去Y.所以,我們只要討論刪除最下層的非終端結(jié)點(diǎn)中的關(guān)鍵字的情形.B-樹(shù)的刪除

(1)被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于m/2上界取整-1,則只需從該結(jié)點(diǎn)中刪除關(guān)鍵字Ki和相應(yīng)的指針Ai該結(jié)點(diǎn),樹(shù)的其它部分不變.例：刪去下圖中關(guān)鍵字124524539037100617050312btabcdefgh例：刪去下圖中關(guān)鍵字12后的圖312bt45245390371006170503(2)被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目等于m/2上界取整-1，而與該結(jié)點(diǎn)相鄰的右兄弟(或左兄弟)結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于m/2上界取整-1，則需將其兄弟結(jié)點(diǎn)中的最小(或最大)的關(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于(或大于)且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在的結(jié)點(diǎn)中例：刪去下圖中關(guān)鍵字50312bt45245390371006170503例：下圖中刪去50后5390617050ef452437100361907053

bt刪去50,61上移至*e結(jié)點(diǎn)中，53移至*f⑶被刪關(guān)鍵字所在結(jié)點(diǎn)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均等于m/2上界取整-1，假設(shè)該結(jié)點(diǎn)有右兄弟，且其右兄弟結(jié)點(diǎn)地址由雙親結(jié)點(diǎn)中的指針Ai所指，則在刪去關(guān)鍵字之后，它所有結(jié)點(diǎn)中剩余的關(guān)鍵字和指針，加上雙親結(jié)點(diǎn)中的關(guān)鍵字Ki一起，合并到Ai所指兄弟結(jié)點(diǎn)中(若沒(méi)有右兄弟，則合并至左兄弟結(jié)點(diǎn)中)：例：在下圖中刪去535390617050ef452437100361907053

bt4524371003906170

bt從該B-樹(shù)中刪去53，刪去53結(jié)點(diǎn)，并將53結(jié)點(diǎn)的的剩余信息(指針“空”)和雙親結(jié)點(diǎn)*e結(jié)點(diǎn)中的61一起合并到右兄弟結(jié)點(diǎn)*g中。刪除后變化如上圖。ehgabcd4524371003906170

bt再?gòu)脑揃-樹(shù)中刪去37。ehgabcd如果因此使雙親結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目小于m/2上界取整-1，則依次類(lèi)推。如在上圖刪去53結(jié)點(diǎn)后的圖基礎(chǔ)上，刪去關(guān)鍵字37之后，雙親b結(jié)點(diǎn)中剩余信息(指針c)應(yīng)和其雙親*a結(jié)點(diǎn)中關(guān)鍵字45一起合并至右兄弟結(jié)點(diǎn)*e中，刪除后如下圖：45901006170324bteghB+樹(shù)是B-樹(shù)的一個(gè)變型.一個(gè)m階B-樹(shù)和B+樹(shù)的區(qū)別:1.有n棵子樹(shù)的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字.2.所有葉結(jié)點(diǎn)中包含了全部關(guān)鍵字信息,及指向這些關(guān)鍵字的記錄.3.所有非終端結(jié)點(diǎn)可以看成是索引部分,結(jié)點(diǎn)中僅含有子樹(shù)中最大(或者最小)關(guān)鍵字見(jiàn)p246圖9.18

9.3哈希表什么是哈希表哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找及其分析哈希函數(shù)：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f,使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)，稱(chēng)這個(gè)對(duì)應(yīng)關(guān)系f為hash函數(shù)哈希表：通過(guò)hash函數(shù)計(jì)算，將集合中元素存儲(chǔ)在一個(gè)數(shù)組中，這個(gè)數(shù)組為hash表哈希沖突：對(duì)不同的關(guān)鍵字可能得到同一哈希地址，即key1≠key2,而f(key1)=f(key2),這種現(xiàn)象叫沖突

⑴直接定址法取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。即：H(key)=key或H(key)=a.key+b其中a和b為常數(shù)(這種哈希函數(shù)叫做自身函數(shù))⑵數(shù)字分析法將關(guān)鍵字中的某幾位進(jìn)行運(yùn)算后作為hash地址⑶折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進(jìn)位)作為哈希地址哈希函數(shù)的構(gòu)造方法⑸除留余數(shù)法取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址，既H(key)=keyMODpp<=m⑹隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key)=random(key),其中random為隨機(jī)函數(shù)，通常，當(dāng)關(guān)鍵字長(zhǎng)度不等時(shí)采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。處理沖突的方法⑴開(kāi)放定址法公式：Hi=(H(key)+di)MODmi=1,2,…,k(k<=m-1)其中：H(key)為哈希函數(shù)；m為哈希表表長(zhǎng)；di為增量序列，可有下列三種取法：①di=1,2,3,…,m-1,稱(chēng)線性探測(cè)再散列；②di=12,-12,22,-22,32,…,+k2,(k<=m/2)稱(chēng)二次探測(cè)再散列③di=偽隨機(jī)數(shù)序列，稱(chēng)偽隨機(jī)探測(cè)再散列例：在長(zhǎng)度為11的哈希表中已填有關(guān)鍵字分別為17,60,29的記錄(hash函數(shù)H(key)=keyMOD11)，現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為38，由哈希函數(shù)H(38)=38MOD11得到哈希地址為5，產(chǎn)生沖突.下面分別用三種取法解決沖突601729012345678910設(shè)38插入前表如下所示60172938012345678910一：用線性探測(cè)法解決沖突MOD11=5沖突(5+1)MOD11=6沖突(5+2)MOD11=7沖突(5+3)MOD11=8插入38601729012345678910二：用二次探測(cè)法解決沖突MOD11=5沖突(5+12)MOD11=6沖突(5+(-12))MOD11=4插入38601729012345678910三：偽隨機(jī)探測(cè)法解決沖突取偽隨機(jī)數(shù)列為9,則38MOD11=5沖突(5+9)MOD11=3插入⑵再哈希法Hi=RHi(key)i=1,2,…,kRhi均是不同的哈希函數(shù)，既在同義詞產(chǎn)生地址沖突時(shí)計(jì)算機(jī)另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。⑶鏈地址法思想：將具有相同hash函數(shù)值(hash地址)的元素放在同一個(gè)鏈表中例：已知一組關(guān)鍵字為(19,14,23,01,68,11,10,55),則按哈希函數(shù)H(key)=keyMOD13和鏈地址