順序查找是一種最基本和最簡單的查找方法它的思路是

1、查找 順序查找是一種最基本和最簡單的查找方法。它的思路是，從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。對于表中記錄的關(guān)鍵字是無序的表，只能采用這種方法。描述順序查找的算法見框圖8-1。其中n是表r的長度，k是要查的元素的關(guān)鍵字，i查到的元素的序號。 折半查找又稱二分查找，是針對有序表進(jìn)行查找的簡單、有效而又較常用的方法。所謂有序表有序表，即要求表中的各元素按關(guān)鍵字的值有序（升序或降序）存放。折半查找不像順序查找那樣，從第一個(gè)記錄開始逐個(gè)順序搜索，其基本思想是：首先選取表中間位置的記錄，將其關(guān)鍵字與

2、給定關(guān)鍵字k進(jìn)行比較，若相等，則查找成功；否則，若k值比該關(guān)鍵字值大，則要找的元素一定在表的后半部分（或稱右子表），則繼續(xù)對右子表進(jìn)行折半查找；若k值比該關(guān)鍵字值小，則要找的元素一定在表的前半部分（左子表），同樣應(yīng)繼續(xù)對左子表進(jìn)行折半查找。每進(jìn)行一次比較，要么找到要查找的元素，要么將查找的范圍縮小一半。如此遞推，直到查找成功或把要查找的范圍縮小為空（查找失?。?。設(shè)表的長度為n，表的被查找部分的頭為low，尾為high，初始時(shí)，low=1,high=n,k為關(guān)鍵字的值。 （2）若k=rmid.key,成功，否則： 若 krmid.key, 則low=mid+1,重復(fù)（1）； 直到成功或不成功（此

3、時(shí)lowhigh）。具體算法如下：Void binsrch(struct node r ,int n,int k) int mid,low,high,find; low=1; high=n;find=0; /*置區(qū)間初值*/ while (lowrmid.key ) low=mid+1; /*在后半?yún)^(qū)間查找*/ else high=mid-1; /*在前半?yún)^(qū)間查找*/ if (find) return (mid); /*查找成功，返回找到元素的位置*/else return (0); /*查找不成功，返回0標(biāo)記*/采用折半查找，當(dāng)查找成功時(shí)，最少比較次數(shù)為一次，如在上例中查找關(guān)鍵字值為18的結(jié)

4、點(diǎn)，只需一次比較。最多經(jīng)過log2n次比較之后，待查找子表要么為空，要么只剩下一個(gè)結(jié)點(diǎn)，所以要確定查找失敗需要log2n次或log2n+1次比較?？梢宰C明，折半查找的平均查找長度是： 從折半查找的平均查找長度ASL來看，當(dāng)表的長度n很大時(shí)，該方法尤其能顯示出其時(shí)間效率。但由于折半查找的表仍是線性表，若經(jīng)常要進(jìn)行插入、刪除操作，則元素排列費(fèi)時(shí)太多，因此折半查找比較適合于一經(jīng)建立就很少改動而又需要經(jīng)常查找的線性表，較少查找而又經(jīng)常需要改動的線性表可以采用鏈接存儲，使用順序查找。 分塊查找 在處理線性表時(shí)，如果既希望能夠快速查找，又要經(jīng)常動態(tài)變化，則可以采用分塊查找方法。分塊查找又稱索引順序查找，要

5、求將待查的元素均勻的分成塊，塊間按大小排序，塊內(nèi)不排序。因此需要建立一個(gè)塊的最大（或最小）關(guān)鍵字表，稱之為“索引表”。具體而言，假設(shè)我們按結(jié)點(diǎn)元素關(guān)鍵字升序方式組織表中各塊，則要求第一塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第二塊中所有結(jié)點(diǎn)的關(guān)鍵字值；第二塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第三塊中所有結(jié)點(diǎn)的關(guān)鍵字值；如此類推。然后選擇每塊中的最大（或最?。╆P(guān)鍵字值組成索引表。換言之，索引表中的結(jié)點(diǎn)個(gè)數(shù)等于線性表被分割的塊數(shù)。 例如要找關(guān)鍵字為k的元素，則先用折半查找法由索引表查出k所在的塊，再用順序查找法在對應(yīng)的塊中找出k。在圖8-2中若要找關(guān)鍵字值為41的元素，則先由索引表查出41在第二塊中（294164），

6、再在第二塊中找到41。由此我們可以總結(jié)：分塊查找分兩步進(jìn)行，第一步確定要查找結(jié)點(diǎn)在表中的哪一塊，第二步在確定的塊中找到該結(jié)點(diǎn)。分塊查找的平均查找長度為： ASL=ASLb+ASLe其中ASLb是折半查找的平均查找長度，ASLe是用順序查找法查塊內(nèi)元素的平均查找長度。設(shè)每塊中有s個(gè)元素，可以近似的得到：可以看出分塊查找的平均查找長度位于順序查找和折半查找之間。下面我們簡單的對以上幾種查找方法做出比較：（1）平均查找長度：折半查找最小，分塊查找次之，順序查找最大；（2）表的結(jié)構(gòu)：順序查找對有序表、無序表均適用；折半查找僅適用于有序表；分塊查找要求表中元素是逐段有序的，就是塊與塊之間的記錄按關(guān)鍵字有

7、序；（3）存儲結(jié)構(gòu)：順序查找和分塊查找對向量和線性鏈表結(jié)構(gòu)均適用；折半查找只適用于向量存儲結(jié)構(gòu)的表，因而要求表中元素基本不變，而在需要插入或刪除運(yùn)算時(shí)，要移動元素，才能保持表的有序性，所以影響了查找效率。 哈希法 哈希法又名散列法,因其英文單詞Hash而得名,是一種完全不同的查找方法。前面我們所介紹的三種查找方法的共同特點(diǎn)在于：通過對關(guān)鍵字的一系列比較，逐步縮小查找范圍，直到確定結(jié)點(diǎn)的存儲位置或確定查找失敗。而哈希法則希望不經(jīng)過任何比較，一次存取就能得到所查元素，因此必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲位置相對應(yīng)，這樣查找時(shí)只需對結(jié)點(diǎn)

8、的關(guān)鍵字進(jìn)行某種運(yùn)算就能確定結(jié)點(diǎn)在表中的位置。因此哈希法的平均比較次數(shù)和表中所含結(jié)點(diǎn)的個(gè)數(shù)無關(guān)。打個(gè)比方讓我們更清楚的認(rèn)識哈希法的不同。假定某教室有35個(gè)座位，如果不加限定讓學(xué)生任意就座，則要找某個(gè)學(xué)生時(shí)就要將待找學(xué)生與當(dāng)前座位上的學(xué)生一一做比較，這就是我們前面所介紹的查找方法的大致思路。而哈希法則要限定學(xué)生所坐的位置，比如可規(guī)定學(xué)生座位的編號應(yīng)與其學(xué)號的末兩位相同，則學(xué)號為993605的學(xué)生應(yīng)坐編號為5的座位。這樣我們要找某個(gè)學(xué)生時(shí)只需根據(jù)其學(xué)號的末兩位到相應(yīng)座位上去找即可，不必一一比較了。在這個(gè)例子里，學(xué)生好比記錄，學(xué)號則為關(guān)鍵字，對關(guān)鍵字進(jìn)行的操作則是取其末兩位，用以確定記錄的位置。 哈

9、希函數(shù)的構(gòu)造方法 一個(gè)好的哈希函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲空間的有效地址范圍內(nèi)，以盡可能減少沖突。但鑒于實(shí)際問題中關(guān)鍵字的不同，沒法構(gòu)造出統(tǒng)一的哈希函數(shù)。從而構(gòu)造哈希函數(shù)的方法多種多樣，這里只介紹一些比較常用的、計(jì)算較為簡便的方法。1自身函數(shù)自身函數(shù)關(guān)鍵字自身作為哈希函數(shù)，即H（k）=k，也可自身加上一個(gè)常數(shù)作為哈希函數(shù)，即H(k)=k+c。例如上例中建立的哈希函數(shù)H(學(xué)號)=學(xué)號-9900采用的就是這樣的方法。但這種函數(shù)只適用于給定的一組關(guān)鍵字為關(guān)鍵字集合中的全體元素的情況，故不常用。2除余法除余法選擇一個(gè)適當(dāng)?shù)恼麛?shù)m，用m去除關(guān)鍵字，取其余數(shù)作為散列地址，即H（key）=key%m。上

10、例中后來所設(shè)定的函數(shù)H(學(xué)號)=學(xué)號%10采用的就是除余法。但是在這種方法中，m的選擇是值得研究的。如果選擇關(guān)鍵字內(nèi)部代碼基數(shù)的冪次來除關(guān)鍵字，其結(jié)果必定是關(guān)鍵字的低位數(shù)字均勻性較差。若取m為任意偶數(shù)，則當(dāng)關(guān)鍵字內(nèi)部代碼為偶數(shù)時(shí)，得到的哈希函數(shù)值為偶數(shù)；若關(guān)鍵字內(nèi)部代碼為奇數(shù)，則哈希函數(shù)值為奇數(shù)。因此，m為偶數(shù)也是不好的。理論分析和試驗(yàn)結(jié)果均證明m應(yīng)取小于存儲區(qū)容量的素?cái)?shù)。查找：查找：根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。關(guān)鍵字關(guān)鍵字(Keyword)：一個(gè)或一組能唯一標(biāo)識該記錄的數(shù)據(jù)項(xiàng)稱為該記錄的關(guān)鍵字。平均查找長度（平均查找長度（Average Search L

11、ength）：為確定記錄在表中的位置所進(jìn)行的和關(guān)鍵字的比較的次數(shù)的期望值稱之為查找算法的平均查找長度，簡稱ASL。有序表：有序表：表中的各元素按關(guān)鍵字的值有序（升序或降序）存放。哈希表哈希表：將結(jié)點(diǎn)的關(guān)鍵字key作為自變量，通過一個(gè)確定的函數(shù)關(guān)系H，計(jì)算出相應(yīng)的函數(shù)值H(key)，然后以H(key)作為該結(jié)點(diǎn)的存儲單元地址。用這種方式建立起來的線性表稱為哈希表或叫散列表哈希函數(shù)哈希函數(shù)：把結(jié)點(diǎn)關(guān)鍵字轉(zhuǎn)換為該結(jié)點(diǎn)存儲單元地址的函數(shù)H稱為哈希函數(shù)或叫散列函數(shù)。在學(xué)習(xí)這些概念的基礎(chǔ)上，我們先后學(xué)習(xí)了三種基于將待查元素的關(guān)鍵字和表中元素的關(guān)鍵字進(jìn)行比較的查找算法，即順序查找、折半查找和分塊查找，并對它們做出比較。我們也