【正文】 查找表中的位置。 第 8章 查找 ? 分塊查找過程，分為兩個步驟： ? 第一步：索引表查找，先用給定值 kx在索引表中檢測索引項，確定該值在查找表中的分塊位置 。 /*存放索引表中元素個數(shù) */ }Sq_Index。 typedef struct{ /*索引表的數(shù)據(jù)類型 */ IndexNode index[MAXINDEXNODE]。 /*存放對應塊中的最大關(guān)鍵碼值 */ int link。查找時，先用對半法由最大關(guān)鍵字查出所在的塊，再用線性法在塊中查找。 第 8章 查找 3. 分塊查找 （索引順序查找 ） 【 查找過程 】 將 n個元素均勻地分成塊，每塊有 s個記錄，塊間按大小排序，塊內(nèi)元素不排序。 ? 例如 13個元素的折半查找判定樹如下（結(jié)點中的值為數(shù)據(jù)元素在順序表中的位置）： 第 8章 查找 11～ 13 描述折半查找過程的判定樹 ………………………… ..… 比較 1次 8～ 13 8～ 9 4～ 6 1～ 2 1～ 6 12 9 6 3 1 10 13 7 5 11 8 2 4 …………………… 比較 2次 ……… ..… 比較 3次 …… 比較 4次 ASL=（ 1 1＋ 2 2＋ 4 3＋ 6 4） /13＝ 41/13 第 8章 查找 【 折半（二分）查找方法的特點 】 ? 僅適用于有序表 ； ? 只適用順序存儲結(jié)構(gòu)的表 ， 要求表中元素基本不變， 在需要插入或刪除運算時 ， 影響檢索效率 ； ? 平均查找長度最小 ， ? ASL=(n+1)/n * log2（ n+1） 1 ? ASL=log2（ n+1） 1 (N50) ? 時間復雜度 O（ log2n） 第 8章 查找 分塊查找 ? 分塊查找要求將查找表分成若干個子表，每個子表稱之為“塊”，要求順序表中的數(shù)據(jù)元素“按塊有序”。 /*查找不成功 */ ? } 第 8章 查找 low high mid 例 1 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 令 low=1,high=n, mid=?(low+high)/ 若 k[mid].key， 則 high=mid1 若 k[mid].key， 則 low=mid+1 成功 第 8章 查找 例 2 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 第 8章 查找 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high lowhigh 不成功 第 8章 查找 算法性能分析 ? 從折半查找過程看，以表的中點為比較對象，并以中點將表分割為兩個子表，對定位到的子表繼續(xù)這種操作。 第 8章 查找 對于有序表 st，給定關(guān)鍵碼值 kx，折半查找的步驟如下： ① 設(shè)置初始區(qū)間： low=1； high=； ② 當 lowhigh時，表示在 low和 high區(qū)間內(nèi)沒有數(shù)據(jù)元素，說明查找不成功，返回查找失敗信息； ③ 當 low≤high，設(shè)置中間點 mid=(low+high)/2，這時存在三種情況： a. 若 kx=[mid].key，說明查找成功，返回數(shù)據(jù)元素在表中位置； b. 若 kx[mid].key， high=mid1；轉(zhuǎn)② ，在左半?yún)^(qū)繼續(xù)查找； c. 若 kx[mid].key， low=mid+1；轉(zhuǎn)② ，在右半?yún)^(qū)繼續(xù)查找； 第 8章 查找 算法 83 折半查找算法 ? int binsearch(Sq_Table st， KeyType kx) { /* 在有序表 st中查找關(guān)鍵碼值為 kx的數(shù)據(jù)元素，若找到返回該元素在表中的位置，否則，返回 0 */ int mid； low=1； high=； /*設(shè)置初始區(qū)間 */ while(low=high) /* 表空測試 */ { /* 非空，進行比較測試 */ mid = (low+high)/2； /*得到中點 */ if(kx == [mid].key) return mid。 ? 折半查找的思想為 ：在有序表中，取中間元素作為比較對象，若給定值與中間元素的關(guān)鍵碼相等，則查找成功；若給定值小于中間元素的關(guān)鍵碼，則在中間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵碼，則在中間元素的右半?yún)^(qū)繼續(xù)查找。 ? 在有序表中，查找運算可以用效率更高的折半查找來實現(xiàn)。 else return i； } 第 8章 查找 ? 不足之處：每次比較的時候都要判斷 ? i = ? 可不可以不做這個判斷，以減少比較次數(shù)？ 第 8章 查找 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個元素： 1 查找第 n1個元素： 2 ………. 查找第 1個元素： n 查找第 i個元素： n+1i 查找失敗 ： n+1 第 8章 查找 算法 82 設(shè)置監(jiān)視哨的順序查找算法 ? int search_sqtable(Sq_Table st， KeyType kx) { /*在表 st中查找關(guān)鍵碼值為 kx的數(shù)據(jù)元素，若找到返回該元素在數(shù)組中的下標，否則返回 0 */ int i=。amp。 第 8章 查找 ? int search_sqtable(Sq_Table st， KeyType kx) { /*在表 st中查找關(guān)鍵碼值為 kx的數(shù)據(jù)元素，若找到返回該元素在數(shù)組中的下標，否則返回 0 */ int i = 1。 typedef struct{ RecNode elem[MAXNODENUM]； /* 數(shù)據(jù)元素 */ int length； /* 順序表中數(shù)據(jù)元素的個數(shù) */ }Sq_Table； 第 8章 查找 查找方法： ? 順序查找 （線性查找） 從表的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者符合，查到所要找的元素為止。 define MAXNODENUM 1000 typedef struct{ KeyType key。對一個含 n個數(shù)據(jù)元素的表， 查找成功 時： ??niii cpA SL1*＝第 8章 查找 4 靜態(tài)查找與動態(tài)查找 ?靜態(tài)查找表 ：一個查找表只進行查詢某個特定的數(shù)據(jù)元素或某個特定數(shù)據(jù)元素的各種屬性的操作 。 平均查找長度 ASL是指為確定數(shù)據(jù)元素在表中的位置所進行的關(guān)鍵碼比較次數(shù)的期望值（平均值）。 能唯一標識數(shù)據(jù)元素的數(shù)據(jù)項 為主關(guān)鍵碼 ，否則稱為 次關(guān)鍵碼。 ? 集合中的數(shù)據(jù)元素的邏輯結(jié)構(gòu)是松散的數(shù)據(jù)結(jié)構(gòu)。 第 8章 查找 第 8章 查找 ? 基本概念與基本運算 ? 靜態(tài)查找表 ? 動態(tài)查找表 1——樹表