【正文】 [第 18頁 /81] 分塊查找算法描述 step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表； step2 查找分兩個部分： – 先對索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中； – 在已確定的塊中用順序法進(jìn)行查找。 則查找過程如下： 第 1次 ： { 5， 6， 11， 17， 21， 23， 28， 30， 32， 40 } low=0 mid=(0+9)/2 =4 high=9 等概率情況下其平均查找長度 為 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 下一頁 上一頁 停止放映 [第 17頁 /81] 分塊查找 ? 分塊查找又稱索引順序查找 ， 這是順序查找的一種改進(jìn)方法 。 //查找成功 else if( key[mid].x ) high = mid1。 low = 0。 下一頁 上一頁 停止放映 [第 14頁 /81] ? 算法步驟： – step1 首先確定整個查找區(qū)間的中間位置 ， mid = （ left + right ） / 2 – step2 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較； ?若相等 ， 則查找成功； ?若大于 ， 則在后半?yún)^(qū)域繼續(xù)進(jìn)行二分查找； ?若小于 ， 則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找 。 即通過一次比較 ， 將查找區(qū)間縮小一半 。 //從后往前找 return k。 下一頁 上一頁 停止放映 [第 11頁 /81] 改進(jìn)的順序查找算法 C++語言描述如下： int SqSearch(SSTable amp。 下一頁 上一頁 停止放映 [第 10頁 /81] 在 上述算法中為了避免 “ 出界 ” ，需在循環(huán)中作 k 的判斷，這使算法的執(zhí)行時間幾乎增加一倍。 if (k) return k+1。L, KeyType key) { int k = 0。 下一頁 上一頁 停止放映 [第 7頁 /81] 算法描述 ? 查找操作步驟： – step1 從第 1個元素開始查找； – step2 用待查關(guān)鍵字值與各結(jié)點(diǎn)（ 記錄 ） 的關(guān)鍵字值逐個進(jìn)行比較；若找到相等的結(jié)點(diǎn) ， 則查找成功；否則 ， 查找失敗 。 //存儲空間地址 int length。 下一頁 上一頁 停止放映 [第 4頁 /81] 平均查找長度： 為了確定數(shù)據(jù)元素在查找表中的位置，需要將給定值和表中的數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較的次數(shù)的期望值。 動態(tài)查找的例子 ——詞匯統(tǒng)計問題。 下一頁 上一頁 停止放映 [第 3頁 /81] 靜態(tài)查找表 : 查找表一旦建立 ， 在以后的查找過程中就不會改變 。 查找表是具有一定存儲結(jié)構(gòu)的數(shù)據(jù)集合，比如順序表結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、樹形結(jié)構(gòu)等。 查找往往根據(jù)數(shù)據(jù)元素的某個屬性進(jìn)行。 它所對應(yīng)的查找算法屬于靜態(tài)查找技術(shù) 。就是統(tǒng)計一篇文章中使用了多少詞匯以及每個詞匯的使用次數(shù)。平均查找長度 ASL的計算方法為： ???niii CPA S L1n 為表長； Pi為查找第 i個元素的概率。 //表的長度 }。 下一頁 上一頁 停止放映 [第 8頁 /81] 順序查找算法框圖 i=0 seq_search(A， n， key) A 待查表 n 元素個數(shù) key 要找的值 inamp。 while(kamp。 //返回數(shù)據(jù)元素位置 else return 0。為提高效率，對查找表的結(jié)構(gòu)改動如下： 適當(dāng)設(shè)置數(shù)組長度，將元素存于 data[1]至data[length1]中，在 0號單元預(yù)存待查找數(shù)據(jù) key作為監(jiān)視哨。L, KeyType key) { [0].x= key。 //找不到時 ， k為 0 } 該算法若查找成功 ， 則函數(shù)返回值為目標(biāo)元素在表中的位置 ， 否則返回 0。 ? 二分查找是一種高效的查找方法 。 – Step3 對確定的縮小區(qū)域再按二分公式 ， 重復(fù)上述步驟； – 最后 ， 得到結(jié)果： ?要么 ， 查找成功 ， 要么 ， 查找失敗 。 high = 。 //繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1。 ? 方法描述 ：將 n個數(shù)據(jù)元素 “ 按塊有序 ” 劃分為 m塊 （ m ? n） 。 下一頁 上一頁 停止放映 [第 19頁 /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的元素。 /* 塊最大值 */ int link。能否設(shè)計更好的算法？使其既有二分法的高效率，又有鏈表靈活性的查找方法？ ? 動態(tài)查找技術(shù)所依賴的查找表就是這樣的算法，例如二叉排序樹等。 下一頁 上一頁 停止放映 [第 22頁 /81] 二叉排序樹的定義： 二叉排序樹 可能為一棵空的二叉樹，若非空則 必須 滿足以下特征： （ 1）根結(jié)點(diǎn)左子樹中所有結(jié) 點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān) 鍵字； （ 2）根結(jié)點(diǎn)右子樹中所有結(jié) 點(diǎn)的關(guān)鍵字大于或等于根結(jié) 點(diǎn)的關(guān)鍵字； （ 3）根結(jié)點(diǎn)的左右子樹也都 是二叉排序樹。 下一頁 上一頁 停止放映 [第 24頁 /81] 二叉排序樹結(jié)點(diǎn)結(jié)構(gòu) typedef struct BinNode { ElemType x。 struct tree *create_btree(),*search_btree(),*root=0。 //插入頭結(jié)點(diǎn) else create_btrr(root,root,*s)。 while( key) //反復(fù)搜索循環(huán) { cout“Enter a key to find:”。 } } 下一頁 上一頁 停止放映 [第 28頁 /81] 生成二叉排序樹程序 struct tree create_btree(struct tree *root, struct tree *r, char info) { if (r == 0 ) { r = new (struct tree)。 rright=0。 //或插入右子 } else //若根為空 { rright=0。 //插入左子樹 if(info=rinfo) create_btree(r,rright,info)。 return root。 break 。假定由整數(shù)序列 {10， 6， 19， 22， 8， 2}生成一棵二叉排序樹，可以采用逐個元素插入的方法實(shí)現(xiàn)。 上述方法都是把查找建立在比較的基礎(chǔ)上 ， 而哈希查找則是通過計算存儲地址的方法進(jìn)行查找的 。 在哈希表中可以實(shí)現(xiàn)對數(shù)據(jù)元素的快速檢索 。 下一頁 上一頁 停止放映 [第 35頁 /81] 沖突及沖突處理 在哈希元素求解過程中 ， 不同關(guān)鍵字值對應(yīng)到同一個存儲地址的現(xiàn)象稱為沖突 。 處理沖突是建立哈希表過程中不可缺少的一部分 。 下一頁 上一頁 停止放映 [第 38頁 /81] 鏈地址法處理沖突 對給定數(shù)列 { 22,41,53,46,30,13,1,67 },建立哈希表 。 若該地址對應(yīng)的存儲空間還沒有被占用 ， 則將該元素存入；否則執(zhí)行 step2解決沖突 。 表長取 9,即 [0~8]。 Step2 重復(fù)計算處理沖突的下一個存儲地址 Dk=R （ Dk1 ） ， 直到 HST[Dk] 為空 ， 或HST[Dk}=k為止 。 查找 key = 21 比較 8次找不到 ,查找失敗。 這些關(guān)鍵字相互之間可以進(jìn)行比較 ， 即在它們之間存在著這樣一個關(guān)系Kp1≤K p2≤ … ≤K pn， 按此固有關(guān)系將最初的記錄序列重新排列為 { Rp1, Rp2, … ， Rpn }的操作稱作排序 。 簡單的排序法 包括插入排序、選擇排序、冒泡排序等，它們的時間復(fù)雜度為 O(n2)。 下一頁 上一頁 停止放映 [第 51頁 /81] 插入排序算法步驟 ? Step1 從有序數(shù)列 {a1}和無序數(shù)列 {a2,a3,… ,an}開始進(jìn)行排序 。 下一頁 上一頁 停止放映 [第 52頁 /81] 插入排序舉例 設(shè)有數(shù)列 { 18， 12， 10， 12， 30， 16 } 初始狀態(tài)： {18}， {12， 10， 12， 30， 16} 比較次數(shù) i=1 {18}， {12， 10， 12， 30， 16} 1 i=2 {12， 18}， {10， 12， 30， 16} 2 i=3 {10， 12， 18}， {12， 30， 16} 2 i=4 {10， 12， 12， 18}， {30， 16} 1 i=5 {10， 12， 12， 18， 30}， {16} 3 {10， 12， 12， 16， 18， 30 } 總計： 9 次 下一頁 上一頁 停止放映 [第 53頁 /81] 插入排序算法 insert_sort(int *item , int n ) { int i， j， t 。