數(shù)據(jù)結(jié)構(gòu)-查找ds_chap(參考版)
2025-05-22 21:08本頁(yè)面
【正文】 ?要求 ?用除留余數(shù)法構(gòu)造哈希函數(shù)，用二次探測(cè)再散列解決沖突。程序加上適當(dāng)?shù)淖⑨尅? ? 查找時(shí)，對(duì)給定值 kx通過(guò)哈希函數(shù)計(jì)算出哈希地址 i， 先與基本表的 base_tbl[i]單元比較，若相等，查找成功；否則，再到溢出表中進(jìn)行查找。 ? 經(jīng)典的構(gòu)造函數(shù)都是 對(duì)數(shù)字型關(guān)鍵字而言 的，對(duì)非數(shù)字的關(guān)鍵字要先將其轉(zhuǎn)化為數(shù)字型關(guān)鍵字 ? 常見(jiàn)的哈希構(gòu)造函數(shù)有直接定址法、數(shù)字分析法、平方取中法、折疊法等，每種方法均有其適用條件 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表的構(gòu)造 ? 直接定址法 H(key)=key 或 H(key)=a*key +b ? 僅限于地址集合的大小等于關(guān)鍵字集合的大小 ,如前例中學(xué)生學(xué)號(hào)和學(xué)生信息位置的映射 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表的構(gòu)造 ? 數(shù)字分析法 ? 關(guān)鍵字由多位數(shù)字構(gòu)成，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址 ? 例：南航學(xué)生的學(xué)號(hào)構(gòu)成如下 年份 +專(zhuān)業(yè)號(hào) +班號(hào) +流水號(hào) ? 限制條件：能夠預(yù)估全體關(guān)鍵字每一位上各數(shù)字出現(xiàn)的頻度 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表的構(gòu)造 ? 平方取中法 ? 關(guān)鍵字中每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象，則先求關(guān)鍵字的平方，通過(guò) “ 平方 ” 擴(kuò)大差別，同時(shí)平方值中的中間幾位受到整個(gè)關(guān)鍵字各位的影響 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表的構(gòu)造 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表的構(gòu)造 ? 折疊法 ? 關(guān)鍵字位數(shù)特別多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻，可將其分割為幾個(gè)部分，取其疊和為哈希地址，有 “ 移伴疊加 ” 和 “ 間界疊加 ” ，如 ISBN號(hào) 0442205864 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表的構(gòu)造 ? 除留余數(shù)法（取模法） H(key)=key mod p。 f稱(chēng)為 哈希函數(shù) ，按這個(gè)思想建立的表稱(chēng)為 哈希表 。 }//Delete 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 哈希表 ? 什么是哈希表 ? 哈希表的構(gòu)造方法 ? 哈希表的沖突處理方法 ? 哈希表的查找 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 什么是哈希表 ? 例 1:招 1000個(gè)新生 ,將其學(xué)號(hào)從 000編到 999，則可以用一個(gè)順序表來(lái)存放學(xué)生的住處，每個(gè)學(xué)生的學(xué)號(hào)正好是他的信息在順序表的序號(hào) ? 學(xué) 號(hào) ?哈希函數(shù) ?學(xué)生信息在表中的序號(hào) （關(guān)鍵字） （位置） 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 什么是哈希（ hash）表 ? 靜態(tài)查找表和動(dòng)態(tài)查找表元素的位置和它的關(guān)鍵字之間不存在一個(gè) 確定關(guān)系 ,查找只能通過(guò)關(guān)鍵字的比較操作 ,查找效率只能取決于和給定值比較的關(guān)鍵字個(gè)數(shù)。 delete s。 if (q!=p) qrchild=slchild。 s=srchild。 s=plchild。 free(q)。 } else { if (!plchild){ q=p。 p=plchild。 } }//DeleteBST 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的刪除算法 ? Status Delete(BiTree amp。 } else if (LT(key,T)) return DeleteBST(Tlchild,key)。p, KeyType key){ if (!T) return FALSE。 53 78 88 17 94 09 23 刪除 78 缺左子樹(shù) , 用右子女頂替 53 94 88 17 09 23 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的刪除 ?被刪結(jié)點(diǎn)左、右子樹(shù)都存在，可以在它的右子樹(shù)中尋找中序下的第一個(gè)結(jié)點(diǎn) (關(guān)鍵碼最小 ),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來(lái)處理這個(gè)結(jié)點(diǎn)的刪除問(wèn)題。 53 78 65 17 87 09 23 45 刪除 65 雙親結(jié)點(diǎn)指針清零 53 78 17 87 09 23 45 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的刪除 ?被刪結(jié)點(diǎn)缺右子樹(shù)，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。 ?為保證在刪除后樹(shù)的搜索性能不至于降低，還需要防止重新鏈接后樹(shù)的高度增加。key)。 while (key!=ENDKEY) /*ENDKEY為自定義常數(shù) */ { InsertBST(bst, key)。 scanf(%d, amp。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的建立算法 ?void CreateBST(BSTree bst) /*從鍵盤(pán)輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹(shù) */ { KeyType key。T， ElemType e)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1