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

第9章查找主要內(nèi)容：靜態(tài)查找表----順序、折半、分塊動態(tài)查找表----各種樹表哈希表討論各種查找方法的效率相關(guān)術(shù)語及概念查找表（SearchTable）:由同一類型的數(shù)據(jù)元素構(gòu)成的集合。關(guān)鍵字（key）：用來標(biāo)識一個數(shù)據(jù)元素的數(shù)據(jù)項。查找（Searching）：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素，若表中存在這樣的一個記錄，則查找成功，否則查找不成功。靜態(tài)查找表（StaticSearchTable）:查找過程中查找表本身不發(fā)生變化的查找表。（無插入、刪除操作）動態(tài)查找表（DynamicSearchTable）:查找過程中查找表本身發(fā)生變化(插入或刪除元素)的查找表。查找方法評價

查找速度占用存儲空間多少算法本身復(fù)雜程度平均查找長度ASL(AverageSearchLength):為確定記錄在表中的位置，需和給定值進行比較的關(guān)鍵字的個數(shù)的期望值對含有n個記錄的查找表，查找成功時的平均查找長度為：

nASL=∑

pici

i=1n其中：pi為查找表中第i個記錄的概率，且∑pi=1

i=1

ci為找到表中第i個元素所需比較次數(shù)9.1靜態(tài)查找表ADTStaticSearchTable{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均具有相同類型，各元素具有可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。基本操作P：

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());}ADTStaticSearchTabletypedef

struct{KeyTypekey; ….}ElemType;

typedef

struct{ElemType *elem;int length;}SSTable;一、順序表的查找int

Search_Seq(SSTableST,keyTypekey){ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}查找過程：從表的一端開始逐個進行記錄的關(guān)鍵字和給定值的比較。i例01234567891011

251392117966415288822找6464監(jiān)視哨iiii查找成功返回7

查找3535iiiiiiiiiiii查找不成功返回0性能分析：

n平均查找長度ASL=∑

pici

i=1順序查找時比較次數(shù)取決于所查找記錄在表中的位置。一般情況：Ci=n–i+1在等概率情況下：nASL=∑

(n–i+1）/n=(n+1)/2

i=1即：成功查找的平均比較次數(shù)約為順序表長度的一半。若key在表中不存在，則需進行n+1次比較設(shè)查找成功概率為p，則查找失敗的概率為q=1-p則：ASL=p*(n+1)/2+q*(n+1)=p(n+1)/2+(1-p)(n+1)=(n+1)(1-p/2)設(shè)查找成功和失敗的概率各為50%，即p=q=1/2則：ASL=?(n+1)順序查找：算法簡單，對表中元素排列沒有要求，實際應(yīng)用較多，特別是記錄少時較有效。檢索時間較長二、有序表查找條件：順序存儲并且有序舉例：1234567891011513192137566475808892找21lowhighmid1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidmid=(1+11)/2=6high=mid-1=5mid=(1+5)/2=3low=(mid+1)=4mid=(4+5)/2=4成功：返回4lowhighmid1234567891011513192137566475808892找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidmid=(1+11)/2=6low=(mid+1)=7mid=(7+11)/2=9high=(mid-1)=8mid=(7+8)/2=7low=(mid+1)=8mid=(8+8)/2=8high<low查找不成功：返回0high=(mid-1)=7high算法實現(xiàn)：設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k==r[mid].key，查找成功若k<r[mid].key，則high=mid-1若k>r[mid].key，則low=mid+1重復(fù)上述操作，直至low>high時，查找失敗intSearch_Bin(SSTableST,keyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)high=mid–1;elselow=mid+1;}return0;}性能分析：

折半查找過程中，每經(jīng)過一次比較就把查找范圍縮小一半第i次比較可能涉及的元素個數(shù)

比較次數(shù)涉及元素下限涉及元素上限

11=201=21–1

22=213=22–1

34=227=23–1

48=2315=24–1………

j2j-12j–1設(shè)表中有n個元素，則2j-1<n<=2j–1取上限：n=2j–1則最大查找長度j=「log2(n+1)∣

平均查找長度在n個元素的查找表中有：

1個元素需1次比較

2=21………2……4=22………3……8=23………4……………2h-1………h(huán)……+______________________________________________2h-1設(shè)n=2h-1

n平均查找長度ASL=∑

pici

i=11h=—∑j*2j-1nj=1

n平均查找長度ASL=∑

pici

i=11h=—∑j*2j-1(n=2h-1)nj=11=—(h*2h–n)n1=—(h*(n+1)–n)n1=—(n+1)h–1n

n+1

=—log2(n+1)–1n由此可見，平均查找長度和最大查找長度相差不多?！?/p>

log2(n+1)–1折半查找：比較次數(shù)少，查找快，但需先排序最大查找長度j=「log2(n+1)∣三、分塊查找將順序表分成多塊，塊內(nèi)元素任意存放，但塊間有序。12345678910111213141516171822121389203342443824486058745786532248861713索引表查38查找過程：先在索引表中查找記錄所在塊，再在塊內(nèi)查找。由索引項組成的索引表是按關(guān)鍵字有序的，則確定塊的查找可以用順序查找或折半查找，而塊中記錄是任意排列的，則在塊中只能順序查找。性能分析：分塊查找的平均長度為：

ASL=Lb+Lw其中：Lb為查找索引表確定所在塊的平均查找長度

Lw為在塊中查找元素的平均查找長度設(shè)將長度為n的表均勻分成b塊，每塊含有s個記錄則b=「n/s∣

假定記錄的查找概率相等則每塊查找概率為1/b即：s/n若用順序查找確定所在塊

1b1s則：ASL=Lb+Lw=—∑j+—∑ibj=1si=1

b+1s+1=—+—2

2

1n=—(—+s)+12

s

1nASL=—(—+s)+12

s平均查找長度不僅和n有關(guān)，而且和每塊中記錄個數(shù)s有關(guān)在給定n的前提下，當(dāng)s=n時，ASL取最小值

ASL=n+1≈n設(shè)順序表有10000個記錄順序查找一個記錄的平均查找長度為：（n+1)/2即：5000次比較分塊查找：s=n=100，即分成100塊，每塊100個元素分塊查找平均查找長度為：n=100次折半查找：最大查找長度為「log2(n+1)∣=14次ASL最大最小兩者之間表結(jié)構(gòu)無要求有序表分塊有序表存儲結(jié)構(gòu)順序鏈表順序順序鏈表三種查找方法比較順序查找折半查找分塊查找9.2動態(tài)查找表動態(tài)查找表的特點是：表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的。即對給定的關(guān)鍵字，若在表中存在，則查找成功，否則插入該關(guān)鍵字的記錄。ADTDynamicSearchTable{

數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合?；静僮鱌：

InitDSTable(&DT);

DestroyDSTable(&DT);

SearchDSTable(DT,key);

InsertDSTable(&DT,e);

DeleteDSTable(&DT,key);

TraverseDSTable(DT,Visit());}ADTDynamicSearchTable一、二叉排序樹和平衡二叉樹1、二叉排序樹及其查找過程定義：二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值若它的右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值它的左、右子樹也分別為二叉排序樹45125390337619924由定義得到性質(zhì)：二叉排序樹的中序序列為遞增有序序列在二叉排序樹中查找關(guān)鍵字key操作：

①

若根結(jié)點的關(guān)鍵字等于給定關(guān)鍵字key，則返回指向根的指針

②

若根結(jié)點的關(guān)鍵字小于key，

則在其左子樹上查找，否則在其右子樹上查找45125390337619924BiTree

SearchBST(BiTreeT,keyTypekey){if((!T)||EQ(key,T->data.key))return(T);elseifLT(key,T->data.key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}2、二插排序樹的插入和刪除二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結(jié)點應(yīng)為根結(jié)點；否則，繼續(xù)在其左、右子樹上查找，直至某個結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該結(jié)點的左孩子或右孩子二叉排序樹生成：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹例：給定關(guān)鍵字序列{45，24，53，45，12，24，90}由生成過程可知：在二叉排序樹中插入一個結(jié)點時，插入結(jié)點總是二叉排序樹的葉子結(jié)點，即增加一個葉子結(jié)點，所以在插入結(jié)點時不需要改變樹中其它結(jié)點，只修改一下指針即可實現(xiàn)。所以操作簡單，主要操作是查找插入位置。構(gòu)造二插排序樹的過程，是對無序序列的排序過程二叉排序樹具有類似于折半查找的特性StatusSearchBST(BiTree

T,keyType

key,BiTree

f,BiTree&p){if(!T){p=f;returnFALSE;}elseifEQ(key,T->data.key){p=T;returnTRUE;}elseifLT(key,T->data.key)SearchBST(T->lchild,key,T,p);elseSearchBST(T->rchild,key,T,p);}StatusInsert_BST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rhild=NULL;if(!p)T=s;elseifLT(e.key,p->data.key)p->lchild=s;

lsep->rchild=s;returnTRUE;}elsereturnFALSE;}二叉排序樹結(jié)點的刪除要刪除二叉排序樹中的p結(jié)點，分三種情況：①若P為葉子結(jié)點，則直接刪除。②若P只有左子樹PL或只有右子樹PR，則用其左（右）子樹的根代替被刪除結(jié)點PSPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQ中序遍歷：PPRSQSPRQ中序遍歷：PRSQSPPRQ③若P結(jié)點的左、右子樹均不空，則沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹變成為S的雙親Q的右子樹，用S取代p中序遍歷：FPCPRCLQQLSSLFSCPRCLQQLSL中序遍歷：CLC……QLQSLSPPRFCLC……QLQSLSPRFFPCPRCL中序遍歷：CLCPPRFFCPRCL中序遍歷：CLCPRF③若P結(jié)點的左、右子樹均不空，則若C無右子樹，用C取代p刪除算法StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;else{ifEQ(key,T->data.key)Delete(T);elseifLT(key,T->data.key)DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);returnTRUE;}}voidDelete（

BiTree

＆p）{if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}}FPCPRCLQQLSSL3、二叉排序樹的查找分析關(guān)鍵字序列（45,24,53,12,37,93）452412533793ASL=(1+2+2+3+3+3)/6=14/6關(guān)鍵字序列（12,24,37,45,53,93）122437455393ASL=(1+2+3+4+5+6)/6=21/6含有n個結(jié)點的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)最好情況：平均查找長度和log2n成正比，即O(log2n)最壞情況：平均查找長度為(n+1)/2，即O(n)平均情況：設(shè)有n個關(guān)鍵字序列，其中i個小于第1個關(guān)鍵字，則有n-i-1個大于第1個關(guān)鍵字,

其平均查找長度為p(n,i)根i個n-i-1個P(i)P(n-i-1)p(n,i)=[1+i*(p(i)+1)+(n-i-1)*(p(n-i-1)+1)]/n假設(shè)n個關(guān)鍵字的排列是隨機的，即小于第1個關(guān)鍵字的個數(shù)i從0到n-1按等概率計算1n-1P(n)=—∑p(n,i)ni=0

2n-1=1+—∑i*p(i)n≥2n2i=1因：P(0)=0;P(1)=1可證明：P(n)≤1+4log2n對n!中二叉排序樹進行平均，平均比較次數(shù)為O(log2n)4、平衡二叉樹（BalancedBinaryTree）定義：平衡二叉樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹，它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。平衡因子BF（BalancedFactor）:

該結(jié)點左子樹深度減去其右子樹深度例：關(guān)鍵字序列（13,24,37,90,53）一般情況下，若插入一個葉子結(jié)點，相應(yīng)子樹的根結(jié)點變化大致有三種情況：1）結(jié)點原來平衡，現(xiàn)在變成左重或右重2）結(jié)點原來某一邊重，而現(xiàn)在成為平衡的3）結(jié)點原來就是左重或右重，而新結(jié)點加在重的一邊有兩種情況需要調(diào)整(1)由于新結(jié)點加到本來就重的一邊，如右重新結(jié)點插入到右邊的右子樹中（相對為左重插入到左邊的左子樹中）ABα

h-1β

h-1γ

h-2-1中序序列：αAβBγ

RRABα

h-1β

h-1γ

h00中序序列：αAβBγ

h+1h+1voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}rcp左重插入到左邊的左子樹中21中序序列：αBβAγ

LL中序序列：αBβAγ

ABγ

h-1β

h-1α

hABγ

h-1β

h-1α

h00h+1h+1voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}plc(2)原樹右重，新結(jié)點插入到右邊的左子樹中（相對為左重插入到左邊的右子樹中）-21中序序列：αAβCγBδRLABα

h-1γ

h-2β

h-1Cδh-11中序序列：αAβCγBδABα

h-1γ

h-2β

h-1Cδh-1ABα

h-1γ

h-2β

h-1Cδ

h-10-10插入前深度：h+1調(diào)整后深度：h+1#defineLH+1#defineEH0#defineRH-1typedef

struct

BSTNode{

ElemTypedata;

intbf;

struct

BSTNode*lchild,*rchild;}BSTNode,*BSTree;voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}StatusInsertAVL(BSTree&T,ElemTypee,Boolean&taller){if(!T){T=(BSTree)malloc(sizeof(BSTNode));T->data=e;T->lchild=T->rchild=NULL;T->bf=EH;taller=TRUE;}else{ifEQ(e.key,T->data.key)

{taller=FALSE;return0;}ifLT(e.key,T->data.key){if(!InsertAVL(T->lchild,e,taller))return0;if(taller)switch(T->bf){caseLH:

LeftBalance(T);taller=FALSE;brack;caseEH:T->bf=LH;taller=TRUE;break;caseRH:T->bf=EH;taller=FALSE;break;}//switch}//ifelse{

else{if(!InsertAVL(T->rchild,e,taller))return0;if(taller)switch(T->bf){caseLH:T->bf=EH;taller=FALSE;break;caseEH:T->bf=RH;taller=TRUE;break;caseRH:

RightBalance(T);taller=FALSE;brack;}//switch}//else}/elsereturn1;}0voidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){

caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;caseRH:rd=lc->right;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504030604520Tlc000112voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}40306045Tlc502000010深度不變voidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;

caseRH:rd=lc->right;switch(rd->bf){

caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504030604542Tlc0100-12voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}深度不變rd-100000voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}50456040T3042lcrdrd45506040T3042lcvoidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;

caseRH:rd=lc->right;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;

caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504045Tlc0-1-2voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}深度不變rd000voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}504540Tlcrdrd455040TlcvoidLeftBalance(BSTree&T){lc=T->lchild;switch(lc->bf){caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;

caseRH:rd=lc->right;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;

caseRH:T->bf=EH;lc->bf=LH;break;}rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);break;}}504030604548Tlc0-100-12voidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}深度不變rd000010voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}50456040T3048lcrd48rd45506040T30lcvoidL-Rotate(BSTree&p){rc=p->rchild;p->rchild=rc->lchild;

rc->lchild=p;p=rc;}voidR-Rotate(BSTree&p){lc=p->lchild;p->lchild=lc->rchild;

lc->rchild=p;p=lc;}二、B-樹和B+樹一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：(1)樹中每個結(jié)點至多有m棵子樹;(2)若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹;(3)除根之外的所有非終端結(jié)點至少有m/2棵子樹(4)所有非終端結(jié)點中包含下列信息數(shù)據(jù)（n,A0，K1,A1,K2,A2，…Kn,An）其中：Ki(i=1,…,n)為關(guān)鍵字，且Ki＜Ki＋1(i=1,…,n－1)；Ai(i=0,…,n)為指向子樹根結(jié)點的指針，且指針Ai－1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki(i=1,…,n)，An所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn，n(m/2-1≤n≤m-1)為關(guān)鍵字的個數(shù)(或n＋1為子樹個數(shù))。所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空）。

4階B-樹

hgfedcba135118111127139199243784764533t＃definem3typedef

struct

BTNode{

int

keynum;

struct

BTNode*parent;

keyTypekey[m+1];

struct

BTNode*ptr[m+1];Record*recptr[m+1];}BTNode*BTree;

typedef

struct{

BTNode*pt;

inti;

inttag;}Result;查找算法ResultSearchBTree(BtreeT,KeyTypeK){p=T;q=NULL;found=FALSE;i=0;while(p&&!found){n=p->keynum;i=Search(p,k);if(i>0&&p->key[i]==k)found=TRUE;else{q=p;p=p->ptr[i];}

｝

if(found)return(p,i,l);elsereturn(q,i,0);}查找分析在文件系統(tǒng)中，結(jié)點查找在磁盤上進行，關(guān)鍵字查找在內(nèi)存中進行，所以查找結(jié)點是影響效率的主要因素。即：B樹的層數(shù)是決定B樹查找效率的主要因素。主要問題：最壞情況下，含有N個關(guān)鍵字的m階B樹的最大深度是多少？以2-3樹為例：一般情況：在B樹中，具有N個關(guān)鍵字，則有N+1個葉子結(jié)點，按每個結(jié)點盡可能少的關(guān)鍵字來組織B樹，則根據(jù)定義：第一層至少有1個結(jié)點第二層至少有2個結(jié)點第三層至少有2(m/2)個結(jié)點第四層至少有2(m/2)*(m/2)個結(jié)點第l+1層至少有2(m/2)l-1個結(jié)點查找成功時，在前l(fā)層上，查找失敗為l+1層因?qū)τ贜個關(guān)鍵字的m階B樹有N+1個葉子所以N+1=2(m/2)l-1此時因各層取最小值，則l取最大值因此l<=logm/2(N+1)/2+1也就是說，在含有N個關(guān)鍵字的B樹上進行查找時，從根結(jié)點到關(guān)鍵字所在結(jié)點的路徑上涉及的結(jié)點數(shù)不超過

l<=logm/2(N+1)/2+1例：N=1999998m=199l最大為4插入算法StatusInsertBTree(Btree&T,KeyTypeK,Btreeq,inti){x=K;ap=NULL;finished=FALSE;while(q&&!finished){Insert(q,i,x,ap);if(q->keynum<m)finished=TRUE;else{s=m/2;split(q,s,ap);x=q->key[s];q=q->parent;if(q