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