版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
第九章查找重點:掌握順序查找、折半查找、二叉排序樹上查找以及散列表上查找的基本思想和算法實現(xiàn)。難點:二叉排序樹的刪除算法及B-樹上的插入和刪除算法。相關(guān)定義----查找表查找表(SearchTable)定義:由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。
“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)操作查詢某個“特定的”數(shù)據(jù)元素是否在查找表中;檢索某個“特定的”數(shù)據(jù)元素的各種屬性;相關(guān)定義----查找表及其分類操作在查找表中插入一個數(shù)據(jù)元素;從查找表中刪去某個數(shù)據(jù)元素。查找表的分類靜態(tài)查找表:僅作查詢和檢索操作的查找表。動態(tài)查找表:在查詢過程中同時插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個數(shù)據(jù)元素。相關(guān)定義----關(guān)鍵字關(guān)鍵字定義:是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值,用以標識(識別)一個數(shù)據(jù)元素(或記錄)。若此關(guān)鍵字可以唯一地標識一個記錄,則稱之為主關(guān)鍵字;若此關(guān)鍵字能識別若干記錄,則稱之為次關(guān)鍵字。相關(guān)定義----查找查找定義:根據(jù)給定的某個值,在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。
若查找表中存在這樣一個記錄,則稱查找是成功的,此時查找結(jié)果為給出整個記錄的信息,或指示該記錄在查找表中的位置;
否則稱查找不成功,此時查找結(jié)果可給出一個空記錄或空指針。相關(guān)定義----類型定義typedefstruct{KeyTypekey; //關(guān)鍵字域
…… //其它域}ElemType;根據(jù)具體的關(guān)鍵字類型,定義用于比較的、帶參的宏#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)原型:externintstrcmp(constchar*s1,constchar*s2);
用法:#include<string.h>功能:比較字符串s1和s2。
說明:當s1<s2時,返回值<0當s1=s2時,返回值=0當s1>s2時,返回值>09.1.1順序查找查找表結(jié)構(gòu):以順序表或線性鏈表表示基本思想:從一端開始向另一端,逐個進行記錄的關(guān)鍵字和給定值的比較,若某個記錄的關(guān)鍵字和給定值比較相等,則查找成功;反之,若直至另一端,其關(guān)鍵字和給定值比較都不等,則表明表中沒有所查記錄,查找不成功。
查找成功示例:
(34,44,43,12,53,55,73,64,77),key=64
查找不成功示例:
(34,44,43,12,53,55,73,64,77),key=889.1.1順序查找對順序表的順序查找typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲空間基址
intlength; //表長度}SSTable;i01234567891011
513192137566475808892找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù):查找第n個元素:1查找第n-1個元素:2……….查找第1個元素:n查找第i個元素:n+1-i查找失敗:n+1查找過程:從表的一端開始逐個進行記錄的關(guān)鍵字和給定值的比較。例如:9.1.1順序查找9.1.1順序查找對順序表的順序查找
intSearch_Seq(SSTableST,KeyTypekey)
{
//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。
//若找到,則函數(shù)值為該元素在表中的位置,否則為0。
ST.elem[0].key
=key;
//“哨兵”
//從后往前找
for(i=ST.length;ST.elem[i].key!=key;--i);
returni;
//找不到時,i為0
}//Search_Seq
哨兵的作用:免去查找過程中每一步都要檢測整個表是否查找完畢。
上述順序查找表的查找算法簡單,但平均查找長度較大,特別不適用于表長較大的查找表。若以有序表表示靜態(tài)查找表,則查找過程可以基于“折半”進行。9.1.2有序表的查找----折半查找1.設表長為n,low、high和mid分別指向待查元素所在區(qū)間的下界上界和中點,key為給定值。
2.初始時,令
low=1,high=n,mid=(low+high)/2
讓key與mid指向的記錄比較
若key==ST[mid].key,查找成功
若key<ST[mid].key,則high=mid-1
若key>ST[mid].key,則low=mid+1
3.重復上述操作,直至low>high時,查找失敗。9.1.2有序表的查找-折半查找折半查找(二分查找)查找表結(jié)構(gòu):有序表基本思想:查找區(qū)間逐步縮小(折半)
查找成功示例:
123456789
(12,33,40,45,53,55,64,66,77),key=64
low指示查找區(qū)間的下界;
high指示查找區(qū)間的上界;
mid=(low+high)/2
。9.1.2有序表的查找-折半查找lowhighmidlowlowmidmid9.1.2有序表的查找-折半查找基本思想:查找區(qū)間逐步縮小(折半)
查找不成功示例:
123456789
(12,33,40,45,53,55,64,66,77),key=68lowhighmidlowlowmidmidlowlowmidmidlowlowmidmidhighhigh9.1.2有序表的查找-折半查找intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;
//置區(qū)間初值
while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;
//找到待查元素
elseif(LT(key,ST.elem[mid].key))high=mid-1;
//繼續(xù)在前半?yún)^(qū)間進行查找
elselow=mid+1;
//繼續(xù)在后半?yún)^(qū)間進行查找
}return0;
//順序表中不存在待查元素}//Search_Bin9.1.2有序表的查找-折半查找性能分析判定樹:折半查找的查找過程可以用二叉樹描述。n=ST.length=10時,判定樹的形態(tài)為:
52816397410查找成功時的ASL=該結(jié)點在判定樹中的層次判定樹的形態(tài)與n直接相關(guān),與關(guān)鍵字的取值無關(guān)查找不成功時練習:畫出對長度為12的有序表進行折半查找的判定樹9.1.2有序表的查找-折半查找第九章查找9.1順序查找9.2動態(tài)查找表9.3哈希表9.2.1二叉排序樹----定義二叉排序樹(二叉查找樹)
BinarySort/SearchTree定義(遞歸):或者是一棵空樹,或者是具有如下特性的二叉樹:若它的左子樹不空,則左子樹上所有結(jié)點的值均小于根結(jié)點的值;若它的右子樹不空,則右子樹上所有結(jié)點的值均大于根結(jié)點的值;它的左、右子樹也分別是二叉排序樹。503080209010854035252388例如:是二叉排序樹。66不9.2.1二叉排序樹----定義通常,取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)。typedefstruct
BiTNode
{//結(jié)點結(jié)構(gòu)
TElemTypedata;structBiTNode*lchild,*rchild;
//左右孩子指針}BiTNode,*BiTree;9.2.1二叉排序樹----定義1)若給定值等于根結(jié)點的關(guān)鍵字,則查找成功;2)若給定值小于根結(jié)點的關(guān)鍵字,則繼續(xù)在左子樹上進行查找;3)若給定值大于根結(jié)點的關(guān)鍵字,則繼續(xù)在右子樹上進行查找。否則若二叉排序樹為空,則查找不成功;9.2.1-二叉排序樹:查找算法50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095,9.2.1-二叉排序樹:查找算法從上述查找過程可見,在查找過程中,生成了一條查找路徑:
從根結(jié)點出發(fā),沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者
從根結(jié)點出發(fā),沿著左分支或右分支逐層向下直至指針指向空樹為止。
——查找成功——查找不成功9.2.1-二叉排序樹:查找算法9.2.1二叉排序樹----插入二叉排序樹的插入新插入的結(jié)點一定是一個新添加的葉子結(jié)點,并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。示例:從空樹出發(fā),待插的關(guān)鍵字序列為33,44,23,46,12,37334423461237中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列。該例中,中序遍歷結(jié)果為:12,23,33,37,44,46
若從一棵空樹出發(fā),經(jīng)過一系列的查找插入操作之后,可生成一棵二叉樹。且對其進行中序遍歷可得到一個關(guān)鍵字的有序序列。這說明一個無序序列可通過構(gòu)造一棵二叉排序樹而變成一棵有序序列。
9.2.1-二叉排序樹:改進的查找算法503080209010854035252388中序序列為:1020232530354050808588909.2.1-二叉排序樹:改進的查找算法9.2.1二叉排序樹----刪除二叉排序樹的刪除假設被刪結(jié)點為*p,其雙親結(jié)點為*f,*p為葉子結(jié)點:刪去*p,并修改*f的孩子域。*p只有左子樹PL或只有右子樹PR:令PL或PR直接成為*f的子樹334423461237464633442346124544464546459.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空33442346123744405048353846504833231237403538方法1:PL
接替*p成為*f的子樹,PR成為PL最右下結(jié)點(中序遍歷PL所得序列的最后一個結(jié)點)的右子樹。40這種方法可能會導致二叉排序樹高度的增長!本例中高度:564846509.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空334423461237444050483538332312方法2:與方法1對稱,PR接替*p成為*f的子樹,PL成為PR最左下結(jié)點(中序遍歷PR所得序列的最前一個結(jié)點)的左子樹。46374035389.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空方法3、令*p的中序遍歷的直接前驅(qū)替代*p,再從二叉排序樹中刪去它的直接前驅(qū)。這種方法不會導致二叉排序樹高度的增長!本例中高度:55刪除時,如何不增長樹的高度?334423461237444050483538404038383344234612374440504835389.2.1二叉排序樹----刪除二叉排序樹的刪除*p的左子樹PL和右子樹PR均不為空方法4:與方法3對稱,令*p的中序遍歷的直接后繼替代*p,再從二叉排序樹中刪去它的直接后繼。334423461244504837403538464648504850334423461237444050483538334423461237444050483538334423461237444050483538404038389.2.1二叉排序樹----刪除算法9.2.1二叉排序樹----性能分析二叉排序樹的查找分析與給定值比較的關(guān)鍵字個數(shù)不超過二叉排序樹的深度示例:從空樹出發(fā),待插的關(guān)鍵字序列為33,44,23,46,12,37334423461237二叉排序樹的形態(tài)與關(guān)鍵字的插入次序直接相關(guān)!如:將上例的關(guān)鍵字插入次序調(diào)整為:
12,23,33,44,37,46122333374446查找成功且各記錄的查找概率相等時
ASL(a)=(1+2*2+3*3)/6=14/6查找成功且各記錄的查找概率相等時ASL(b)=(1+2+3+4+5*2)/6=20/69.2.1二叉排序樹----性能分析9.2.1二叉排序樹----性能分析對給定序列建立二叉排序樹,若左右子樹均勻分布,則其查找過程類似于有序表的折半查找。但若給定序列原本有序,則建立的二叉排序樹就蛻化為單鏈表,其查找效率和順序查找一樣。第九章查找9.1順序查找9.2動態(tài)查找表9.3哈希表9.3哈希表9.3.1什么是哈希表9.3.2哈希函數(shù)的構(gòu)造方法9.3.3處理沖突的方法9.3.4哈希表的查找及其分析9.3.1什么是哈希表9.1和9.2節(jié)討論的各查找方法記錄在查找表中的位置和它的關(guān)鍵字之間不存在確定的關(guān)系;查找是建立在比較的基礎上(給定值vs.表中的關(guān)鍵字)查找效率依賴于查找過程中所進行的比較次數(shù)如何一次存取便能得到所查記錄?記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應關(guān)系H,以H(key)作為關(guān)鍵字為key的記錄在表中的位置,稱這個對應關(guān)系H為哈希(Hash)函數(shù)。9.3.1什么是哈希表例:30個地區(qū)的各民族人口統(tǒng)計表編號地區(qū)名總?cè)丝跐h族回族…1北京2上海┆┆以編號作關(guān)鍵字,構(gòu)造哈希函數(shù):H(key)=keyH(1)=1H(2)=2以地區(qū)名作關(guān)鍵字,取地區(qū)名的第一個拼音字母的序號作哈希函數(shù):H(Beijing)=2H(Shanghai)=19H(Shenyang)=199.3.1什么是哈希表哈希函數(shù)是一個映象,哈希函數(shù)的設定很靈活,只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可;沖突:key1≠key2,但H(key1)=H(key2)的現(xiàn)象
具有相同哈希函數(shù)值的關(guān)鍵字稱做同義詞。根據(jù)設定的哈希函數(shù)
H(key)和所選中的處理沖突的方法,將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上,并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置,這種表便稱為哈希表,這一映象過程稱為哈希造表或散列,所得存儲位置稱哈希地址或散列地址。9.3.2哈希函數(shù)的構(gòu)造方法直接定址法哈希函數(shù)為關(guān)鍵字的線性函數(shù),即
H(key)=key或者H(key)=a·key+b此法僅適合于:地址集合的大小==關(guān)鍵字集合的大小,其中a和b為常數(shù);例:解放后出生的人口調(diào)查表H(key)=key-1948地址010203…22…年份194919501951…1970…人數(shù)…………15000…┆9.3.2哈希函數(shù)的構(gòu)造方法數(shù)字分析法關(guān)鍵字是以r為基的數(shù),且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的,則取關(guān)鍵字的若干數(shù)位組成哈希地址。例:有80個記錄,關(guān)鍵字為8位十進制數(shù),哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..分析:只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以:取任意兩位,或兩位與另兩位的疊加作哈希地址9.3.2哈希函數(shù)的構(gòu)造方法平方取中法取關(guān)鍵字平方后的中間幾位作為哈希地址求“關(guān)鍵字平方”的目的是“擴大差別”,同時平方值的中間幾位數(shù)和關(guān)鍵字的每一位都相關(guān)。9.3.2哈希函數(shù)的構(gòu)造方法(4)折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同),然后取它們的疊加和(舍去進位)為哈希地址。移位疊加:將分割后的幾部分低位對齊相加;間界疊加:從一端沿分割界來回折迭,然后對齊相加。例:關(guān)鍵字為0442205864,哈希地址分別為586442200410088H(key)=0088移位疊加5864022404
6092H(key)=6092間界疊加9.3.2哈希函數(shù)的構(gòu)造方法除留余數(shù)法H(key)=keyMODp,p≤mp為質(zhì)數(shù)或不包含小于20的質(zhì)因子的合數(shù)
為什么?例:給定一組關(guān)鍵字為:12,39,18,24,33,21,若取p=9,則它們對應的哈希函數(shù)值將為:
3,3,0,6,6,3
可見,若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上,從而增加了“沖突”的可能。
注意:p最好選取小于或等于表長m的最大素數(shù)。如表長為20,那么p選19,若表長為25,則p可選23,…。表長m與模p的關(guān)系可按下表對應:
m=8,16,32,64,128,256,512,1024,…
p=7,13,31,61,127,251,503,1019,…9.3.3處理沖突的方法“處理沖突”的實際含義是:
為產(chǎn)生沖突的地址尋找下一個哈希地址。處理沖突的方法
開放定址法、鏈地址法、再哈希法、建立公共溢出區(qū)開放定址法為產(chǎn)生沖突的地址H(key)求得一個地址序列:
H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm,其中:i=1,2,…,s H(key)為哈希函數(shù); m為哈希表長; di為增量序列;9.3.3處理沖突的方法開放定址法對增量di的三種取法:線性探測再散列
di=c×i,最簡單的情況c=1平方探測再散列
di=12,-12,22,-22,…,隨機探測再散列
di
是一偽隨機數(shù)序列二次聚集:在處理同義詞的沖突過程中又添加了非同義詞的沖突,這種現(xiàn)象稱作“二次聚集”。9.3.3處理沖突的方法開放定址法例:給定關(guān)鍵字集合構(gòu)造哈希表
{19,01,23,14,55,68,11,82,36}設定哈希函數(shù)H(key)=keyMOD11(表長=11)若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突012345678910191011232141551683116822365012345678910191011232141551684113821362二次探測會降低“二次聚集”發(fā)生的概率9.3.3處理沖突的方法鏈地址法將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中例:關(guān)鍵字
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 蘇教版八年級生物上冊第5單元生物的多樣性第三節(jié)生物進化的學說課件
- 2024-2025學年七年級第一學期語文期中摸底檢測卷含答案
- 陜西省2022年中考歷史真題A卷(含答案)
- 化 學元素 同步訓練-2024-2025學年九年級化學人教版上冊
- 南省郴州市重點名校2024屆中考數(shù)學五模試卷含解析
- 湘教版音樂一年級上冊全冊教案
- 金融科技創(chuàng)新應用聲明書:基于大模型技術(shù)的智能信貸管理服務
- 2024年二級建造師《建筑工程管理與實務》考前模擬卷二(貴州地區(qū))
- 中班找小貓課件
- 關(guān)于酒吧轉(zhuǎn)讓合同模板
- 廣告設計師培訓教程課件
- 部編版統(tǒng)編版小學五年級上冊語文學歷案教學設計
- 寧波軌道交通
- 2023年江蘇蘇州市相城區(qū)人民法院公益性崗位招聘10人筆試備考試題及答案解析
- 銳捷產(chǎn)品線拓撲圖標合集
- 四位數(shù)乘四位數(shù)乘法題500道
- 第五章 工程師的職業(yè)倫理
- 藥品采購供應及藥品儲備情況
- 鐵路工程施工單位各崗位職責
- 臍帶干細胞存儲項目合作協(xié)議書
- 德育工作基地方案總結(jié)
評論
0/150
提交評論