軟件技術(shù)基礎(chǔ)第03章查找.ppt

《軟件技術(shù)基礎(chǔ)第03章查找.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《軟件技術(shù)基礎(chǔ)第03章查找.ppt（50頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第 1 頁(yè),思考問(wèn)題,數(shù)據(jù)存放在計(jì)算機(jī)中如何查找？ 查找方法有所不同嗎？不同方法的查找效率有區(qū)別嗎？ 基本的查找方式有幾種？,第 2 頁(yè),教學(xué)目標(biāo),了解有關(guān)查找的 基本概念 查找的主要算法,第 3 頁(yè),教學(xué)要求,通過(guò)本單元的學(xué)習(xí)，了解、掌握有關(guān)查找的： 基本概念 查找、平均查找長(zhǎng)度 主要查找算法 順序查找、折半查找、分塊查找 哈希查找,第 4 頁(yè),本單元涉及的內(nèi)容,第3章 3.1 基本的查找技術(shù) 3.2 哈希表技術(shù),第 5 頁(yè),一、基本概念,查找 查找表 靜態(tài)查找 動(dòng)態(tài)查找 平均查找長(zhǎng)度,第 6 頁(yè),查找,查找 就是在給定的DS中找出滿足某種條件的結(jié)點(diǎn)；若存在這樣的結(jié)點(diǎn)，查找成功；否則，查找失

2、敗。 查找表 是一組待查數(shù)據(jù)元素的集合。 靜態(tài)查找 是僅僅進(jìn)行查詢和檢索操作，不改變查找表中數(shù)據(jù)元素間的邏輯關(guān)系的查找。 動(dòng)態(tài)查找 是除了進(jìn)行查詢和檢索操作外，還對(duì)查找表進(jìn)行插入、刪除操作的查找，動(dòng)態(tài)地改變查找表中數(shù)據(jù)元素之間的邏輯關(guān)系。,第 7 頁(yè),平均查找長(zhǎng)度,平均查找長(zhǎng)度 （ASL-Average Search Length） 在查找過(guò)程中，對(duì)每個(gè)結(jié)點(diǎn)記錄中的關(guān)鍵字要進(jìn)行反復(fù)比較，以確定其位置。因此，與關(guān)鍵字進(jìn)行比較的平均次數(shù)，就成為平均查找長(zhǎng)度。 它是用來(lái)評(píng)價(jià)一個(gè)算法好壞的一個(gè)依據(jù)。 對(duì)含有n個(gè)數(shù)據(jù)元素的查找表，查找成功時(shí)的平均查找長(zhǎng)度為：,,其中：Pi 為查找表中第i個(gè)數(shù)據(jù)元素的概率

3、，且,Ci為查找到第i個(gè)數(shù)據(jù)元素時(shí)需進(jìn)行比較的次數(shù)。 顯然，Ci隨查找過(guò)程及DS的不同而各異。,第 8 頁(yè),基本的查找技術(shù),順序查找 折半查找 分塊查找,第 9 頁(yè),1.順序查找,算法思想： 最古老的算法。從第1個(gè)元素到最后1個(gè)元素，逐個(gè)進(jìn)行比較。 查找表的存儲(chǔ)結(jié)構(gòu) 既適用于順序存儲(chǔ)結(jié)構(gòu) 也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 算法描述 算法討論,第 10 頁(yè),算法描述,查找操作步驟： step1 從第1個(gè)元素開(kāi)始查找； step2 用待查關(guān)鍵字值與各結(jié)點(diǎn)（記錄）的關(guān)鍵字值逐個(gè)進(jìn)行比較；若找到相等的結(jié)點(diǎn)，則查找成功；否則，查找失敗。,第 11 頁(yè),順序查找算法,seq_search(int *item ,n ,

4、 key ) int i=0 ; while ( i < n ,第 12 頁(yè),順序查找算法（改進(jìn)算法）,seq_search_adv(int *item ,n , key ) int i=0 ; itemn=key ; /* 設(shè)置哨兵 */ while ( itemi!= key ) i++; /* 查找key */ if ( i< n ) /* 如果 i = n，沒(méi)找到 */ printf(“查找成功 !n”); return (i); else printf(“查找失敗 !n”); return (-1); 注: 設(shè)置哨兵目的在于免去查找過(guò)程中每一步都要

5、檢測(cè)整個(gè)表是否查完 順序查找算法中,執(zhí)行頻率最高的是while語(yǔ)句,改進(jìn)后,可以節(jié)省近一半的時(shí)間,第 13 頁(yè),順序查找算法主程序,#include “stdio.h” #define n 7 main() int key,loc=0; int a10=43,15,21,37,2,5,82; printf(“Input key:”); scanf(“%d”, ,第 14 頁(yè),算法討論,平均查找長(zhǎng)度ASL在等概率的情況下,平均查找長(zhǎng)度ASL在等概率的情況下,優(yōu)點(diǎn): 對(duì)結(jié)點(diǎn)的邏輯次序(不必有序)和存儲(chǔ)結(jié)構(gòu)(順序、鏈表均可）無(wú)要求；當(dāng)序列中的記錄“基本有序”或N值較小時(shí)，是較好的算法； 缺點(diǎn)：

6、 ASL較長(zhǎng) 討論：能否減少比較次數(shù)，以提高效率。,例如，,二分法等,第 15 頁(yè),2.折半查找,算法思想： 將有序數(shù)列的中點(diǎn)設(shè)置為比較對(duì)象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。 即通過(guò)一次比較，將查找區(qū)間縮小一半。 二分查找的先決條件是查找表中的數(shù)據(jù)元素必須有序。,第 16 頁(yè),算法描述,算法步驟： step1 首先確定整個(gè)查找區(qū)間的中間位置， mid = （ left + right ）/ 2 step2 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較； 若相等，則查找成功； 若大于，則在后半?yún)^(qū)域繼續(xù)進(jìn)行二分查找； 若小于，則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找。

7、 對(duì)確定的縮小區(qū)域再按二分公式，重復(fù)上述步驟； 最后，得到結(jié)果： 要么，查找成功， 要么，查找失敗。 存儲(chǔ)結(jié)構(gòu) 用一維數(shù)組存放。,第 17 頁(yè),折半查找算法舉例,對(duì)給定數(shù)列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。,第二次： 23，28，30，32，50 ,mid1= （1+10）/2 = 5,mid2 = （6+10） /2 = 8,第 18 頁(yè),折半查找算法,bin_search ( item , n ,key ) int *item, n, key; int left ,right , mid; left=0; ri

8、ght = n-1; while ( left right ) mid = ( left + right )/2 ; /* 計(jì)算中點(diǎn)位置 */ if ( key itemmid) left = mid + 1; /* 待查區(qū)間在右部 */ else printf ( “ Successful searchn”); return mid ; /* 查找成功 */ printf( “ Search failure n”); return -1; /* 查找失敗 */ ,第 19 頁(yè),折半查找算法的主程序,#define “stdio.h” int

9、num; main( ) int res, key ; int s10=1,3,5,7,9,11,13，15，17，19，21，23; res=b_search(s,12,7); if(res0) printf(res=%d , num=%dn,res+1,num); else printf(“search failuren”); ,第 20 頁(yè),算法分析,優(yōu)點(diǎn): ASL log2n;即每經(jīng)過(guò)一次比較,查找范圍就縮小一半。經(jīng)log2n 次計(jì)較就可以完成查找過(guò)程。 缺點(diǎn)：因要求有序，所以對(duì)所有數(shù)據(jù)元素按大小排序是非常費(fèi)時(shí)的操作。另外，順序存儲(chǔ)結(jié)構(gòu)的插入、刪除操作不大便利。 考慮

10、： 能否一次比較拋棄更多的部分（即一次比較，使查找范圍縮得更?。?，以達(dá)到提高效率的目的； ？,把兩種方法（順序查找和二分查找）結(jié)合起來(lái)，即取順序查找簡(jiǎn)單和二分查找高效之所長(zhǎng)，來(lái)達(dá)到提高效率的目的？,第 21 頁(yè),3.分塊查找,分塊查找又稱索引順序查找，這是順序查找的一種改進(jìn)方法。 方法描述： 將n個(gè)數(shù)據(jù)元素“按塊有序”劃分為m塊（m n）。 每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，。每個(gè)塊中元素不一定是有序的。,第 22 頁(yè),分塊查找算法描述,step1 先選取各塊中的

11、最大關(guān)鍵字構(gòu)成一個(gè)索引表； step2 查找分兩個(gè)部分： 先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中； 在已確定的塊中用順序法進(jìn)行查找。,第 23 頁(yè),分塊查找舉例,有數(shù)列如下： 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 按“塊有序”分三塊:(22,12,13,9,8),(33,42,44,38,24), (48,60,58,74,47)。選取每塊中最大的關(guān)鍵字組成索引表22,44,74,查找關(guān)鍵字值為60的元素。 用二分法，確定在索引表中的位置為 mid=2，key值60與a2比較，60a2,取第3個(gè)塊;在第3塊中用順序法查找,比

12、較兩次,就可以找出60的元素來(lái)。,第 24 頁(yè),索引表結(jié)構(gòu)定義,#include stdio.h typedef struct int key; /* 塊最大值 */ int link; /* 指向塊入口地址 */ index;,第 25 頁(yè),index_seq_search.c子函數(shù),index_seq_search(index ls,int s,int m,int key,int l) int i,j; i=0; while(ilsi.key) i++; /* 確定在哪塊查找 */ if(i=m) printf(“ Searching failuren); ret

13、urn(-1); else /* 否則，查找成功處理 */,第 26 頁(yè),分塊查找子函數(shù)（續(xù)）, j=lsi.link; /* 塊入口地址 */ while (key !=sj /* 結(jié)束 */,第 27 頁(yè),分塊查找主函數(shù),main() index ls5= 14,0,34,5 ,66,10,85,15,100,20 ; int a=8,4,3,2,14, 34,20,17,28,29 ,58,61,59,66,48, 81,80,79,83,69,89,100,96,86,87; int i,j=0,key; for(i=0;i<25;i++) if (j==0) pri

14、ntf( ); if (j==5) printf( ); j=0; printf( ); printf(%4d,ai); j++; printf( n); printf(Enter key: ); scanf(%d, ,第 28 頁(yè),算法討論,設(shè)索引表使用二分法，則有： ASL log2（n/S +1）+ S/2 其中：n為表長(zhǎng)，S為塊長(zhǎng)（假設(shè)各塊長(zhǎng)度相等）。 優(yōu)點(diǎn)： 插入、刪除操作方便；只要找到對(duì)應(yīng)的塊，在塊中任意位置操作均可。 缺點(diǎn)： 索引表增加了輔助存儲(chǔ)空間。 注： 索引表在數(shù)據(jù)庫(kù)系統(tǒng)中廣泛使用。 還有什么方法嗎？,,樹(shù)表查找,第 29 頁(yè),二、哈希（hash）表技

15、術(shù),哈希查找也稱為散列查找。它不同于前面介紹的幾種查找方法。上述方法都是把查找建立在比較的基礎(chǔ)上，而哈希查找則是通過(guò)計(jì)算存儲(chǔ)地址的方法進(jìn)行查找的。 計(jì)算是計(jì)算機(jī)的特點(diǎn)之一，因此，建立在計(jì)算基礎(chǔ)上的哈希查找是一種快速查找方法。,第 30 頁(yè),哈希查找的基本概念,哈希表 由哈希函數(shù)的值組成的表。哈希查找是建立在哈希表的基礎(chǔ)上，它是線性表的一種重要存儲(chǔ)方式和檢索方法。在哈希表中可以實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的快速檢索。 哈希函數(shù) 哈希表中元素是由哈希函數(shù)確定的。將數(shù)據(jù)元素的關(guān)鍵字K作為自變量，通過(guò)一定的函數(shù)關(guān)系（稱為哈希函數(shù)），計(jì)算出的值，即為該元素的存儲(chǔ)地址。表示為： Addr = H（key） 建立哈希

16、函數(shù)的原則 均勻性 H（key）的值均勻分布在哈希表中； 簡(jiǎn)單 以提高地址計(jì)算的速度。,第 31 頁(yè),哈希函數(shù)常用的構(gòu)造方法,數(shù)字分析法 平方取中法 折疊法 除留余數(shù)法（求模取余法） 直接定址法,第 32 頁(yè),數(shù)字分析法,當(dāng)關(guān)鍵字的位數(shù)比存儲(chǔ)區(qū)地址碼位數(shù)多時(shí)，可合理選擇關(guān)鍵字的某幾位組成的哈希地址。 選取的原則：盡量避免計(jì)算出的地址有沖突。 舉例：學(xué)校的電話號(hào)碼是7位十進(jìn)制數(shù)，學(xué)校的程控交換機(jī)是3000門。但經(jīng)分析不難得出： 0XXX 266 8XXX 9XXX 前3位是相同的，第4位分別為“0、8、9”，這樣一來(lái)，正好可以表示3000個(gè)不同的電話號(hào)碼。 H（KEY）=

17、Right（telnum，4）,,第 33 頁(yè),平方取中法,取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時(shí)不知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適，在這種情況下，取一個(gè)數(shù)平方后的中間幾位數(shù)作哈希地址。取的位數(shù)由表長(zhǎng)決定。 例如，3288，平方后是“10810944”，取后4位為哈希地址，即“0944”。,第 34 頁(yè),折疊法,將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址。 關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻時(shí)，可采用折疊法。 舉例：某資料室藏書(shū)近萬(wàn)冊(cè)。采用國(guó)際標(biāo)準(zhǔn)圖書(shū)編

18、號(hào)（ISBN），每個(gè)編號(hào)10位十進(jìn)制數(shù)字。可用折疊法構(gòu)造一個(gè)4位數(shù)的哈希函數(shù)。 例如： 書(shū)號(hào)為： 0 - 4 4 2 - 2 0 5 8 6 - 4 5 8 6 4 4 2 2 0 H（key）= 0088 0 4,,,,+）,1 0 0 8 8,,第 35 頁(yè),除留余數(shù)法（求模取余法）,取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址。 H（key） = key MOD p 這是一種最簡(jiǎn)單，也是最常用的構(gòu)造哈希函數(shù)的方法。 舉例，32834872 ，哈希表長(zhǎng)為4位十進(jìn)制數(shù)。 P值可取小于9999的數(shù)，例如，取5000； H（KEY）= 32834872 MOD

19、 5000 = 4872 由經(jīng)驗(yàn)得知：通常選p為小于哈希表長(zhǎng)的最大素?cái)?shù)。,第 36 頁(yè),直接定址法,取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址，即： H（key） = key H（key） = a * key + b （a，b為常數(shù)） 例如： 在1100歲的人口統(tǒng)計(jì)表中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字本身。 再如： 解放后出生人口統(tǒng)計(jì)表中，年份作為關(guān)鍵字，哈希函數(shù)取為： H（key）= key +（ -1948）,第 37 頁(yè),選擇哈希函數(shù)的標(biāo)準(zhǔn),哈希函數(shù)計(jì)算所需要的時(shí)間 關(guān)鍵字的長(zhǎng)度 哈希表的長(zhǎng)度 關(guān)鍵字的分布情況 記錄的查找頻率,第 38 頁(yè),沖突及沖突處理,在哈希元素（地址）求

20、解過(guò)程中，不同關(guān)鍵字值對(duì)應(yīng)到同一個(gè)存儲(chǔ)地址的現(xiàn)象稱為沖突。即關(guān)鍵字K1 K2， 但哈希函數(shù)值 H（K1）= H（K2）。 均勻的哈希函數(shù)可以減少?zèng)_突，但不能避免沖突。發(fā)生沖突后，必須解決；也即必須尋找下一個(gè)可用地址。 處理沖突是建立哈希表過(guò)程中不可缺少的一部分。 處理沖突有兩種方法： 開(kāi)放地址法 鏈地址法,第 39 頁(yè),處理沖突 -- 開(kāi)放地址法,當(dāng)發(fā)生地址沖突后，求解下一個(gè)地址用 Hi =( H（key）+di） MOD m i=1,2,,k(k m-1) 其中: H(key)為哈希函數(shù),m為哈希表長(zhǎng)度,di為增量序列。增量序列的不同取法，又構(gòu)成不同的開(kāi)放地址法。 線性探測(cè)再散列 di=

21、1,2,,m-1 二次探測(cè)再散列,di=12 , -12, 22, -22, ,+k2, -k2(k m/2),第 40 頁(yè),處理沖突 -- 鏈地址法,當(dāng)發(fā)生地址沖突后,將所有函數(shù)值相同的記錄連成一個(gè)單鏈表。,第 41 頁(yè),哈希查找操作步驟,用給定的哈希函數(shù)構(gòu)造哈希表 根據(jù)選擇的沖突處理方法解決地址沖突 在哈希表的基礎(chǔ)上執(zhí)行哈希查找,第 42 頁(yè),建立哈希表,建立哈希表操作步驟： step1 取數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其哈希函數(shù)值（地址）。若該地址對(duì)應(yīng)的存儲(chǔ)空間還沒(méi)有被占用，則將該元素存入；否則執(zhí)行step2解決沖突。 step2 根據(jù)選擇的沖突處理方法，計(jì)算關(guān)鍵字key的下一個(gè)存儲(chǔ)地址。

22、若下一個(gè)存儲(chǔ)地址仍被占用，則繼續(xù)執(zhí)行step2，直到找到能用的存儲(chǔ)地址為止。,第 43 頁(yè),舉例,對(duì)給定數(shù)列 22,41,53,46,30,13,1,67 ,建立哈希表。表長(zhǎng)取9,即08。哈希函數(shù)設(shè)定為: H(key) = key MOD 8 ,用線性探測(cè)解決沖突 Hi=(H(key)+di) MOD m ,di=1,2,,m-1。 取22，計(jì)算H（22）=6，該地址空，可用；,,,,,,,,,0 1 2 3 4 5 6 7 8,,22,,,,,,,,,,22,0 1 2 3 4 5 6 7 8,41,比較次數(shù)： 1 1,取41，計(jì)算

23、H（41）=1，該地址空，可用；,第 44 頁(yè),舉例（續(xù)一）,取53，計(jì)算 H（53）= 5，該地址空，可用；,,,,,,,,,,22,41,0 1 2 3 4 5 6 7 8,53,,,,,,,,,,22,41,53,46,0 1 2 3 4 5 6 7 8,比較次數(shù)： 1 1 1,比較次數(shù)： 1 1 1 2,取46，計(jì)算 H（46）= 6，該地址沖突，用線性探測(cè)法計(jì)算下一個(gè)可用地址 Hi=（6+1）MOD 8 = 7，該地址空，可用；,第 45 頁(yè),舉例（續(xù)二）,取30，計(jì)算 H（30）= 6，該地址沖突，用線性探

24、測(cè)法計(jì)算下一個(gè)可用地址 Hi=（6+1）MOD 8 = 7， 該地址沖突，再用線性探測(cè)法計(jì)算下一個(gè)可用地址；Hi=0，地址空，可用；,,,,,,,,,,22,41,0 1 2 3 4 5 6 7 8,53,,,,,,,,,,22,41,53,46,0 1 2 3 4 5 6 7 8,比較次數(shù)： 3 1 1 1 2,比較次數(shù)： 3 1 6 1 1 2,46,30,30,13,取13，計(jì)算 H（13）= 5，依法解決沖突，得出：,第 46 頁(yè),舉例（續(xù)三）,取1，計(jì)算 H（1）= 1，該地址沖突，解決沖突可得：,,,,,,

25、,,,,22,41,0 1 2 3 4 5 6 7 8,53,,,,,,,,,,22,41,53,46,,46,30,30,13,比較次數(shù)： 3 1 6 3 1 1 2,1,13,1,67,比較次數(shù)： 3 1 6 3 2 1 1 2,0 1 2 3 4 5 6 7 8,取67，計(jì)算 H（67）= 3，沖突，解決沖突，得出：,第 47 頁(yè),哈希查找,哈希查找的過(guò)程和建立哈希表的過(guò)程是一致的。 設(shè)哈希表為HST0M-1，哈希函數(shù)取H（key），解決沖突的方法為R（x），則哈希查找步驟為： Step1 對(duì)給定k值，計(jì)算哈希地址 Di=

26、H（k）；若HSTi為空，則查找失敗；若HSTi=k，則查找成功；否則，執(zhí)行step2（處理沖突）。 Step2 重復(fù)計(jì)算處理沖突的下一個(gè)存儲(chǔ)地址 Dk=R（Dk-1），直到HSTDk為空，或HSTDk=k為止。 若HSTDk=K，則查找成功，否則查找失敗。,第 48 頁(yè),查找舉例,以上述哈希表為例。 哈希函數(shù)為H(key)=key MOD 8, 設(shè)有數(shù)列22,41,53,46,30,13,1,67,用線性探測(cè)法解決沖突,建立的哈希的表為:,0 1 2 3 4 5 6 7 8,比較次數(shù)： 3 1 6 3 2 1 1 2,,,,,,,,,,22,41,53,46,30,13,1,

27、67,平均查找長(zhǎng)度ASL= (3+1+6+3+2+1+1+2)= 查找key = 67 比較兩次找到,查找成功; 查找key = 21 比較8次找不到,查找失敗。,第 49 頁(yè),鏈地址法處理沖突,以上述數(shù)列為例，產(chǎn)生的哈希表為：,1 2 3 4 5 6 7,,,,,,,,,,41,1 ,,46,,13 ,,30 ,,,,22,,,53,,,,67,,H(22)=H(46)=H(30)=6,H(53)=H(13)=5,H(67)=3,H(41)=H(1)=1,平均查找長(zhǎng)度ASL= (1+1+1+1+2+2+2+3)=,第 50 頁(yè),思考題,1：長(zhǎng)度為12的按關(guān)鍵字有序的查找表采用順序組織方式，若采用二分查找法，則在等概的情況下，查找失敗時(shí)的ASL值為？查找成功時(shí)的ASL值？ 答案：成功時(shí)：37/12；失敗時(shí)：49/13 2、哈希表平均ASL的計(jì)算,