第1章电脑的基本操作课件.ppt

1、資料結構資料結構-使用使用 C 語言語言 2循序搜尋(sequential search)又稱為線性搜尋（linear search），適用在小檔案。這是一種最簡單的搜尋方法，從頭開始找一直到找到為止。資料結構資料結構-使用使用 C 語言語言 3二元搜尋(binary search)是找尋一個已排序的檔案最好的方法。二元搜尋的觀念與二元樹十分類似，其比較是從所有記錄的中間點M開始，若欲搜尋的鍵值小於M，則從M之前的記錄繼續搜尋，否則搜尋M以後的記錄，如此反覆進行，直到鍵值被找到為止。資料結構資料結構-使用使用 C 語言語言 4舉例來說，假設在已排序數列12,23,29,38,44,57,64,

2、75,82,98，若欲以二元搜尋法找尋82，則先從數列的中間點M=(left+right)/2=(1+10)/2=5（第5筆記錄）開始比對，如下所示：資料結構資料結構-使用使用 C 語言語言 5資料結構資料結構-使用使用 C 語言語言 6二元搜尋每一次比較，檔案皆縮小一半，從1/2，1/4，1/8，1/16，.在第k次比較時，最多只剩下n/2k。最壞的情況是搜尋到最後只剩下一個記錄n/2k=1，所以 K=log2n，即最多的比較次數是log2n。資料結構資料結構-使用使用 C 語言語言 7在雜湊法中，鍵值（key value）或識別字（identifier）在記憶體的位址是經由函數（funct

3、ion）轉換而得的，如圖14-1。此種函數，一般稱之為雜湊函數（hashing funciton）或鍵值對應位址轉換（key to address transformation）。資料結構資料結構-使用使用 C 語言語言 84.3.1 雜湊函數一般常用的雜湊函數有下列四種方法：n平方後取中間值法（mid-square）此種方法乃是將鍵值平方，然後視儲存空間的大小來決定取幾位數。n除法（division）此種方法將鍵值利用模數運算（mod）後，其餘數即為此鍵值所對稱的位址，亦即Fd(x)=x mod m。資料結構資料結構-使用使用 C 語言語言 9n數位分析法（digit analysis）此種

4、方法適合大的靜態資料，亦即所有的鍵值均事先知道，然後檢查鍵值的所有數位，分析每一數位是否分佈均勻，將不均勻的數位刪除，然後根據儲存空間的大小來決定數位的數目。資料結構資料結構-使用使用 C 語言語言 10很容易可觀察在7個鍵值中1、2、3位（由左邊算起）的數值顯得太不均勻，故刪除第1，2，3位數，再觀察第8位也太多8，故刪除。假設有1000個儲存空間，而且挑選每一鍵值的4，6，7位做為再儲存的位址，分別為523,937,382,497,616,954,236。資料結構資料結構-使用使用 C 語言語言 11上述提及利用四種方法將鍵值（或識別字）轉換其對應的儲存位址，這些儲存位址，一般稱之為雜湊表

5、（Hash table）。在雜湊表內將儲存空間劃分為b個桶（bucket），分別為HT(0)，HT(1)，.，HT(b-1)。每個桶具S個記錄，亦即由S個槽（slot）所組合而成。因此雜湊函數是把鍵值轉換；對應到雜湊表的0至b-1桶中。資料結構資料結構-使用使用 C 語言語言 12在C語言中所有合乎規定變數名稱共有 ，此處假設變數名稱只有六位數是合法的。而變數名稱不一定要設六位，只要低於或等於六位即可，因此總共有27+2737+27372+27373+27374+27375 即 。資料結構資料結構-使用使用 C 語言語言 13假設有n個，則稱n/T為識別字密度（identifier densi

6、ty），而稱=n/(sb)為裝載密度（loading density）或裝載因子（loading factor）。假使有識別字k1和k2，經過雜湊函數轉換，若此二個識別字對應到相同的桶中，此時稱之為碰撞（collision）或同義字（synonyms）。若桶中的S槽還未用完，則凡是該桶的同義字均可對應至該桶中。資料結構資料結構-使用使用 C 語言語言 14如果識別字對應至一個已滿的桶中時，此稱之為溢位（overflow）。如果桶的大小S只有一個槽，則碰撞與溢位必然會同時發生。假設雜湊表HT 中b=27桶，每桶有2個槽，即S=2，而且某程式中所用的變數n=10個識別字。資料結構資料結構-使用使用

7、 C 語言語言 15裝載因子=10/2720.19。雜湊函數必須能夠將所有的識別字對應到1-27的整數中，假設以1-27整數來代替英文字母A-Z及底線(_)，則將雜湊函數定義為f(x)=識別字X的第一個字母。資料結構資料結構-使用使用 C 語言語言 16例如HD、E、K、H、J、B2、B1、B3、B5與M分別對應到8、5、11、8、10、2、2、2、2、及13號桶中，其中B1、B2、B3、B5分別對應到2號桶中，是同義字亦即產生碰撞。HD與H亦是同義字，其對應到8號桶中，圖14-2是HD、E、K、H、J、B2與B1對應到雜湊表的情形。資料結構資料結構-使用使用 C 語言語言 17在圖14-2當

8、B3再進入雜湊表時，就發生溢位。假使每個桶中只有一個槽，則產生的溢位的機率就增加了。資料結構資料結構-使用使用 C 語言語言 1814.3.2 解決溢位的方法（overflow handling）線性探測（linear probing）：是把雜湊位址視為環狀的空間，當溢位發生時，以線性方式從下一號桶開始探測，找尋一個空的儲存位址將資料存入。n若找完一個循環還沒有找到空間，則表示位置已滿。如將HD、E、H、B2、B1、B3、B5、K、A、Z與ZB，放入具有每一桶只有一個槽的雜湊表中，其結果如圖14-3所示：資料結構資料結構-使用使用 C 語言語言 19資料結構資料結構-使用使用 C 語言語言 2

9、0n由於f(x)=X的第一字母，所以f(HD)=8，f(E)=5，亦即HD、E分別放在雜湊表中第8號與第5號桶中，f(H)=8，此時8號桶已有HD，故發生碰撞及溢位，利用線性探測即往8號桶下找一空白的桶號，發現9號是空的，所以9號桶為H。資料結構資料結構-使用使用 C 語言語言 21nf(B2)=2放入2號桶，f(B1)與f(B3)=2，由於2號桶已存B2，故往下找各別存於3與4號桶，當B5再轉進來時就存於6號桶。f(K)=11放入11號桶，f(A)=1放入1號桶，f(Z)=26放入26號桶，f(ZB)亦是26只好從1號桶往下找一空間放入7號。n由上例應該明瞭線性探測如何處理溢位的情形。線性探

10、測又稱為線性開放位址（linear open addressing）。資料結構資料結構-使用使用 C 語言語言 22n利用線性探測以解決溢位間題，極易造成鍵值聚集在一塊，增加搜尋的時間，如欲尋找ZB則必須尋找HT(26)、HT(1)、.、HT(7)，共須八次比較。資料結構資料結構-使用使用 C 語言語言 23重覆雜湊（rehashing）：乃是先設計好一套的雜湊函數f1，f2，f3，.，fm，當溢位發生時先使用f1，若再發生溢位則使用f2，.一直到沒有溢位發生。資料結構資料結構-使用使用 C 語言語言 24平方探測（quadratic probing）：此法是用來改善線性探測之缺失，避免相近的鍵值聚集在一塊。當f(x)的位址發生溢位時，下一次是探測(f(x)+i2)%b與(f(x)-i2)%b，其中1 i (b-1)/2，b是具有4j+3型式的質數。資料結構資料結構-使用使用 C 語言語言 25鏈結串列（chaining）：是將雜湊空間建立成b個串列，起初只有b個串列首，故放起始位址，並不存放資料，相同位址的鍵值，將形成一個鍵值結串列如圖14-4所示。B5，B3，B1，B2放在第2個串列，H與HD收在第8個串列，以及ZB與Z放在第26個串列上。資料結構資料結構-使用使用 C 語言語言 26