2.7查找

1、2.7查找2.7.1查找的基本概念找的基本概念查找的定找的定義：給定一個定一個值K，在含有，在含有n個記錄記錄的文件中的文件中進行搜索，行搜索，尋找一個關(guān)找一個關(guān)鍵字值等于K的記錄記錄，如找到，如找到則輸則輸出該記錄該記錄；否；否則輸則輸出查找不成功信息。找不成功信息。2.7.2線性查找線性查找又稱找又稱順序查找，是一種最找，是一種最簡單簡單的查找方法，它的基本思想是從第一個找方法，它的基本思想是從第一個記錄記錄開始，逐個比始，逐個比較

2、記錄較記錄的關(guān)的關(guān)鍵字，直到和字，直到和給定的定的K值相等，相等，則查則查找成功；若比找成功；若比較結(jié)較結(jié)果與文件果與文件中n個記錄記錄的關(guān)的關(guān)鍵字都不等，字都不等，則查則查找失找失敗。如。如圖2.68和圖2.692.7.3對分查找又稱又稱為跳躍式查找，假找，假設(shè)記錄設(shè)記錄是按關(guān)是按關(guān)鍵字遞增有序排列的，增有序排列的，對分查找的基本思想是：先找的基本思想是：先找到找到“中間記錄間記錄”，比，比較其關(guān)其關(guān)鍵字與字與給定值K相等，相等，則查

3、則查找成功；如果關(guān)找成功；如果關(guān)鍵字小于字小于給定值K則說則說明被明被查找記錄記錄必在前半?yún)^(qū)必在前半?yún)^(qū)間中；反之中；反之則在后半?yún)^(qū)在后半?yún)^(qū)間中。中。這樣這樣把搜索區(qū)把搜索區(qū)間縮間縮小了一半，了一半，繼續(xù)進繼續(xù)進行查找。找。在算法中，在算法中，設(shè)置一個下界指示器置一個下界指示器low和一個上界指示器和一個上界指示器high，它，它們分別指向待指向待查文件文件搜索區(qū)搜索區(qū)間的頭、尾。由、尾。由low和high的值可以可以計算出算出“中間記錄

4、間記錄”位置，由位置，由表示。表示。設(shè)順設(shè)順序表序表r[1:n]的關(guān)的關(guān)鍵字項為項為r[i].key(1≤i≤n)將K值r[].key比較：若r[].key=K查找成功找成功若r[].key＞K令high=1，繼續(xù)查繼續(xù)查找若r[].key＜K令low=1，繼續(xù)查繼續(xù)查找若low＞high查找不成功找不成功的關(guān)的關(guān)鍵字則不一定有序?；舅枷氩灰欢ㄓ行颉；舅枷霝椋合葘⒏鳎合葘⒏鲏K中的最大關(guān)中的最大關(guān)鍵字構(gòu)成一個索引表，由于字構(gòu)成一個索引

5、表，由于文件是分文件是分塊有序的因此索引表是有序的因此索引表是遞增有序的。增有序的。查找過程分兩步程分兩步進行，第一步先行，第一步先對索引索引表進行對分或分或順序查找，以確定找，以確定記錄記錄在哪一在哪一塊；第二步在所在；第二步在所在塊中進行順序查找。如找。如圖2.72所示所示2.7.5二叉排序二叉排序樹查樹查找BSTSEARCH(Kt)K為查為查找給定值t為根結(jié)點指點指針1.p←tp為查為查找過程中程中進行掃描的指描的指針2.whil