




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
\第8章查找.
ISJI^H
f’數(shù)據(jù)結(jié)構(gòu)(C++描述)
目錄
8.1查找的基本概念
8.1杳找的基本概念
查找,也稱(chēng)為檢索。在我們?nèi)粘I钪?,隨處可見(jiàn)查找
的實(shí)例。如查找某人的地址、電話號(hào)碼;查某單位45歲
以上職工等,都屬于查找范疇。本書(shū)中,我們規(guī)定查找
是按關(guān)鍵字進(jìn)行的,所謂關(guān)鍵字(key)是數(shù)據(jù)元素(或記
錄)中某個(gè)數(shù)據(jù)項(xiàng)的值,用它可以標(biāo)識(shí)(或識(shí)別)一個(gè)數(shù)據(jù)
元素。例如,描述一個(gè)考生的信息,可以包含:考號(hào)、
姓名、性別、年齡、家庭住址、電話號(hào)碼、成績(jī)等關(guān)鍵
字。但有些關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素,而有的
關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。如剛才的考生信息
中,姓名不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(因有同名同姓的
人),而考號(hào)可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(每個(gè)考生考號(hào)
是唯一的,不能相同)。我們將能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素
的關(guān)鍵字稱(chēng)為主關(guān)鍵字,而其它關(guān)鍵字稱(chēng)為輔助關(guān)鍵字
或從關(guān)鍵字。
用了主關(guān)鍵字及關(guān)鍵字后,我們可以給查找下一個(gè)完整
的定義。所謂查找,就是根據(jù)給定的值,在一個(gè)表中查
找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素,若表中有這樣的
元素,則稱(chēng)查找是成功的,此時(shí)查找的信息為給定整個(gè)
數(shù)據(jù)元素的輸出或指出該元素在表中的位置;若表中不
存在這樣的記錄,則稱(chēng)查找是不成功的,或稱(chēng)查找失敗,
并可給出相應(yīng)的提示。
因?yàn)椴檎沂菍?duì)已存入計(jì)算機(jī)中的數(shù)據(jù)所進(jìn)行的操作,所
以采用何種查找方法,首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)
表示“表”,即表中結(jié)點(diǎn)是按何種方式組織的。為了提
高查找速度,我們經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)組織
表。因此在研究各種查找算法時(shí),我們首先必須弄清這
些算法所要求的數(shù)據(jù)結(jié)構(gòu),特別是存儲(chǔ)結(jié)構(gòu)。
查找有內(nèi)查找和外查找之分。若整個(gè)查找過(guò)程全部在內(nèi)
存進(jìn)行,則稱(chēng)這樣的查找為內(nèi)查找;反之,若在查找過(guò)
程中還需要訪問(wèn)外存,則稱(chēng)之為外查找。我們僅介紹內(nèi)
查找。
要衡量一種查找算法的優(yōu)劣,主要是看要找的值與關(guān)鍵字
的比較次數(shù),但我們將找到給定值與關(guān)鍵字的比較次數(shù)的
平均值來(lái)作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn),對(duì)于一個(gè)含
有n個(gè)元素的表,查找成功時(shí)的平均查找長(zhǎng)度可表示為
ASL=E”,,其中Pi為查找第i個(gè)元素的概率,且Zp,=1
一般情形下我們認(rèn)為查找每個(gè)元素的概率相等,Ci為查找
第i個(gè)元素所用到的比較次數(shù)。
要衡量一種查找算法的優(yōu)劣,主要是看要找的值與關(guān)鍵字
的比較次數(shù),但我們將找到給定值與關(guān)鍵字的比較次數(shù)的
平均值來(lái)作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn),對(duì)于一個(gè)含
有n個(gè)元素的表,查找成功時(shí)的平均查找長(zhǎng)度可表示為
ASL=,其中Pi為查找第i個(gè)元素的概率,且=1。一般情
形下我們認(rèn)為查找每個(gè)元素的概率相等,Ci為查找第i個(gè)
元素所用到的比較次數(shù)。
8.2線性表的查找
8.2.1順序查找
L順序查找的基本思想
順序查找是一種最簡(jiǎn)單的查找方法,它的基本思想是:
從表的一端開(kāi)始,順序掃描線性表,依次將掃描到的
結(jié)點(diǎn)關(guān)鍵字和待找的值K相比較,若相等,則查找成
功,若整個(gè)表掃描完畢,仍末找到關(guān)鍵字等于K的元
素,則查找失敗。
順序查找既適用于順序表,也適用于鏈表。若用順序
表,查找可從前往后掃描,也可從后往前掃描,但若
采用單鏈表,則只能從前往后掃描。另外,順序查找
的表中元素可以是無(wú)序的。
F面以順序表的形式來(lái)描述算法。
2.順序查找算法實(shí)現(xiàn)
constintn=maxn〃口為表的最大長(zhǎng)度
structnode
{...
elemtypekey;//key為關(guān)鍵字,類(lèi)型設(shè)定為elemtype
);
intseqsearch(nodeR[n+l]?elemtypek)〃在表R
中查找關(guān)鍵字值為K的元素
{R[0].key=k;inti=n;〃從表尾開(kāi)始向前掃描
while(R[i].key!=k)i—;
returni;}
在函數(shù)seqsearch中,若返回的值為0表示查找不成功,
否則查找成功。函數(shù)中查找的范圍從R[n]到R[l],
「注R[0]為監(jiān)視哨,起兩個(gè)作用,其一,是為了省去判
定while循環(huán)中下標(biāo)越界的條件以1,從而節(jié)省比較時(shí)
:1間,其二,保存要找值的副本,若查找時(shí),遇到它,
表示查找不成功。若算法中不設(shè)立監(jiān)視哨R[0],程序
A花費(fèi)的時(shí)間將會(huì)增加,這時(shí)的算法可寫(xiě)為下面形式。
intseqsearch(nodeR[n+1],elemtypek)
{inti=n;
while(R[i].key!=k)&&(i>=1)i—;
returni;
\}當(dāng)然上面算法也可以改成從表頭向后掃描,將監(jiān)視哨設(shè)在右
A邊,這種方法請(qǐng)讀者自己完成。
’3,順序查找性能分析
假設(shè)在每個(gè)位置查找的概率相等,即有p=l/n,由于查
找是從后往前掃描,則有每個(gè)位置的查找比較次數(shù)C『l,
Cn4=2,…,G=n,于是,查找成功的平均查找ASL=
口〃]"1>7-4-1、,
=Xpici=Z…+1)]=-,即它的時(shí)間復(fù)雜度為0(n)。
這就是說(shuō);查找成功的平均比較次數(shù)約為表長(zhǎng)的一半。
I若k值不在表中,則必須進(jìn)行n+1次比較之后才能確定查
\找失敗。另處,從ASL可知,當(dāng)n較大時(shí),ASL值較大,
Q查找的效率較低。
順序查找的優(yōu)點(diǎn)是算法簡(jiǎn)單,對(duì)表結(jié)構(gòu)無(wú)任何要求,無(wú)
論是用向量還是用鏈表來(lái)存放結(jié)點(diǎn),也無(wú)論結(jié)點(diǎn)之間是
否按關(guān)鍵字有序或無(wú)序,它都同樣適用。順序查找的缺
點(diǎn)是查找效率低,當(dāng)n較大時(shí),不宜采用順序查找,而
必須尋求更好的查找方法。
822二分查找
1.二分查找的基本思想
二分查找,也稱(chēng)折半查找,它是一種高效率的查找方法。
但二分查找有條件限制:要求表必須用向量作存貯結(jié)構(gòu),
且表中元素必須按關(guān)鍵字有序(升序或降序均可)。我們不
妨假設(shè)表中元素為升序排列。二分查找的基本思想是:
首先將待查值K與有序表R[l]到R[n]的中點(diǎn)mid上的關(guān)鍵
字R[mid].key進(jìn)行比較,若相等,則查找成功;否則,若
R[mid].key>k,則在R[l]到R[mid-1]中繼續(xù)查找,若有
R[mid].key<k,則在R[mid+1]到R[n]中繼續(xù)查找。每通
過(guò)一次關(guān)鍵字的比較,區(qū)間的長(zhǎng)度就縮小一半,區(qū)間的
個(gè)數(shù)就增加一倍,如此不斷進(jìn)行下去,直到找到關(guān)鍵字
為K的元素;若當(dāng)前的查找區(qū)間為空(表示查找失?。?/p>
從上述查找思想可知,每進(jìn)行一次關(guān)鍵字比較,區(qū)間數(shù)
目增加一倍,故稱(chēng)為二分(區(qū)間一分為二),而區(qū)間長(zhǎng)
度縮小一半,故也稱(chēng)為折半(查找的范圍縮小一半)。
2.二分查找算法實(shí)現(xiàn)
intbinsearch(nodeR[n+1],elemtypek)
vl
{intlow=1,high=n;
while(low<=high)
{intmid=(low+high)/2;〃取區(qū)間中點(diǎn)
if(R[mid].key==k)returnmid;〃查找成功
elseif(R[mid].key>k)
high=mid-1;〃在左子區(qū)間中查找
elselow=mid+l;}〃在右子區(qū)間中查找
return0;}〃查找失敗
例如,假設(shè)給定有序表中關(guān)鍵字為
8,17,25,44,68,77,98,100,115,125,將查找K=17和K=120
的情況描述為圖8-1及圖8-2形式。
[817254468779810115125]
loWhigh
(a)初始情形
684498100115125
lowhighmid
(b)經(jīng)過(guò)一次比較后的情形
]687798100115125
Iowmidhigh
(c)經(jīng)過(guò)二次比較后的情形(R[mid].key=17)
圖8-1查找K=17的示意圖(查找成功)
17254468779810011512.5]
A
lowhigh
(a)初始情形
81725446[7,7981001151
midlowhigh
(b)經(jīng)過(guò)一次比較后的情形
8172544687798100115125]
midlowhigh
(c)經(jīng)過(guò)二次比較后的情形
8172544687798100115125]
肯midIowhigh
(d)經(jīng)過(guò)三次比較后的情形
1725447798100115125
highlowmid
(e)經(jīng)過(guò)四次比較后的情形(highvlow)
圖8-2查找K=120的示意圖(查找不成功)
,3.二分查找的性能分析
為了分析二分查找的性能,可以用二叉樹(shù)來(lái)描述二分查找
f|過(guò)程。把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn),左子區(qū)間和右
I子區(qū)間分別作為根的左子樹(shù)和右子樹(shù),左子區(qū)間和右子區(qū)
V間再按類(lèi)似的方法,由此得到的二叉樹(shù)稱(chēng)為二分查找的判
/定樹(shù)。例如,圖8-1給定的關(guān)鍵字序列
U8,17,25,44,68,77,98,100,115,125,的判定樹(shù)見(jiàn)圖8-3。
圖8-3具有10個(gè)關(guān)鍵字序列的二分查找判定樹(shù)
'從圖8-3可知,查找根結(jié)點(diǎn)68,需一次查找,查找17和
100,各需二次查找,查找8、25、77、115各需三次查
窯找,查找44、98、125各需四次查找。于是,可以得到
n結(jié)論:二叉樹(shù)第K層結(jié)點(diǎn)的查找次數(shù)各為k次(根結(jié)點(diǎn)為
第1層),而第k層結(jié)點(diǎn)數(shù)最多為2-個(gè)。假設(shè)該二叉樹(shù)的
深度為h,則二分查找的成功的平均查找長(zhǎng)度為(假設(shè)
每個(gè)結(jié)點(diǎn)的查找概率相等):
n
2h1
ASL=ZP£=l/nyCi<l/n(l+2x2+3x2+...+hx2-)
i=1
因此,在最壞情形下,上面的不等號(hào)將會(huì)成立,并根據(jù)
二叉樹(shù)的性質(zhì),最大的結(jié)點(diǎn)數(shù)n=2M,h=log2(n+l),于是
可以得到平均查找長(zhǎng)度ASL=(n+l)/nlog2(n+l)-lo該公式
可以按如下方法推出:
:設(shè)5=Z“2=20+2,2i+3.22+...+(h-l).2h-2+h.2h-i
<k=\
貝U2s=242.22+…+(h?2).2h-2+h/).2h-i+h.2h
“s=2s-s
=h.2七(20+21+22+...+2>2+2>1)
■
=h.2h-(2h-l)
=log2(n+l).(n+l)-n
所以,ASL=s/n=(n+l)/nlog2(n+l)-lo
當(dāng)n很大時(shí),ASL^log2(n+l)-l可以作為二分查找成功
時(shí)的平均查找長(zhǎng)度,它的時(shí)間復(fù)雜度為0(1"2口)。
8.2.3索引查找
1.索引查找的思想
索引查找,又稱(chēng)分級(jí)查找,它既是一種查找方法,又是
一種存貯方法,稱(chēng)為索引存貯。它在我們的日常生活中
有著廣泛的應(yīng)用。例如,在漢語(yǔ)字典中查找某個(gè)漢字時(shí),
若知道某個(gè)漢字讀者,則可以先在音節(jié)表中查找到對(duì)應(yīng)
正文中的頁(yè)碼,然后再在正文中所對(duì)應(yīng)的頁(yè)中查出待查
的漢字;若知道該漢字的字形,但不知道讀者,則可以
先在部首表中根據(jù)字的部首查找到對(duì)應(yīng)檢字表中的頁(yè)碼,
再在檢字表中根據(jù)字的筆畫(huà)找到該漢字所在的頁(yè)碼。在
這里,整個(gè)字典就是索引查找的對(duì)象,字典的正文是字
典的主要部分,被稱(chēng)之為主表,而檢字表,部首表和音
節(jié)表都有是為了方便查找主表而建立的索引,所以被稱(chēng)
之為索引表。
.?腔二■在索引查找中,主表只有一個(gè),其中包含的是待查找的
內(nèi)容,而索引表可以有多個(gè),包含一級(jí)索引,二級(jí)索
引……,所需的級(jí)數(shù)可根據(jù)具體問(wèn)題而定。如剛才的利
用讀音查找漢字為一級(jí)索引,而利用字形查找漢字為二
n級(jí)索引(部首表一檢字表一漢字)。在此,我們僅討論
\:一級(jí)索引。
’索引查找是在線性表(主表)的索引存貯結(jié)構(gòu)上進(jìn)行的,
而索引存貯的基本思想是:首先將一個(gè)線性表(主表)按
照一定的規(guī)則分成若干個(gè)邏輯上的子表,并為每個(gè)子表分
別建立一個(gè)索引項(xiàng),由所有這些索引項(xiàng)得到主表的一個(gè)索
引表,然后,可采用順序或鏈接的方法來(lái)存儲(chǔ)索引表和各
個(gè)子表。索引表中的每個(gè)索引項(xiàng)通常包含三個(gè)域:一是索
引值域,用來(lái)存儲(chǔ)標(biāo)識(shí)對(duì)應(yīng)子表的索引值,它相當(dāng)于記錄
的關(guān)鍵字,在索引表中由此索引值來(lái)唯一標(biāo)識(shí)一個(gè)索引項(xiàng)
(子表);二是子表的開(kāi)始位置,用來(lái)存儲(chǔ)對(duì)應(yīng)子表的第
一個(gè)元素的存儲(chǔ)位置;三是子表的長(zhǎng)度,用來(lái)存儲(chǔ)對(duì)應(yīng)子
!表的元素個(gè)數(shù)。
例如,設(shè)有一個(gè)學(xué)校部分教師檔案表如表8-1所示,設(shè)
編號(hào)為主關(guān)鍵字,則該表可以用一個(gè)線性表L=_(金噢,
a3,a4,a59a6,a7?a89a95a10)來(lái)表示,其中正(iSign)表示第"立
教師的信息(包含有編號(hào),姓名,部門(mén),職稱(chēng)),而
它的索引表可以按部門(mén)進(jìn)行,也可以按職稱(chēng)進(jìn)行,按
部門(mén)的索引表中有4個(gè)子表,分別為:
計(jì)算機(jī)系J=(包/2閏3戶(hù)4)
電工系D=(a5,a65a7)
管理系6=但8擔(dān)9)
成教部C=(aio)
該4個(gè)子表示成一個(gè)索引表如表8-2所示。
表8-1教師檔案表表8-2按部門(mén)的索引表
編號(hào)姓名部門(mén)
職稱(chēng)indexstartlength
J001趙一計(jì)算機(jī)系教授
J04
J002錢(qián)二計(jì)算機(jī)系講師
D43
J003張三計(jì)算機(jī)系副教授
G72
J004李四計(jì)算機(jī)系助教
C91
D001王五電工系講師
D002孫六電工系助教
D003劉七電工系副教授
G001朱八管理系教授
G002楊九管理系講師
C001羅十成教部副教授
若按職稱(chēng)進(jìn)行索引,則得到的索引表中也有4個(gè)子表,
分別為:
Jiaosou=(a],a8)
FuJiaosou=(a3,a7,a10)
Jiangshi=(a2,a5,a9)
Zhiyiao=(a4,a6)
這時(shí)的主表用順序存貯不太方便,因相同職稱(chēng)的教師沒(méi)
有連在一起,故用鏈?zhǔn)酱鎯?chǔ)得到主表較方便。具體的存
貯如圖8-4所示。在圖8-4中,箭頭上面的數(shù)字表示該元
素在主表中的下標(biāo)位置(指針),每個(gè)子表中最后個(gè)元
素的指針為-1,表示為空指針。
07
教授a】a8.]
6
2a9
副教授3a7a?(),_1
講師
35
助教a4
圖8-4按職稱(chēng)的鏈?zhǔn)酱尜A結(jié)構(gòu)
于是,可以得到如表8-3所示的職稱(chēng)索引表。
表8-3按職稱(chēng)的索引表
indexstartlength
教授02
副教授23
講師13
助教32
、從剛才的兩種索引表中,可以給出索引查找的基本思
想如下:
弟一步,在索引表中按index域查找所給值K1,這時(shí)可
得到子表起始位置start和長(zhǎng)度length,若找不到K1,結(jié)
束查找,表示查找不成功。第二步,在主表的start位置
開(kāi)始,長(zhǎng)度為length的范圍內(nèi)查找所給值K2,若找到,
查找不成功,否則,查找不成功。
例如,對(duì)于按部門(mén)的索引查找,主表可以用順序存貯,假設(shè)
K1="D”,“D”代電工系,K2="孫六”,則先在表8-2的索引
表中找到的index域?yàn)?D”的項(xiàng),得到start=4,length=3,
然后從主表的第4個(gè)位置開(kāi)始(SPa5)找姓名為“孫六”的
人,則在主表的第5個(gè)位置可以找到,故查找成功。若假設(shè)
K1="D",K2=“楊九”,則索引表的查找與上面相同,然后
在主表的第4個(gè)位置開(kāi)始查找,沒(méi)找到,進(jìn)入第5個(gè)位置查找,
還沒(méi)找到進(jìn)入第6位置查找,仍然沒(méi)找到,但查找的length=3,
既只允許3次查找,故查找不成功。若假設(shè)K1="F",K2=”張
三”,則首先在索引表中就找不到“F”,故無(wú)需進(jìn)入主表進(jìn)
行查找,查找不成功。
J;:;’3.索引查找的性能分析
2"由于索引查找中涉及到兩方面查找,第一個(gè)是索引表的
r\查找,第二個(gè)是主表的查找,假設(shè)兩種查找都按順序查
\找方式進(jìn)行,則索引表的平均查找長(zhǎng)度為(m+l)/2,主表
7中的平均查找長(zhǎng)度為(s+1)/2,(m為索引表的長(zhǎng)度,S為
n主表中相應(yīng)子表的長(zhǎng)度),則索引查找的平均查找長(zhǎng)度為:
\ASL=(m+l)/2+(s+1)/2o若假定每個(gè)子表具有相同的長(zhǎng)
度,而主表的長(zhǎng)度為n,則有n=m.s,這時(shí)當(dāng)s1;時(shí),
U索引查找具有最小的平均查找長(zhǎng)度,即ASL=1亡o
A從該公式可以看出,索引查找的性能優(yōu)先順序*找,但
比二分查找要差,時(shí)間復(fù)雜度介于0(182口)?0(n)之間。
「824分塊查找
1.分塊查找的思想
分塊查找實(shí)際上就是一種索引查找,但查找的性能更優(yōu)
先于索引查找。原因是分塊查找的索引表是一個(gè)有序表,
故可以用二分查找來(lái)代替順序查找實(shí)現(xiàn)索引表的快速
查找。
具體實(shí)現(xiàn)如下:將一個(gè)含有n個(gè)元素的主表分成m個(gè)子表,
但要求子表之間元素是按關(guān)鍵字有序排列的,而子表中
元素可以無(wú)序的,然后建立索引表,索引表中索引域的
值用每個(gè)子表最大關(guān)鍵字代替,則可以按索引查找思想
找到表中元素。
例如,給定關(guān)鍵字序列如下:
"18,7,26,34,15,42,36,70,60,55,83,90,78,72,74,假設(shè)m=3,
2s=5,即將該序序分成3個(gè)子表,每個(gè)子表有5個(gè)元素,則
rI得到的主表和索引表如圖8-5所示。
01234567891011121314
18726341542367060558390787274
(a)15個(gè)關(guān)鍵字序列得到的主表
indexstartlength
3405
7055
90105
(b)按關(guān)鍵字序列遞增得到的索引表
圖8-5分塊查找的主表和索引表
廣二3.分塊杳找的性能分析
'分塊查找實(shí)際上就是索引查找,但分塊查找中索引的域
’的類(lèi)型與主表的關(guān)鍵字域的類(lèi)型相同,且索引表按索
了聲引域遞增(或遞減)有序,故它的平均查找長(zhǎng)度與索
I引查找接近,且優(yōu)于索引查找。
-8.3樹(shù)表查找
(8.3」二叉排序樹(shù)查找
號(hào)L什么是二叉排序樹(shù)
。二叉排序樹(shù)(BinarySortingTree),它或者是一棵空樹(shù),
A或者是一棵具有如下特征的非空二叉樹(shù):
\(1)若它的左子樹(shù)非空,則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均
\小于根結(jié)點(diǎn)的關(guān)鍵字;
J(2)若它的右子樹(shù)非空,則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均
V大于等于根結(jié)點(diǎn)的關(guān)鍵字;
<(3)左、右子樹(shù)本身又都是一棵二叉排序樹(shù)。
2.二叉排序樹(shù)的數(shù)據(jù)類(lèi)型描述
和第六章類(lèi)似,可以用一個(gè)二叉鏈表來(lái)描述一棵二叉
排序樹(shù),具體為:
structBtreenode
{elemtypedata;〃代表關(guān)鍵字
Btreenode*left/right;〃代表左、右孩子
};
3.二叉排序樹(shù)的基本運(yùn)算
(1)二叉排序樹(shù)的插入
若二叉排序樹(shù)為空,則作為根結(jié)點(diǎn)插入,否則,若待
插入的值小于根結(jié)點(diǎn)值,則作為左子樹(shù)插入,否則作為
右子樹(shù)插入,算法描述為:
voidInsert(Btreenode*BST,elemtypeX)
{if(BST==NULL)
{Btreenode*p=newBtreenode;
p->data=X;
p->left=p->right=NULL;
BST=p;}
elseif(BST->data>=X)
Insert(BST->left,X);〃在左子樹(shù)中桿
入
elseInsert(BST->right,X);}〃在右子樹(shù)中打入
(2)二叉排序樹(shù)的建立
只要反復(fù)調(diào)用二叉排序樹(shù)的托入算法即可,算法描述
為:
Btreenode*Creat(intn)〃建立含有n個(gè)結(jié)點(diǎn)的二叉
排序樹(shù)
{Btreenode*BST=NULL;
for(inti=l;i〈=n;i++)
{cin?x;〃輸入關(guān)鍵字序列
Insert(BST,x);
)
returnBST;}
例如,結(jié)定關(guān)鍵字序列79,62,68,90,88,89,17,
5,100,120,生成二叉排序樹(shù)過(guò)程如圖8-6所示。(注:
二叉排序樹(shù)與關(guān)鍵字排列順序有關(guān),排列順序不一樣,
得到的二叉排序樹(shù)也不一樣)
(a)(e)
⑴
圖8-6二叉排序樹(shù)的生成過(guò)程
4.二叉排序樹(shù)上的杳找
(1)二叉排序樹(shù)的查找思想
若二叉排樹(shù)為空,則查找失敗,否則,先拿根結(jié)點(diǎn)值與
待查值進(jìn)行比較,若相等,則查找成功,若根結(jié)點(diǎn)值大
于待查值,則進(jìn)入左子樹(shù)重復(fù)此步驟,否則,進(jìn)入右子
樹(shù)重復(fù)此步驟,若在查找過(guò)程中遇到二叉排序樹(shù)的葉子
結(jié)點(diǎn)時(shí),還沒(méi)有找到待找結(jié)點(diǎn),則查找不成功。
(2)二叉排序樹(shù)查找的算法實(shí)現(xiàn)
Btreenode*find(Btreenode*BST,elentypex)
〃在以BST為根指針的二叉排隊(duì)樹(shù)中查找值為x的結(jié)點(diǎn)
{if(BST==NULL)
returnNULL;〃查找失敗
else(
if(BST->data==x)〃查找成功
returnBST;
elseif(BST->data>x)〃進(jìn)入左子樹(shù)查找
returnfind(BST->left,x);
else〃進(jìn)入右子樹(shù)查找
returnfind(BST->right,x);}}
5.二叉排序樹(shù)杳找的性能分析
在二叉排序樹(shù)查找中,成功的查找次數(shù)不會(huì)超過(guò)二叉樹(shù)
的深度,而具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的深度,最好為
log2n,最壞為n。因此,二叉排序樹(shù)查找的最好時(shí)間復(fù)
雜度為O(log2n),最壞的時(shí)間復(fù)雜度為0(n),一般情形
下,其時(shí)間復(fù)雜度大致可看成O(log2n),比順序查找效
率要好,但比二分查找要差。
8.3.2平衡二叉樹(shù)查找
X.平衡二叉樹(shù)的概念
平衡二叉樹(shù)(balancedbinarytree)是由阿德?tīng)柹D維爾斯和
蘭迪斯(Adelson-VelskiiandLandis)于1962年首先提出的,
所以又稱(chēng)為AVL樹(shù)。
<'若一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)的深度之差的絕
對(duì)值不超過(guò)1,則稱(chēng)這樣的二叉樹(shù)為平衡二叉樹(shù)。將該
結(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)深度的值,稱(chēng)為該結(jié)點(diǎn)的
平衡因子(balancefactor)o也就是說(shuō),一棵二叉排序樹(shù)
中,所有結(jié)點(diǎn)的平衡因子只能為0、1、-1時(shí),則該二叉
排序樹(shù)就是一棵平衡二叉樹(shù),否則就不是一棵平衡二叉
樹(shù)。如圖8-8所示二叉排序樹(shù),是一棵平衡二叉樹(shù),而
如圖8-9所示二叉排序樹(shù),就不是一棵平衡二叉樹(shù)。
圖8-8一棵平衡二叉樹(shù)
圖8-9一棵非平衡二叉樹(shù)
二F一0共平衡一▽樹(shù)的平衡Xz卜壬甲
六二,若一棵二叉排序樹(shù)是平衡二叉樹(shù),托入某個(gè)結(jié)點(diǎn)后,
可能會(huì)變成非平衡二叉樹(shù),這時(shí),就可以對(duì)該二叉
樹(shù)進(jìn)行平衡處理,使其變成一棵平衡二叉樹(shù)。處理
的原則應(yīng)該是處理與托入點(diǎn)最近的、而平衡因子又
比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡
■處理
(1)(L型的處理(左左型)
如圖8-10所示,在C的左孩子B上打入一個(gè)左孩子結(jié)點(diǎn)A,
使C的平衡因子由1變成了2,成為不平衡的二叉樹(shù)序樹(shù)。
這時(shí)的平衡處理為:將C順時(shí)針旋轉(zhuǎn),成為B的右子樹(shù),
而原來(lái)B的右子樹(shù)則變成C的左子樹(shù),待托入結(jié)點(diǎn)A作為B
的左子樹(shù)。(注:圖中結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)的平衡
因子)
(_2)LR型的處理(左右型)
如圖8-H所示,在C的左孩子A上打入一個(gè)右孩子B,
使的C的平衡因子由1變成了2,成為不平衡的二叉
排序樹(shù)。這是的平衡處理為:將B變到A與C之間,
使之成為L(zhǎng)L型,然后按第(1)種情形LL型處理。
r(3)RR型的處理(右右型)
如圖8-12所示,在A的右孩子B上打入一個(gè)右孩子C,使
A的平衡因子由-1變成-2,成為不平衡的二叉排序樹(shù)。
這時(shí)的平衡處理為:將A逆時(shí)針旋轉(zhuǎn),成為B的左子樹(shù),
而原來(lái)B的左子樹(shù)則變成A的右子樹(shù),待托入結(jié)點(diǎn)C成為
B的右子樹(shù)。
-2
平衡處理
A
0
圖8-12RR型平衡處理
(4)RL型的處理(右左型)
如圖8-13所示,在A的右孩子C上打入一個(gè)左孩子B,
使A的平衡因子由-1變成-2,成為不平衡的二叉排序
樹(shù)。這時(shí)的平衡處理為:將B變到A與C之間,使之
成為RR型,然后按第(3)種情形RR型處理。
-2
平衡處理
圖8-13RL型平衡處理
例8-2,給定一個(gè)關(guān)鍵字序列4,5,7,2,1,3,6,試生成一棵
平衡二叉樹(shù)。
分析:平衡二叉樹(shù)實(shí)際上也是一棵二叉排序樹(shù),故可
以按建立二叉排序樹(shù)的思想建立,在建立的過(guò)程中,
若遇到不平衡,則進(jìn)行相應(yīng)平衡處理,最后就可以建
成一棵平衡二叉樹(shù)。具體生成過(guò)程見(jiàn)圖8-14。
(a)插入4(b)插入5(c)插入7
iQ2
入2
(e)插入1
型
圖8-14平衡二叉樹(shù)的生成過(guò)程
3.平衡二叉樹(shù)的查找及性能分析
平衡二叉樹(shù)本身就是一棵二叉排序樹(shù),故它的查找與二
叉排序樹(shù)完全相同。但它的查找性能優(yōu)于二叉排序樹(shù),
不像二叉排序樹(shù)一樣,會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度0(n),
它的時(shí)間復(fù)雜度與二叉排序樹(shù)的最好時(shí)間復(fù)雜相同,都
為(Xkgn)。
:’例8-3,對(duì)例8-2給定的關(guān)鍵字序列4,5,7,2,1,3,6,試用二
叉排序樹(shù)和平衡二叉樹(shù)兩種方法查找,給出查找6的次
數(shù)及成功的平均查找長(zhǎng)度。
分析:由于關(guān)鍵字序列的順序己經(jīng)確定,故得到的二叉
排序樹(shù)和平衡二叉樹(shù)都是唯一的。得到的平衡二叉樹(shù)見(jiàn)
圖8-14,得到區(qū)二叉排序樹(shù)見(jiàn)圖8-15。
圖8-15由關(guān)鍵字序列4,5,7,2,1,3,6生成的
二叉排序樹(shù)
從圖8-15的二叉排序樹(shù)可知,查找6需4次,平均查
找長(zhǎng)度ASL=(l+2+2+3+3+3+4)/7=18/7=2.57。
從圖8-14的平衡二叉樹(shù)可知,查找6需2次,平均查
找長(zhǎng)度
ASL=(l+2+2+3+3+3+3尸17/7=2.43。
從結(jié)果可知,平衡二叉樹(shù)的查找性能優(yōu)于二叉排
序樹(shù)。
8.4散列查找
立卡8.4.1基本概念
散列查找,也稱(chēng)為哈希查找。它既是一種查找方法,又
■是一種存貯方法,稱(chēng)為散列存貯。散列存貯的內(nèi)存存放
形式也稱(chēng)為散列表。
散列查找,與前面介紹的查找方法完全不同,前面介紹
的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而
實(shí)現(xiàn)的查找方法,而散列查找是通過(guò)構(gòu)造散列函數(shù)來(lái)得
到待查關(guān)鍵字的地址,按理論分析真正不需要用到比較
的一種查找方法。例如,要找關(guān)鍵字為k的元素,則只需
求出函數(shù)值H(k),H(k)為給定的散列函數(shù),代表關(guān)
鍵字k在存貯區(qū)中的地址,而存貯區(qū)為一塊連續(xù)的內(nèi)存單
元,可用一個(gè)一維數(shù)組(或鏈表)來(lái)表示。
例8-4,假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46,
給定散列函數(shù)H(k)=k%13,存貯區(qū)的內(nèi)存地址從0到
15,則可以得到每個(gè)關(guān)鍵字的散列地址為:
H(18)=18%13=5
H(75)=75%13=10
H(60)=60%13=8
H(43)=43%13=4
H(54)=54%13=2
H(90)=90%13=12
H(46)=46%13=7
于是,根據(jù)散列地址,可以將上述7個(gè)關(guān)鍵字序列存貯
到一個(gè)一維數(shù)組HT(散列表)中,具體表示為:
0123456789101112131415
54431846607590
其中HT就是散列存貯的表,稱(chēng)為散列表。從散列表中
查找一個(gè)元素相當(dāng)方便,例如,查找75,只需計(jì)算出
H(75)=75%13=10,則可以在HT[10]中找到75。
上面討論的散列表是一種理想的情形,即每一個(gè)關(guān)鍵
字對(duì)應(yīng)一個(gè)唯一的地址。但是有可能出現(xiàn)這樣的情形,
兩個(gè)不同的關(guān)鍵字有可能對(duì)應(yīng)同一個(gè)內(nèi)存地址,這樣,
將導(dǎo)致后放的關(guān)鍵字無(wú)法存貯,我們把這種現(xiàn)象叫做
沖突(collision)o在散列存貯中,沖突是很難避免的,
除非構(gòu)造出的散列函數(shù)為線性函數(shù)。散列函數(shù)選得比
較差,則發(fā)生沖突的可能性越大。我們把相互發(fā)生沖
突的關(guān)鍵字互稱(chēng)為“同義詞”。
在散列存貯中,若發(fā)生沖突,則必須采取特殊的方法
來(lái)解決沖突問(wèn)題,才能使散列查找能順利進(jìn)行。雖然
沖突不可避免,但發(fā)生沖突的可能性卻與三個(gè)方面因
素有關(guān)。第一是與裝填因子口有關(guān),所謂裝填因子是
指散列表中己存入的元素個(gè)數(shù)n與散列表的大小m的比
值,即a=n/m。當(dāng)a越小時(shí),發(fā)生沖突的可能性越小,
a越大(最大為1)時(shí),發(fā)生沖突的可能性就越大。但
是,為了減少?zèng)_突的發(fā)生,不能將a變得太小,這樣
將會(huì)造成大量存貯空間的浪費(fèi),因此必須兼顧存儲(chǔ)空
間和沖突兩個(gè)方面。第二是與所構(gòu)造的散列函數(shù)有關(guān)
(前面己介紹)。第三是與解決沖突的方法有關(guān),這些
內(nèi)容后面將再作進(jìn)一步介紹。
廣£工38.4.2散列函數(shù)的構(gòu)造
’散列函數(shù)的構(gòu)造目標(biāo)是使散列地址盡可能均勻地分布在
勺士散列空間上,同時(shí)使計(jì)算盡可能簡(jiǎn)單。具體常用的構(gòu)造
方法有如下幾種:
;1.直接定址法
不可表示為H(k)=a.k+b,其中a、b均為常數(shù)。
J這種方法計(jì)算特別簡(jiǎn)單,并且不會(huì)發(fā)生沖突,但當(dāng)關(guān)
,\鍵字分布不連續(xù)時(shí),會(huì)出現(xiàn)很多空閑單元,將造成大
*量存貯單元的浪費(fèi)。
2.數(shù)字分析法
對(duì)關(guān)鍵字序列進(jìn)行分析,取那些位上數(shù)字變化多的、頻率
大的作為散列函數(shù)地址。
例如,對(duì)如下的關(guān)鍵字序列:
430104681015355
430101701128352
430103720818350
430102690605351
430105801226356
通過(guò)對(duì)上述關(guān)鍵字序列分析,發(fā)現(xiàn)前5位相同,第6、
8、10位上的數(shù)字變化多些,若規(guī)定地址取3位,則散
列函數(shù)可取它的第6、8、10位。于是有:
H(430104681015355)=480
H(430101701128352)=101
H(430103620805351)=328
H(430102690605351)=296
H(430105801226356)=502
?二:一3?平方取中法
>|<'取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。這是一
7,.種比較常用的散列函數(shù)構(gòu)造方法,但在選定散列函數(shù)
"『時(shí)不一定知道關(guān)鍵字的全部信息,取其中哪幾位也不
!1一定合適,而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一
位都相關(guān),因此,可以使用隨機(jī)分布的關(guān)鍵字得到函
數(shù)地址。
(I如圖8-1;中,隨機(jī)給出一些關(guān)鍵字,并取平方后的第2到
A,4位為函數(shù)地址。_____________________________
2
關(guān)鍵字(關(guān)鍵字)函數(shù)地址
01000010000010
11001210000210
12001440000440
11601370400370
20614310541310
圖8-16利用平方取中法得到散列函數(shù)地址
4.折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位
數(shù)可以不同),然后取這幾部分的疊加和(舍去進(jìn)位)
作為散列函數(shù)地址,稱(chēng)為折疊法。
例如,假設(shè)關(guān)鍵字為某人身份證號(hào)碼430104681015355,
則可以用4位為一組進(jìn)行疊加,即有5355+8101+1046
+430=14932,舍去高位,則有H(430104681015355)
=4932為該身份證關(guān)鍵字的散列函數(shù)地址。
5.除留余數(shù)法
該方法是用關(guān)鍵字序列中的關(guān)鍵字k除以散列表長(zhǎng)度m所
得余數(shù)作為散列函數(shù)的地址,即有H(k)=k%m。
r除留余數(shù)法計(jì)算簡(jiǎn)單,適用范圍廣,是一種最常使用的
y!方法。這種方法的關(guān)鍵是選取較理想的m值,使得每一
個(gè)關(guān)鍵字通過(guò)該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址
1的概率都相等,從而盡可能減少發(fā)生沖突的可能性。一
般情形下,m取為一個(gè)素?cái)?shù)較理想,并且要求裝填因子
a最好是在0.6s0.9之間,所以m最好取1.1ns1.7n之間
11的一個(gè)素?cái)?shù)較好,其中口為散列表中待裝元素個(gè)數(shù)。
:'、8.4.3解決沖突的方法
》由于散列存貯中選取的散列函數(shù)不是線性函數(shù),故不可避
《免地會(huì)產(chǎn)生沖突,下面給出常見(jiàn)的解決沖突方法。
\L開(kāi)放定址法
開(kāi)放定址法就是從發(fā)生沖突的那個(gè)單元開(kāi)始,按照一定
Y的次序,從散列表中找出一個(gè)空閑的存儲(chǔ)單元,把發(fā)生
Q沖突的待托入關(guān)鍵字存儲(chǔ)到該單元中,從而解決沖突的
、發(fā)生。
1一二?.在開(kāi)放定址法中,散列表中的空閑單元(假設(shè)地址為K)
Lj'J:'不僅向散列地址為K的同義詞關(guān)鍵字開(kāi)放,即允許它們
,?、使用,而且還向發(fā)生沖突的其它關(guān)鍵字開(kāi)放(它們的
號(hào)屋散列地址不為K),這些關(guān)鍵字稱(chēng)為非同義詞關(guān)鍵字。
例如,設(shè)有關(guān)鍵字序列14,27,40,15,16,散列函
I數(shù)為H(k)=k%13,則14,27,40的散列地址都為1,
V因此發(fā)生沖突,即14,27,40互為同義詞,這時(shí),假
i\設(shè)處理沖突的方法是從沖突處順序往后找空閑位置,
V找到后放入沖突數(shù)據(jù)即可。則14放入第1個(gè)位置,27只
\\能放入第2個(gè)位置,40就只能放入第3個(gè)位置,接著往
/后有關(guān)鍵字15,16要放入散列表中,而15,16的散列
/地址分別為2和3,即15應(yīng)放入第2個(gè)位置,16應(yīng)放入第
A3個(gè)位置,而第2個(gè)位置己放入了27,第3個(gè)位置己放入
\\了40,故也發(fā)生沖突,但這時(shí)是非同義詞沖突,即15
\)和27、16和40相互之間是非同義詞。這時(shí),解決沖突
V后,15應(yīng)放入第4個(gè)位置,16應(yīng)放入第5個(gè)位置。因此,
。在使用開(kāi)放定址法處理沖突的散列表中,地址為K的單
A元到底存儲(chǔ)的是同義詞中的一個(gè)關(guān)鍵字,還是非同義
.}詞關(guān)鍵字,這就要看誰(shuí)先占用它。
二:Ui在開(kāi)放定址法中,解決沖突時(shí)具體使用下面一些方法。
(1)線/陛探杳法
m假設(shè)散列表的地址為Osm-l,則散列表的長(zhǎng)度為m。若
一個(gè)關(guān)鍵字在地址d處發(fā)生沖突,則依次探查d+1,
!d+2,…,m-1(當(dāng)達(dá)到表尾m-1時(shí),又從0,1,2,....開(kāi)
始探查)等地址,直到找到一個(gè)空閑位置來(lái)裝沖突處的
)\關(guān)鍵字,將這一種方法稱(chēng)為線性探查法。假設(shè)發(fā)生沖突
U時(shí)的地址為d0=H(k),則探查下一位置的公式為4=((
最后將沖突位置的關(guān)鍵字存入地
(》\址i+l中)%。m(l<i<m-l),4
A例8-5給定關(guān)鍵字序列為19,14,23,1,68,20,84,27,
(\55,11,10,79,散到函數(shù)H(k)=k%13,散列表空間地
址為0si2,試用線性探查法建立散列存貯(散列表)結(jié)構(gòu)。
V得到的散列表如圖8-17所示
0123456789
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 品質(zhì)管理表格
- 汽修廠前臺(tái)接待服務(wù)流程標(biāo)準(zhǔn)化規(guī)定
- 浙江溫州圖書(shū)館招聘試題帶答案分析2024年
- 陜西商洛圖書(shū)館招聘試題帶答案分析2024年
- 江蘇鹽城圖書(shū)館招聘試題帶答案分析2024年
- 高溫作業(yè)現(xiàn)場(chǎng)急救站設(shè)置
- 車(chē)管助理考試試題及答案
- 第2課時(shí) 條形統(tǒng)計(jì)圖(2) 導(dǎo)學(xué)案 人教版數(shù)學(xué)四年級(jí)上冊(cè)
- 建筑公司綠色施工成果展示推廣制度
- 江蘇海奕控股集團(tuán)有限公司招聘筆試真題2024
- 公文寫(xiě)作技能題庫(kù)及答案
- 2025年廣東省中考語(yǔ)文試卷真題(含答案解析)
- 遼寧省“三支一扶”招募考試真題2024
- 多能工培訓(xùn)方案
- 學(xué)生自信心培養(yǎng)的教育心理學(xué)研究
- 2025中國(guó)內(nèi)地薪酬指南-kos高奧士國(guó)際-202506
- 2025年中國(guó)嬰兒搖鈴?fù)婢咝袠I(yè)市場(chǎng)發(fā)展前景及發(fā)展趨勢(shì)與投資戰(zhàn)略研究報(bào)告
- 2024年包頭職業(yè)技術(shù)學(xué)院招聘筆試真題
- 2025廣西專(zhuān)業(yè)技術(shù)人員公需科目培訓(xùn)考試答案
- 2024年山東高中學(xué)業(yè)水平合格考試化學(xué)試卷真題(含答案詳解)
- 國(guó)開(kāi)機(jī)考答案-工程力學(xué)(本)(閉卷)
評(píng)論
0/150
提交評(píng)論