數(shù)據(jù)結構課件c語言-展示頁
2025-05-26 21:43本頁面
【正文】 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. ….. ?? ? ??? ?? 分析： ?只取 8 ?只取 1 ?只取 4 ?只取 5 ????數(shù)字分布近乎隨機 所以：取 ????任意兩位或兩位 與另兩位的疊加作哈希地址 第 8章 查找 3. 平方取中法 ? 構造：取關鍵字平方后中間幾位作哈希地址 ? 適于不知道全部關鍵字情況 ? 例如，若關鍵碼 K＝ 1234，哈希表長為 1000，則有：K2=1522756，取中間 3位 227作為哈希地址。 比如：取學號某些位排定學生宿舍號。key+b 比如：統(tǒng)計 1100歲的人口，用年齡做關鍵字，哈希函授可以就取關鍵字本身。 ⑵ 制定解決沖突的方案，如果發(fā)生了沖突怎么解決。 (注意到哈希表建立的時候用哈希函數(shù)） 例 30個地區(qū)的各民族人口統(tǒng)計表 編號 地區(qū) 總人口 漢族 回族 …... 1 北京 2 上海 …... …... 以編號作關鍵字， 構造 哈希函數(shù)： H(key)=key H(1)=1 H(2)=2 以地區(qū)作關鍵字，取地區(qū) 名稱第一個拼音字母的序號 作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 第 8章 查找 5. 沖突 k1?k2， 但 H(k1)=H(k2)的現(xiàn)象叫 沖突 (Collision)，映射到同一哈希地址上的關鍵碼稱 為 “ 同義詞 ” 。 哈希函數(shù)可寫成： addr(ai)=H(ki) 其中： ai 是表中的一個元素 , addr(ai)是 ai的存儲地址 , ki 是 ai的關鍵字 第 8章 查找 ? 3 哈希表 ? 應用哈希函數(shù)，由記錄的關鍵字確定記錄在表中的 地址 ，并將記錄放入此地址，這樣構成的表叫 哈希表 ( 數(shù)組的推廣）。第 8章 查找 1 第 8章 查找 基本概念與基本運算 靜態(tài)查找表 動態(tài)查找表 1—— 樹表 動態(tài)查找表 2—— 哈希表查找 第 8章 查找 回顧 ? 1 靜態(tài)查找表查找的 ASL是？對應的時間復雜度 ? 2 動態(tài)樹表查找的 ASL，對應的時間復雜度 ? 3 一個查找算法最理想的的時間復雜度應該是什么？ ? 4 在數(shù)組中按編號查找某個元素的時間復雜度是？ ? 5 對給定的查找表（數(shù)據(jù)元素的集合）能否把它們采用特別的方法組織到數(shù)組中呢？ 第 8章 查找 把 數(shù)據(jù)元素的關鍵碼 通過 某種計算 方法直接確它在 數(shù)組中的存儲位置 ? 這樣構造的數(shù)組就是 哈希表 0 m–1 h(k1) h(k4) h(k3) U (universe of keys) k1 k2 k3 k5 k4 第 8章 查找 動態(tài)查找表 2—— 哈希表查找 ? 哈希表的概念 1. 哈希查找的基本思想 在記錄的 存儲地址 和它的 關鍵字 之間建立一個確定的 對應關系 ；這樣不經(jīng)過比較 (或進行少量比較），一次存取就能得到所查元素的查找方法。 2. 哈希函數(shù) 在記錄的關鍵字與記錄的存儲地址之間建立的一種對應關系叫 哈希函數(shù) 。 第 8章 查找 4. 哈希查找 又叫散列查找，利用哈希函數(shù)進行查找的過程叫 哈希查找。 0 m–1 h(k1) h(k4) h(k3) U (universe of keys) k1 k2 k3 k5 k4 第 8章
法律信息相關推薦
鄂ICP備17016276號-1