61線性查找62折半查找63分快查找64二元查找樹65散列-資料下載頁
2024-09-30 09:51本頁面
【導(dǎo)讀】設(shè)Pi為查找表中第i個(gè)記錄的概率。國家示范性軟件學(xué)院2020·
【正文】 H2(8)=(3+1)%8=4 H(34)=1+(34%7)=7(沖突 )， H1(34)=(7+1)%8=0 H(19)=1+(19%7)=6 H(21)=1+(21%7)=1 地址 0 1 2 3 4 5 6 7 Key 34 21 15 22 8 19 13 探測次數(shù) 2 1 1 2 3 1 1 哈希表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 24 (2) 使用步長為 3的線性探測法解決沖突，對(duì)應(yīng)地址為： H(13)=1+(13%7)=7 H(15)=1+(15%7)=2 H(22)=1+(22%7)=2(沖突 )， H1(22)=(2+3)%8=5 H(8)=1+(8%7)=2 (沖突 )， H1(8)=(2+3)%8=5 (仍沖突 ) H2(8)=(5+3)%8=0 H(34)=1+(34%7)=7(沖突 )， H1(34)=(7+3)%8=2 (仍沖突 ) H2(34)=(2+3)%8=5 (仍沖突 ) H3(34)=(5+3)%8=0 (仍沖突 ) H4(34)=(0+3)%8=3 H(19)=1+(19%7)=6 H(21)=1+(21%7)=1 地址 0 1 2 3 4 5 6 7 Key 8 21 15 34 22 19 13 探測次數(shù) 3 1 1 5 2 1 1 哈希表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 25 (3) 使用再哈希法解決沖突， 再哈希函數(shù)為 H(x)=1+(x%6) H(13)=1+(13%7)=7 H(15)=1+(15%7)=2 H(22)=1+(22%7)=2(沖突 )， H1(22)=1+(22%6)=5 H(8)=1+(8%7)=2 (沖突 )， H1(8)=1+(8%6)=3 H(34)=1+(34%7)=7(沖突 )， H1(34)=1+(34%6)=5 (仍沖突 ) H2(34)=1+(34%5)=5 (仍沖突 ) H3(34)=1+(34%4)=3 (仍沖突 ) H4(34)=1+(34%3)=2 (仍沖突 ) H5(34)=1+(34%2)=1 H(19)=1+(19%7)=6 H(21)=1+(21%7)=1(沖突 ) ， H1(21)=1+(21%6)=4 地址 0 1 2 3 4 5 6 7 Key 34 15 8 21 22 19 13 探測次數(shù) 6 1 2 2 2 1 1 哈希表 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 26 例 2： 已知一組記錄的鍵值為 {1， 9， 25， 11， 12， 35， 17， 29}， 請(qǐng)構(gòu)造一個(gè)散列表。 （ 1）采用除留余數(shù)法構(gòu)造散列函數(shù)，線性探測法處理沖突，要 求新插入鍵值的平均探測次數(shù)不多于 ，請(qǐng)確定散列表 的長度 m及相應(yīng)的散列函數(shù)。分別計(jì)算查找成功和查找失敗 的平均查找長度。 （ 2）采用（ 1）中的散列函數(shù)，但用鏈地址法處理沖突，構(gòu)造 散列表，分別計(jì)算查找成功和查找失敗的平均查找長度。 解： （ 1） ASLu = ≤ 得 α ≤1/2 因?yàn)? 8/m ≤1/2, 所以 m ≥ 16 取 m=16 , 散列函數(shù)為 H(key)=key%13 給定鍵值序列為 :{1,9,25,11,12,35,17,29} 散列地址為 : d:1,9,12,11,12,9,4,3 用線性探測解決沖突，見下表： )1( 1 121 ???數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 27 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Key 1 29 17 9 35 11 25 12 成功探 測次數(shù) 1 1 1 1 2 1 1 2 失敗探 測次數(shù) 1 2 1 3 2 1 1 1 1 6 5 4 3 查找成功的平均查找長度： ASLs=(6+4)/8= 查找失敗的平均查找長度： ASLu=(6 1+2+3+2+6+5+4+3)/13= (2)使用鏈地址法處理沖突構(gòu)造散列表。 查找成功的平均查找長度： ASLs=(6+4)/8= 查找失敗的平均查找長度： ASLu=(4 1+2 2)/13≈ ^ ^ ^ ^ ^ ^ ^ ^ 1 ^ 29 ^ 17 ^ ^ 25 12 ^ 35 ^ 9 0 1 2 3 4 5 6 7 8 9 10 11 12
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1