【正文】 的二叉排序樹(shù)。能否設(shè)計(jì)更好的算法？使其既有二分法的高效率，又有鏈表靈活性的查找方法？ ? 動(dòng)態(tài)查找技術(shù)所依賴(lài)的查找表就是這樣的算法，例如二叉排序樹(shù)等。 示例 下一頁(yè) 上一頁(yè) 停止放映 [第 21頁(yè) /81] 動(dòng)態(tài)查找技術(shù) ? 前兩種查找方法各有千秋。 /* 塊最大值 */ int link。在第 3塊中用順序法查找 ,比較兩次 ,就可以找出 60的元素來(lái)。 下一頁(yè) 上一頁(yè) 停止放映 [第 19頁(yè) /81] 分塊查找舉例 有數(shù)列如下： { 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47} 按 “ 塊有序 ” 分三塊 : (22,12,13,9,8),(33,42,44,38,24), (48,60,58,74,47) 選取每塊中最大的關(guān)鍵字組成索引表 [22,44,74],查找關(guān)鍵字值為 60的元素。 每個(gè)塊中元素不一定是有序的 。 ? 方法描述 ：將 n個(gè)數(shù)據(jù)元素 “ 按塊有序 ” 劃分為 m塊 （ m ? n） 。 //不存在待查元素 } 下一頁(yè) 上一頁(yè) 停止放映 [第 16頁(yè) /81] 對(duì)給定有序數(shù)列 { 5， 6， 11， 17， 21， 23， 28， 30，32， 40}進(jìn)行半查找算法 ， 查找關(guān)鍵字值為 30的數(shù)據(jù)元素 。 //繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1。 if(key==[mid].x) return mid+1。 high = 。L, KeyType key ) { int low, high, mid。 – Step3 對(duì)確定的縮小區(qū)域再按二分公式 ， 重復(fù)上述步驟； – 最后 ， 得到結(jié)果： ?要么 ， 查找成功 ， 要么 ， 查找失敗 。 但是 ， 二分查找的先決條件是查找表中的數(shù)據(jù)元素必須有序 。 ? 二分查找是一種高效的查找方法 。 算法討論 例子 下一頁(yè) 上一頁(yè) 停止放映 [第 13頁(yè) /81] 2．折半查找 (也稱(chēng)二分查找 ) ? 算法思想： 將 有序數(shù)列 的 中點(diǎn) 設(shè)置為比較對(duì)象 ， 如果要找的元素值小于該中點(diǎn)元素 ， 則將待查序列縮小為左半部分 ， 否則為右半部分 。 //找不到時(shí) ， k為 0 } 該算法若查找成功 ， 則函數(shù)返回值為目標(biāo)元素在表中的位置 ， 否則返回 0。 while([k].x!=key) k=k1。L, KeyType key) { [0].x= key。 因?yàn)檠h(huán)查找過(guò)程至少會(huì)在 0號(hào)單元停止，這樣就不必在每一次循環(huán)中都判別是否數(shù)組出界。為提高效率，對(duì)查找表的結(jié)構(gòu)改動(dòng)如下： 適當(dāng)設(shè)置數(shù)組長(zhǎng)度，將元素存于 data[1]至data[length1]中，在 0號(hào)單元預(yù)存待查找數(shù)據(jù) key作為監(jiān)視哨。 這里元素位置從 1開(kāi)始算起 。 //返回?cái)?shù)據(jù)元素位置 else return 0。[k].x!=key) k++。 while(kamp。A[i]!=key? Y N 查找 key的循環(huán) 顯示“查找失敗” 返回 開(kāi)始 i++ A[i]==key? Y N 顯示“查找成功” 下一頁(yè) 上一頁(yè) 停止放映 [第 9頁(yè) /81] 順序查找算法 C++語(yǔ)言描述如下： int SqSearch(SSTable amp。 下一頁(yè) 上一頁(yè) 停止放映 [第 8頁(yè) /81] 順序查找算法框圖 i=0 seq_search(A， n， key) A 待查表 n 元素個(gè)數(shù) key 要找的值 inamp。 下一頁(yè) 上一頁(yè) 停止放映 [第 6頁(yè) /81] 1．順序查找 順序查找的方法是從表的一端開(kāi)始 ， 逐一比較給定的數(shù)據(jù) key和表中數(shù)據(jù)元素的關(guān)鍵字 x的值 ， 若兩個(gè)數(shù)據(jù)一致則查找成功 ， 同時(shí)給出該數(shù)據(jù)元素在表中的位置 ，否則查找失敗 。 //表的長(zhǎng)度 }。 在等概率條件下（ Pi=1/n）這時(shí)平均查找長(zhǎng)度為： 11???niiP其中 ： ???niiCnA S L11下一頁(yè) 上一頁(yè) 停止放映 [第 5頁(yè) /81] 靜態(tài)查找技術(shù) 假設(shè)靜態(tài)順序查找表的存儲(chǔ)結(jié)構(gòu)為： struct SSTable{ ElemType *data。平均查找長(zhǎng)度 ASL的計(jì)算方法為： ???niii CPA S L1n 為表長(zhǎng)； Pi為查找第 i個(gè)元素的概率。顯然，這個(gè)查找表是不斷擴(kuò)張的。就是統(tǒng)計(jì)一篇文章中使用了多少詞匯以及每個(gè)詞匯的使用次數(shù)。 它所對(duì)應(yīng)的查找算法屬于動(dòng)態(tài)查找技術(shù) 。 它所對(duì)應(yīng)的查找算法屬于靜態(tài)查找技術(shù) 。這種被用于查找的元素屬性一般稱(chēng)為 關(guān)鍵字 ，它往往可以唯一標(biāo)識(shí)一個(gè)元素。 查找往往根據(jù)數(shù)據(jù)元素的某個(gè)屬性進(jìn)行。下一頁(yè) 上一頁(yè) 停止放映 第 2章 查找和排序 西安交通大學(xué)計(jì)教中心 下一頁(yè) 上一頁(yè) 停止放映 [第 2頁(yè) /81] 查找基本概念 查找表 : 由同一類(lèi)數(shù)據(jù)構(gòu)成的用于查找的集合被稱(chēng)作查找表。 查找表是具有一定存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)集合，比如順序表結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、樹(shù)形結(jié)構(gòu)等。例如根據(jù)學(xué)號(hào)查找某個(gè)學(xué)生記錄。 下一頁(yè) 上一頁(yè) 停止放映 [第 3頁(yè) /81] 靜態(tài)查找表 : 查找表一旦建立 ， 在以后的查找過(guò)程中就不會(huì)改變 。 動(dòng)態(tài)查找表 ： 查找表建立后 ， 在后來(lái)的查找過(guò)程中仍會(huì)改變查找表的內(nèi)容 。 動(dòng)態(tài)查找的例子 ——詞匯統(tǒng)計(jì)問(wèn)題。 解決方法是先建立一個(gè)空的查找表，以后每讀到一個(gè)詞就在查找表中查詢(xún)一下，如果該詞匯存在則將其使用次數(shù)加一，否則將新詞插入到查找表中并設(shè)使用次數(shù)為一次。 下一頁(yè) 上一頁(yè) 停止放映 [第 4頁(yè) /81] 平均查找長(zhǎng)度： 為了確定數(shù)據(jù)元素在查找表中的位置，需要將給定值和表中的數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較的次數(shù)的期望值。 Ci為找到該記錄時(shí)，曾和給定值比較過(guò)的數(shù)據(jù)元素的個(gè)數(shù)。 //存儲(chǔ)空間地址 int length。 順序查找表元素存放在 data[0]至 data[length1]中。 下一頁(yè) 上一頁(yè) 停止放映 [第 7頁(yè) /81] 算法描述 ? 查找操作步驟： – step1 從第 1個(gè)元素開(kāi)始查找； – step2 用待查關(guān)鍵字值與各結(jié)點(diǎn)（ 記錄 ） 的關(guān)鍵字值逐個(gè)進(jìn)行比較；若找到相等的結(jié)點(diǎn) ， 則查找成功；否則 ， 查找失敗 。amp。L, KeyType key) { int k = 0。amp。 if (k) return k+1。 } 該算法若查找成功 ， 則函數(shù)返回值為目標(biāo)元素在表中的位置 ， 否則返回 0。 下一頁(yè) 上一頁(yè) 停止放映 [第 10頁(yè) /81] 在 上述算法中為了避免 “ 出界 ” ，需在循環(huán)中作 k 的判斷，這使算法的執(zhí)行時(shí)間幾乎增加一倍。改寫(xiě)查找過(guò)程為從后往前查找。 下一頁(yè) 上一頁(yè) 停止放映 [第 11頁(yè) /81] 改進(jìn)的順序查找算法 C++語(yǔ)言描述如下： int SqSearch(SSTable amp。 //監(jiān)視哨 int k = 。 //從后往前找 return k。 下一頁(yè) 上一頁(yè) 停止放映 [第 12頁(yè) /81] 對(duì)于改進(jìn)的順序查找而言 ， 找到第 i個(gè)元素的比較次數(shù) Ci = ni+1， 所以在等概率查找的情況下 ， 順序表查找的平均查找長(zhǎng)度為： ? ? 2 1111????? ??ninnA SLniASL≤ n 2 ?優(yōu)點(diǎn) : ?對(duì)結(jié)點(diǎn)的邏輯次序 (不必有序 )和存儲(chǔ)結(jié)構(gòu) (順序、鏈表均可）無(wú)要求； ?當(dāng)序列中記錄 “ 基本有序 ” 或 N值較小時(shí)，是較好的算法； ?缺點(diǎn)： ?ASL較長(zhǎng) ?討論：能否減少比較次數(shù)，以提高效率。 即通過(guò)一次比較 ， 將查找區(qū)間縮小一半 。 它可以明顯減少比較次數(shù) ， 提高查找效率 。 下一頁(yè) 上一頁(yè) 停止放映 [第 14頁(yè) /81] ? 算法步驟： – step1 首先確定整個(gè)查找區(qū)間的中間位置 ， mid = （ left + right ） / 2 – step2 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較； ?若相等 ， 則查找成功； ?若大于 ， 則在后半?yún)^(qū)域繼續(xù)進(jìn)行二分查找； ?若小于 ， 則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找 。 下一頁(yè) 上一頁(yè) 停止放映 [第 15頁(yè) /81] 折半查找算法的 C++語(yǔ)言描述如下： int BinSearch( SSTable amp。 low = 0。 //設(shè)置查找區(qū)間初值 while (low = high) { mid = (low + high) / 2。 //查找成功 else if( key[mid].x ) high = mid1。 //繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 } return 0。 則查找過(guò)程如下： 第 1次 ： { 5， 6， 11， 17， 21， 23， 28， 30， 32， 40 } low=0 mid=(0+9)/2 =4 high=9 等概率情況下其平均查找長(zhǎng)度 為 1)1(l o g 2 ??? nA S L ，即 O(log2n) 例子 第 2次： { 5， 6， 11， 17， 21， 23， 28， 30， 32， 40 } low=5 mid=7 high=9 下一頁(yè) 上一頁(yè) 停止放映 [第 17頁(yè) /81] 分塊查找 ? 分塊查找又稱(chēng)索引順序查找 ， 這是順序查找的一種改進(jìn)方法 。 每一塊中的結(jié)點(diǎn)不必有序 ， 但塊與塊之間必須 “ 按塊有序 ” ；即第 1快中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第 2塊中任一元素又都必須小于第 3塊中的任一元素 ， …… 。 下一頁(yè) 上一頁(yè) 停止放映 [第 18頁(yè) /81] 分塊