數據結構與算法-第九章

第9章查找查找的基本概念靜態查找表動態查找表哈希表主要知識點查找的基本概念查找表：

同一類型數據元素構成的集合。(集合則無相同元素)

查找:查詢關鍵字是否在(數據元素集合）表中的過程。也稱作檢索。主關鍵字:能夠惟一區分各個不同數據元素的關鍵字次關鍵字:通常不能惟一區分各個不同數據元素的關鍵字查找成功:在數據元素集合中找到了要查找的數據元素查找不成功:在數據元素集合中沒有找到要查找的數據元素靜態查找:只查找，不改變數據元素集合內的數據元素動態查找:既查找，又改變（增減）集合內的數據元素靜態查找表:靜態查找時構造的查找表動態查找表:動態查找時構造的查找表平均查找長度:查找過程所需進行的關鍵字比較次數的平均值,是衡量查找算法效率的最主要標準,其數學定義為：其中，Pi是要查找數據元素出現的概率，Ci是查找相應數據元素的比較次數。9.1靜態查找表

靜態查找表主要有三種結構：

順序表有序順序表索引順序表靜態查找表的順序存儲結構：typedefstruct{ElemType*elem;//數據元素存儲空間基址，0號單元留空

intlength/*表長度*/}SSTable;typedefintKeyType;typedefchar*InfoType;定義要查找數據元素的結構體為：typedefstruct{KeyTypekey;/*關鍵字域*/InfoTypeotherinfo;/*其他域*/}ElemType;9.1.1順序表順序查找的基本思想是：從順序表的一端開始，用給定數據元素的關鍵字逐個和順序表中各數據元素的關鍵字比較，若在順序表中查找到要查找的數據元素，則查找成功，函數返回該數據元素在順序表中的位置；否則查找失敗，函數返回0。查找函數設計如下：intSearch_Seq(SSTableST,KeyTypekey){//算法9.1//在順序表ST中順序查找其關鍵字等于key的數據元素。//若找到，則函數值為該元素在表中的位置，否則為0。

inti=0;ST.elem[0].key=key;//"哨兵"for(i=ST.length;ST.elem[i].key!=key;--i);//從后往前找returni;//找不到時，i為0}//Search_Seq利用監視哨的算法。思考：監視哨作用？算法分析(順序表)查找成功時的平均查找長度ASL成功為：

ASL=PiCi=1/n*(n-i+1)=(n+1)/2(約表長的一半)查找失敗時的平均查找長度ASL失敗顯然為n+19.1.2有序表的查找有序順序表上的查找算法主要有順序查找和折半查找兩種方法。一、有序表的順序查找有序順序表上的順序查找算法和順序表上的查找算法方法類同二、二分查找（又稱折半查找）算法的基本思想：先給數據排序（一般按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至前半部內查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。反之，如果key大，則縮小至后半部內查找。查找21

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow(a)查找成功示例算法示例

如圖(a)，(b)所示。查找71

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow(b)查找不成功示例二分查找算法如下：intSearch_Bin(SSTableST,KeyTypekey){//算法9.2//在有序表ST中折半查找其關鍵字等于key的數據元素。//若找到，則函數值為該元素在表中的位置，否則為0。intlow,high,mid;low=1;high=ST.length;//置區間初值while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//繼續在前半區間進行查找elselow=mid+1;//繼續在后半區間進行查找}return0;//順序表中不存在待查元素}//Search_Bin

算法分析查找時每經過一次比較，查找范圍就縮小一半，該過程可用一棵二叉樹表示：

◆

根結點就是第一次進行比較的中間位置的記錄；◆排在中間位置前面的作為左子樹的結點；◆排在中間位置后面的作為右子樹的結點；對各子樹來說都是相同的。這樣所得到的二叉樹稱為判定樹(DecisionTree)。②將二叉判定樹的第㏒2n+1層上的結點補齊就成為一棵滿二叉樹，深度不變。折半查找的性能分析6391410275811可用判定樹描述折半查找(其它查找也可)過程:

判定樹的各層結點由查找過程中從大到小可

能出現的各區間中點(分割點)構成。包括

外部結點(方,對應不成功查找)和內部結點。

該樹接近滿二叉樹(葉子未在左邊排緊),

樹高與結點數的關系相同(倒2層缺左孩,因整除2造成)

求平均查找長度,為方便,假設表長n=2h-1對應滿二叉樹。按等概率Pi=1/n

ASL=iPiCi=(j

j*2j-1)/n=(n+1)/n*Log2(n+1)-1(推導過程略去)其它有序表查找算法:取區間某分割點與x比較,類似折半。9.1.4索引順序表的查找

當順序表中的數據元素個數非常大時，采用在順序表上建立索引表的辦法提高查找速度。把要在其上建立索引表的順序表稱作主表。主表中存放著數據元素的全部信息，索引表中只存放主表中要查找數據元素的主關鍵字和索引信息。主表按塊有序8146910223418193140385466467178688085140034516610285153keylink下標索引表012345678910111213141516171819key其它域位置主表索引表結構圖

索引表中的數據元素由兩個域構成，key域為被索引的若干個數據元素中關鍵字的最大值，link域為被索引的若干個數據元素中第一個數據元素的位置編號。算法示例索引表1234567891011121314151617182212138920334244382448605874578653查38224886

1713分塊查找示例9.2動態查找表動態查找表主要有二叉樹結構和樹結構兩種類型。二叉樹結構有二叉排序樹、平衡二叉樹等。樹結構有B-樹、B+樹等。1.二叉排序樹一、基本概念----或是一棵空樹；或者是具有如下性質的非空二叉樹：

（1）左子樹的所有結點均小于根的值；（2）右子樹的所有結點均大于根的值；（3）它的左右子樹也分別為二叉排序樹。二叉排序樹中結點的結構體定義如下：typedefstructBiTNode{ElemTypedata;structnode*lchild;structnode*rchild;}BiTNode,*BiTree3811241094039454035190146476760445600800下圖所示就是一棵二叉排序樹二、二叉排序樹的查找算法StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){/*在根指針T所指二叉排序樹中遞歸地查找其關鍵字等于key的數據元素，若查找成功，則指針p指向該數據元素結點，并返回TRUE，否則指針p指向查找路徑上訪問的最后一個結點并返回FALSE，指針f指向T的雙親，其初始調用值為NULL*/if(!T){p=f;returnFALSE;}//查找不成功elseif(EQ(key,T->data.key)){p=T;returnTRUE;}//查找成功elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);//在左子樹中繼續查找elsereturnSearchBST(T->rchild,key,T,p);//在右子樹中繼續查找}//SearchBST與判定樹相類似，但有本質區別，判定樹順序存儲，二叉排序樹鏈式存儲。插入操作要求首先查找數據元素是否在二叉排序樹中存在，若存在則返回；若不存在，插入查找失敗時結點的左指針或右指針上。插入算法設計如后:三、二叉排序樹的插入算法StatusInsertBST(BiTree&T,ElemTypee){//算法9.6//當二叉排序樹T中不存在關鍵字等于e.key的數據元素時，//插入e并返回TRUE，否則返回FALSEBiTreep,s;if(!SearchBST(T,e.key,NULL,p)){//查找不成功s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s為新的根結點elseif(LT(e.key,p->data.key))p->lchild=s;//插入s為左孩子elsep->rchild=s;//插入s為右孩子returnTRUE;}elsereturnFALSE;//樹中已有關鍵字相同的結點，不再插入}//InsertBST下圖是調用上述插入函數依次插入數據元素4,5,7,2,1,9,8,11,3的過程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)刪除二叉排序樹的結點刪除方案:

要求刪除二叉排序樹中結點

P后,不破壞二叉排序樹特性.

F為其雙親.若P只有左(右)子

樹,將子樹接到F的左指針即

可,若同時有左右子樹,有兩

種方案:FPCfpPrQS...Sl.FfpPrCQS..Sl方案1:將P的右子樹接到P的左子樹方案1方案2

中序序列最后結點的右指針處,將P的左子樹接到F的左指針

處,結果樹可能增高.FSCfpPrQ...Sl方案2:刪除P的左子樹中序序列最后結點S,來頂替P結點,原S的左

子樹接到原S的雙親的右指針處,結果樹可能降低。刪除二叉排序樹結點的算法StatusDeleteBST(BiTree&T,KeyTypekey){//算法9.7//若二叉排序樹T中存在關鍵字等于key的數據元素時，//則刪除該數據元素結點p，并返回TRUE；否則返回FALSEif(!T)returnFALSE;//不存在關鍵字等于key的數據元素else{if(EQ(key,T->data.key))//找到關鍵字等于key的數據元素returnDelete(T);elseif(LT(key,T->data.key))returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}}//DeleteBST二叉排序樹刪除算法(方案2)StatusDelete(BiTree&p){//算法9.8//從二叉排序樹中刪除結點p，并重接它的左或右子樹BiTreeq,s;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;//s指向被刪結點的“后繼”if(q!=p)q->rchild=s->lchild;//重接*q的右子樹elseq->lchild=s->lchild;//重接*q的左子樹free(s);}returnTRUE;}//Delete2.平衡二叉樹的定義平衡二叉樹或者是空樹，或者是滿足下列性質的二叉樹。⑴：左子樹和右子樹深度之差的絕對值不大于1；⑵：左子樹和右子樹也都是平衡二叉樹。

平衡因子(BalanceFactor)：二叉樹上結點的左子樹的深度減去其右子樹深度稱為該結點的平衡因子。因此，平衡二叉樹上每個結點的平衡因子只可能是-1、0和1，否則，只要有一個結點的平衡因子的絕對值大于1，該二叉樹就不是平衡二叉樹。如果一棵二叉樹既是二叉排序樹又是平衡二叉樹，稱為平衡二叉排序樹(BalancedBinarySortTree)。平衡化旋轉

一般的二叉排序樹是不平衡的，若能通過某種方法使其既保持有序性，又具有平衡性，就找到了構造平衡二叉排序樹的方法，該方法稱為平衡化旋轉。在對AVL樹進行插入或刪除一個結點后，通常會影響到從根結點到插入(或刪除)結點的路徑上的某些結點，這些結點的子樹可能發生變化。以插入結點為例，影響有以下幾種可能性◆

以某些結點為根的子樹的深度發生了變化；◆

某些結點的平衡因子發生了變化；◆

某些結點失去平衡。一、LL型平衡化旋轉⑴失衡原因在結點a的左孩子的左子樹上進行插入，插入使結點a失去平衡。a插入前的平衡因子是1，插入后的平衡因子是2。設b是a的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1(否則b就失衡)。⑵平衡化旋轉方法通過順時針旋轉操作實現，如圖所示。用b取代a的位置，a成為b的右子樹的根結點，b原來的右子樹作為a的左子樹。⑶插入后各結點的平衡因子分析①旋轉前的平衡因子設插入后b的左子樹的深度為HbL，則其右子樹的深度為HbL-1；a的左子樹的深度為HbL+1。abbRaRbLxabbRaRbLx圖9-7LL型平衡化旋轉示意圖a的平衡因子為2，則a的右子樹的深度為：HaR=HbL+1-2=HbL-1。②旋轉后的平衡因子

a的右子樹沒有變，而左子樹是b的右子樹，則平衡因子是：HaL-HaR=(HbL-1)-(HbL-1)=0

即a是平衡的，以a為根的子樹的深度是HbL。

b的左子樹沒有變化，右子樹是以a為根的子樹，則平衡因子是：HbL-HbL=0

即b也是平衡的，以b為根的子樹的深度是HbL+1，與插入前a的子樹的深度相同，則該子樹的上層各結點的平衡因子沒有變化，即整棵樹旋轉后是平衡的。二、LR型平衡化旋轉⑴失衡原因

在結點a的左孩子的右子樹上進行插入，插入使結點a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。設b是a的左孩子，c為b的右孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否則，c就是失衡結點。（2）平衡化旋轉方法

先以b進行一次逆時針旋轉(將以b為根的子樹旋轉為以c為根)，再以a進行一次順時針旋轉，如圖9-8所示。將整棵子樹旋轉為以c為根，b是c的左子樹，a是c的右子樹；c的右子樹移到a的左子樹位置，c的左子樹移到b的右子樹位置。圖9-8LR型平衡化旋轉示意圖abbLaRcLxcRxcacbLaRcLxcRxb(3)

插入后結點c的平衡因子的變化分析①插入后c的平衡因子是1：即在c的左子樹上插入。設c的左子樹的深度為HcL，則右子樹的深度為HcL-1；b插入后的平衡因子是-1，則b的左子樹的深度為HcL，以b為根的子樹的深度是HcL+2。因插入后a的平衡因子是2，則a的右子樹的深度是HcL。②插入后c的平衡因子是0：c本身是插入結點。設c的左子樹的深度為HcL，則右子樹的深度也是HcL；因b插入后的平衡因子是-1，則b的左子樹的深度為HcL，以b為根的子樹的深度是HcL+2；插入后a的平衡因子是2，則a的右子樹的深度是HcL。③插入后c的平衡因子是-1：即在c的右子樹上插入。設c的左子樹的深度為HcL，則右子樹的深度為HcL+1，以c為根的子樹的深度是HcL+2；因b插入后的平衡因子是-1，則b的左子樹的深度為HcL+1，以b為根的子樹的深度是HcL+3；則a的右子樹的深度是HcL+1。⑷旋轉后各結點(a,b,c)平衡因子分析

①

旋轉前(插入后)c的平衡因子是1：

a的左子樹深度為HcL-1，其右子樹沒有變化，深度是HcL，則a的平衡因子是-1；b的左子樹沒有變化，深度為HcL，右子樹是c旋轉前的左子樹，深度為HcL，則b的平衡因子是0；c的左、右子樹分別是以b和a為根的子樹，則c的平衡因子是0。②

旋轉前

(插入后)c的平衡因子是0：旋轉后a，b，c的平衡因子都是0。

③

旋轉前

(插入后)c的平衡因子是-1：旋轉后a，b，c的平衡因子分別是0，-1，0。綜上所述，即整棵樹旋轉后是平衡的。三、RL型平衡化旋轉⑴失衡原因

在結點a的右孩子的左子樹上進行插入，插入使結點a失去平衡，與LR型正好對稱。對于結點a，插入前的平衡因子是-1，插入后a的平衡因子是-2。設b是a的右孩子，c為b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同樣，c在插入前的平衡因子只能是0，否則，c就是失衡結點。(2)平衡化旋轉方法

先以b進行一次順時針旋轉，再以a進行一次逆時針旋轉，如圖9-9所示。即將整棵子樹(以a為根)旋轉為以c為根，a是c的左子樹，b是c的右子樹；c的右子樹移到b的左子樹位置，c的左子樹移到a的右子樹位置。圖9-9RL型平衡化旋轉示意圖abbRaLcLxcRxcbcbRaLcLxcRxa(3)

插入后結點c的平衡因子的變化分析

①插入后c的平衡因子是1：在c的左子樹上插入。設c的左子樹的深度為HcL，則右子樹的深度為HcL-1。因b插入后的平衡因子是1，則其右子樹的深度為HcL，以b為根的子樹的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹的深度是HcL。②插入后c的平衡因子是0：c本身是插入結點。設c的左子樹的深度為HcL，則右子樹的深度也是HcL；因b插入后的平衡因子是1，則b的右子樹的深度為HcL，以b為根的子樹的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹的深度是HcL。③插入后c的平衡因子是-1：在c的右子樹上插入。設c的左子樹的深度為HcL，則右子樹的深度為HcL+1，以c為根的子樹的深度是HcL+2；因b插入后的平衡因子是1，則b的右子樹的深度為HcL+1，以b為根的子樹的深度是HcL+3；則a的右子樹的深度是HcL+1。⑷旋轉后各結點(a,b,c)的平衡因子分析①

旋轉前

(插入后)c的平衡因子是1：

a的左子樹沒有變化，深度是HcL，右子樹是c旋轉前的左子樹，深度為HcL，則a的平衡因子是0；b的右子樹沒有變化，深度為HcL，左子樹是c旋轉前的右子樹，深度為HcL-1

，則b的平衡因子是-1；c的左、右子樹分別是以a和b為根的子樹，則c的平衡因子是0。

②

旋轉前

(插入后)c的平衡因子是0：旋轉后a，b，c的平衡因子都是0。

③

旋轉前

(插入后)c的平衡因子是-1：旋轉后a，b，c的平衡因子分別是1，0，0。綜上所述，即整棵樹旋轉后是平衡的。四、RR型平衡化旋轉⑴失衡原因在結點a的右孩子的右子樹上進行插入，插入使結點a失去平衡。要進行一次逆時針旋轉，和LL型平衡化旋轉正好對稱。⑵平衡化旋轉方法

設b是a的右孩子，通過逆時針旋轉實現，如圖9-10所示。用b取代a的位置，a作為b的左子樹的根結點，b原來的左子樹作為a的右子樹。圖9-10RR型平衡化旋轉示意圖babLaLbRxabbLaLbRx哈希表概念：哈希表設計思想不基于比較(不依賴n),關鍵字地址的映射。

Hash函數--雜湊。沖突,同義詞,二次聚集,散列,哈希(散列)地址。哈希函數構造：

1.直接定址2.數字分析3.平方取中4.折疊5.偽隨機數法

6.除留余數(模取質數或不包含質因數小于20的合數)

考慮因素：1.計算哈希函數耗時2.關鍵字長度3.哈希表尺寸

4.關鍵字分布情況5.記錄查找頻率沖突處理：

1.開放定址法Hi=(H(key)+di)MODm

線性探測(易聚集)/二次探測/偽隨機數探測再散列

2.再哈希法

3.鏈地址法

4建公共溢出區哈希表查找與分析查找類似于構造過程,要能區分出空位(NULLKEY)。存儲結構:

inthashsize[]={997,…};//哈希表容量遞增表,合適的素數序列

typedefstruct{

elemtype*elem;//元素存儲基址

intcount,sizeindex;//當前元素數,hashsize[sizeindex]當前容量

}hashtable;//哈希表結構

#defineSUCCESS1

#defineUNSUCCESS0

#defineDUPLICATE-1

statussearchhash(hashtableh,keytypek,int*p,int*c){

p0=*p=hash(k);q=-1;//*c為沖突計數，實參初值取0

while(h.elem[*p].key!=NULLKEY&&h.elem[*p].key!=k){

if(h.elem[*p].key==DELKEY&&q==-1)q=*p;/*記第一個刪標記位置*/

collision(*p,++*c);/*求探查地址*p*/if(*p==p0){*p=-1;returnUNSUCCESS;}/*防循環探測,用改表長來處理*/

}if(k==h.elem[*p].key)returnSUCCESS;

else{if(q!=-1)*p=q;returnUNSUCCESS;}

}//查找算法增加了對刪除標記DELKEY的處理(綠色部