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