數(shù)據(jù)結(jié)構(gòu)課件第8章 查找_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件第8章 查找_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件第8章 查找_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件第8章 查找_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)課件第8章 查找_第5頁(yè)
已閱讀5頁(yè),還剩62頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論