【正文】 第九章 查找 ￡ 查找表 ￡ 概述 查找表 （ Search Table）：是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu) 成的集合。 對(duì)查找表經(jīng)常進(jìn)行的 操作 通常有： （ 1） 查詢 某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中； （ 2） 檢索 某個(gè)“特定的”數(shù)據(jù)元素的各種屬性； （ 3）在查找表中 插入 一個(gè)數(shù)據(jù)元素； （ 4）從查找表中 刪去 某個(gè)數(shù)據(jù)元素。 靜態(tài)查找表 （ Static Search Table）：只對(duì)查找表作“查找”操作的 一類查找表。 動(dòng)態(tài)查找表 （ Dynamic Search Table）：對(duì)查找表不僅作“查找”操 作，在查找過(guò)程中還同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找 表中刪除已存在的某個(gè)數(shù)據(jù)元素的一類查找表。 ￡ 相關(guān)術(shù)語(yǔ) 關(guān)鍵字 （ Key）：是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用 它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。 主關(guān)鍵字 （ Primary Key）：可以唯一的標(biāo)識(shí)一個(gè)建立的關(guān)鍵字。 次關(guān)鍵字 （ Secondary Key）：用以識(shí)別若干記錄的關(guān)鍵字。 查找 （ Searching）：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。 查找成功：查找表中存在關(guān)鍵字等于給定值的記錄。此時(shí)查找的結(jié)果為給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置。 查找失?。翰檎冶碇胁淮嬖陉P(guān)鍵字等于給定值的記錄。此時(shí)查找 的結(jié)果可給出一個(gè)“空”記錄或“空”指針。 （ 2）查找操作的性能分析 衡量查找算法好壞的 依據(jù) ：其關(guān)鍵字和給定值進(jìn)行過(guò)比較的記錄個(gè) 數(shù)的平均值。 平均查找長(zhǎng)度 （ Average Search Length）：為確定記錄在查找表中 的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在 查找成功時(shí)的平均查找長(zhǎng)度。 對(duì)于含有 n個(gè)記錄的表，查找成功時(shí)的平均查找長(zhǎng)度為： ??? niiiCPA SL1（ 9－ 1） 其中： Pi為查找表中查找第 i個(gè)記錄的概率，且 ???ni iP11 ； Ci為找到表中其關(guān) 鍵字與給定值相等的第 i個(gè)記錄時(shí)，和給定值已進(jìn)行過(guò)比較的關(guān)鍵字個(gè)數(shù)。 查找算法的平均查找長(zhǎng)度＝ 查找成功時(shí)的平均查找長(zhǎng)度 ＋ 查找不成功時(shí)的平均查找長(zhǎng)度 ￡ 順序表的查找 （ 1）順序存儲(chǔ)結(jié)構(gòu)的類型定義 typedef struct { ElemType *elem。 //數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按 //實(shí)際長(zhǎng)度分配， 0號(hào)單元留空 int length。 //表長(zhǎng)度 } SSTable （ 2）順序查找的實(shí)現(xiàn) 順序查找 （ Sequential Search）的 查找過(guò)程 為：從表中最后一個(gè)記錄開(kāi) 始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值 比較相等，則查找成功，找到所查記錄；反之，若直至第一個(gè)記錄，其關(guān)鍵 字和給定值比較都不等，則表明表中沒(méi)有所查記錄，查找不成功。 int Search_Seq (SSTable ST, KeyType key) { //在順序表 ST中順序查找其關(guān)鍵字等于 key的數(shù)據(jù)元素。 //若找到，則函數(shù)值為該元素在表中的位置，否則為 0。 [0].key = key。 //“哨兵” for (i = 。 !EQ([i].key, key)。 ――i)。 //從后往前找 return i。 //找不到時(shí) i為 0 } // Search_Seq 算法 ： i 例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 64 64 監(jiān)視哨 i i i i 比較次數(shù) =5 比較次數(shù)： 查找第 n個(gè)元素： 1 查找第 n1個(gè)元素： 2 ………. 查找第 1個(gè)元素： n 查找第 i個(gè)元素： n+1i 查找失敗 ： n+1 ? P217 監(jiān)視哨的作用 （ 3）性能分析 假設(shè) n＝ ，則順序查找的平均長(zhǎng)度為： ASL = nP1 + (n－ 1)P2 + … + 2Pn1 + Pn ??? niiiSS CPA S L1????? niinn1)1(121?? nA S LSS① 只考慮查找成功時(shí)的情況 在順序查找的過(guò)程中，式（ 9－ 1）中 Ci取決于所查記錄在表中的位置。 假設(shè)查找每個(gè)記錄的概率相等，即 Pi＝ 1/n。則在等概率情況下順序查 找的平均查找長(zhǎng)度為： ② 考慮查找成功和查找不成功時(shí)的情況 順序查找中，不論給定值 key為何值，查找不成功時(shí)和給定值進(jìn)行比較的關(guān) 鍵字個(gè)數(shù)均為 n＋ 1。 假設(shè)查找成功與不成功的可能性相同，對(duì)每個(gè)記錄的查找概率也相等，則 Pi＝ 1/(2n)，此時(shí)順序查找的平均查找長(zhǎng)度為： )1(21)1(211????? ??ninnA SL niSS )1(43 ?? n缺點(diǎn)：平均查找長(zhǎng)度較大，特別是當(dāng) n很大時(shí)，查找效率較低。 （ 4）順序查找算法的特點(diǎn) 優(yōu)點(diǎn)：算法簡(jiǎn)單且適應(yīng)面廣。它對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論 記錄是否按關(guān)鍵字有序均可應(yīng)用。 ￡ 有序表的查找 （ 1）有序表查找的實(shí)現(xiàn) 折半查找 （ Binary Search）的 查找過(guò)程 ：先選定待查記錄所在范 圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 特點(diǎn) : 查找過(guò)程：每次將待查記錄所在區(qū)間縮小一半 適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表 算法實(shí)現(xiàn) : 設(shè)表長(zhǎng)為 n， low、 high和 mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn) ,k為給定值 初始時(shí)，令 low=1,high=n,mid=?(low+high)/2? 讓 k與 mid指向的記錄比較 若 k==r[mid].key， 查找成功 若 kr[mid].key， 則 high=mid1 若 kr[mid].key， 則 low=mid+1 重復(fù)上述操作，直至 lowhigh時(shí)，查找失敗 int Search_Bin (SSTable ST, KeyType key) { //在有序表 ST中折半查找其關(guān)鍵字等于 key的數(shù)據(jù)元素。 //若找到，則函數(shù)值為該元素在表中的位置，否則為 0。 low = 1。 //置區(qū)間初值 high = 。 //low和 high分別指示待查元素所在范圍的下界和上界 while (low = high) { mid = (low + high) / 2。 //mid指示區(qū)間的中間位置 if (EQ(key, [mid].key)) //找到待查元素 return mid。 else if (LT(key, [mid].key)) //繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 high = mid－ 1。 else low = mid + 1。 //繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 } // while return 0。 } // Search_Bin 算法 ： ? 算法描述 low high mid 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 21 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 找 70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 ? 二分查找實(shí)現(xiàn)時(shí)可以用鏈表嗎 ? （ 3）性能分析 ① 查找算法的判定樹(shù) 判定樹(shù) ：描述查找過(guò)程的二叉樹(shù)。 判定樹(shù)中圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)；方形結(jié)點(diǎn)為外部結(jié)點(diǎn)（由內(nèi)部結(jié)點(diǎn)的 空指針域鏈接）。 樹(shù)中每個(gè)圓形結(jié)點(diǎn)標(biāo)識(shí)表中一個(gè)記錄 ，結(jié)點(diǎn)中的值為該 記錄在表中的位置。 方形結(jié)點(diǎn)中的值 v為：第 i結(jié)點(diǎn)的值 v 第 i＋ 1結(jié)點(diǎn)的 值； 若 i結(jié)點(diǎn)為第 1個(gè)結(jié)點(diǎn)則 v 第 1個(gè)結(jié)點(diǎn)的值；若 i結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)則 v 最后一個(gè)結(jié)點(diǎn)的值。 多不超過(guò)樹(shù)的深度，而具有 n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度為 ，所以， 顯然，折半查找法在查找成功（或不成功）時(shí)進(jìn)行比較的關(guān)鍵字個(gè)數(shù)最 ? ? 1log 2 ?n折半查找法在查找成功時(shí)和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)至多為 。 ? ? 1log 2 ?n 例如，上述 11個(gè)元素的表的例子。查找 21的過(guò)程如紅線所示，查找 85的過(guò)程如藍(lán)線所示。 圖 判定樹(shù)和查找 21(紅線 )， 85(藍(lán)線 )的過(guò)程 6 3 9 1 4 7 10 2