數(shù)據(jù)結(jié)構(gòu)_查找原理與典型查找算法第一頁，共107頁。查找的基本概念1.查找表2.查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字查找：根據(jù)某個給定的值，在表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。查找成功查找失敗第二頁，共107頁。查找的基本概念3.查找表的分類靜態(tài)查找表動態(tài)查找表4.衡量查找算法效率的標(biāo)準(zhǔn)平均查找長度ASL(AverageSearchLength)查找成功時的平均查找長度第三頁，共107頁。查找的基本概念5.本章數(shù)據(jù)元素類型與比較運(yùn)算的符號約定數(shù)據(jù)類型定義

typedefstruct{KeyTypekey; ……}ElemType關(guān)鍵字比較的符號約定EQ(a,b)LT(a,b)LQ(a,b)第四頁，共107頁。查找的基本概念6.查找的基本方法比較式查找法計算式查找法基于線性表的查找法（靜態(tài)查找）基于樹的查找法（動態(tài)查找）——HASH查找法順序查找法折半查找法分塊查找法二叉排序樹平衡二叉樹B－樹B＋樹第五頁，共107頁。9.1靜態(tài)查找表靜態(tài)查找表主要有三種結(jié)構(gòu)：順序表有序順序表索引順序表針對靜態(tài)查找表的查找算法主要有：順序查找（線性查找）折半查找（二分查找）分塊查找（索引順序查找）第六頁，共107頁。9.1.1順序查找法1.順序表上的順序查找的基本思想從順序表的一端開始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個與順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若在順序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在順序表中的位置；否則查找失敗，函數(shù)返回0。2.順序表的機(jī)內(nèi)存儲結(jié)構(gòu)typedefstruct{ ElemType*elem; intlength;}SSTable;第七頁，共107頁。xa1a2a3……an-2an-1anintSearch_Seq(SSTableST,KeyTypekey){

ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}9.1.1順序查找法順序查找過程第八頁，共107頁。9.1.1順序查找法3.順序查找操作的性能分析（設(shè)n＝ST.length）（1）查找成功時的平均查找長度xi查找成功的比較次數(shù)為n－i＋1（1≤i≤n）等概率情況下查找成功的平均查找長度：第九頁，共107頁。9.1.1順序查找法（2）任意關(guān)鍵字查找不成功的比較次數(shù)為n＋1（3）當(dāng)查找不成功的情形不能忽視時，需要計算查找不成功的平均查找長度，則：平均查找長度＝查找成功的平均查找長度＋查找成功的平均查找長度假設(shè)查找成功和查找不成功的可能性相同，對每個查找概率也相等第十頁，共107頁。9.1.1順序查找法順序查找法的特點：優(yōu)點：算法簡單、適用面廣（對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用）缺點：

ASL太大，時間效率太低。第十一頁，共107頁。9.1.1順序查找法思考題：問：對單鏈表結(jié)構(gòu)如何線性查找？答：從頭指針始“順藤摸瓜”。問：對非線性（樹結(jié)構(gòu)）如何順序查找?答：借助各種二叉樹遍歷操作！第十二頁，共107頁。9.1.2有序表的查找有序順序表上的查找算法（1）順序查找法有序順序表上順序查找算法類同順序表上的順序查找算法（2）二分查找法（又稱折半查找法）前提條件：1）表中的記錄按關(guān)鍵字有序（設(shè)遞增有序）2）查找表采用順序存儲結(jié)構(gòu)查找過程第十三頁，共107頁。折半查找過程示例1)查找關(guān)鍵字等于21的記錄1234567891011513192137566475808892ST.elem[mid].key>21513192137566475808892ST.elem[mid].key<21513192137566475808892ST.elem[mid].key=21(查找成功）第十四頁，共107頁。2)查找關(guān)鍵字等于85的記錄1234567891011513192137566475808892ST.elem[mid].key<85513192137566475808892ST.elem[mid].key<85513192137566475808892ST.elem[mid].key>85513192137566475808892失敗第十五頁，共107頁。9.1.2有序表的查找算法描述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;}第十六頁，共107頁。9.1.2有序表的查找思考題：1.若表中的記錄按關(guān)鍵字遞減有序，如何完成折半查找？2.能否使用單鏈表結(jié)構(gòu)進(jìn)行折半查找？無法實現(xiàn)！因全部元素的定位只能從頭指針head開始，是一種非隨機(jī)存取結(jié)構(gòu)。3.對非線性(樹)結(jié)構(gòu)如何進(jìn)行折半查找？可借助二叉排序樹來查找（屬動態(tài)查找表形式）。第十七頁，共107頁。9.1.2有序表的查找折半查找過程可以描述為一棵二叉樹折半查找的判定樹如：（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11）a9a6a3a1a4a7a10a2a5a8a11~a1a3-a4a6-a7a9-a10a1-a2a2-a3a4-a5a5-a6a7-a8a8-a9a10-a11a11-第十八頁，共107頁。9.1.2有序表的查找折半查找算法的性能分析可以看出：n個結(jié)點的判定樹的深度和n個結(jié)點的完全二叉樹的深度相同，即第十九頁，共107頁。9.1.2有序表的查找查找成功：查找成功的過程：走了一條從根結(jié)點到與該記錄對應(yīng)結(jié)點的路徑。比較的關(guān)鍵字個數(shù)為：該結(jié)點在判定樹上的層次數(shù)。查找成功時比較的關(guān)鍵字個數(shù)最多不超過樹的深度。不妨設(shè)n＝2h－1，則折半查找的判定樹為深為h的滿二叉樹，在等概率情況下的平均查找長度：第二十頁，共107頁。查找失?。翰檎沂〉倪^程是：走了一條從根結(jié)點到外部結(jié)點的路徑。查找失敗時比較的關(guān)鍵字個數(shù)最多不超過樹的深度。折半查找法的特點：優(yōu)點：效率高缺點：適用范圍?。ㄖ荒苁怯行蝽樞虮恚﹩栴}：對順序查找除了折半查找改進(jìn)法外，還有無其他改進(jìn)算法？答：有，如分塊查找法。第二十一頁，共107頁。9.1.4索引順序表的查找基本思路：（1）先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值?。ǖ颖韮?nèi)部未必有序）。2448605874491312920334244388653822特點：塊間有序，塊內(nèi)無序第二十二頁，共107頁。137186482253497458608648243844423320981312229.1.4索引順序表的查找（分塊查找）（2）然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址。第二十三頁，共107頁。9.1.4索引順序表的查找（分塊查找）2.分塊查找的基本思想：查找步驟分兩步進(jìn)行：（1）對索引表使用折半查找（或順序查找）法，確定元素所在的塊（子表）。（2）在子表內(nèi)采用順序查找法（因為各子表內(nèi)部是無序表）；則：分塊查找的平均查找長度為：

ASLbs=ASLb+ASLw

。對索引表查找的ASL對塊內(nèi)查找的ASL第二十四頁，共107頁。9.1.4索引順序表的查找（分塊查找）3.性能分析設(shè)長度為n的表均勻地分為b塊，每塊有s個記錄，且表中每個記錄的查找概率相等，則：（1）若對索引表進(jìn)行順序查找：問題：如何進(jìn)行分塊可以取得最好的查找效率？第二十五頁，共107頁。9.1.4索引順序表的查找（分塊查找）2）若折半查找確定所在塊：第二十六頁，共107頁。靜態(tài)查找表小結(jié)：靜態(tài)查找表三種查找方法的比較順序查找折半查找分塊查找平均查找長度最大最小介于二者之間表結(jié)構(gòu)有序/無序表有序表表中元素逐段有序存儲結(jié)構(gòu)順序/鏈?zhǔn)酱鎯樞虼鎯樞?鏈?zhǔn)酱鎯Φ诙唔?，?07頁。9.2動態(tài)查找表ADTDynamicSearchTable{

數(shù)據(jù)對象D:具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合 基本操作P：

InitDSTable(&DT); DestroyDSTable(&DT); SearchDSTable(DT,key); InsertDSTable(&DT,e); DeleteDSTable(&DT,key); TraverseDSTable(DT,visit());} 第二十八頁，共107頁。9.2.1二叉排序樹和平衡二叉樹一、二叉排序樹二、平衡二叉樹第二十九頁，共107頁。一、二叉排序樹1.定義、特點、構(gòu)造過程（1）定義二叉排序樹或者是一棵空樹，或是具有下列性質(zhì)的二叉樹：若左子樹非空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值。若右子樹非空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值。它的左右子樹也分別為二叉排序樹。第三十頁，共107頁。（2）將線性表構(gòu)造成二叉排序樹的優(yōu)點：①查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；②中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實現(xiàn)了排序運(yùn)算）；③如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除時只需修改指針而不需移動元素?？傊憾媾判驑浼扔蓄愃朴谡郯氩檎业奶匦?，又采用了鏈表存儲，它是動態(tài)查找表的一種適宜表示。第三十一頁，共107頁。45125333710024一、二叉排序樹（3）構(gòu)造過程:例：輸入序列{45，12，37，3，53，100，24}第三十二頁，共107頁。第三十三頁，共107頁。一、二叉排序樹（2）非遞歸查找過程BiTreeSearchBST(BiTreeT,KeyTypekey){ BiTreep=T; while(p&&!(EQ(key,p->data.key)) ifLT(key,p->data.key)p=p->lchild; elsep=p->rchild; returnp;}//SearchBST第三十四頁，共107頁。一、二叉排序樹3.二叉排序樹的插入思路：查找不成功，生成一個新結(jié)點（如s），并將其插入到二叉排序樹中；查找成功則返回。第三十五頁，共107頁。（1）修改過的查找算法StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,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);}第三十六頁，共107頁。一、二叉排序樹（2）二叉排序樹的插入StatusInsert(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){ s=(BiTree)malloc(sizeof(BiTNode)); s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s; elseifLT(e.key,p->data.key)p->lchild=s; elsep->rchild=s; returnTRUE; }elsereturnFALSE;}第三十七頁，共107頁。一、二叉排序樹參考算法：StatusinsertBST(BiTree&T,ElemTypex){if(T==NULL){T=(BiTree)malloc(sizeof(BiTNode)); T->data=x; T->lchild=T->rchild=NULL; returnTRUE;//插入成功

}else{ if(x.key<T->data.key)insertBST(T->lchild,x);elseif(x.key>T->data.keyinsertBST(T->rchild,x);elsereturnFALSE;//插入失敗}}//insert第三十八頁，共107頁。一、二叉排序樹4.二叉排序樹的刪除對于二叉排序樹，刪除樹上一個結(jié)點相當(dāng)于刪除有序序列中的一個記錄，要求刪除后仍需保持二叉排序樹的特性。如何刪除一個結(jié)點？第三十九頁，共107頁。一、二叉排序樹設(shè)待刪結(jié)點指針為p，p的雙親結(jié)點指針為f，不失一般性，設(shè)p為f的左子女（若為右子女，類似）。情況1：p為葉結(jié)點f->lchild=NULL；free(p);FfPp第四十頁，共107頁。f->lchild=p->lchild；free(p);FfPpPLFfPpPRFfPLFfPRf->lchild=p->rchild；free(p);一、二叉排序樹情況2：P只有左子樹PL或只有右子樹PR第四十一頁，共107頁。情況3：PL，PR均非空

FfPpPRPLPR作為s的右子女:s->rchild=p->rchild;c作為f的左子女：f->lchild=p->lchild;刪除p: free(p);方法①FfCCLQQLSSLPRqscqsPRFfPpCCLQQLSSLc第四十二頁，共107頁。方法②qsPRFfPpCCLQQLSSLcFfCCLQQLSSLPRqpc以S代替P,然后刪除s: p->data=s->data;SL作為Q的右子女:q->rchild=s->lchild;釋放結(jié)點s: free(s);第四十三頁，共107頁。一、二叉排序樹算法9.7StatusDeleteBST(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;} }}//DeleteBST第四十四頁，共107頁。一、二叉排序樹算法9.8voidDelete(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;}}//Delete第四十五頁，共107頁。一、二叉排序樹5.二叉排序樹的查找分析：含有n個結(jié)點的二叉樹的平均查找長度和樹的形狀有關(guān)。

ASL(a)＝1/6(1+2+2+3+3+3)＝14/6

ASL(b)＝1/6(1+2+3+4+5+6)＝21/6452453123793(a)122437459353(b)第四十六頁，共107頁。一、二叉排序樹一般的：1)二叉排序樹上查找某關(guān)鍵字等于結(jié)點值的過程，其實就是走了一條從根到該結(jié)點的路徑。比較的關(guān)鍵字次數(shù)＝此結(jié)點的層次數(shù);最多的比較次數(shù)＝樹的深度（或高度；2)一棵二叉排序樹的平均查找長度為：第四十七頁，共107頁。一、二叉排序樹最好的情況二叉排序樹的形態(tài)同折半查找的判定樹（即形態(tài)比較均衡）ASL＝樹的深度為：log2(n＋1)－1；最壞的情況插入的n個元素從一開始就有序，二叉排序樹的形態(tài)為一棵單支樹ASL＝1/n(1＋2＋3＋……＋n)＝(n＋1)/2一般的情況ASL＝O(㏒n)第四十八頁，共107頁。一、二叉排序樹思考：如何提高二叉排序樹的查找效率？解決方法盡量讓二叉樹的形狀均衡??！平衡二叉樹第四十九頁，共107頁。四、平衡二叉樹定義1.結(jié)點的平衡因子（BF）2.平衡二叉樹（AVL樹）或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：它的左子樹和右子樹深度之差的絕對值不超過1左子樹和右子樹都是AVL樹。3.平衡二叉排序樹abecdf452453123793第五十頁，共107頁。四、平衡二叉樹問題：如何使構(gòu)造的二叉排序樹成為AVL樹？答：如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)（單向右旋平衡處理）

RR平衡旋轉(zhuǎn)（單向左旋平衡處理）

LR平衡旋轉(zhuǎn)（雙向[先左后右]旋平衡處理）

RL平衡旋轉(zhuǎn)（雙向[先右后左]旋平衡處理）第五十一頁，共107頁。ABDCE右單旋1.ABDCEh四、平衡二叉樹第五十二頁，共107頁。四、平衡二叉樹ACDBEACEDB左單旋2.第五十三頁，共107頁。ABDCFEGAEBDCFG左單旋右單旋ABDCFEhh-1G3.四、平衡二叉樹3.第五十四頁，共107頁。右單旋左單旋4.DACBEFhh-1GACBEFGDACBEFGD四、平衡二叉樹第五十五頁，共107頁。9.2.2B_樹和B+樹一、B－樹及其查找1.定義：一棵m階的B－樹，或為一棵空樹，或為滿足下列條件的m叉樹：樹中每個結(jié)點至多m棵子樹；若根結(jié)點不是葉結(jié)點，則至少2棵子樹；除根以外的所有非終端結(jié)點至少有┌m/2┐棵子樹；所有非終端結(jié)點中包含下列信息數(shù)據(jù)：（A0,K1,A1,K2,A2,…,Kn,An)葉結(jié)點位于同一層次（外部結(jié)點/失敗點）第五十六頁，共107頁。2.示例（一棵4階B－樹及查找過程）351181784321112713916447533991FFFFFFFFFFFFabcdefghT查找時間取決因素（1）等于給定值的關(guān)鍵字所在結(jié)點的層次；（2）結(jié)點中關(guān)鍵字的個數(shù)。第五十七頁，共107頁。3.查找過程：

順指針查找結(jié)點和在結(jié)點的關(guān)鍵字中順序查找交叉進(jìn)行的過程。具體方法：從根結(jié)點開始，將key與根結(jié)點中的各個關(guān)鍵字k1,k2,……，kj進(jìn)行比較，由于該關(guān)鍵字序列有序，可采用順序/二分查找方法。若key＝ki,(1≤i≤j),則查找成功；若key＜k1,則沿指針A0所指的子樹中繼續(xù)查找；若ki＜key＜ki+1,則沿指針Ai所指的子樹中繼續(xù)查找；若key＞kj,則沿指針Aj所指的子樹中繼續(xù)查找。在自上向下的查找過程中，若直到葉結(jié)點也沒有找到值為key的關(guān)鍵字，則查找失敗。第五十八頁，共107頁。9.2.2B_樹和B+樹二、B＋樹（B－的變型樹）1.定義：一棵m階的B＋

樹與B－樹的區(qū)別在于：有n棵子樹的結(jié)點中含有n個關(guān)鍵字；所有的葉結(jié)點包含了全部關(guān)鍵字的信息，及指向這些關(guān)鍵字記錄的指針，且葉結(jié)點本身依關(guān)鍵字從小到大排列。所有的非終端結(jié)點可看成是索引部分，結(jié)點中僅含有其子樹中根結(jié)點的最大/最小關(guān)鍵字。第五十九頁，共107頁。2.示例（一棵3階B＋樹及查找過程）59971544597297101521374451596272859197rootsqt第六十頁，共107頁。小結(jié)：比較式查找法計算式查找法基于線性表的查找法（靜態(tài)查找）基于樹的查找法（動態(tài)查找）——HASH查找法順序查找法折半查找法分塊查找法二叉排序樹平衡二叉樹B－樹B＋樹第六十一頁，共107頁。9.3哈希表9.3.1什么是哈希表9.3.2哈希函數(shù)的構(gòu)造方法9.3.3處理沖突的方法9.3.4哈希表的查找及其分析第六十二頁，共107頁。9.3.1什么是哈希表HASH查找法又稱散列法、雜湊法或關(guān)鍵字地址計算法等；相應(yīng)的表稱為哈希表。1.基本思想

H(key)關(guān)鍵字集合地址集合(0..m－1)Hkey第六十三頁，共107頁。9.3.1什么是哈希表2.哈希函數(shù)哈希函數(shù)是一個映像；設(shè)置一個長為m的表A，用函數(shù)H把數(shù)據(jù)集合中的n個記錄的關(guān)鍵字盡可能唯一地轉(zhuǎn)換成0～m－1范圍的數(shù)值，即對集合中的任意關(guān)鍵字key有0≤H(key)≤m－1。第六十四頁，共107頁。9.3.1什么是哈希表例1：若將學(xué)生信息按如下方式存入計算機(jī)，如：將21的所有信息存入A[01]單元；將22的所有信息存入A[02]單元；……將21的所有信息存入A[31]單元。則：欲查找學(xué)號為26的信息，便可直接訪問A[16]！第六十五頁，共107頁。9.3.1什么是哈希表例2：有6個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。(1)若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結(jié)構(gòu)圖。地址…9…11…14…232425…39…內(nèi)容9111423242539明顯缺點：空間效率低如何解決？第六十六頁，共107頁。9.3.1什么是哈希表(2)選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7關(guān)鍵字集合：（14，23，39，9，25，11）。通過哈希函數(shù)對6個元素建立哈希表：2596個元素用7個地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！地址01234567內(nèi)容142339第六十七頁，共107頁。9.3.1什么是哈希表3.哈希沖突通常情況下，關(guān)鍵字的取值范圍遠(yuǎn)遠(yuǎn)超過哈希表的地址，因而可能出現(xiàn)不同的關(guān)鍵字得到相同的哈希函數(shù)值，即：key1≠key2，而H(key1)＝H(key2)，這種現(xiàn)象稱為哈希沖突。對于哈希表來說，最理想的情況是沒有沖突，但一般情況下，哈希函數(shù)是一個壓縮映射，故沖突不可完全避免。第六十八頁，共107頁。9.3.1什么是哈希表綜上所述，哈希表的設(shè)計主要包括如下三個方向的內(nèi)容：（1）確定哈希表的空間范圍，即確定哈希函數(shù)的值域；（2）構(gòu)造好的哈希函數(shù)；所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度；所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址內(nèi)集中并大致均勻分布，以減少空間浪費(fèi)。（3）制定一個好的解決沖突的方案第六十九頁，共107頁。9.3.2哈希函數(shù)的構(gòu)造方法一、直接定址法二、數(shù)字分析法三、平方取中法四、折疊法五、除留余數(shù)法第七十頁，共107頁。一、直接定址法1.定義：所謂直接定址法是指取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。即：

H(key)＝a×key＋b（其中a,b為常數(shù)）2.特點：優(yōu)點：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突。缺點：要占用連續(xù)地址空間，空間效率低。第七十一頁，共107頁。二、數(shù)字分析法定義選用關(guān)鍵字的某幾位組合成哈希地址。選用原則應(yīng)當(dāng)是：各種符號在該位上出現(xiàn)的頻率大致相同。例：有一組（80個）關(guān)鍵碼，其樣式如下：34705243491487348269634852703486305349805834796713473919位號：①②③④⑤⑥⑦第七十二頁，共107頁。二、數(shù)字分析法特點：該法需要事先知道所有關(guān)鍵字或大多數(shù)關(guān)鍵字的值，對關(guān)鍵字的各位進(jìn)行分析，丟掉分布不均勻的位值，留下分布較均勻的位值構(gòu)造其哈希函數(shù)。第七十三頁，共107頁。三、平方取中法定義：取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。即：

H(key)=“key2的中間幾位”如：第七十四頁，共107頁。四、折疊法定義根據(jù)哈希表長將關(guān)鍵字分成盡可能等長的若干段（最后一部分位數(shù)可以短些），然后將這幾段的值相加，并將高位的進(jìn)位舍掉，所得結(jié)果為其哈希地址。分段疊加方法法1：移位疊加─將各部分的最后一位對齊相加。法2：折疊疊加─從一端向另一端沿分割界來回折疊后，最后一位對齊相加。適用于：關(guān)鍵字位數(shù)較多且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況。第七十五頁，共107頁。四、折疊法例如：23034712020+)11052330647211020+)

907(a)移位疊加(b)折疊疊加

第七十六頁，共107頁。五、隨機(jī)函數(shù)法采用一個偽隨機(jī)函數(shù)作哈希函數(shù)，即

H(key)＝random(key)適用于：關(guān)鍵字長度不等的情況，造表和查找都很方便。第七十七頁，共107頁。六、除留余數(shù)法

H(key)=key%p(0＜p≤m)該法產(chǎn)生的哈希函數(shù)的好壞取決于p的選取。討論：p取某個整數(shù)d的i次冪用p對關(guān)鍵字取余，只留下關(guān)鍵字最低的i位d進(jìn)制數(shù)，等于將關(guān)鍵字的高位去掉，于是高位不同而低i位相同的關(guān)鍵字均為同義詞，故發(fā)生沖突的可能性大。p為偶數(shù)則所有的奇關(guān)鍵字被映射到奇地址，而所有的偶關(guān)鍵字被映射到偶地址，故很可能不均勻。第七十八頁，共107頁。key33304548422439H(key)30031299六、除留余數(shù)法若p為奇數(shù)并有質(zhì)因子，即p＝q×f，那么所有含有q或f因子的關(guān)鍵字的哈希地址均為q或f的倍數(shù)。如p＝15,則含有因子3的關(guān)鍵字對15取模的哈希地址均為3的倍數(shù)。第七十九頁，共107頁。六、除留余數(shù)法實踐證明：p取不超過哈希表長的最大質(zhì)數(shù)；或是不包含小于20的質(zhì)因子的合數(shù)，這樣可以減少沖突出現(xiàn)的可能性。第八十頁，共107頁。六、除留余數(shù)法例：設(shè)有如下關(guān)鍵字集合： {19,14,23,01,68,20,84,27,55,11,10,79}，若哈希表長為15，則采用除留余數(shù)法構(gòu)造哈希函數(shù)為：

H(key)=key%13key191423016820842755111079H(key)611013761311101第八十一頁，共107頁。9.3.3哈希沖突的解決方法一、開放定址法二、再哈希法三、鏈地址法四、建立一個公共溢出區(qū)第八十二頁，共107頁。一、開放定址法設(shè)計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。即：Hi＝(H(key)＋di)%m

其中：i＝1,2,…,k(k≤m－1))（d1,d2,…,dm－1）為增量序列m為哈希表長度第八十三頁，共107頁。一、開放定址法具體實現(xiàn)的幾種方案線性探測再散列 di＝1,2,3,m－1二次探測再散列 di＝12,－12,22,－22,…，±k2偽隨機(jī)探測再散列 di＝偽隨機(jī)探測再散列第八十四頁，共107頁。key191423016820842755111079H(key)611013761311101一、開放定址法例1：關(guān)鍵字集合為：{19,14,23,01,68,20,84,27,55,11,10,79}，設(shè)：哈希表表長為m=15；哈希函數(shù)為Hash(key)=key％13；則：關(guān)鍵字的直接哈希地址為：第八十五頁，共107頁。一、開放定址法（1）擬用線性探測再散列處理沖突：0123456789101112131401234567891011121314140168275519208479231110哈希表建立如下：key191423016820842755111079H(key)611013761311101第八十六頁，共107頁。一、開放定址法討論：線性探測法的優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；線性探測法的缺點：可能出現(xiàn)二次“聚集”，降低查找效率。解決方案：可采用二次探測法或偽隨機(jī)探測法，以改善“二次聚集”問題。第八十七頁，共107頁。一、開放定址法（2）擬用二次探測再散列處理沖突：0123456789101112131401234567891011121314271401685584192010231179哈希表建立如下：key191423016820842755111079H(key)611013761311101第八十八頁，共107頁。一、開放定址法（3）偽隨機(jī)探測再散列

若di＝偽隨機(jī)序列，就稱為偽隨機(jī)探測再散列。第八十九頁，共107頁。二、再哈希法 Hi=RHi(key)

i＝1,2,…,k注：RHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時就計算另一個哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點：不易產(chǎn)生“聚集”；缺點：需要定義多個不同的哈希函數(shù)，并且增加了計算的時間。第九十頁，共107頁。三、鏈地址法基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，p個哈希地址就設(shè)p個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)。定義：LinkListChainHash[p];例：關(guān)鍵字集合為：{19,14,23,01,68,20,84,27,55,11,10,79}，設(shè)：哈希表表長為m=15；哈希函數(shù)為Hash(key)=key％13；則:擬采用鏈地址法解決沖突所構(gòu)造的哈希表如下：第九十一頁，共107頁。三、鏈地址法第九十二頁，共107頁。四、建立一個公共溢出區(qū)基本思路：除設(shè)計哈?；颈硪酝?，另外設(shè)立一個溢出向量表，將所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。第九十三頁，共107頁。9.3.4哈希表的查找過程及分析一、哈希表的查找過程及示例二、哈希表的查找分析第九十四頁，共107頁。TA[i]

為空？i=H（key)A[i].key==key?i＝根據(jù)沖突解決方法獲得下一個地址失敗成功TFF一、哈希表的查找過程及示例查找過程的流程圖第九十五頁，共107頁。一、哈希表的查找過程及示例查找效率的度量標(biāo)準(zhǔn)哈希查找法是一種基于計算的查找方法，但是由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進(jìn)行比較