第九章查找數(shù)據(jù)結(jié)構(gòu)主講：岳靜

2第九章查找9.1靜態(tài)查找表及查找算法順序查找折半查找9.3哈希表及查找算法3幾個基本概念查找表關(guān)鍵字查找靜態(tài)查找動態(tài)查找由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素記錄中某個數(shù)據(jù)項(xiàng)的值，可用來識別一個記錄查找成功→若表中存在特定元素，稱查找成功查找不成功4幾個基本概念(續(xù))查找算法的性能查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過程。用比較次數(shù)的平均值來評估算法的優(yōu)劣。平均查找長度ASL(AverageSearchLength)?=×=niPiASL1Ci5幾個基本概念(續(xù))ASL值越小，時(shí)間效率越高請同學(xué)們思考，如何利用ASL的結(jié)果判定查找算法的優(yōu)劣?=×=niPiASL1Ci6靜態(tài)查找表1順序表查找2有序表查找9.2.1順序查找法順序查找法的特點(diǎn)是：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。

212569102246√81順序查找約定從表中最后一個記錄開始查找，逐個將記錄的關(guān)鍵字和給定值進(jìn)行比較若存在某記錄的關(guān)鍵字等于給定值查找成功：查找失敗：

直至第一個記錄，關(guān)鍵字都不與給定值相等9不設(shè)置監(jiān)視哨的順序查找算法intSeqSearch（RecordListl,KeyTypek）/*不用監(jiān)視哨法，在順序表中查找關(guān)鍵字等于k的元素*/{i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)return（i）elsereturn(0);}循環(huán)條件i>=1判斷查找是否越界。設(shè)置哨崗2125691022466111順序查找(續(xù))算法9.1intSearch_Seq(SStableST,KeyTypekey){

ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}哨兵相對于傳統(tǒng)順序查找算法有何優(yōu)勢？順序表給定值intSearch_Seq(SStableST,KeyTypekey){for(i=ST.length;i>=1;--i);if(EQ(ST.elem[i].key,key))break;returni;}121順序查找(續(xù))算法性能分析?=×=niPiASL1Ci假設(shè)n=ST.length，每個記錄查找的概率相等查找成功ASL=(n+1)/2131順序查找(續(xù))當(dāng)表中查找記錄的概率不相同時(shí)，如何考慮提高順序查找的效率？將記錄按查找概率進(jìn)行排序，將查找概率高的排在最靠近開始查找的一端141順序查找(續(xù))順序查找算法的特點(diǎn)算法簡單適應(yīng)面廣效率低152有序表查找折半查找(BinarySearch)51319213756請同學(xué)回憶折半查找(二分法)的查找算法查找給定值5616折半查找的算法開始Low=1High=l.lengthLow<=highMid=(low+high)/2k==l.r[mid].keyReturnmidYYReturn0Nk<l.r[mid].keyNHigh=mid-1low=mid+1YN17折半查找算法5131921375619193737565621513描述查找過程的判定樹查找成功時(shí)比較的次數(shù)<=判定樹的深度查找不成功的比較次數(shù)？18外部結(jié)點(diǎn)(5,13)(13,19)折半查找算法5131921375619193737565621513查找成功時(shí)比較的次數(shù)查找不成功的比較次數(shù)<=判定樹的深度<5(19,21)(21,37)(37,56)>5619折半查找算法(續(xù))ASL假設(shè)記錄個數(shù)為n=2h-1折半查找的判定樹為深度為h的滿二叉樹假設(shè)每個記錄的查找概率相同h

表示二叉樹的深度j

表示當(dāng)前層次/查找過程中比較的次數(shù)20折半查找算法(續(xù))特點(diǎn)查找效率較順序查找高但只適合有序表，且限于順序存儲結(jié)構(gòu)是否任何情況下都可用折半查找方法?哈希表基本思想建立關(guān)鍵字與其存儲位置的對應(yīng)關(guān)系，或者說，由關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。優(yōu)點(diǎn)查找速度極快O(1)，查找效率與元素個數(shù)無關(guān)！22哈希表(續(xù))例1：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；

……

將2001011810231的所有信息存入V[31]單元。欲查找學(xué)號為2001011810216的信息，便可直接訪問V[16]！23哈希表(續(xù))

有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H(k)＝k，請畫出存儲結(jié)構(gòu)圖。H(k)稱為散列函數(shù)解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，……，對應(yīng)散列存儲表（哈希表）如下：地址…9…11…14…232425…39…內(nèi)顯缺點(diǎn)：空間效率低24哈希表(續(xù))哈希函數(shù)的構(gòu)造方法直接定址法數(shù)字分析法折疊法除留余數(shù)法隨機(jī)法…哈希表：根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映像到一個有限地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表就稱為哈希表，這一映像過程稱為哈希造表或散列，所得地址為哈希地址或散列地址。25哈希函數(shù)的構(gòu)造方法直接定址法Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵字key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。26哈希函數(shù)的構(gòu)造方法數(shù)字分析法特點(diǎn)：選用關(guān)鍵字的某幾位組合成哈希地址。選用原則是：各種符號在該位上出現(xiàn)的頻率大致相同。2734705243491487348269634852703486305349805834796713473919例：有一組（例如80個）關(guān)鍵字，其樣式如下：討論：①第1、2位均是“3和4”，第3位也只有“

7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅80個），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。數(shù)字分析法（舉例）28哈希函數(shù)的構(gòu)造方法除留余數(shù)法Hash(key)=keymodp(設(shè)哈希表長度為m)特點(diǎn)：以關(guān)鍵字除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的m？技巧：取p≤m且為質(zhì)數(shù)（一般取不大于m的最大質(zhì)數(shù)）29哈希表(續(xù))有6個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過哈希函數(shù)對6個元素建立哈希表：253923914110123456例有沖突！30哈希表(續(xù))沖突的解決沖突不可避免，只能盡可能減少1構(gòu)造一個較好的哈希函數(shù)函數(shù)簡單，以便提高轉(zhuǎn)換速度所選函數(shù)對關(guān)鍵字計(jì)算出的地址，應(yīng)在哈希表中并大致均勻分布，以減少空間浪費(fèi)2制定一個較好的解決沖突的方案31哈希表(續(xù))哈希沖突的解決方法開放定址法（開地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數(shù)法）建立一個公共溢出區(qū)32哈希沖突的解決方法1開放定址法（開地址法）設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。33具體實(shí)現(xiàn)：Hi=(Hash(k)+di)modm(1≤i<m)

其中：

Hash(k)為哈希函數(shù)

m為哈希表長度

di

為增量序列1，2，…m-1

（1）線性探測法含義：一旦沖突，就找附近（下一個）空地址存入。開放定址法（開地址法）34關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用線性探測法處理沖突。建哈希表如下：012345678910291116922283例47735線性探測法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；線性探測法的缺點(diǎn)：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測法或偽隨機(jī)探測法，以改善“堆積”問題。討論：36仍舉上例，改用二次探測法處理沖突，建表如下：012345678910112234792167298△▲△△注：只有3這個關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod

11=2，找到空的哈希地址，存入。（2）二次探測法Hi=(Hash(k)±di)modm其中：Hash(k)為哈希函數(shù)

di為增量序列

12，-12，22，-22，…37哈希沖突的解決方法2鏈地址法（拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，m個哈希地址就設(shè)m個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)。38

設(shè){47,7,29,11,16,92,22,8,3,50,37,89}的哈希函數(shù)為：Hash(key)=keymod11，用拉鏈法處理沖突，則建表如右圖所示。

例：

01234567891022118934737922971650810有沖突的元素可以插在表尾,也可以插在表頭。鏈地址法（拉鏈法）39哈希沖突的解決方法3再哈希法（雙哈希函數(shù)法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時(shí)就計(jì)算另一個哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點(diǎn)：不易產(chǎn)生聚集；缺點(diǎn)：增加了計(jì)算時(shí)間。40哈希沖突的解決方法4建立一個公共溢出區(qū)思路：除設(shè)立哈?；颈硗?，另設(shè)立一個溢出向量表。 所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。41哈希表的查找及分析明確：散列函數(shù)沒有“萬能”通式，要根據(jù)元素集合的特性而分別構(gòu)造。討論：哈希查找的速度是否為真正的O（1）？不是。由于沖突的產(chǎn)生，使得哈希表的查找過程仍然要進(jìn)行比較，仍然要以平均查找長度ASL來衡量。一般地，ASL依賴于哈希表的裝填因子,它標(biāo)志著哈希表的裝滿程度。裝填因子：哈希表中已經(jīng)被占用的空間（哈希表中的記錄數(shù)）與哈希表整個空間（哈希表的長度）的比。即：0≤≤1越大，表中記錄數(shù)越