DS11查找與散列結(jié)構(gòu)

1、DS11查找與散列結(jié)構(gòu)主要內(nèi)容根本概念靜態(tài)查找表 動態(tài)查找表 哈希Hash表及其查找 查找查找表：由同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合。查找表的根本操作1) 查詢某個“特定的數(shù)據(jù)元素是否在表中2) 檢索某個“特定的數(shù)據(jù)元素的各種屬性3) 插入一個數(shù)據(jù)元素4) 刪去某個數(shù)據(jù)元素靜態(tài)查找表：只作查詢和檢索操作的查找表。動態(tài)查找表：在查找過程中同時作插入或刪除操作的查找表。 查找關(guān)鍵字：能標識一個數(shù)據(jù)元素或記錄的數(shù)據(jù)項。主關(guān)鍵字：能唯一地標識一個記錄的關(guān)鍵字。次關(guān)鍵字：用以識別假設(shè)干記錄的關(guān)鍵字。 學(xué)號 姓名 專業(yè) 年齡 20030001 李莫愁 計算機 17 20030002 高 手 計算機 18

2、 20030003 王重陽 計算機 18 20030004 張無忌 信息工程 20 20030005 高 手 信息工程 19 查找 學(xué)號 姓名 專業(yè) 年齡 20030001 李莫愁 計算機 17 20030002 高 手 計算機 18 20030003 王重陽 計算機 18 20030004 張無忌 信息工程 20 20030005 高 手 信息工程 19查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素，假設(shè)表中存在這樣的記錄，那么稱查找成功，查找結(jié)果為記錄信息或其位置；否那么稱為查找不成功，查找結(jié)果通常為0或NULL。 查找查找方法評價：平均查找長度平均查找長度A

3、SL ( Average Search Length)：為確定記錄在表中的位置，需和給定值進展比較的關(guān)鍵字的個數(shù)的期望值叫查找算法的平均查找長度。用于度量查找算法的效率時間復(fù)雜度 Ci：查找到第 i 個記錄所需的比較次數(shù) Pi：查找到第 i 個記錄的概率 平均查找長度ASL = PiCi ( Pi=1 ) 查找靜態(tài)查找在指定的表中查找某一個“特定的數(shù)據(jù)元素是否存在，檢索某一個“特定數(shù)據(jù)元素的各種屬性。動態(tài)查找在查找的過程中同時插入表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素。靜態(tài)查找順序表的查找：順序查找有序表的查找：折半查找索引順序表的查找：分塊查找靜態(tài)查找表查找表可用線性表

4、表示L1=(45,61,12,3,37,24,90,53,98,78順序查找從最后一個第一個記錄開場，逐個進展比較 查找不成功的標記 用順序表表示靜態(tài)查找表 用線性鏈表表示靜態(tài)查找表 靜態(tài)查找表第 10 頁順序表類型定義 typedef struct ElemType *elem; / 0號單元留空 int length; SSTable;靜態(tài)查找表 0 1 2 3 4 5 6 7 8 9 10 m-1 45 61 12 3 37 24 90 53 98 78ST.elemSSTable ST;10第 11 頁int Search_Seq ( SSTable ST, KeyType key )

5、 /在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。假設(shè)找到，那么函數(shù)值為該元素在表中的位置，否那么為0。 ST.elem0.key = key; / “哨兵 for ( i=ST.length; !EQ(key, ST.elemi.Key); -i )； return i; / 假設(shè)表中不存在待查元素, i=0 /Search_Seq靜態(tài)查找表 0 1 2 3 4 5 6 7 8 9 10 m-1 45 61 12 3 37 24 90 53 98 78ST.elemkey免去查找過程中每一步都要檢測整個表是否查找完畢11第 12 頁例1：在下表中查找 key = 8 的結(jié)點。靜態(tài)查找表

6、8012n-3n-2n-1nST.elem key100100713iiiiiii查找不成功，i = 08012n-3n-2n-1nST.elem key例2：在下表中查找 key = 8 的結(jié)點。100100813iii查找成功，i = n-212順序查找特點無排序要求；算法簡單；存儲構(gòu)造：順序、鏈式；效率不高 靜態(tài)查找表查找表：用有序表表示查找方法：折半查找二分查找查找過程：先確定待查記錄所在的范圍區(qū)間，然后逐步縮小范圍直到找到或找不到該記錄為止。例：有原始查找表45,61,12,3,37,24,90,53,98,78為進展折半查找，需要先進展排序： L=(3,12,24,37,45,53

7、,61,78,90,98) 靜態(tài)查找表-有序表查找例：查找 Key=24 的記錄。 靜態(tài)查找表-有序表查找 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98lowmid high 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98lowmid high 2445 2412 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 98Low highmidbool Search_Bin ( SSTable ST, KeyType key ) /在有序表ST中折半

8、查找法查找其關(guān)鍵字等于key的數(shù)據(jù)元素。假設(shè)找到，那么返回該元素在表中的位置，否那么返回false。 low=1; high=ST.length; while ( lowkey，因此令highmid1high=7mid=4low=1low=1high=3mid=2此時ST.elemmid.key5 key，因此令highmid1low=1mid=1此時ST.elemmid.key4 high查找不成功折半查找的特點要求元素按關(guān)鍵字有序。存儲構(gòu)造：順序。 靜態(tài)查找表-有序表查找查找表的組織：分塊有序，除表本身以外，尚需建立一個“索引表。查找方法：查找索引表；在數(shù)據(jù)塊內(nèi)順序查找 靜態(tài)查找表-索引順

9、序表的查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38查找方法比較 靜態(tài)查找表ASL最大最小兩者之間表構(gòu)造有序表、無序表有序表分塊有序表存儲構(gòu)造順序存儲構(gòu)造線性鏈表順序存儲構(gòu)造順序存儲構(gòu)造線性鏈表順序查找折半查找分塊查找動態(tài)查找二叉排序樹：或者是一棵空樹；或者是具有以下性質(zhì)的二叉樹： 1假設(shè)左子樹不空，那么左子樹上所有結(jié)點的值均小于根結(jié)點的值； 2假設(shè)右子樹不空，那么右子樹上所有結(jié)點的值均大于根結(jié)點的值； 3根

10、結(jié)點的左、右子樹也分別為二叉排序樹。 動態(tài)查找表二叉排序樹的查找過程1假設(shè)給定值等于根結(jié)點的關(guān)鍵字，那么查找成功；2假設(shè)給定值小于根結(jié)點的關(guān)鍵字，那么繼續(xù)在左子樹上進展遞歸查找；3假設(shè)給定值大于根結(jié)點的關(guān)鍵字，那么繼續(xù)在右子樹上進展遞歸查找。從根結(jié)點開場，假設(shè)二叉排序樹為空，那么查找不成功；否那么，在查找過程中，生成了一條查找路徑： 從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者 從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。 查找成功 查找不成功性能分析查找表：3,12,24,37,45,53,61,78,90,98 動態(tài)查找表 45 12 3 37

11、 53 90 24 78 98 61ASL=(1+22+34+43)/10 4512337539024789861單支樹一般情況下，沒有對二叉排序樹的深度進展控制。在構(gòu)造二叉排序樹的過程中進展“平衡化處理，成為平衡二叉樹AVL樹。平衡二叉樹：左子樹和右子樹的深度之差的絕對值不超過1。 動態(tài)查找表二叉排序樹的特點動態(tài)查找 (插入刪除的時機)含有n個結(jié)點的二叉排序樹不唯一，與結(jié)點插入的順序有直接關(guān)系。刪除某個結(jié)點后，二叉排序樹要重組?？傻玫狡胶舛鏄?。二叉排序樹的適用范圍用于組織規(guī)模較小的、內(nèi)存中可以容納的數(shù)據(jù)。對于數(shù)據(jù)量較大必須存放在外存中的數(shù)據(jù)，那么無法快速處理。 動態(tài)查找表問題引入：前面討論

12、的各種構(gòu)造，記錄在構(gòu)造中的相對位置是隨機的，和記錄的關(guān)鍵字之間不存在確定關(guān)系，因此，在構(gòu)造中查找記錄時需要進展一系列和關(guān)鍵字的比較。 哈希表理想情況是希望不經(jīng)過任何比較，一次存取就能得到所查記錄解決方法：在記錄的存儲位置和其關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f，使每個關(guān)鍵字和構(gòu)造中的唯一的存儲位置相對應(yīng)。 在查找時，只要根據(jù)該對應(yīng)關(guān)系f可找到給定值K的存儲位置f(K)。假設(shè)構(gòu)造中存在關(guān)鍵字和K相等的記錄，那么一定在f(K)的存儲位置上，所以不需要進展比較即可直接得到所查記錄。哈希表：對應(yīng)關(guān)系f為哈希函數(shù)，根據(jù)上述思想建立的表為哈希表。 哈希表 哈希表根本概念哈希函數(shù)構(gòu)造方法哈希函數(shù)沖突處理根本思

13、想： 在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。即：通過簡單計算直接得到數(shù)據(jù)的地址。1) 哈希(Hash)函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可。哈希函數(shù)可寫成：addr(ai)=H(ki)ai是表中的一個元素addr(ai)是ai的存儲地址ki是ai的關(guān)鍵字。 哈希表關(guān)鍵字集合存儲地址集合hash2) 由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突現(xiàn)象，即：key1 key2，而 f(key1) = f(key2)。3) 很難找到一個

14、不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。 哈希表 1 2 3 51 52年份人數(shù) 1949 1950 1951 1999 2000 2000 2100 2200 4400 4420例 某地區(qū)的人口統(tǒng)計表H(年度）=年度-1948 哈希表例 30個地區(qū)的各民族人口統(tǒng)計表編號 地區(qū) 總?cè)丝?漢族 回族.1 北京2 上海.以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)作關(guān)鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19哈希表應(yīng)用哈希函數(shù)，由記錄

15、的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表。哈希查找又叫散列查找，利用哈希函數(shù)進展查找的過程叫哈希查找。 哈希表哈希函數(shù)的構(gòu)造方法 構(gòu)造哈希函數(shù)的準那么：使關(guān)鍵字經(jīng)過哈希函數(shù)得到一個“隨機的地址，以便使一組關(guān)鍵字的哈希地址均勻地分布在逐個地址區(qū)間，從而減少沖突。 常用的構(gòu)造方法：1直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址,如年齡。2數(shù)字分析法：假設(shè)關(guān)鍵字是以 r 為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，那么可取關(guān)鍵字的假設(shè)干數(shù)位組成哈希地址 哈希表 常用的構(gòu)造方法：2數(shù)字分析法：假設(shè)事先知道關(guān)鍵字集合，且關(guān)鍵字的位數(shù)比哈希表的地址位數(shù)多，

16、那么可選取數(shù)字分布比較均勻的假設(shè)干位作為散列地址。例如，有一組8位數(shù)字組成的關(guān)鍵字： 經(jīng)過分析可知，前三位和第五位分布不均勻，所以，假設(shè)表長為1000，那么可取4、6、7位的數(shù)字作為哈希地址，假設(shè)表長為100，那么可取4、6與7、8位之和并舍去進位作為散列地址。關(guān)鍵字散列地址1散列地址287142653 87172232 8718274587107136 87127281 87137394465723874013228339990432370327 哈希表3平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。 通常，要預(yù)先估計關(guān)鍵字的數(shù)字分布并不容易，要找數(shù)字均勻分布的位數(shù)更難。此時可采用平方取中

17、法：即先通過求關(guān)鍵字的平方來擴大差異，再取其中的幾位或其組合作為散列地址。 例如：一組關(guān)鍵字： (0100，0110，1010，1001，0111)平方結(jié)果為：(0010000，0012100，1020210，1002001，0012321)假設(shè)表長為3位，那么可取中間三位作為散列地址集： (100，121，201，020，123) 哈希表4折疊法：假設(shè)關(guān)鍵字位數(shù)較多，可將關(guān)鍵字分割成位數(shù)一樣的幾段最后一段的位數(shù)可以不同，段的長度取決于哈希表的地址位數(shù)，然后將各段的迭加和舍去進位作為哈希地址。 例如，對于key=58242324169 582 423 241 + 69 1315H(key)=3

18、15移位迭加 582 324 241 + 96 1243H(key)=243間界迭加 哈希表5除留余數(shù)法：選擇一個適當(dāng)?shù)恼麛?shù)P，用P去除關(guān)鍵字，取所得的余數(shù)作為哈希地址，即： H(key) = key%P這個方法的關(guān)鍵是選取適當(dāng)?shù)腜。選擇P最好不要是偶數(shù)，也不要是基數(shù)的冪。一般地選P為小于或等于散列表長度m的某個最大素數(shù)比較好。例如： m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1019除余法的地址計算公式簡單，而且在很多情況下效果較好，因此是一種常用的構(gòu)造哈希函數(shù)的方法。 哈希表 實際工作中需視情況的不同而采用不同的

19、哈希函數(shù)。 通常需要考慮的因素有： A. 計算哈希函數(shù)所需時間; B. 關(guān)鍵碼的長度; C. 哈希表的大小; D. 關(guān)鍵碼的分布情況; E. 記錄的查找頻率。 哈希表在構(gòu)造這種特殊的“查找表 時，除了需要選擇一個“好盡可能少產(chǎn)生沖突的哈希函數(shù)之外，還需要找到一種“處理沖突 的方法?！疤幚頉_突 的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。常用的解決沖突的方法：開放定址法，鏈地址法，再哈希法，建立一個公共溢出區(qū)。 哈希表處理沖突的方法1 開放定址法 用開放地址法解決沖突的根本思想是：當(dāng)沖突發(fā)生時，使用某種方法在散列表中形成一個探測序列，按此序列逐個單元的查找，直到找到一個指定的關(guān)鍵字或碰到一

20、個開放的地址單元為空為止。插入時碰到開放的地址，即可將待插入新結(jié)點放到該地址單元中；查找時碰到開放的地址，那么說明表中沒有待查的關(guān)鍵字。 形成探測的方法不同，所得到的解決沖突的方法也不同。 哈希表1 開放定址法在根本區(qū)域內(nèi)形成一個探測序列 Hi = (H(key) + di)MOD m, i = 1, 2, , k ( k m-1)其中：m為表長，di為增量序列，可有多種取法： A. di = 1, 2, 3, , m-1, 稱線性探測再散列; B. di = 12, -12, 22, -22, , k2, -k2 (k m/2) 稱為二次探測再散列； C. di = 偽隨機數(shù)序列，稱偽隨機探測再散列。 哈希表例：在長度為11的哈希表中已有關(guān)鍵字分別為17，60，29的記錄哈希函數(shù)H(key)=key MOD 11,現(xiàn)有第四個記錄，其關(guān)鍵字為38，由哈希函數(shù)得到的哈希地址是5，產(chǎn)生沖突。假設(shè)用線性探測再散列方法處理，得到下一個地址6，仍沖突；再求一個地址7，仍沖突；直到哈希地址是8的位置為“空時止，處理沖突過程完畢，將記錄填入哈希表中序號為8的位置。 哈希表60172901234567891011601729382 再哈希法 Hi = R Hi(key) i = 1, 2, , k R Hi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時