數(shù)據(jù)結(jié)構(gòu)課件第九章(編輯修改稿)
2025-06-19 21:41 本頁面
【文章內(nèi)容簡介】 規(guī)則 : 右旋 ，以失去平衡的結(jié)點的兒子結(jié)點為基準，整棵子樹向右下方旋轉(zhuǎn)。 A B BL BR AR B A BR AR BL 0 0 RL型 : 新結(jié)點加入到右子樹的左子樹中。 1 調(diào)整規(guī)則 : A B BR AL C CL CR 1 0 0 211先右旋 ，以失去平衡的結(jié)點的兒子結(jié)點為基準，構(gòu)造成 RR型 。 后左旋 。 A C CL AL B CR BR 2 1 1 C BCL AL A CR BR 0 1 0 LR型 : 新結(jié)點加入到左子樹的右子樹中。 1 調(diào)整規(guī)則 : A B BL AR C CL CR 先左旋 ，以失去平衡的結(jié)點的兒子結(jié)點為基準，構(gòu)造成 LL型 。 后右旋 。 1 0 0 21 1 哈希表 前面介紹的內(nèi)容中，記錄在文件中的存儲地址是 隨機 的。 202102 202105 202101 張三 李四 王五 19 21 20 202105202101202102李四王五張三212019查找某一條記錄需要進行一系列的“ 比較 ”。 查找的效率依賴于比較的次數(shù)。 能否在記錄的 關(guān)鍵字 和 存儲地址 之間構(gòu)造這樣一種關(guān)系 f ，使得關(guān)鍵字和存儲地址一一對應(yīng) ？ 此對應(yīng)關(guān)系 f 稱為 哈希函數(shù) 。 學(xué)號 姓名 年齡 01 02 03 例，設(shè)關(guān)鍵字為年齡字段， H(key) = key 年齡 學(xué)號 姓名 01 02 03 56 100 . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 56 100 19 20 21 19 20 21 . . . . . . 張三 王五 李四 202102 202101 202105 1. 哈希函數(shù)的構(gòu)造方法 (1) 直接定址法 取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。 H(key) = key (i) 或 H ( key) = a key + b . (ii) (i) 例，以 年齡 作為關(guān)鍵字 (ii) 例，統(tǒng)計解放后出生人口，以 出生年份 作為關(guān)鍵字 地址 出生年份 01 1949 02 1950 23 1971 48 1996 . . . . . . . . . . . . . . . . . . H(key) = key – 1949 + 1 (2) 數(shù)字分析法 對關(guān)鍵字進行按 “位” 分析，取重復(fù)度小的若干位組合成哈希地址。 例，多條記錄，關(guān)鍵字為 8 位十進制數(shù)，要求取兩位作為哈希地址。 8 1 3 4 6 5 3 7 7 1 3 7 2 2 4 7 8 1
公司管理相關(guān)推薦
鄂ICP備17016276號-1