靜態(tài)搜索結(jié)構(gòu)動態(tài)搜索結(jié)構(gòu)散列可擴充散列-資料下載頁
2025-09-19 08:23本頁面
【導(dǎo)讀】構(gòu)成的數(shù)據(jù)集合。主關(guān)鍵字唯一地表示一個紀(jì)錄。順序表——線性表、數(shù)組、鏈表。字與中點關(guān)鍵字的大小，反復(fù)直到成功。先找比較第13個，如果小，再比較第8個，····如果大比較后幾個數(shù)的第5個······不等概率查找時折半查找不一定好，
【正文】 35 1 18 2 43 60 1 39 1 47 F F F F 刪除一個關(guān)鍵字 53 1 78 99 F F 關(guān)鍵字 78繼續(xù)下移，與 60交換 F B+樹 ?B樹的變形 ?根結(jié)點 (非葉時 )至少有兩個結(jié)點 ?除根外，非葉結(jié)點至少有 [m/2]棵子樹 最多有 m棵子樹 ,非葉結(jié)點都是索引， 含有子樹中的最大或最少關(guān)鍵字 ?含有 n個關(guān)鍵字的非葉結(jié)點有 n棵子樹 ?所有的葉子結(jié)點都在同一個層次上，葉子結(jié)點中包含全部關(guān)鍵字，以及指向這些關(guān)鍵字的指針 59 97 15 44 59 72 97 10 15 21 37 44 51 59 85 91 97 63 72 B+樹 根 葉 兩種查找：從根開始，從葉起始 B+樹查找成功的時間復(fù)雜性 設(shè)第 i層最少結(jié)點數(shù) Ni N1=[m/2], N2=2[m/2], N3=2 [m/2]2 Nh= 2[m/2]h1 n≥Nh n ≥ 2[m/2]h1 h1=log[m/2](n/2) h=log[m/2](n/2)+1 h[m/2]=(log[m/2](n/2)+1)[m/2] O(log2n) B+樹的插入和刪除 與 B樹類似 鍵樹 __ 數(shù)字查找樹 Trie樹 (Digital Search Tree) 度 ≥2的樹， 每個結(jié)點只包含組成關(guān)鍵字的部分符號。 為查找方便，約定簡述為有序樹，同層兄弟有序排列。 鍵樹的例 16個關(guān)鍵字 CAI,CAO,LI,LAN,CHA,CHANG,WEN, CHAO,YUN,YANG,LONG,WANG,ZHAO, LIU,WU,CHEN 以首字符分組： {CAI,CAO, CHA,CHANG, CHAO,CHEN} {LI,LAN, LONG, LIU} {WEN,WANG,WU} {YANG,YUN} {ZHAO} 繼續(xù)以第二 ,第三 字符分組 直到每組一個關(guān)鍵字 {{{CAI},{CAO}}, {{CHA},{CHANG}, {CHAO}}, {CHEN}} {{LAN} , {LIU}, {LONG}} {{WANG}, {WEN},{WU}} {{YANG},{YUN}} 以集合 ,子集 ,元素的層次組成樹 C L W Y Z A H A I O A E U A U H $ $ $ A O $ I O A E N $ U N N N $ G $ $ N N A N O $ $ G $ G $ $ $ $ $ N 鍵樹的孩子兄弟表示 ———雙鏈樹 C L W Y Z A H A I O A E U A U H $ $ $ A O $ I O A E N $ U N N N $ G $ $ N N A N O $ $ G $ G $ $ $ $ $ N 鍵樹的查找成功時間復(fù)雜性 鍵樹的結(jié)點的 最大度 d由基決定 : 關(guān)鍵字是英文單詞： d=27 數(shù)字： d=11 查找每一位的平均長度 (1+d)/2 設(shè)鍵樹的 深度 為 h 假設(shè)關(guān)鍵字的位數(shù)都相等 則查找一個字的平均長度 h(1+d)/2 三、哈希表 Hashing table___散列 一種搜索結(jié)構(gòu) 不經(jīng)過任何比較，一次存取就能得到所查的紀(jì)錄： 每個記錄和存儲位置之間建立一個一一對應(yīng)關(guān)系 f , 對每個關(guān)鍵字 K, f(K)就是 K的存儲位置 稱 f為哈希函數(shù)。 哈希函數(shù)的例 int HF(int key)//直接定址法 a,b是選定的常數(shù) { return a*key+b。} 1993 1994 1996 1999 2020 1993 1994 1996 1999 2020 留余數(shù)法 int HF(int key)//模一個 素數(shù) 得到的余數(shù) { return key%11。 } 23 35 18 48 107 9 43 60 23 35 48 60 107 18 9 43 數(shù)字分析法 1939 1949 1969 1999 2020 以第三位定位 2020 1939 1949 1969 1999 int HF(char *key)//首末字母法，首末字母之和模 101 { int len=strlen(key), hashf=0。 if(len=1)hashf=key[0]。 else hashf=key[0]+key[len1]。 return hashf%101。 } Beijing Shanghai Tianjin Chongqing Beijing ChongQing Shanghai Tianjin int HF(char *key)//全字母法，所有字母的和模 101 { int hashf=0。 while(*key)hashf+=*key++。 return hashf%101。 } int HF(int key)//平方取中法 { key*=key。 //key平方 key=11。 //右移 11位，去掉末尾 11位 return key%1024。//去掉前面 11位 } 處理沖突的方法 沖突 collision: 不同的關(guān)鍵字得到同一個地址 ——線性探查法 23 35 48 17 60 29 38 40 23 35 48 60 17 29 38 40 開放定址法 查找成功平均查找次數(shù) (1+1+1+1+1+4+3)/8=12/8=3/2 23 35 48 60 17 29 38 40 哈希表的裝填因子 α 表中填入的紀(jì)錄數(shù) α=———————— 哈希表的長度 開放定址法 的查找成功的平均查找次數(shù) (1+1/(1α))/2 查找不成功的平均查找次數(shù) (1+1/(1α)2)/2 開放定址法的缺點 容易引起 “二次聚集” 發(fā)生沖突的點引起再一次沖突的可能性增加 使沖突點聚集 可以用 再哈希法 改進 即定義一個哈希函數(shù)序列 發(fā)生沖突的關(guān)鍵字用下一個哈希函數(shù)確定位置 避免聚集 鏈地址法 19 14 23 01 68 20 84 27 55 11 10 79 0 1 2 3 4 5 6 7 8 9 10 11 12 ∧ ∧ ∧ ∧ ∧ ∧ ∧ 01 14 27 79 ∧ 55 68 ∧ 19 84 ∧ 20 ∧ 10 23 ∧ 11 ∧ 查找成功的平均查找次數(shù) （ 1+2+3+4+1+2+1+2+1+1+2+1） /12 =21/12 α=12/12=1 1+1/2= 鏈地址法 查找成功的平均查找次數(shù) 1+α/2 查找不成功的平均查找次數(shù) α+eα
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1