【正文】 ② 表空測試 ， 非空； mid=7 ③ 得到中點 ， 比較測試為 a情形 ↑ ↑ low=1 high=6 high=mid1， 調(diào)整到左半?yún)^(qū) ────────────────────────── ↑ ② 表空測試 ， 非空； mid=3 ③ 得到中點 ， 比較測試為 b情形 ↑ ↑ low=4 high=6 low=mid+1， 調(diào)整到右半?yún)^(qū) ─────────────────────────── 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 26 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ② 表空測試 ， 非空； mid=5 ③ 得到中點 ， 比較測試為 a情形 ↑↑ low=4 high=4 high=mid1， 調(diào)整到左半?yún)^(qū) ──────────────────────────── ↑ ② 表空測試 ， 非空； mid=4 ③ 得到中點 ， 比較測試為 b情形 ↑ ↑ high=4 low=5 low=mid+1， 調(diào)整到右半?yún)^(qū) ──────────────────────────── ② 表空測試 ， 為空；查找失敗 ， 返回查找失敗信息為 0 ──────────────────────────── 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 27 【 算法 】 int Binary_Search(S_TBL tbl， KEY kx) { /* 在表 tbl中查找關(guān)鍵碼為 kx的數(shù)據(jù)元素 ， 若找到返回該元素在表中的位置 ， 否則 ，返回 0 */ int mid， flag=0； low=1； high=length； /* ① 設(shè)置初始區(qū)間 */ while(low=high) /* ② 表空測試 */ { /* 非空 ， 進行比較測試 */ mid=(low+high)/2； /* ③ 得到中點 */ if (kx[mid].key) high=mid1； /* 調(diào)整到左半?yún)^(qū) */ else if(kx[mid].key) low=mid+1； /* 調(diào)整到右半?yún)^(qū) */ else { flag=mid； break； } /* 查找成功 ， 元素位置設(shè)置到 flag中 */ } return flag。 對于 n個結(jié)點的判定樹 ，樹高為 k， 則有 2k11n≤2k1， 即 k1log2(n+1)≤k， 所以k= 。 假設(shè)表中每個元素的查找是等概率的 ， 則樹的第 i層有 2i1個結(jié)點 ， 因此 ， 折半查找的平均查找長度為： ? ?)1(lo g 2 ?n2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 30 ASL= Pi 二叉排序樹 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 33 由圖 中 可以看出 ， 對二叉排序樹進行中序遍歷 ， 便可得到一個按關(guān)鍵碼有序的序列 ， 因此 ，一個無序序列 ， 可通過構(gòu)一棵二叉排序樹而成為有序序列 。 /*數(shù)據(jù)元素字段 */ struct NODE *lc,*rc。 while(*q) /*從根結(jié)點開始查找 */ if(kx(*q)) /*kx大于當前結(jié)點 *q的元素關(guān)鍵碼 */ { *p=*q。} /*將當前結(jié)點 *q的左子女置為新根 */ else {flag=1。 因此 ， 新插入結(jié)點一定是作為葉子結(jié)點添加上去的 。 if (!SearchElem(t,amp。 /*申請結(jié)點 ， 并賦值 */ s=kx。 /*設(shè)置插入成功標志 */ if (!p) t=s。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 38 【 例 】 記錄的關(guān)鍵碼序列為： 63， 90， 70， 55， 67， 42，98， 83， 10， 45， 58， 則構(gòu)造一棵二叉排序樹的過程如下： φ 63 70 55 67 42 98 83 63 90 63 90 70 63 90 55 70 63 90 67 55 70 63 90 42 67 55 70 63 90 98 42 67 55 70 63 90 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 39 83 98 42 67 55 70 63 90 10 45 58 83 98 42 67 55 70 63 90 10 45 83 98 42 67 55 70 63 90 10 從空樹開始建立二叉排序樹的過程 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 40 哈希表 查找（雜湊法） 哈希表與哈希方法 以上討論的查找方法 ， 由于數(shù)據(jù)元素的存儲位置與關(guān)鍵碼之間不存在確定的關(guān)系 ， 因此 ， 查找時 ，需要進行一系列對關(guān)鍵碼的查找比較 ， 即 “ 查找算法 ” 是建立在比較的基礎(chǔ)上的 ， 查找效率由比較一次縮小的查找范圍決定 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 42 哈希表與哈希方法 ： 選取某個函數(shù) ， 依該函數(shù)按關(guān)鍵碼計算元素的存儲位置 ， 并按此存放；查找時 ， 由同一個函數(shù)對給定值 kx計算地址 ， 將 kx與地址單元中元素關(guān)鍵碼進行比 ， 確定查找是否成功 ， 這就是哈希方法 (雜湊法 )；哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù) (雜湊函數(shù) )；按這個思想構(gòu)造的表稱為哈希表 (雜湊表 )。 可以說 ， 沖突不可能避免 ， 只能盡可能減少 。 常用的哈希函數(shù) 一 . 直接定址法 Hash(key)=a p一般選取質(zhì)數(shù) ， 也可以是不包含小于 20質(zhì)因子的合數(shù) 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 46 四 . 數(shù)字分析法 設(shè)關(guān)鍵碼集合中 ， 每個關(guān)鍵碼均由 m位組成 ， 每位上可能有 r種不同的符號 。 所選的位應是各種符號在該位上出現(xiàn)的頻率大致相同 。 六 、 折疊法 (Folding) 此方法將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分 ， 最后一部分位數(shù)可以短些 ， 然后將這幾部分疊加求和 ，并按哈希表表長 ， 取后幾位作為哈希地址 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 49 【 例 】 關(guān)鍵碼為 key=05326248725， 設(shè)哈希表長為三位數(shù) ， 則可對關(guān)鍵碼每三位一部分來分割 。 另外 ， 2 8同樣在哈希地址上有沖突 ， 也是由 H1找到空的哈希地址的； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 52 而 Hash(3)=3， 哈希地址上沖突 ， 由 H1=(Hash(3)+1) mod 11=4 仍然沖突； H2=(Hash(3)+2) mod 11=5 仍然沖突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址 ， 存入 。 di) mod m 其中： Hash(key)為哈希函數(shù) m為哈希表長度 ， m要求是某個 4k+3的質(zhì)數(shù) (k是整數(shù) ) di 為增量序列 12， 12， 22， 22， …… ， q2， q2且q≤ (1/2)*(m1) 【 例 】 關(guān)鍵碼集為 {47， 7， 29， 11， 16， 92， 22，8， 3}， 用二次探測法處理沖突 ， 建表如下： 0 1 2 3