數(shù)據(jù)結(jié)構(gòu)第七章查找(編輯修改稿)
2025-06-18 21:27 本頁面
【文章內(nèi)容簡介】 Ew=（ s+1） /2 ， Eb =（ b+1） /2 ，所以 ASL=Eb+Ew=（ b+s） /2+1=（ n/s+s） /2+1 當(dāng) s= 時， ASL取最小值，這時 ASL= +1。 分塊查找 n n分塊查找的速度比順序查找要快得多，但又不如二分法查找。如果線性表元素個數(shù)很多，且被分成的塊數(shù) b 很大時，對索引表的查找可以采用二分法查找，還能進(jìn)一步提高速度。 優(yōu)點： 在線性表中插入或刪除一個元素時，只要找到元素應(yīng)屬于的塊，然后在塊內(nèi)進(jìn)行插入和刪除運算。由于塊內(nèi)元素的存放是任意的，所以插入和刪除比較容易，不需要移動大量元素。 分塊查找 練習(xí) ? 采用分塊查找時，若線性表中共有 625個元素，查找每個元素的概率相同，假設(shè)采用順序查找來確定結(jié)點所在的塊時，每塊應(yīng)分為多少個結(jié)點最佳。 【 答案 】 根據(jù)公式 s =√n = √625 = 25， 每塊應(yīng)分為 25個結(jié)點最佳。 【 三種查找方法比較 】 順序查找 折半查找 分塊查找 平均查找長度 最大 等概率查找最小 次小 表的結(jié)構(gòu) 有序表、無序表均可 僅適用于有序表 表中元素逐段有序 表的存儲結(jié)構(gòu) 順序、鏈?zhǔn)?結(jié)構(gòu)均可 僅適用于順序存儲 順序、鏈?zhǔn)骄?，索引表順序存? 散列表及其查找 散列表的概念 散列法亦稱 哈希（ HASH）法 ，是在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系 H，使每個關(guān)鍵字與一個惟一的存儲位置相對應(yīng)。 散列方法不同于順序查找、二分查找。它不以關(guān)鍵字的比較為基本操作，而采用 直接尋址技術(shù) 。在理想情況下，無須任何比較就可以找到待查關(guān)鍵字，查找的期望時間為 O(1)。 散列表及其查找 基本思想 :以記錄中關(guān)鍵字的值為自變量，通過確定的函數(shù) H（散列函數(shù)）進(jìn)行計算，求出對應(yīng)的函數(shù)值，把這個函數(shù)值作為存儲地址，將該記錄（或 記錄的關(guān)鍵字）存放在這個位置上，查找時仍按這個確定的函數(shù) H進(jìn)行計算，獲得的將是待查的關(guān)鍵字所在記錄的存儲地址。 此表建好后，就可據(jù)此表查出任一關(guān)鍵字值的對應(yīng)位置。 散列表及其查找 U（全集）：可能出現(xiàn)的關(guān)鍵字集合 K：實際存儲的關(guān)鍵字集合 T： 散列表 h： 散列函數(shù) h(ki)：關(guān)鍵字為 ki結(jié)點的存儲地址，即 散列值 （散列地址） 將結(jié)點按照其關(guān)鍵字的散列地址存儲到散列表中的過程就是 散列 ? 【 例如 】 建立一張全國 30個地區(qū)的各民族統(tǒng)計表 – H1：取鍵值中第一個字母在字母表中的序號作為散列函數(shù)。 – H2：先求鍵值中首尾兩個字母在字母表中的序號之和，如果這個和大于 30，則減去 30。 BEJING SHANXI SHANGHAI SHAN DONG HENAN K 北京 山西 上海 山東 河南 H1(K) 02 19 19 19 08 H2(K) 09 28 28 26 22 散列表及其查找 散列表及其查找 由此可見 : （ 1）散列函數(shù)是一個映象，因此散列函數(shù)的設(shè)定很靈活，只要使得任何鍵值由此所得的散列函數(shù)值都落在表長允許的范圍之內(nèi)即可 。 （ 2）對于不同的鍵值可能得到相同的散列地址， 即K1≠K2，而 H（ K1） =H（ K2），這種現(xiàn)象稱為 散列沖突 。具有相同函數(shù)值的鍵值稱該 散列函數(shù)的同義詞 。 在一般的情況下，沖突只能盡可能地減少，而不能完全避免。 散列法查找歸結(jié)為如下兩個方面 : （ 1）對給定的一組關(guān)鍵字構(gòu)造一個計算簡單且散列均勻的散列函數(shù) 。 （ 2）擬訂一個較好解決沖突的方法。 散列表及其查找 散列函數(shù)的構(gòu)造方法 1. 直接定址法 取關(guān)鍵字的某個線性函數(shù)值為散列地址，即 : H(key) = key 或 H(key) = a key + b （ a和 b為常數(shù)） 由于直接定址法所得地址集合和關(guān)鍵字大小相同，因此，關(guān)鍵字不會產(chǎn)生沖突，但實際應(yīng)用中能夠使用這種散列函數(shù)的情況很少。 散列表及其查找 2. 數(shù)字分析法 鍵值的位數(shù)比存儲區(qū)域的地址碼的位數(shù)多，在這種情況下可以對鍵值的各位進(jìn)行分析，丟掉分布不均勻的位，留下分布均勻的位作為地址。 適用于 關(guān)鍵字集中的集合，且關(guān)鍵字是事先知道的。 散列表及其查找 若 以下標(biāo)為 000 ~ 999 的 順序表 表示之。 【 例如 】 為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為 xx000 ~ xx999 (前兩位為年份 )。 則查找過程可以簡單進(jìn)行：取給定值（學(xué)號）的后三位， 不需要經(jīng)過比較 便可 直接從順序表中找到待查關(guān)鍵字。 2. 數(shù)字分析法 如 :關(guān)鍵字序列 9 9 3 4 6 5 3 2 9 9 3 7 2 2 4 2 9 9 3 8 7 4 3 3 9 9 3 0 1 3 6 7 9 9 3 2 2 8 1 7 9 9 3 3 8 9 6 7
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1