計(jì)算機(jī)軟件基礎(chǔ)Thesoftwarebasicofcomputer主講劉志強(qiáng)

1、計(jì)算機(jī)軟件基礎(chǔ)The software basic of computer計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心第6單元8/19/20221教學(xué)目標(biāo)了解有關(guān)查找的基本概念查找的主要算法2教學(xué)要求通過本單元的學(xué)習(xí)，了解、掌握有關(guān)查找的：基本概念查找、平均查找長度主要查找算法順序查找、折半查找、分塊查找樹表查找、哈希查找3本單元涉及的內(nèi)容第3章3.1 什么是查找 3.2 順序表查找3.3 樹表查找3.4 哈希查找P90P1024一、基本概念查找查找表靜態(tài)查找動(dòng)態(tài)查找平均查找長度5查找查找 就是在給定的DS中找出滿足某種條件的結(jié)點(diǎn)；若存在這樣的結(jié)點(diǎn)，查找成功；否則，查找失敗。查找表 是一組待查數(shù)據(jù)元素的集合。靜態(tài)查找

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

3、個(gè)數(shù)據(jù)元素時(shí)需比較的次數(shù)。 顯然，Ci隨查找過程及DS的不同而各異。7二、主要查找算法順序查找折半查找分塊查找樹表查找哈希查找81、順序查找算法思想： 最古老的算法。從第1個(gè)元素到最后1個(gè)元素，逐個(gè)進(jìn)行比較。順序查找是最簡單、最普通的查找方法。查找表的存儲(chǔ)結(jié)構(gòu)：既適用于順序存儲(chǔ)結(jié)構(gòu)也適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 9算法描述查找操作步驟：step1 從第1個(gè)元素開始查找；step2 用待查關(guān)鍵字值與各結(jié)點(diǎn)（記錄）的關(guān)鍵字值逐個(gè)進(jìn)行比較；若找到相等的結(jié)點(diǎn)，則查找成功；否則，查找失敗。10順序查找算法框圖i=0seq_search(A，n，key)A 待查表n 元素個(gè)數(shù)key 要找的值in&Ai!=key?Y

4、N查找key的循環(huán)顯示“查找失敗”返回開始i+Ai=key?YN顯示“查找成功”11順序查找算法3-1 seq_search(item , n , key ) int *item ,n , key ; int i=0 ; while ( i n & itemi != key ) i+; /* 查找key的循環(huán) */ if (itemi= = key ) printf(“查找成功 !n”); return (i); else printf(“查找失敗 !n”); return (-1); 示例12改進(jìn)順序查找算法框圖i=0 ； An=keys_search_a(A，n，key)Ai!=key?Y

5、N查找key的循環(huán)顯示“查找失敗”返回開始i+i n?YN顯示“查找成功”設(shè)置哨兵13順序查找算法3-2（改進(jìn)算法） seq_search_adv(item , n , key ) int *item ,n , key ; int i=0 ; itemn=key ; /* 設(shè)置哨兵 */ while ( itemi!= key ) i+; /* 查找key */ if ( i0) printf(“l(fā)oc=%d,key=%dn”,loc,key); 示例15算法討論平均查找長度ASL在等概率的情況下平均查找長度ASL在等概率的情況下i=1n12n+1ni=1nASL = Pi*Ci = (n-i

6、+1) =優(yōu)點(diǎn):對結(jié)點(diǎn)的邏輯次序(不必有序)和存儲(chǔ)結(jié)構(gòu)(順序、鏈表均可）無要求；當(dāng)序列中的記錄“基本有序”或N值較小時(shí)，是較好的算法；缺點(diǎn)：ASL較長討論：能否減少比較次數(shù)，以提高效率。nASL 2例如，二分法等162、折半查找算法思想： 將有序數(shù)列的中點(diǎn)設(shè)置為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。 即通過一次比較，將查找區(qū)間縮小一半。二分查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。但是，二分查找的先決條件是查找表中的數(shù)據(jù)元素必須有序。17算法描述算法步驟：step1 首先確定整個(gè)查找區(qū)間的中間位置， mid = （ left

7、 + right ）/ 2step2 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較；若相等，則查找成功；若大于，則在后半?yún)^(qū)域繼續(xù)進(jìn)行二分查找；若小于，則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找。Step3 對確定的縮小區(qū)域再按二分公式，重復(fù)上述步驟；最后，得到結(jié)果： 要么，查找成功， 要么，查找失敗。存儲(chǔ)結(jié)構(gòu)用一維數(shù)組存放。18折半查找算法舉例對給定數(shù)列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。 第1次： 3，5，11，17，21，23，28，30，32，50 mid1= （1+10）/2 = 5 第2次： 23，28，30，32，50 m

8、id2 = （6+10） /2 = 8leftrightmidleftrightmid19折半查找算法3-3 bin_search ( item , n ,key ) int *item, n, key; int left ,right , mid; left=0; right = n-1; while ( left right ) mid = ( left + right )/2 ; /* 計(jì)算中點(diǎn)位置 */ if ( key itemmid) left = mid + 1; /* 待查區(qū)間在右部 */ else printf ( “ Successful searchn”); return

9、 mid ; /* 查找成功 */ printf( “ Search failure n”); return -1; /* 查找失敗 */ 20折半查找算法3-3主程序 #define “stdio.h” int 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”); 示例21算法討論優(yōu)點(diǎn): ASL log2n;即每經(jīng)過

10、一次比較,查找范圍就縮小一半。經(jīng)log2n 次計(jì)較就可以完成查找過程。缺點(diǎn)：因要求有序，所以對所有數(shù)據(jù)元素按大小排序是非常費(fèi)時(shí)的操作。另外，順序存儲(chǔ)結(jié)構(gòu)的插入、刪除操作不大便利?？紤]：能否一次比較拋棄更多的部分（即一次比較，使查找范圍縮得更?。?，以達(dá)到提高效率的目的；？ 把兩種方法（順序查找和二分查找）結(jié)合起來，即取順序查找簡單和二分查找高效之所長，來達(dá)到提高效率的目的？223、分塊查找分塊查找又稱索引順序查找，這是順序查找的一種改進(jìn)方法。方法描述：將n個(gè)數(shù)據(jù)元素“按塊有序”劃分為m塊（m n）。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須“按塊有序”；即第1快中任一元素的關(guān)鍵字都必須小于第2塊中

11、任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，。每個(gè)塊中元素不一定是有序的。23分塊查找算法描述step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表；step2 查找分兩個(gè)部分：先對索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；在已確定的塊中用順序法進(jìn)行查找。24分塊查找舉例有數(shù)列如下： 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47 按“塊有序”分三塊:(22,12,13,9,8),(33,42,44,38,24), (48,6,58,74,47)。選取每塊中最大的關(guān)鍵字組成索引表22,44,74,查找關(guān)鍵字值為60的元素。

12、用二分法，確定在索引表中的位置為 mid=2，key值60與a2比較，60a2,取第3個(gè)塊;在第3塊中用順序法查找,比較兩次,就可以找出60的元素來。4422742212139833424438244860587447List1List2List325索引表結(jié)構(gòu)定義#include stdio.htypedef struct int key; /* 塊最大值 */ int link; /* 指向塊入口地址 */ index;26分塊查找邏輯框圖i_s_search(ls,s,m,key,l)ls 索引表S 待查表M 塊數(shù)key 要找的值l 塊長度i=0ilsi.key?YN確定塊的循環(huán)j=ls

13、i.link返回開始i+i m?YN顯示“查找失敗”塊入口地址塊內(nèi)查找循環(huán)key!=sj且j在范圍內(nèi)?j+Y key=sj?N查找失敗查找成功返回YN27index_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); return(-1); else /* 否則，查找成功處理 */28分塊查找子函數(shù)（續(xù)） j=lsi.link; /* 塊入口

14、地址 */ while (key !=sj & (j-lsi.link)l) j+; if(key=sj&(j-lsi.link)l)/* 查找成功*/ printf(Successful searchn LOC(s%2d)=%dn,j,sj); return(j); else /* 查找失敗 */ printf(Searching failuren); return(-1); /* 結(jié)束 */29分塊查找主函數(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

15、,66,48, 81,80,79,83,69,89,100,96,86,87; int i,j=0,key; for(i=0;ileft = 0;r-right = 0;r-info = info ;非根結(jié)點(diǎn)infoinfo?Yt=r-leftt=r-rightN調(diào)用本函數(shù)root?返回YNr-left=0r-right=0root-left=r或root-right=r37 查詢二叉排序樹算法框圖開始Search_btree(root，key) root 根指針 key 要找的值!rootY顯示“空樹”返回Nroot-info!=key循環(huán)keyinfo?root=root-leftroot

16、=root-rightroot=0?NY查找成功,顯示返回顯示“失敗”root!=0?循環(huán)結(jié)束?NY38 打印算法框圖開始print_btree(root，l ) root 根指針 l 起始點(diǎn)距離r=0?YN調(diào)用自身打印左子打印當(dāng)前結(jié)點(diǎn)值調(diào)用自身打印右子返回39 主程序Btree.C#include “stdio.h” struct tree char info; struct tree *left,*right; main ( ) char *s,*c,key=; struct tree *create_btree(),*search_btree(),*root=0; do printf(“

17、Enter a letter:”); gets(s); if (!root) root=create_btree(root,root,*s); else create_btrr(root,root,*s); while (*s) ;40 主程序Btree.C(續(xù)） print_btree(root,0); key=1; while ( key) printf(“Enter a key to find:”); scanf(“%s”,&c); key=search_btree(root,c); printf(“press to continuen”); /* Btree.C 結(jié)束 */ 41生成二

18、叉排序樹程序 struct tree create_btree(root,r,info) struct tree *root,*r; char info; if (r = = 0 ) r=malloc(sizeof(struct tree); if ( r = = 0) printf(“Out of memoryn”); exit(0); r-left= 0; r-right=0; r-info=info; if (root) if(infoinfo) root - left=r; else root-right=r; else r-right=0; r-left = 0; return r;

19、 /* if = = 0 接下頁 */42生成二叉排序樹程序（續(xù)） if (info info) create_btree(r,r-left,info); if(info=r-info) create_btree(r,r-right,info); /* create_btree(root,r,info) */43打印二叉排序樹程序print_btree(r,l)struct tree *r;int l; int i; if (r = = 0) return ; print_tree(r-left,l+1); for(i=0;iinfo); print_btree(r-right,l+1); 4

20、4 struct tree *search_btree(root,key) struct tree *root; char key; if (!root) printf(“Emptu btreen”);return root; while(root-info!=key) /* 查找key 的循環(huán) */ if(keyinfo) root=root-left; /* 沿左路查找 */ else root=root-right; /* 沿右路查找 */ if(root= =0) /* 到葉結(jié)點(diǎn)也沒找到 */ printf(“Search Failuren”); break ; if (root !=

21、0) /* 查找成功 */ printf(“Successful searchn key=%cn”,root-info); return root ;查詢二叉排序樹程序示例45程序輸入輸入： 輸出： h b d d p e r h b p e r 46 舉例對數(shù)列10，18，3，4，9，13，25，生成二叉排序樹如右；查找關(guān)鍵字值25。25比較根結(jié)點(diǎn)值10，走右路，再與18進(jìn)行比較，走右路，最后與25進(jìn)行比較，相等，查找成功。比較了3次。若查找35，則與10、18、25 分別進(jìn)行比較后仍沒找到相等 元素，查找失敗，也比較了三次。1039418132547算法討論二叉排序樹查找的 ASL log

22、2n。若其平衡特性較好的話，ASL與折半查找相同。二叉排序樹是動(dòng)態(tài)生成的，其特性隨插入結(jié)點(diǎn)的先后次序的不同而改變，為防止其蛻化為單枝樹，要進(jìn)行平衡化處理。二叉排序樹因采用鏈表結(jié)構(gòu)，需要輔助存儲(chǔ)空間。上述方法都是建立比較基礎(chǔ)上的，還有其它類型的方法嗎？485、哈希（hash）查找哈希查找也稱為散列查找。它不同于前面介紹的幾種查找方法。上述方法都是把查找建立在比較的基礎(chǔ)上，而哈希查找則是通過計(jì)算存儲(chǔ)地址的方法進(jìn)行查找的。計(jì)算是計(jì)算機(jī)的特點(diǎn)之一，因此，建立在計(jì)算基礎(chǔ)上的哈希查找是一種快速查找方法。49哈希查找的基本概念哈希表 由哈希函數(shù)的值組成的表。哈希查找是建立在哈希表的基礎(chǔ)上，它是線性表的一種重

23、要存儲(chǔ)方式和檢索方法。在哈希表中可以實(shí)現(xiàn)對數(shù)據(jù)元素的快速檢索。哈希函數(shù) 哈希表中元素是由哈希函數(shù)確定的。將數(shù)據(jù)元素的關(guān)鍵字K作為自變量，通過一定的函數(shù)關(guān)系（稱為哈希函數(shù)），計(jì)算出的值，即為該元素的存儲(chǔ)地址。表示為： Addr = H（key）建立哈希函數(shù)的原則均勻性 H（key）的值均勻分布在哈希表中；簡單 以提高地址計(jì)算的速度。 50哈希函數(shù)常用的構(gòu)造方法數(shù)字分析法平方取中法折疊法除留余數(shù)法（求模取余法）直接定址法51數(shù)字分析法當(dāng)關(guān)鍵字的位數(shù)比存儲(chǔ)區(qū)地址碼位數(shù)多時(shí)，可合理選擇關(guān)鍵字的某幾位組成的哈希地址。選取的原則： 盡量避免計(jì)算出的地址有沖突。舉例： 學(xué)校的電話號(hào)碼是7位十進(jìn)制數(shù)，學(xué)校的程

24、控交換機(jī)是3000門。但經(jīng)分析不難得出： 0XXX 266 8XXX 9XXX 前3位是相同的，第4位分別為“0、8、9”，這樣一來，正好可以表示3000個(gè)不同的電話號(hào)碼。 H（KEY）= Right（telenum，4）52平方取中法取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時(shí)不知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適，在這種情況下，取一個(gè)數(shù)平方后的中間幾位數(shù)作哈希地址。取的位數(shù)由表長決定。例如，3288，平方后是“”，取后4位為哈希地址，即“0944”。53折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部

25、分的疊加和（舍去進(jìn)位）作為哈希地址。關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻時(shí)，可采用折疊法。舉例：某資料室藏書近萬冊。采用國際標(biāo)準(zhǔn)圖書編號(hào)（ISBN），每個(gè)編號(hào)10位十進(jìn)制數(shù)字?？捎谜郫B法構(gòu)造一個(gè)4位數(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 854除留余數(shù)法（求模取余法）取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。 H（key） = key MOD p 這是一種最簡單，也是最常用的構(gòu)造哈希函數(shù)的方法。舉例，32834872 ，哈希表長為4位十進(jìn)制

26、數(shù)。 P值可取小于9999的數(shù)，例如，取5000； H（KEY）= 32834872 MOD 5000 = 4872由經(jīng)驗(yàn)得知： 通常選p為小于哈希表長的最大素?cái)?shù)。55直接定址法取關(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）地址年份人數(shù) 01 02 42194919501990. 4319913000350025002300.

27、56選擇哈希函數(shù)的標(biāo)準(zhǔn)哈希函數(shù)計(jì)算所需要的時(shí)間關(guān)鍵字的長度哈希表的長度關(guān)鍵字的分布情況記錄的查找頻率57沖突及沖突處理在哈希元素（地址）求解過程中，不同關(guān)鍵字值對應(yīng)到同一個(gè)存儲(chǔ)地址的現(xiàn)象稱為沖突。即關(guān)鍵字K1 K2， 但哈希函數(shù)值 H（K1）= H（K2）。均勻的哈希函數(shù)可以減少?zèng)_突，但不能避免沖突。發(fā)生沖突后，必須解決；也即必須尋找下一個(gè)可用地址。處理沖突是建立哈希表過程中不可缺少的一部分。處理沖突有兩種方法：開放地址法鏈地址法58處理沖突 開放地址法當(dāng)發(fā)生地址沖突后，求解下一個(gè)地址用 Hi =( H（key）+di） MOD m i=1,2,k(k m-1) 其中: H(key)為哈希函數(shù)

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

29、處理方法，計(jì)算關(guān)鍵字key的下一個(gè)存儲(chǔ)地址。若下一個(gè)存儲(chǔ)地址仍被占用，則繼續(xù)執(zhí)行step2，直到找到能用的存儲(chǔ)地址為止。 62舉例對給定數(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，計(jì)算H（22）=6，該地址空，可用；取41，計(jì)算H（41）=1，該地址空，可用； 0 1 2 3 4 5 6 7 82222 0 1 2 3 4 5 6 7 841比較次數(shù)： 1 163舉例（續(xù)一）取53，計(jì)算 H（53）= 5，該地址空，可用；取46，計(jì)算 H（46）= 6，該地址沖突，用線性探測法計(jì)算下一個(gè)可用地址 Hi=（6+1）MOD 8 = 7， 該地址空，可用；2241 0 1 2 3 4 5 6 7 853224153460 1 2 3 4 5 6 7 8 比較次數(shù)： 1 1 1 比較次數(shù)： 1 1 1 264舉例（續(xù)二）取30，計(jì)算 H（30）= 6，該地址沖突，用線性探測法計(jì)算下一個(gè)可用地址 Hi=（6+1）MOD 8 = 7， 該地址沖突，再用線性探測法計(jì)算下