數(shù)據(jù)結(jié)構(gòu)第七章查找-資料下載頁
2025-05-13 21:27本頁面
【正文】 d+22 ， … ，或表示為（ d+i2） % m （ 0≤i≤m1） 平方探查法是一種較好的處理沖突的方法，它 能夠減少堆積現(xiàn)象的發(fā)生 。它的缺點(diǎn)是 不能探查到散列表上的所有單元 ，但至少能探查到一半單元。不過在實(shí)際應(yīng)用中，能探查到一半單元也就足夠了，若探查到一半單元仍找不到一個(gè)空閑單元，表明此散列表太滿應(yīng)該重新建立。 散列表及其查找 這種方法使用兩個(gè)散列函數(shù) H1和 H2，其中 H1和前面的 H（ K）一樣，是以關(guān)鍵字為自變量產(chǎn)生一個(gè) 0至 m1之間的數(shù)作為散列地址， H2也是以關(guān)鍵字為自變量，產(chǎn)生一個(gè) 1至m1之間并和 m互素的數(shù)（即 m 不能被該數(shù)整除）作為探查序列的地址增量（即步長），雙散列函數(shù)的探查序列為 d0=H1（ K） di=（ di1+H2（ K）） % m （ 1≤i≤m1） 散列表及其查找 （ 3） 雙散列函數(shù)探查法 2. 鏈接法 鏈接法（又叫鏈地址法）就是把發(fā)生沖突的同義詞元素用單鏈表鏈接起來的方法。它需要在散列表的每個(gè)單元中增加一個(gè)指針域，用來存儲由發(fā)生沖突的同義詞元素所構(gòu)成的單鏈表的表頭結(jié)點(diǎn)指針。 散列表及其查找 單鏈表中的結(jié)點(diǎn)可以是靜態(tài)結(jié)點(diǎn)也可以是動態(tài)結(jié)點(diǎn)，相應(yīng)的鏈接法被稱為 靜態(tài)鏈接法 和 動態(tài)鏈接法 。 靜態(tài)鏈接法： 首先要把整個(gè)散列表分為基本區(qū)和溢出區(qū) ( 即鏈接區(qū) )，按照元素的關(guān)鍵字計(jì)算出的散列地址 d被存儲在基本區(qū)上，若發(fā)生沖突就從溢出區(qū)中取出一個(gè)空結(jié)點(diǎn)，把對應(yīng)的元素存入該結(jié)點(diǎn)的值域，再把它鏈接到下標(biāo)為 d的單鏈表上。 動態(tài)鏈接法（無基本區(qū)）： 當(dāng)沖突發(fā)生時(shí)，首先產(chǎn)生一個(gè)新結(jié)點(diǎn)，把待插入元素存入該結(jié)點(diǎn)的值域，然后再把它鏈接到具有同義詞結(jié)點(diǎn)的單鏈表中。 2. 鏈接法 (將所有哈希地址 相同的記錄 都鏈接在同一鏈表中 ) 0 1 2 3 4 5 6 14 1 36 19 82 23 11 68 55 ? ? ? ? ? ? ? ASL=(6 1+2 2+3)/9=13/9 例如 : 關(guān)鍵字集合 { 19, 1, 23, 14, 55, 68, 11, 82, 36 } 哈希函數(shù)為 H(key)=key ％ 7 〔 動態(tài)鏈接法 〕 2. 鏈接法 什么是裝填因子？？ 由于發(fā)生的沖突次數(shù)與表的填滿程度直接有關(guān)，所以引進(jìn)裝填因子 α（ α 1） : α= 表中已有的記錄數(shù) / 表的長度 散列表及其查找 例： 已知一組關(guān)鍵字為（ 26， 36， 41， 38， 44， 15，68， 12， 6， 51， 25），分別用線性探查法和鏈接法解決散列沖突。構(gòu)造這組關(guān)鍵字的散列表，散列函數(shù) H(K)=K % P。 令裝填因子 α= 。則散列表長 m = n/α= 11/≈ ，取整 15，即散列表為 HT［ 0..14］。 H（ K） = K % P中， P取接近 14的最大素?cái)?shù) 13，即散列函數(shù)為 H（ K） = K % 13。 散列表及其查找 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 41 44 36 38 1 1 1 1 1 存入 2 3 4 3 44后的散列表 （ 1）散列表用順序表實(shí)現(xiàn)，線性探查法解決沖突。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 41 15 68 44 6 36 38 12 51 1 1 2 2 1 1 1 1 2 3 存入 51后的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 25 41 15 68 44 6 36 38 12 51 1 5 1 2 2 1 1 1 1 2 3 存入 25后的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 41 15 68 44 36 38 12 1 1 2 2 1 1 1 2 存入 1 6 12后的散列表 散列表及其查找 （ 2）散列表用鏈表實(shí)現(xiàn)，用動態(tài)鏈接地址法解決散列沖突。 練習(xí) 設(shè)散列表的長度為 13，散列函數(shù)為 H(K) = K % 13，給定的 關(guān)鍵字序列為 19， 14， 23， 1， 68， 20， 84， 27， 55， 11， 10， 79。試畫出分別用線性探查法和鏈接法解決沖突時(shí) 所構(gòu)造的散列表，并求等概率下這兩種方法查找成功的平均 查找長度。 1. 查找是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。在許多軟件系統(tǒng)中最耗時(shí)間的部分是查找。因此，研究高效的查找方法是本章的重點(diǎn)。 2. 本章的基本內(nèi)容是 線性表 的查找（順序查找、二分法查找和分塊查找），順序查找比較慢，但適用面廣 。二分法查找速度快，但必須是有序表 。分塊查找是二者的折中方法。 3. 前面三種查找方法是基于比較的查找方法，而 散列法 是希望不經(jīng)過任何比較，一次存取便能得到所查的記錄，但由于 沖突 是不可避免的，解決沖突將也是散列法的一個(gè)主要問題，可以通過 開放地址法 或 鏈接法 解決沖突，每種方法又有多種實(shí)現(xiàn)方案 本章小結(jié)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1