查找的概念順序查找折半查找分塊查找哈希查找(編輯修改稿)
2025-08-15 20:06 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 長(zhǎng)分塊查找（索引順序查找） ?查找過(guò)程：將表分成幾塊，塊內(nèi)無(wú)序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找 ?適用條件：分塊有序表 ?算法實(shí)現(xiàn) ?用數(shù)組存放待查記錄 ,每個(gè)數(shù)據(jù)元素至少含有關(guān)鍵字域 ?建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本塊第一個(gè)結(jié)點(diǎn)的指針 ?算法描述 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 索引表 查 38 ?分塊查找方法評(píng)價(jià) 2)1(l o g)2(1)(21212111)1(211ssnA S LssnsbisjbA S LsbnLLLLA S Lbssibjbswbwbbs??????????????????：用折半查找確定所在塊：用順序查找確定所在塊查找概率相等，則：記錄的個(gè)記錄，并設(shè)表中每個(gè)塊，每塊含的表平均分成若將表長(zhǎng)為均查找長(zhǎng)度—在塊中查找元素的平—塊的平均查找長(zhǎng)度—查找索引表確定所在—其中：ASL 最大 最小 兩者之間 表結(jié)構(gòu) 有序表、無(wú)序表 有序表 分塊有序表 存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 線性鏈表 順序存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 線性鏈表 查找方法比較 順序查找 折半查找 分塊查找 哈希查找 ?基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過(guò)比較，一次存取就能得到所查元素的查找方法 ?定義 ?哈希函數(shù) —— 在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系叫 ~ ?哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象 ?哈希函數(shù)可寫(xiě)成： addr(ai)=H(ki) ?ai是表中的一個(gè)元素 ?addr(ai)是 ai的存儲(chǔ)地址 ?ki是 ai的關(guān)鍵字 關(guān)鍵字 集合 存儲(chǔ)地址 集合 hash ?哈希表 —— 應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫 ~ ?哈希查找 —— 又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程叫 ~ 例 30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表 編號(hào) 地區(qū)別 總?cè)丝? 漢族 回族 …... 1 北京 2 上海 …... …... 以編號(hào)作關(guān)鍵字， 構(gòu)造 哈希函數(shù)： H(key)=key H(1)=1 H(2)=2 以地區(qū)別作關(guān)鍵字，取地區(qū) 名稱第一個(gè)拼音字母的序號(hào) 作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 從例子可見(jiàn)： ?哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可 ?沖突： key1?key2， 但 H(key1)=H(key2)的現(xiàn)象叫 ~ ?同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的 ~ ?哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免 ，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法 ?哈希函數(shù)的構(gòu)造方法 ?直接定址法 ?構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即H(key)=key 或 H(key)=akey+b ?特點(diǎn) ?直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突 ?實(shí)際中能用這種哈希函數(shù)的情況很少 ?數(shù)字分析法 ?構(gòu)造：對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址 ?適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況 例 有 80個(gè)記錄，關(guān)鍵字為 8位十進(jìn)制數(shù)，哈希地址為 2位十進(jìn)制數(shù) 8 1 3 4 6 5 3 2 8
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1