數(shù)據(jù)結(jié)構(gòu)1七查找

1、第七章 查找查找也叫檢索，是根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它可以標(biāo)識一個數(shù)據(jù)元素查找方法評價查找速度占用存儲空間多少算法本身復(fù)雜程度平均查找長度ASL(Average Search Length)：為確定記錄在表中的位置，需和給定值進行比較的關(guān)鍵字的個數(shù)的期望值叫查找算法的7.1 順序查找查找過程：從表的一端開始逐個進行記錄的關(guān)鍵字和給定值的比較算法描述Ch7_1.ci例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464監(jiān)視哨iiii比較次數(shù)=5比較次

2、數(shù)：查找第n個元素： 1查找第n-1個元素：2.查找第1個元素： n查找第i個元素： n+1-i查找失敗： n+1順序查找方法的ASL7.2 折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲結(jié)構(gòu)的有序表算法實現(xiàn)設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k=rmid.key，查找成功若krmid.key，則low=mid+1重復(fù)上述操作，直至lowhigh時，查找失敗算法描述lowhighmid例 1 2 3 4 5 6 7 8 9

3、 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmidCh7_2.c例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lo

4、whighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定樹：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法評價判定樹：描述查找過程的二叉樹叫有n個結(jié)點的判定樹的深度為

5、log2n+1折半查找法在查找過程中進行的比較次數(shù)最多不超過其判定樹的深度折半查找的ASL7.3 分塊查找查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實現(xiàn)用數(shù)組存放待查記錄,每個數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個索引表結(jié)點含有最大關(guān)鍵字域和指向本塊第一個結(jié)點的指針?biāo)惴枋鯟h7_3.c1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38分塊查找方法評價AS

6、L最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找7.4 哈希查找基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法定義哈希函數(shù)在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系叫哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象哈希函數(shù)可寫成：addr(ai)=H(ki)ai是表中的一個元素addr(ai)是ai的存儲地址ki是ai的關(guān)鍵字關(guān)鍵字集合存儲地址集合hash哈希表應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中

7、的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希查找又叫散列查找，利用哈希函數(shù)進行查找的過程叫例 30個地區(qū)的各民族人口統(tǒng)計表編號 地區(qū)別 總?cè)丝?漢族 回族.1 北京2 上海.以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫同義詞：具有相同函數(shù)值的兩

8、個關(guān)鍵字，叫該哈希函數(shù)的哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處理沖突的方法哈希函數(shù)的構(gòu)造方法直接定址法構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)作哈希地址，即H(key)=key 或 H(key)=akey+b特點直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突實際中能用這種哈希函數(shù)的情況很少數(shù)字分析法構(gòu)造：對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或其組合作哈希地址適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例 有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28

9、 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機所以：取任意兩位或兩位 與另兩位的疊加作哈希地址平方取中法構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址適于不知道全部關(guān)鍵字情況折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例

10、 關(guān)鍵字為 ： ，哈希地址位數(shù)為45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key MOD p，pm特點簡單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞隨機數(shù)法構(gòu)造：取關(guān)鍵字的隨機函數(shù)值作哈希地址，即H(key)=random(key)適于關(guān)鍵字長度不等的情況選取哈希函數(shù)，考慮以下因素：計算哈希函數(shù)所需時間關(guān)鍵字長度哈希表長度（哈希地址范圍）關(guān)鍵字分布情

11、況記錄的查找頻率處理沖突的方法開放定址法方法：當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函數(shù) m哈希表表長 di增量序列分類線性探測再散列：di=1,2,3,m-1二次探測再散列：di=1,-1,2,-2,3,k(km/2)偽隨機探測再散列：di=偽隨機數(shù)序列例 表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄， H(key)=key MOD 11,現(xiàn)有第4個記錄，其關(guān)鍵字為38， 按三種處理沖突的方法，將它填入表中0 1

12、 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 38(2) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5-1) MOD 11=4 不沖突38(3) H(38)=38 MOD 11=5 沖突 設(shè)偽隨機數(shù)序列為9，則： H1=(5+9) MOD 11=3 不沖突38再哈希法方法：構(gòu)造若干個哈希函數(shù)，當(dāng)發(fā)生沖突時，計算下一個哈希地址，即：Hi=Rhi(key) i=1,

13、2,k其中：Rhi不同的哈希函數(shù)特點：計算時間增加鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為：H(key)=key MOD 13, 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011哈希查找過程及分析哈希查找過程給定k值計算H(k)此地址為空關(guān)鍵字=k查找失敗查找成功按處理沖突方法計算HiYNYN哈希查找分析哈希查找過程仍是一個給定值與關(guān)鍵字進行比較的過程評價哈希查找效率仍要用ASL

14、哈希查找過程與給定值進行比較的關(guān)鍵字的個數(shù)取決于：哈希函數(shù)處理沖突的方法哈希表的填滿因子=表中填入的記錄數(shù)/哈希表長度例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為：H(key)=key MOD 13, 哈希表長為m=16， 設(shè)每個記錄的查找概率相等(1) 用線性探測再散列處理沖突，即Hi=(H(key)+di) MOD mH(55)=3 沖突，H1=(3+1)MOD16=4 沖突，H2=(3+2)MOD16=5H(79)=1 沖突，H1=(1+1)MOD16=2 沖突，H2=(1+2)MOD16=3 沖突，H3=(1+3)MOD16=4

15、 沖突，H4=(1+4)MOD16=5 沖突，H5=(1+5)MOD16=6 沖突，H6=(1+6)MOD16=7 沖突，H7=(1+7)MOD16=8 沖突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1 沖突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 沖突，H1=(6+1)MOD16=7 沖突，H2=(6+2)MOD16=8H(27)=1 沖突，H1=(1+1)MOD16=2 沖突，H2=(1+2)MOD16=3 沖突，H3=(1+3)MOD16=4H(11)=11H(10)=10 沖突，H1=(10+1)MOD16=11 沖突，H