電腦的基本操作課件

1、 Chapter 14 搜尋14.1 循序搜尋14.2 二元搜尋14.3 雜湊第1頁(yè)，共26頁(yè)。14.1 循序搜尋循序搜尋(sequential search)又稱(chēng)為線性搜尋（linear search），適用在小檔案。這是一種最簡(jiǎn)單的搜尋方法，從頭開(kāi)始找一直到找到為止。2第2頁(yè)，共26頁(yè)。14.2 二元搜尋二元搜尋(binary search)是找尋一個(gè)已排序的檔案最好的方法。二元搜尋的觀念與二元樹(shù)十分類(lèi)似，其比較是從所有記錄的中間點(diǎn)M開(kāi)始，若欲搜尋的鍵值小於M，則從M之前的記錄繼續(xù)搜尋，否則搜尋M以後的記錄，如此反覆進(jìn)行，直到鍵值被找到為止。3第3頁(yè)，共26頁(yè)。14.2 二元搜尋舉例來(lái)說(shuō)，

2、假設(shè)在已排序數(shù)列12, 23, 29, 38, 44, 57, 64, 75, 82, 98，若欲以二元搜尋法找尋82，則先從數(shù)列的中間點(diǎn)M = (left+right)/2 = (1+10)/2 = 5（第5筆記錄）開(kāi)始比對(duì)，如下所示：4第4頁(yè)，共26頁(yè)。14.2 二元搜尋5第5頁(yè)，共26頁(yè)。14.2 二元搜尋二元搜尋每一次比較，檔案皆縮小一半，從1/2，1/4，1/8，1/16，.在第k次比較時(shí)，最多只剩下n/2k 。最壞的情況是搜尋到最後只剩下一個(gè)記錄n/2k = 1，所以 K = log2n，即最多的比較次數(shù)是log2n。6第6頁(yè)，共26頁(yè)。14.3 雜湊在雜湊法中，鍵值（key va

3、lue）或識(shí)別字（identifier）在記憶體的位址是經(jīng)由函數(shù)（function）轉(zhuǎn)換而得的，如圖14-1。此種函數(shù)，一般稱(chēng)之為雜湊函數(shù)（hashing funciton）或鍵值對(duì)應(yīng)位址轉(zhuǎn)換（key to address transformation）。7第7頁(yè)，共26頁(yè)。14.3 雜湊4.3.1 雜湊函數(shù)一般常用的雜湊函數(shù)有下列四種方法：平方後取中間值法（mid-square）此種方法乃是將鍵值平方，然後視儲(chǔ)存空間的大小來(lái)決定取幾位數(shù)。除法（division）此種方法將鍵值利用模數(shù)運(yùn)算（mod）後，其餘數(shù)即為此鍵值所對(duì)稱(chēng)的位址，亦即Fd(x) = x mod m 。8第8頁(yè)，共26頁(yè)。14

4、.3 雜湊數(shù)位分析法（digit analysis）此種方法適合大的靜態(tài)資料，亦即所有的鍵值均事先知道，然後檢查鍵值的所有數(shù)位，分析每一數(shù)位是否分佈均勻，將不均勻的數(shù)位刪除，然後根據(jù)儲(chǔ)存空間的大小來(lái)決定數(shù)位的數(shù)目。9第9頁(yè)，共26頁(yè)。14.3 雜湊很容易可觀察在7個(gè)鍵值中1、2、3位（由左邊算起）的數(shù)值顯得太不均勻，故刪除第1，2，3位數(shù)，再觀察第8位也太多8，故刪除。假設(shè)有1000個(gè)儲(chǔ)存空間，而且挑選每一鍵值的4，6，7位做為再儲(chǔ)存的位址，分別為523, 937, 382, 497, 616, 954, 236。10第10頁(yè)，共26頁(yè)。14.3 雜湊上述提及利用四種方法將鍵值（或識(shí)別字）轉(zhuǎn)換

5、其對(duì)應(yīng)的儲(chǔ)存位址，這些儲(chǔ)存位址，一般稱(chēng)之為雜湊表（Hash table）。在雜湊表內(nèi)將儲(chǔ)存空間劃分為b個(gè)桶（bucket），分別為HT(0)，HT(1)，.，HT(b-1) 。每個(gè)桶具S個(gè)記錄，亦即由S個(gè)槽（slot）所組合而成。因此雜湊函數(shù)是把鍵值轉(zhuǎn)換；對(duì)應(yīng)到雜湊表的0至b-1桶中。11第11頁(yè)，共26頁(yè)。14.3 雜湊在C語(yǔ)言中所有合乎規(guī)定變數(shù)名稱(chēng)共有 ，此處假設(shè)變數(shù)名稱(chēng)只有六位數(shù)是合法的。而變數(shù)名稱(chēng)不一定要設(shè)六位，只要低於或等於六位即可，因此總共有27 + 2737 + 27372 + 27373 + 27374 + 27375 即 。12第12頁(yè)，共26頁(yè)。14.3 雜湊假設(shè)有n個(gè)，則

6、稱(chēng)n/T為識(shí)別字密度（identifier density），而稱(chēng)= n/(sb)為裝載密度（loading density）或裝載因子（loading factor）。假使有識(shí)別字k1和k2，經(jīng)過(guò)雜湊函數(shù)轉(zhuǎn)換，若此二個(gè)識(shí)別字對(duì)應(yīng)到相同的桶中，此時(shí)稱(chēng)之為碰撞（collision）或同義字（synonyms）。若桶中的S槽還未用完，則凡是該桶的同義字均可對(duì)應(yīng)至該桶中。13第13頁(yè)，共26頁(yè)。14.3 雜湊如果識(shí)別字對(duì)應(yīng)至一個(gè)已滿的桶中時(shí)，此稱(chēng)之為溢位（overflow）。如果桶的大小S只有一個(gè)槽，則碰撞與溢位必然會(huì)同時(shí)發(fā)生。假設(shè)雜湊表HT 中b = 27桶，每桶有2個(gè)槽，即S = 2，而且某程式

7、中所用的變數(shù)n = 10個(gè)識(shí)別字。14第14頁(yè)，共26頁(yè)。14.3 雜湊裝載因子= 10/2720.19。雜湊函數(shù)必須能夠?qū)⑺械淖R(shí)別字對(duì)應(yīng)到1-27的整數(shù)中，假設(shè)以1-27整數(shù)來(lái)代替英文字母A-Z及底線(_)，則將雜湊函數(shù)定義為f(x) =識(shí)別字X的第一個(gè)字母。15第15頁(yè)，共26頁(yè)。14.3 雜湊例如HD、E、K、H、J、B2、B1、B3、B5與M分別對(duì)應(yīng)到8、5、11、8、10、2、2、2、2、及13號(hào)桶中，其中B1、B2、B3、B5分別對(duì)應(yīng)到2號(hào)桶中，是同義字亦即產(chǎn)生碰撞。HD與H亦是同義字，其對(duì)應(yīng)到8號(hào)桶中，圖14-2是HD、E、K、H、J、B2與B1對(duì)應(yīng)到雜湊表的情形。16第16頁(yè)

8、，共26頁(yè)。14.3 雜湊在圖14-2當(dāng)B3再進(jìn)入雜湊表時(shí)，就發(fā)生溢位。假使每個(gè)桶中只有一個(gè)槽，則產(chǎn)生的溢位的機(jī)率就增加了。17第17頁(yè)，共26頁(yè)。14.3 雜湊14.3.2 解決溢位的方法（overflow handling）線性探測(cè)（linear probing）：是把雜湊位址視為環(huán)狀的空間，當(dāng)溢位發(fā)生時(shí)，以線性方式從下一號(hào)桶開(kāi)始探測(cè)，找尋一個(gè)空的儲(chǔ)存位址將資料存入。若找完一個(gè)循環(huán)還沒(méi)有找到空間，則表示位置已滿。如將HD、E、H、B2、B1、B3、B5、K、A、Z與ZB，放入具有每一桶只有一個(gè)槽的雜湊表中，其結(jié)果如圖14-3所示：18第18頁(yè)，共26頁(yè)。14.3 雜湊19第19頁(yè)，共26頁(yè)

9、。14.3 雜湊由於f(x) = X的第一字母，所以f(HD) = 8，f(E) = 5，亦即HD、E分別放在雜湊表中第8號(hào)與第5號(hào)桶中，f(H) = 8，此時(shí)8號(hào)桶已有HD，故發(fā)生碰撞及溢位，利用線性探測(cè)即往8號(hào)桶下找一空白的桶號(hào)，發(fā)現(xiàn)9號(hào)是空的，所以9號(hào)桶為H。20第20頁(yè)，共26頁(yè)。14.3 雜湊f(B2) = 2放入2號(hào)桶，f(B1)與f(B3) = 2，由於2號(hào)桶已存B2，故往下找各別存於3與4號(hào)桶，當(dāng)B5再轉(zhuǎn)進(jìn)來(lái)時(shí)就存於6號(hào)桶。f(K) = 11放入11號(hào)桶，f(A) = 1放入1號(hào)桶，f(Z) = 26放入26號(hào)桶，f(ZB)亦是26只好從1號(hào)桶往下找一空間放入7號(hào)。由上例應(yīng)該明

10、瞭線性探測(cè)如何處理溢位的情形。線性探測(cè)又稱(chēng)為線性開(kāi)放位址（linear open addressing）。21第21頁(yè)，共26頁(yè)。14.3 雜湊利用線性探測(cè)以解決溢位間題，極易造成鍵值聚集在一塊，增加搜尋的時(shí)間，如欲尋找ZB則必須尋找HT(26)、HT(1)、.、HT(7)，共須八次比較。22第22頁(yè)，共26頁(yè)。14.3 雜湊重覆雜湊（rehashing）：乃是先設(shè)計(jì)好一套的雜湊函數(shù)f1，f2，f3，.，fm，當(dāng)溢位發(fā)生時(shí)先使用f1，若再發(fā)生溢位則使用f2，.一直到?jīng)]有溢位發(fā)生。23第23頁(yè)，共26頁(yè)。14.3 雜湊平方探測(cè)（quadratic probing）：此法是用來(lái)改善線性探測(cè)之缺失，避免相近的鍵值聚集在一塊。當(dāng)f(x)的位址發(fā)生溢位時(shí)，下一次是探測(cè)(f(x)+i2) % b與(f(x) - i2) % b，其中1 i (b-1)/2，b是具有4j+3型式的質(zhì)數(shù)。24第24頁(yè)，共26頁(yè)。14