數(shù)據(jù)結(jié)構(gòu)與算法-第九章

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

同一類型數(shù)據(jù)元素構(gòu)成的集合。(集合則無相同元素)

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

靜態(tài)查找表主要有三種結(jié)構(gòu)：

順序表有序順序表索引順序表靜態(tài)查找表的順序存儲結(jié)構(gòu)：typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲空間基址，0號單元留空

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

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

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

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow

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

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

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow(b)查找不成功示例二分查找算法如下：intSearch_Bin(SSTableST,KeyTypekey){//算法9.2//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。//若找到，則函數(shù)值為該元素在表中的位置，否則為0。intlow,high,mid;low=1;high=ST.length;//置區(qū)間初值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;//繼續(xù)在前半?yún)^(qū)間進行查找elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進行查找}return0;//順序表中不存在待查元素}//Search_Bin

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

◆

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

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

能出現(xiàn)的各區(qū)間中點(分割點)構(gòu)成。包括

外部結(jié)點(方,對應不成功查找)和內(nèi)部結(jié)點。

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

樹高與結(jié)點數(shù)的關(guān)系相同(倒2層缺左孩,因整除2造成)

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

ASL=iPiCi=(j

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

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

索引表中的數(shù)據(jù)元素由兩個域構(gòu)成，key域為被索引的若干個數(shù)據(jù)元素中關(guān)鍵字的最大值，link域為被索引的若干個數(shù)據(jù)元素中第一個數(shù)據(jù)元素的位置編號。算法示例索引表1234567891011121314151617182212138920334244382448605874578653查38224886

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

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

要求刪除二叉排序樹中結(jié)點

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

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

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

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

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

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

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

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

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

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

以某些結(jié)點為根的子樹的深度發(fā)生了變化；◆

某些結(jié)點的平衡因子發(fā)生了變化；◆

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

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

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

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

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

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

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

插入后結(jié)點c的平衡因子的變化分析①插入后c的平衡因子是1：即在c的左子樹上插入。設c的左子樹的深度為HcL，則右子樹的深度為HcL-1；b插入后的平衡因子是-1，則b的左子樹的深度為HcL，以b為根的子樹的深度是HcL+2。因插入后a的平衡因子是2，則a的右子樹的深度是HcL。②插入后c的平衡因子是0：c本身是插入結(jié)點。設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。⑷旋轉(zhuǎn)后各結(jié)點(a,b,c)平衡因子分析

①

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

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

旋轉(zhuǎn)前

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

③

旋轉(zhuǎn)前

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

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

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

插入后結(jié)點c的平衡因子的變化分析

①插入后c的平衡因子是1：在c的左子樹上插入。設c的左子樹的深度為HcL，則右子樹的深度為HcL-1。因b插入后的平衡因子是1，則其右子樹的深度為HcL，以b為根的子樹的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹的深度是HcL。②插入后c的平衡因子是0：c本身是插入結(jié)點。設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。⑷旋轉(zhuǎn)后各結(jié)點(a,b,c)的平衡因子分析①

旋轉(zhuǎn)前

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

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

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

②

旋轉(zhuǎn)前

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

③

旋轉(zhuǎn)前

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

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

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

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

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

考慮因素：1.計算哈希函數(shù)耗時2.關(guān)鍵字長度3.哈希表尺寸

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

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

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

2.再哈希法

3.鏈地址法

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

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

typedefstruct{

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

intcount,sizeindex;//當前元素數(shù),hashsize[sizeindex]當前容量

}hashtable;//哈希表結(jié)構(gòu)

#defineSUCCESS1

#defineUNSUCCESS0

#defineDUPLICATE-1

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

p0=*p=hash(k);q=-1;//*c為沖突計數(shù)，實參初值取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;}/*防循環(huán)探測,用改表長來處理*/

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

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

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