【正文】 return j。 } 19 搜索 (Search)的概念 靜態(tài)搜索表 ? 所謂 搜索 ， 就是在數(shù)據(jù)集合中尋找滿足某 ? 種條件的數(shù)據(jù)對象 。 ? 搜索的結(jié)果通常有兩種可能： ? 搜索成功 ，即找到滿足條件的數(shù)據(jù)對象 這時 ,作為結(jié)果 , 可報告該對象在結(jié)構(gòu)中 的位置 , 還可給出該對象中的具體信息。 ? 搜索不成功 ，或搜索失敗。作為結(jié)果 , 應(yīng)報告一些信息 , 如失敗標(biāo)志、位置等。 20 ? 通常稱用于搜索的數(shù)據(jù)集合為 搜索結(jié)構(gòu) ，它是由 同一數(shù)據(jù)類型的對象 (或記錄 )組成。 ? 在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標(biāo)識這個對象。稱為關(guān)鍵碼。 使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。 但在實際應(yīng)用時，搜索條件是多方面的，可以 使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。 21 ? 實施搜索時有兩種不同的環(huán)境。 ? 靜態(tài)環(huán)境 ，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。 ? 靜態(tài)搜索表 ? 動態(tài)環(huán)境 ，為保持較高的搜索效率 , 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 ? 動態(tài)搜索表 22 define MaxSize 100 //搜索表最大尺寸 typedef int DataType。 //搜索數(shù)據(jù)的類型 typedef struct { //搜索表結(jié)點定義 DataType key。 //關(guān)鍵碼域 other。 //其他數(shù)據(jù)域 } ListNode。 typedef struct dataList { //搜索表結(jié)點定義 ListNode data[MaxSize]。 //數(shù)據(jù)存儲數(shù)組 int n。 //數(shù)組當(dāng)前長度 } 靜態(tài)搜索表結(jié)構(gòu)的定義 23 ? 衡量一個搜索算法的時間效率的標(biāo)準(zhǔn)是：在搜索過程中關(guān)鍵碼的 平均比較次數(shù) ， 也稱為 平均搜索長度 ASL(Average Search Length)， 通常它是 搜索結(jié)構(gòu)中對象總數(shù) n的函數(shù) 。 ? 在靜態(tài)搜索表中 , 利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)對象的存放地址 。 搜索算法 根據(jù)給定值 x, 在數(shù)組中進(jìn)行搜索 。 直到 找到 x在數(shù)組中的位置或可確定在數(shù)組中 找不到 x為止 。 ? 另外衡量一個搜索算法還要考慮算法所需要的存儲量和算法的復(fù)雜性等問題。 24 順序搜索 (Sequential Search) ? 所謂順序搜索 , 又稱線性搜索 , 主要用于在線性結(jié)構(gòu)中進(jìn)行搜索 。 ? 設(shè)若表中有 n 個對象 ， 則順序搜索從表的先端 (或后端 ) 開始 , 順序用各對象的關(guān)鍵碼與 給定值 x 進(jìn)行比較 , 直到找到與其值相等的對象 , 則搜索成功 。 給出該對象在表中的位置 。 ? 若整個表都已檢測完仍未找到關(guān)鍵碼與 x相等的對象 , 則搜索失敗 。 給出失敗信息 。 25 int LinearSearch ( dataList A, DataType x ) { //在數(shù)據(jù)表 [1..n]中順序搜索關(guān)鍵碼為 x //的數(shù)據(jù)對象 , [0].key 作為控制搜索自動 //結(jié)束的 “ 監(jiān)視哨 ” 使用 [0].key = x。 int i = 。 //將 x送 0號位置設(shè)置監(jiān)視哨 while ( [i].key != x ) i 。 //從后向前順序搜索 return i。 } 設(shè)置“監(jiān)視哨”的順序搜索算法 26 順序搜索的平均搜索長度 ?????????1010niiniiis u c c pcpA SL ) 1 ( .)( 11???? ??inpA S Lniis u c c設(shè)搜索第 i 個元素的概率為 pi , 搜索到第 i 個元素所需比較次數(shù)為 ci , 則搜索成功的平均搜索長度 : 在順序搜索并設(shè)置“監(jiān)視哨”情形： ci = n i +1, i = n, n1, ?, 1，因此 27 .)()(?????????? nis u c cnnnninnA SL1 2121111在等概率情形， pi = 1/n, i = 1, 2, ?, n。 在搜索不成功情形， ASLunsucc = n+1. 28 順序搜索的遞歸算法 int SequentSearch ( dataList A, dataType x, intamp。 loc ) { //在數(shù)據(jù)表 [0..n1] 中搜索其關(guān)鍵碼與 //給定值匹配的對象 , 函數(shù)返回其表中位置。 //參數(shù) loc 是在表中開始搜索位置 if ( loc = ) return 1。 //搜索失敗 else if ( [loc].key == x ) return loc。 //搜索成功 else return SequentSearch ( A, x, loc+1 )。 //遞歸搜索 } 29 int SequentSearch ( dataList A, DataType x ) { //在數(shù)據(jù)表 [0..n1] 中 順序搜索關(guān)鍵碼為 x 的數(shù)據(jù)對象 for ( int i = 0。 i 。 i++ ) if ( [i].key == x ) return i。 //成功 else if ( [i].key x ) break。 return 1。 //順序搜索失敗 , 返回失敗信息 } 基于有序順序表的順序搜索算法 30 ? 有序順序表的順序搜索 ( 10, 20, 30, 40, 50, 60 ) 10 50 60 = = = = = = 20 30 40 ? ?27161 50??? ??is u c c iA SL? ?7276171 50?????????????iu n s u c ciA SL31 基于有序順序表的折半搜索 ? 設(shè) n個對象存放在一個按其關(guān)鍵碼從小到大排好了序的有序順序表中 。 ? 折半搜索時 , 先求位于搜索區(qū)間正中的對象的下標(biāo) mid， 用其關(guān)鍵碼與 給定值 x比較 : ? [mid].key == x, 搜索成功 ； ? [mid].key x, 把搜索區(qū)間縮小到 表的 前半部分 ， 繼續(xù)折半搜索 ； ? [mid].key x， 把搜索區(qū)間縮小到表的 后半部分 ， 繼續(xù)折半搜索 。 ? 如果搜索區(qū)間已縮小到一個對象 ， 仍未找到想要搜索的對象 ， 則搜索失敗 。 32 搜索成功的例子 1 0 1 3 4 6 8 10 12 6 0 1 2 3 4 5 6 7 8 搜索 low mid high 6 6 8 10 12 5 6 7 8 low mid high 6 6 5 low mid high 6 33 搜索失敗的例子 1 0 1 3 4 6 8 10 12 5 0 1 2 3 4 5 6 7 8 搜索 low mid high 5 6 8 10 12 5 6 7 8 low mid high 6 5 5 low mid high 5 34 int BinarySearch ( dataList A, DataType x, int low, int high ) { int mid = 1。 if ( low = high ) { mid = ( low + high ) / 2。 if ( [mid].key x ) mid = BinarySearch ( A, x, mid +1, high )。 else if ( [mid].key x ) mid = BinarySearch ( A, x, low, mid 1 )。