61線(xiàn)性查找62折半查找63分快查找64二元查找樹(shù)65散列(編輯修改稿)
2025-11-05 09:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 delete( k, frchild )。 else if ( Frchild == NULL ) F = Flchild 。 else if( Flchild == NULL ) F = Frchild 。 else Fdata =deletemin(Frchild) } 在二元查找樹(shù)中刪除結(jié)點(diǎn) Records deletemin( F ) { records tmp 。 BST p 。 if ( Flchild == NULL ) { p = F 。 tmp = Fdata 。 F = Frchild 。 delete p 。 return tmp 。 } else return ( deletemin( Flchild ) 。 } 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 14 例：二元樹(shù)用二元鏈表表示，且每個(gè)結(jié)點(diǎn)的鍵值互不相同， 編寫(xiě)算法判別該二元樹(shù)是否為二元排序樹(shù)。 int judge(BTree *bt) { BTree *s[100],*p=bt。 int top=0,preval=min。 do{ while(p){ s[top++]=p。 p=plchild。 } if(top0){ p=s[top]。 if(pdatapreval) return 0。 //不是二元排序樹(shù) preval=pdata。 p=prchild。 } }while (p||top0)。 return(1) ； //是二元排序樹(shù) } 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 15 散列法 —— 哈希（ Hash）查找 散列法 —— 地址散列法 被查找元素的存儲(chǔ) 地址 = Hash ( Key ) Key BEIJING （北京 ) TIANJIN (天津 ) HEBEI (河北 ) SHANXI (山西 ) SHANGHAI (上海 ) SHANGDONG (山東 ) HENAN (河南 ) SICHUAN (四川 ) f1(key) 02 20 08 19 19 19 08 19 f2(key) 09 04 17 28 28 26 22 03 f3(key) 04 26 02 13 23 17 16 16 例：全國(guó) 30個(gè)地區(qū)的人口統(tǒng)計(jì)，每個(gè)地區(qū)為一個(gè)記錄，內(nèi)容如下： 編號(hào) 地區(qū)名 總?cè)丝? 漢族 回族 … f1(key): 取關(guān)鍵字第一個(gè)字母在字母表中的序號(hào) f2(key): 求第一和最后字母在字母表中序號(hào)之和，然后取 30的余數(shù) f3(key): 將第一個(gè)字母的八進(jìn)制看成十進(jìn)制，再取 30的余數(shù) 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 16 Hash查找的關(guān)鍵問(wèn)題 ① 構(gòu)造 Hash函數(shù) ②制訂解決沖突的方法 散列（ Hash）函數(shù)（表）分類(lèi) 內(nèi)散列表（數(shù)組） 外散列表（鏈表） 構(gòu)造散列函數(shù)（ Hash）的幾種方法 ： ? 直接定址法： Hash( key ) = key 。 或 Hash( key ) = akey+b 。 ? 質(zhì)數(shù)除余法 ? 平方取中法 ? 折疊法 ? 數(shù)字分析法 ? 隨機(jī)數(shù)法 解決沖突的方法 ： ?開(kāi)放定址法 ?再散列法 ?鏈地址法 ?建立一個(gè)公共溢出區(qū) 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 6 17 地址 01 02 03 04 05 … 25 26 27 … 100 年齡 1 2 3 4 5 … 25 26 27 … 100 人數(shù) 3000 2020 5000 … 6000 … … ： 地址 01 02 03 04 05 … 25 26 27 … 100 年份 1949 1950 1951 … 1973 … 人數(shù) 3000 2020 5000 … 6000 … … ： ?直接定址法： Hash( key ) = key 。 或 Hash( key ) = akey+b 。 例一： Hash( key ) = key 例二： Hash( key ) = key + （ 1949） + 1 數(shù)據(jù)結(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1