第10章查找(文件)
【正文】 一、開放定址法 二、鏈表法 一、開放定址法 設(shè)計思路： 以發(fā)生哈希沖突的哈希地址為自變量、通過某種哈希沖突函數(shù)得到一個新的空閑的內(nèi)存單元地址 。 例 102建立數(shù)據(jù)元素集合 a的哈希表 。 除留余數(shù)法的哈希函數(shù)為： h(K) = K mod m有： h(16) = 3 h(74) = 9 h(60) = 8 h(43) = 4 h(54) = 2 h(90) = 12 h(46) = 7 h(31) = 5 h(29) = 3 h(88) = 10 h(77) = 12 h(66) = 1 h(55) = 3 方法有兩種：第一種方法是為發(fā)生哈希沖突的 不同的同義詞建立不同的單鏈表 。 并設(shè)計一個測試程序進行測試 。 typedef struct { KeyType key。 }HashItem。 }HashTable。 else { hashcurrentSize = 0。 while(hashht[j].info == Active amp。 } if(hashht[j].info == Active) return j。 else if(i != hashtableSize) { hashht[i].data = x。 } else return 0。 return 1。建立數(shù)據(jù)元素集合 a = {180,750,600,430,541,900,460}的哈希表，并分別測試哈希表長度m=13和 m=11兩種情況得到的哈希表。 } void Destroy(HashTable *hash) { free(hashht)。 if(i = 0) { hashht[i].info = Deleted。 hashcurrentSize++。 } int Insert(HashTable *hash, DataType x) { int i = Find(hash, x)。 hashht[j]. != ) { j = (j + 1) % hashtableSize。 } } int Find(HashTable *hash, DataType x) { int i = % hashtableSize。 hashht = (HashItem *)malloc(sizeof(HashItem)*mSize)。 int tableSize。 typedef struct { DataType data。 結(jié)構(gòu)體 HashItem由數(shù)據(jù)元素和表項狀態(tài)兩部分組成 ， 其中數(shù)據(jù)元素僅包括一個關(guān)鍵字域 ， 表項狀態(tài)的數(shù)據(jù)類型為枚舉類型 ， 表項狀態(tài)域有 Empty, Active和 Deleted三種狀態(tài) ， 分別表示表項的空 、 已占用和被刪除三種狀態(tài) 。 采用鏈表法的第一種方法建立的哈希表存儲結(jié)構(gòu) 如下圖所示 link data 下標 0 66 1 54 2 16 3 43 4 31 5 6 46 7 60 8 74 9 88 10 11 90 12 29 55 77 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ data next 4 哈希表設(shè)計 例 103編寫一組包括哈希表初始化 、 哈希表元素插入 、 哈希表元素刪除 、 哈希表查找和哈希表空間撤消操作的函數(shù) 。 要求哈希函數(shù)采用 除留余數(shù)法 ，解決沖突方法采用 鏈表法 。 (2)平方探查法 (3)偽隨機數(shù)法 ??????????? )11(m o d)2()(110mimddKhdiii平方探查法的探查跨步很大，所以可避免出現(xiàn)堆積問題 ?????????? )11(m o d)()(10mimRddKhdii偽隨機數(shù)法的探查跨步是隨機的，也可避免出現(xiàn)堆積問題 非同義詞沖突： 這種由于解決 同義詞沖突而引起沖突 稱作 非同義詞沖突 。 (3)與解決哈希沖突的 哈希沖突函數(shù) 有關(guān) 。若取內(nèi)存單元個數(shù) m為 13，取哈希函數(shù) h(K)為： h(K) = K mod m， 即哈希地址 h(K)為關(guān)鍵字 K除 m所得的余數(shù)，則有： h(180) = 11 h(750) = 9 h(600) = 2 h(430) = 1 h(541) = 8 h(900) = 3 h(460) = 5 若取內(nèi)存單元個數(shù) m為 11，仍取哈希函數(shù) h(K)為： h(K) = K mod m， 則有： h(180) = 4 h(750) = 2 h(600) = 6 h(430) = 1 h(541) = 3 h(900) = 9 h(460) = 9 此時 h(460) =h(900) = 9， 因此存在哈希沖突。 為什么？ 例 101 建立數(shù)據(jù)元素集合 a的哈希表 , a = {180,750,600,430,541,900,460},并比較 m取值不同時的哈希沖突情況。 這種具有 不同關(guān)鍵字 而具有 相同哈希地址 的數(shù)據(jù)元素稱作 “ 同義詞 ” ， 由同義詞引起的沖突稱作 同義詞沖突 。其過程如圖 (e)所示 100 20 40 189 5 10 25 60 120 132 200 (e)刪去 189后的狀態(tài) 哈希表 哈希函數(shù)： 數(shù)據(jù)元素的關(guān)鍵字和該數(shù)據(jù)元素的存放位置之間的映射函數(shù) 哈希表： 通過哈希函數(shù)來確定數(shù)據(jù)元素存放位置的一種特殊表結(jié)構(gòu)。其過程如下圖 (b)所示 100 20 60 120 180 5 10 25 40 80 110 116 132 189 200 100 20 60 120 180 5 10 25 40 80 116 132 189 200 (a)初始狀態(tài) (b)刪去 110后的狀態(tài) （ b） 假如要刪除關(guān)鍵字結(jié)點的關(guān)鍵字個數(shù) n等于 m/2+1， 說明刪去該關(guān)鍵字
公司管理相關(guān)推薦
鄂ICP備17016276號-1