七、檢索
　　
　　1.順序檢索
　　
　　檢索又稱為查找。順序檢索是將待查找的關(guān)鍵碼值與線性表中個(gè)結(jié)點(diǎn)的關(guān)鍵碼值逐一比較，直到找到所需的記錄，檢索成功;或者在表中找不到所需記錄而檢索失敗。順序檢索不要求線性表事先排序。設(shè)線性表有n個(gè)元素，則最多檢索次數(shù)為n，最少檢索次數(shù)為1。

　　　
　　2.二分法檢索
　
　　二分法檢索要求線性表結(jié)點(diǎn)按關(guān)鍵排序且以順序方式存儲(chǔ)。在查找時(shí)，首先與表的中間位置上結(jié)點(diǎn)的關(guān)鍵值比較，若相等則檢索成功;否則根據(jù)比較結(jié)果確定下一步在表的前半部或后半部中繼續(xù)進(jìn)行。二分法檢索的效率較主動(dòng)，設(shè)線性表有n個(gè)元素，則最多的檢索次數(shù)為大于log 2 n的最小整數(shù)，最少的檢索次數(shù)為1。
　　
　　3.分塊檢索
　　
　　分塊檢索把線性表分成若干塊，塊內(nèi)結(jié)點(diǎn)不必有序，但塊與塊之間必須有序，即每一塊中各結(jié)點(diǎn)的關(guān)鍵值必須大于（或小于，與此類推）前一塊最大關(guān)鍵值。為加快查找，還要建立一個(gè)索引表，表中給出每一塊的最大關(guān)鍵值和指向塊內(nèi)第一個(gè)結(jié)點(diǎn)位置的指針。分塊檢索分兩步進(jìn)行，先查索引表，確定要找的記錄在哪一塊;然后再在相應(yīng)的塊中檢索。分塊檢索適合于線性表很大，數(shù)據(jù)又是動(dòng)態(tài)變化的情況。在查索引表時(shí)，可采用順序法或二分法;在塊內(nèi)查找所求記錄時(shí)，采用順序法。由于分塊而縮小了查找范圍，從而加快檢索速。
　　
　　4.散列表檢索

　　根據(jù)關(guān)鍵值，就可以迅速找到該記錄所對(duì)應(yīng)的存儲(chǔ)位置，這就是建立在散列函數(shù)基礎(chǔ)上的散列檢索。設(shè)記錄的關(guān)鍵值為k，則該記錄的存儲(chǔ)位置可用散列函數(shù)H來計(jì)算H=H（k）。常用來產(chǎn)生的散列函數(shù)的方法是除余法，即取H（k）=k mod p設(shè)散列表長度為n，取p為小于n的最大素?cái)?shù)。一般說來，關(guān)鍵碼值的集合比散列表存儲(chǔ)位的數(shù)目大得多，這正是體現(xiàn)散列表的優(yōu)勢所在，但同時(shí)帶來了沖突問題，即不同的關(guān)鍵值經(jīng)散列函數(shù)計(jì)算，可能得到相同的存儲(chǔ)位置。一個(gè)好的散列函數(shù)應(yīng)該使沖突的可能性盡量小。最常用的解決沖突的方法是線性探測法，就是在發(fā)生沖突時(shí)，從H（k）以后的位置逐一探測，直至找到一個(gè)空位置，將新記錄插入;在檢索時(shí)，如果H（k）中不是所需關(guān)鍵值的記錄，也是從H（k）往下逐一搜索，直到找到所需關(guān)鍵值或查找失敗為止。應(yīng)注意查找次序是:H（k），H（k）+1，H（k）+2，…n-1，0，1，2，…，H（k）-1即在n-1以后，又從0開始，因?yàn)樵谖恢蒙鲜茄�環(huán)的。雙重散列技術(shù)是對(duì)線性探測法的改進(jìn)。它使用兩個(gè)散列函數(shù)H1和H2。對(duì)關(guān)鍵值k，計(jì)算H1（k），求得0到n-1之間的一個(gè)散列地址;若在這個(gè)地址上沖突，下一個(gè)被探測的地址為（H1（k）+H2（k））mod n，關(guān)于選擇H2的方法在此不做討論。

希望與更多計(jì)算機(jī)等級(jí)考試的網(wǎng)友交流，請(qǐng)進(jìn)入計(jì)算機(jī)等級(jí)考試論壇

更多信息請(qǐng)?jiān)L問：考試吧計(jì)算機(jī)等級(jí)考試欄目