全國計算機等級考試四級復習綱要二

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

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

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

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

更多信息請訪問：考試吧計算機等級考試欄目