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

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

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

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

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

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

5、檢測整個表是否查完 順序查找算法中,執(zhí)行頻率最高的是while語句,改進后,可以節(jié)省近一半的時間,第 13 頁,順序查找算法主程序,#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 頁,算法討論,平均查找長度ASL在等概率的情況下,平均查找長度ASL在等概率的情況下,優(yōu)點: 對結(jié)點的邏輯次序(不必有序)和存儲結(jié)構(gòu)(順序、鏈表均可）無要求；當(dāng)序列中的記錄“基本有序”或N值較小時，是較好的算法； 缺點：

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

7、 對確定的縮小區(qū)域再按二分公式，重復(fù)上述步驟； 最后，得到結(jié)果： 要么，查找成功， 要么，查找失敗。 存儲結(jié)構(gòu) 用一維數(shù)組存放。,第 17 頁,折半查找算法舉例,對給定數(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 頁,折半查找算法,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 ; /* 計算中點位置 */ if ( key itemmid) left = mid + 1; /* 待查區(qū)間在右部 */ else printf ( “ Successful searchn”); return mid ; /* 查找成功 */ printf( “ Search failure n”); return -1; /* 查找失敗 */ ,第 19 頁,折半查找算法的主程序,#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ōu)點: ASL log2n;即每經(jīng)過一次比較,查找范圍就縮小一半。經(jīng)log2n 次計較就可以完成查找過程。 缺點：因要求有序，所以對所有數(shù)據(jù)元素按大小排序是非常費時的操作。另外，順序存儲結(jié)構(gòu)的插入、刪除操作不大便利。 考慮

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

11、最大關(guān)鍵字構(gòu)成一個索引表； step2 查找分兩個部分： 先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中； 在已確定的塊中用順序法進行查找。,第 23 頁,分塊查找舉例,有數(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個塊;在第3塊中用順序法查找,比

12、較兩次,就可以找出60的元素來。,第 24 頁,索引表結(jié)構(gòu)定義,#include stdio.h typedef struct int key; /* 塊最大值 */ int link; /* 指向塊入口地址 */ index;,第 25 頁,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 頁,分塊查找子函數(shù)（續(xù)）, j=lsi.link; /* 塊入口地址 */ while (key !=sj /* 結(jié)束 */,第 27 頁,分塊查找主函數(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 頁,算法討論,設(shè)索引表使用二分法，則有： ASL log2（n/S +1）+ S/2 其中：n為表長，S為塊長（假設(shè)各塊長度相等）。 優(yōu)點： 插入、刪除操作方便；只要找到對應(yīng)的塊，在塊中任意位置操作均可。 缺點： 索引表增加了輔助存儲空間。 注： 索引表在數(shù)據(jù)庫系統(tǒng)中廣泛使用。 還有什么方法嗎？,,樹表查找,第 29 頁,二、哈希（hash）表技

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

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

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

18、號（ISBN），每個編號10位十進制數(shù)字?？捎谜郫B法構(gòu)造一個4位數(shù)的哈希函數(shù)。 例如： 書號為： 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 頁,除留余數(shù)法（求模取余法）,取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。 H（key） = key MOD p 這是一種最簡單，也是最常用的構(gòu)造哈希函數(shù)的方法。 舉例，32834872 ，哈希表長為4位十進制數(shù)。 P值可取小于9999的數(shù)，例如，取5000； H（KEY）= 32834872 MOD

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

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

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

22、若下一個存儲地址仍被占用，則繼續(xù)執(zhí)行step2，直到找到能用的存儲地址為止。,第 43 頁,舉例,對給定數(shù)列 22,41,53,46,30,13,1,67 ,建立哈希表。表長取9,即08。哈希函數(shù)設(shè)定為: H(key) = key MOD 8 ,用線性探測解決沖突 Hi=(H(key)+di) MOD m ,di=1,2,,m-1。 取22，計算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，計算

23、H（41）=1，該地址空，可用；,第 44 頁,舉例（續(xù)一）,取53，計算 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，計算 H（46）= 6，該地址沖突，用線性探測法計算下一個可用地址 Hi=（6+1）MOD 8 = 7，該地址空，可用；,第 45 頁,舉例（續(xù)二）,取30，計算 H（30）= 6，該地址沖突，用線性探

24、測法計算下一個可用地址 Hi=（6+1）MOD 8 = 7， 該地址沖突，再用線性探測法計算下一個可用地址；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，計算 H（13）= 5，依法解決沖突，得出：,第 46 頁,舉例（續(xù)三）,取1，計算 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，計算 H（67）= 3，沖突，解決沖突，得出：,第 47 頁,哈希查找,哈希查找的過程和建立哈希表的過程是一致的。 設(shè)哈希表為HST0M-1，哈希函數(shù)取H（key），解決沖突的方法為R（x），則哈希查找步驟為： Step1 對給定k值，計算哈希地址 Di=

26、H（k）；若HSTi為空，則查找失敗；若HSTi=k，則查找成功；否則，執(zhí)行step2（處理沖突）。 Step2 重復(fù)計算處理沖突的下一個存儲地址 Dk=R（Dk-1），直到HSTDk為空，或HSTDk=k為止。 若HSTDk=K，則查找成功，否則查找失敗。,第 48 頁,查找舉例,以上述哈希表為例。 哈希函數(shù)為H(key)=key MOD 8, 設(shè)有數(shù)列22,41,53,46,30,13,1,67,用線性探測法解決沖突,建立的哈希的表為:,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,平均查找長度ASL= (3+1+6+3+2+1+1+2)= 查找key = 67 比較兩次找到,查找成功; 查找key = 21 比較8次找不到,查找失敗。,第 49 頁,鏈地址法處理沖突,以上述數(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,平均查找長度ASL= (1+1+1+1+2+2+2+3)=,第 50 頁,思考題,1：長度為12的按關(guān)鍵字有序的查找表采用順序組織方式，若采用二分查找法，則在等概的情況下，查找失敗時的ASL值為？查找成功時的ASL值？ 答案：成功時：37/12；失敗時：49/13 2、哈希表平均ASL的計算,