【正文】 哈希表的元素表 ， 關(guān)鍵碼 0表示結(jié)束位置 */ finished=MovElemToHashTbl(eptr,linktbl,Hash(eptrkey))。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 53 2. 二次 探測法 Hi=(Hash(key)177。 2. 間界疊加法 ── 從一端向另一端沿各部分分界來回折疊后 ， 最后一位對齊相加 。 數(shù)字分析法根據(jù) r種不同的符號 ， 在各位上的分布情況 ， 選取某幾位 ， 組合成哈希地址 。 使用除留余數(shù)法 ， 選取合適的 p很重要 ， 若哈希表表長為 m， 則要求 p≤m， 且接近 m或等于 m。通常關(guān)鍵碼的集合比哈希地址集合大得多 ， 因而經(jīng)過哈希函數(shù)變換后 ， 可能將不同的關(guān)鍵碼映射到同一個哈希地址上 ， 這種現(xiàn)象稱為沖突 (Collision)， 映射到同一哈希地址上的關(guān)鍵碼稱為同義詞 。 /*插入結(jié)點(diǎn)為 p的左子女 */ } return flag。 /*在 *t為根的子樹上查找 */ { s=(NodeType *)malloc(sizeof(NodeType))。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 36 三 .二叉排序樹插入操作和構(gòu)造一棵二叉排序樹 先討論向二叉排序樹中插入一個結(jié)點(diǎn)的過程：設(shè)待插入結(jié)點(diǎn)的關(guān)鍵碼為 kx， 為將其插入 ， 先要在二叉排序樹中進(jìn)行查找 ， 若查找成功 ， 按二叉排序樹定義 ， 待插入結(jié)點(diǎn)已存在 ， 不用插入；查找不成功時 ， 則插入之 。 *q=t。 ⑵ 左右子樹也都是二叉排序樹 。 49 38 29 18 7 42 52 31 23 46 35 14 21 圖 例 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 29 可以看到 ， 查找表中任一元素的過程 ， 即是判定樹中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)鍵碼的比較次數(shù) ，也即該元素結(jié)點(diǎn)在樹中的層次數(shù) 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 19 有序表即是表中數(shù)據(jù)元素按關(guān)鍵碼升序或降序排列 。 就上述算法而言 ， 對于 n個數(shù)據(jù)元素的表 ， 給定值 kx與表中第 i個元素關(guān)鍵碼相等 ， 即定位第 i個記錄時 ， 需進(jìn)行 ni+1次關(guān)鍵碼比較 ， 即 Ci=ni+1。[i].keykx。 /* 出生日期類型定義 */ typedef struct { char year[5]； /* 年：用字符型表示 ， 寬度為 4個字符 */ char month[3]； /* 月：字符型 ， 寬度為 2 */ char date[3]； /* 日：字符型 ， 寬度為 2 */ }BirthDate； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 9 /* 數(shù)據(jù)元素類型定義 */ typedef struct { char number[7]； /* 學(xué)號：字符型 ， 寬度為 6 */ char name[9]； /* 姓名：字符型 ， 寬度為 8 */ char sex[3]； /* 性別：字符型 ， 寬度為 2 */ BirthDate birthdate； /* 出生日期：構(gòu)造類型 ， 由該類型的寬度確定 */ char efrom[21]； /* 來源：字符型 ， 寬度為 20 */ int results； /* 成績：整型 ， 寬度由 “ 程序設(shè)計 C語言工具軟件 ” 決定 */ } ElemType； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 10 以上定義的數(shù)據(jù)元素類型 ， 相當(dāng)于手工繪制的表頭 。 按給定的某個值 kx， 在查找表中查找關(guān)鍵碼為給定值 kx的數(shù)據(jù)元素 （ 記錄 ） 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 6 （ 記錄 ） 數(shù)據(jù)元素是由若干項(xiàng) 、 組合項(xiàng)構(gòu)成的數(shù)據(jù)單位 ， 是在某一問題中作為整體進(jìn)行考慮和處理的基本單位 。因而，一個好的查找方法可以大大提高運(yùn)行速度。2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 1 第九章 查找 ⒈ 教學(xué)內(nèi)容： 基本概念與術(shù)語 靜態(tài)查找表 動態(tài)查找表 哈希表查找 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 2 在英漢字典中查找某個英文單詞的中文解釋；在新華字典中查找某個漢字的讀音、含義；在對數(shù)表、平方根表中查找某個數(shù)的對數(shù)、平方根；郵遞員送信件要按收件人的地址確定位置等等。另外，由于計算機(jī)的特性，象對數(shù)、平方根等是通過函數(shù)求解，無需存儲相應(yīng)的信息表。 數(shù)據(jù)元素有型和值之分 ， 表中項(xiàng)名的集合 ， 也即表頭部分就是數(shù)據(jù)元素的類型；而一個學(xué)生對應(yīng)的一行數(shù)據(jù)就是一個數(shù)據(jù)元素的值 ，表中全體學(xué)生即為數(shù)據(jù)元素的集合 。 關(guān)鍵碼是主關(guān)鍵碼時：由于主關(guān)鍵碼唯一 ， 所以查找結(jié)果也是唯一的 ， 一旦找到 ， 查找成功 ， 結(jié)束查找過程 ， 并給出找到的數(shù)據(jù)元素 （ 記錄 ） 的信息 ， 或指示該數(shù)據(jù)元素 （ 記錄 ） 的位置 。要存儲學(xué)生的信息 ， 還需要分配一定的存儲單元 ， 即給出表長度 。i)； /* 從標(biāo)尾端向前找 */ return i； } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 16 【 性能分析 】 分析查找算法的效率 ， 通常用平均查找長度 ASL來衡量 。 則查找成功時 ， 順序查找的平均查找長度為 : 設(shè)每個數(shù)據(jù)元素的查找概率相等 ， 則等概率情況下有 查找不成功時 ， 關(guān)鍵碼的比較次數(shù)總是 n+1 次 。 折半查找的思想為：在有序表中 ， 取中間元素作為比較對象 ， 若給定值與中間元素的關(guān)鍵碼相等 ， 則查找成功；若給定值小于中間元素的關(guān)鍵碼 ， 則在中間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵碼 ，則在中間元素的右半?yún)^(qū)繼續(xù)查找 。 對于 n個結(jié)點(diǎn)的判定樹 ，樹高為 k， 則有 2k11n≤2k1， 即 k1log2(n+1)≤k， 所以k= 。 二叉排序樹 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 33 由圖 中 可以看出 ， 對二叉排序樹進(jìn)行中序遍歷 ， 便可得到一個按關(guān)鍵碼有序的序列 ， 因此 ，一個無序序列 ， 可通過構(gòu)一棵二叉排序樹而成為有序序列 。 while(*q) /*從根結(jié)點(diǎn)開始查找 */ if(kx(*q)) /*kx大于當(dāng)前結(jié)點(diǎn) *q的元素關(guān)鍵碼 */ { *p=*q。 因此 ， 新插入結(jié)點(diǎn)一定是作為葉子結(jié)點(diǎn)添加上去的 。 /*申請結(jié)點(diǎn) ， 并賦值 */ s=kx。 } 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)系 ， 因此 ， 查找時 ，需要進(jìn)行一系列對關(guān)鍵碼的查找比較 ， 即 “ 查找算法 ” 是建立在比較的基礎(chǔ)上的 ， 查找效率由比較一次縮小的查找范圍決定 。 可以說 ， 沖突不可能避免 ， 只能盡可能減少 。 p一般選取質(zhì)數(shù) ， 也可以是不包含小于 20質(zhì)因子的合數(shù) 。 所選的位應(yīng)是各種符號在該位上出現(xiàn)的頻率大致相同 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 49 【 例 】 關(guān)鍵碼為 key=05326248725， 設(shè)哈希表長為三位數(shù) ， 則可對關(guān)鍵碼每三位一部分來分割 。 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 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 2022年 10月 2