備戰(zhàn)NOIP2010提高組初賽復(fù)習(xí)-數(shù)據(jù)結(jié)構(gòu)

1、 備戰(zhàn)2提0高1組0初賽復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)篇 # #FORTRAN語(yǔ)言?xún)H定早期的程序設(shè)計(jì)主要偏重于數(shù)值計(jì)算領(lǐng)域，采用的數(shù)據(jù)結(jié)構(gòu)相對(duì)簡(jiǎn)單。例如義了數(shù)組(包括多維數(shù)組)和復(fù)數(shù)兩種結(jié)構(gòu)型數(shù)據(jù)，這兩種數(shù)據(jù)類(lèi)型足以應(yīng)付當(dāng)時(shí)多數(shù)的科學(xué)計(jì)算問(wèn)題。但是隨著現(xiàn)代科技的發(fā)展，計(jì)算機(jī)逐漸應(yīng)用于數(shù)據(jù)處理和非數(shù)值計(jì)算問(wèn)題，從客觀事物中抽象出的數(shù)據(jù)日益顯現(xiàn)出多樣化的特征，簡(jiǎn)單的數(shù)據(jù)類(lèi)型已遠(yuǎn)遠(yuǎn)不能滿足需要，各數(shù)據(jù)元素之間的復(fù)雜聯(lián)系已經(jīng)不是普通的數(shù)學(xué)方程式所能表達(dá)的了。在這種背景下，一種專(zhuān)門(mén)研究數(shù)據(jù)之間結(jié)構(gòu)關(guān)系的 #學(xué)科數(shù)據(jù)結(jié)構(gòu)便應(yīng)運(yùn)而生。數(shù)據(jù)結(jié)構(gòu)專(zhuān)門(mén)研究各種數(shù)據(jù)的表示、數(shù)據(jù)的類(lèi)型以及它們之間關(guān)系的集合，其研究范圍主要包括各種數(shù)據(jù)

2、結(jié)構(gòu)的性質(zhì)，即它們的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及施于其上的操作。數(shù)據(jù)結(jié)構(gòu)的類(lèi)型種類(lèi)繁多，可以從不同的角度來(lái)劃分：若從數(shù)據(jù)元素的值在使用時(shí)具有不可分割的性質(zhì)或者是它可以由更基本的成份組成這個(gè)角度來(lái)劃分，數(shù)據(jù)結(jié)構(gòu)可以分成簡(jiǎn)單類(lèi)型和構(gòu)造類(lèi)型兩大類(lèi)；如果從數(shù)據(jù)所占據(jù)的內(nèi)存空間在程序執(zhí)行期間是否發(fā)生變化這個(gè)角度來(lái)劃分，數(shù)據(jù)結(jié)構(gòu)又可以分成靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)兩大類(lèi)；如果從數(shù)據(jù)結(jié)點(diǎn)后繼關(guān)系的多少和是否具有層次性的角度劃分，數(shù)據(jù)結(jié)構(gòu)還可以分 #成線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類(lèi)。簡(jiǎn)單類(lèi)型整型、實(shí)型、字符型、布爾型靜態(tài)數(shù)據(jù)類(lèi)型構(gòu)造類(lèi)型數(shù)組、記錄、集合、字符串文件、指針動(dòng)態(tài)數(shù)據(jù)的類(lèi)型線性結(jié)構(gòu)數(shù)組、棧、隊(duì)列、鏈表、串非線性結(jié)構(gòu)樹(shù)

3、、圖PASCAL就通常高級(jí)程序設(shè)計(jì)語(yǔ)言都提供了各種簡(jiǎn)單類(lèi)型和靜態(tài)構(gòu)造類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。例如提供了叮種類(lèi)型的定義。這皿種類(lèi)型中除了文件和指針屬于動(dòng)態(tài)結(jié)構(gòu)的構(gòu)造類(lèi)型外，其余口 #叮均屬于簡(jiǎn)單類(lèi)型和靜態(tài)構(gòu)造類(lèi)型。在上表的數(shù)據(jù)結(jié)構(gòu)中，像數(shù)組、棧、串和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)屬于線性數(shù)據(jù)結(jié)構(gòu)，而樹(shù)和圖屬于非線性數(shù)據(jù)結(jié)構(gòu)。線性數(shù)據(jù)結(jié)構(gòu)易于表示各結(jié)點(diǎn)之間的聯(lián)系，其存儲(chǔ)方式相對(duì)簡(jiǎn)單；非線性數(shù)據(jù)結(jié)構(gòu)往往能比較形象地反映各結(jié)點(diǎn)之間的層次關(guān)系。無(wú)論是線 #性結(jié)構(gòu)或非線性結(jié)構(gòu)，若采用數(shù)組方式存儲(chǔ)，則屬于靜態(tài)數(shù)據(jù)類(lèi)型；若采用指針類(lèi)型存儲(chǔ)，則屬于動(dòng)態(tài)數(shù)據(jù)類(lèi)型。考慮到篇幅限制和讀者大多具備pascal語(yǔ)言或c語(yǔ)言的基礎(chǔ)，本書(shū)側(cè)重講解

4、線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種。數(shù)據(jù)結(jié)構(gòu)和算法有著密切的聯(lián)系，簡(jiǎn)潔有效的算法很大程度上出自于對(duì)數(shù)據(jù)結(jié)構(gòu)的正確選從問(wèn)題中抽象出的數(shù)據(jù)多半是結(jié)構(gòu)類(lèi)取。奧林匹克信息學(xué)競(jìng)賽的試題大都屬于非數(shù)值計(jì)算問(wèn)題，型的，因此，對(duì)于參與這項(xiàng)活動(dòng)的學(xué)生來(lái)說(shuō)，學(xué)好、用好數(shù)據(jù)結(jié)構(gòu)尤為重要。為此。我們?cè)诒緯?shū)中詳盡地介紹了數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和基本操作，同時(shí)輔之于一些實(shí)例，圍繞編程實(shí)際展開(kāi)討論， 盡可能多給讀者一點(diǎn)啟示。第一章順序存儲(chǔ)結(jié)構(gòu)的線性表線性表是最常用且比較簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，它是由有限個(gè)數(shù)據(jù)元素組成的有序集合，每個(gè)數(shù)據(jù)元素有一個(gè)數(shù)據(jù)項(xiàng)或者含多個(gè)數(shù)據(jù)項(xiàng)。例如26個(gè)英文字母表(A,B,Z)是一個(gè)線性表，11）也是一個(gè)線性表，表

5、中含8個(gè)數(shù)表中每一個(gè)數(shù)據(jù)元素由單個(gè)字母組成數(shù)據(jù)項(xiàng)。又如（圖據(jù)元素，每一個(gè)數(shù)據(jù)元素由n個(gè)選手在該項(xiàng)目的競(jìng)賽成績(jī)組成。、學(xué)生項(xiàng)目、學(xué)生1學(xué)生j學(xué)生n項(xiàng)目總分項(xiàng)目1項(xiàng)目iXxiji=1項(xiàng)目8選手總分sumSumx=xjiji=1（圖11）線性表具有如下結(jié)構(gòu)特征：均勻性：即同一線性表的各數(shù)據(jù)元素的數(shù)據(jù)類(lèi)型一致且數(shù)據(jù)項(xiàng)數(shù)相同；有序性：表中數(shù)據(jù)元素之間的相對(duì)位置是線性的，即存在唯一的“第一個(gè)”和“最后一個(gè)”數(shù)據(jù)元素。除第一個(gè)和最后一個(gè)外，其它元素前面均只有一個(gè)數(shù)據(jù)元素（直接前趨）和后面均只有一個(gè)數(shù)據(jù)元素（直接后繼）。按照表中數(shù)據(jù)元素的存儲(chǔ)方式分順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二類(lèi)線性表。順序存儲(chǔ)結(jié)構(gòu)是指用一組地

6、址連續(xù)的存貯單元依次存儲(chǔ)線性表的元素，通常用數(shù)組實(shí)現(xiàn)；而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，邏輯上相鄰的兩元素，其物理位置不要求相鄰。其實(shí)現(xiàn)既可采用靜態(tài)數(shù)組，亦可采用動(dòng)態(tài)指針。為了擴(kuò)大用戶(hù)空間和更多地體現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的便利，實(shí)踐中大都采用動(dòng)態(tài)鏈表形式。為此，本書(shū)在講解順序存儲(chǔ)結(jié)構(gòu)的線性表時(shí)采用數(shù)組類(lèi)型，在講解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表采用指針類(lèi)型。另外，根據(jù)存取方式的限制和表元素類(lèi)型的限制，還存在幾種特殊類(lèi)型的線性表：棧、隊(duì)列、串，它們一般采用順序存儲(chǔ)結(jié)構(gòu)11數(shù)組若數(shù)組元素不再有分表長(zhǎng)為（d1-c1）*（d2-c2），1個(gè)元素的地址）十位移來(lái)我們稱(chēng)有限個(gè)同類(lèi)型數(shù)據(jù)元素的序列為數(shù)組，它是一種定長(zhǎng)的線性表。量，該

7、序列叫一維數(shù)組；若數(shù)據(jù)元素為數(shù)組，則稱(chēng)該元素為多維數(shù)組。例如varA：arraycDdofatype；B：arraycDd,cDdofbtype；1122A為一維數(shù)組，表長(zhǎng)為（dc+1）,元素類(lèi)型為atype；B為二維數(shù)組，元素類(lèi)型為btype。一維數(shù)組和多維數(shù)組的元素個(gè)數(shù)由其類(lèi)型說(shuō)明或變量說(shuō)明靜態(tài)確定，執(zhí)行中不能增減其內(nèi)存空間。一、數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組的物理實(shí)現(xiàn)是一塊連續(xù)的存儲(chǔ)空間，它是按首址（表中第訪問(wèn)每一個(gè)元素的。設(shè)cDiDd）；loc（ai）A表中元素i的內(nèi)存地皿loc(bi,j)B表中口i,j)元素的內(nèi)存地址(ciDd,jOdD；loc(ai)=loc(ac)+(ic)*llaty

8、pe類(lèi)型的長(zhǎng)度；aa首址位移lbbtype類(lèi)型的長(zhǎng)度；loc(bi，j)=loc(bc，c)+(d-c+1)*(i-c)+(j-c)*l.122212b首址位移一維數(shù)組按照下標(biāo)遞增的順序訪問(wèn)表中元素acDac+1DDad二維數(shù)組按照先行后列的順序訪問(wèn)表中元素bc,cDbc,c+1DDbc,12121Dbd,d12在數(shù)組中,數(shù)據(jù)元素的下標(biāo)間接反映了數(shù)據(jù)元素的存儲(chǔ)地址。dDD2bi-1,dD2bi,cDD2而計(jì)算機(jī)內(nèi)存是隨機(jī)存取的裝bd,1d-12置,所以在數(shù)組中存取一個(gè)數(shù)據(jù)元素只要通過(guò)下標(biāo)計(jì)算它的存儲(chǔ)地址就行了,數(shù)組中任意一個(gè)元素的存取時(shí)間都相等。從這個(gè)意義上講,數(shù)組的存儲(chǔ)結(jié)構(gòu)是一個(gè)隨機(jī)存取的結(jié)

9、構(gòu)。二、數(shù)組在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除設(shè)數(shù)組定義為Constm二數(shù)組的長(zhǎng)度上限；Typevtype二array1Dmofelementype；varn：integer；v：vtype；數(shù)組類(lèi)型數(shù)組的實(shí)際長(zhǎng)度數(shù)組按上述定義，v為一個(gè)長(zhǎng)度為n的數(shù)組v=v1,v2,vn,元素類(lèi)型為elementype。 # #1、插入操作現(xiàn)要在數(shù)組的第i1個(gè)元素vil與第i個(gè)元素vi之間插入一個(gè)新元素b,插入后將得 #到一個(gè)長(zhǎng)度為插入前后兩數(shù)組的元素vj與vj滿足如下關(guān)系n+1的新數(shù)組v=v1,vn,vn+1 # #vj1ji-1vj=bj二ivj-1i1jn1 #ii個(gè)元顯然,若插入運(yùn)算在數(shù)組未尾（即在個(gè)元素即

10、可。但是,在一般情況下,如果插入運(yùn)算在第個(gè)元素及其之后的所有元素都必須移動(dòng)。移動(dòng)從最后一個(gè)元素（即vn后插入新元素）進(jìn)行，則只要在數(shù)組末尾增加一i（1DiDn）個(gè)元素之前進(jìn)行，則原來(lái)第vn）開(kāi)始，直到第 素之間共ni+1個(gè)元素依次向后移動(dòng)一個(gè)位置，然后將新元素插入第i項(xiàng)：procedureinsert(b：elementype；i：integer；beginifndmvarn：integer；varv：vtype)；上溢thenwriteln(overflow)elseif(in+1)thenwriteln(without)elsebeginforj：=ndowntoidovj+1Dvj；vi

11、Dvn向后移動(dòng)一個(gè)位置 viDb；ndn+1；end；elseb插入i位置，v數(shù)組的長(zhǎng)度+1end；insert執(zhí)行insert過(guò)程的時(shí)間復(fù)雜度:數(shù)組中一半的元素。對(duì)順序存儲(chǔ)的數(shù)組作一次插入運(yùn)算，平均起來(lái)，大約需要移動(dòng)2、刪除操作現(xiàn)要?jiǎng)h除數(shù)組v中的第i個(gè)元素，其長(zhǎng)度變?yōu)閚1。顯然刪除前后兩數(shù)組元素vjvjvj+1使得刪除后的v數(shù)組變?yōu)関=v1,v2,vnl,vj和vj滿足下列關(guān)系1ji-1ijn一1 proceduredelet(i：integer；varn：integer；beginif(in)thenwriteln(without)elsebeginforj：=iton1dovjdvj+1

12、；ndn1；end；elseend；deletvarv：vtype)；vi+1Dvn向前移動(dòng)一個(gè)位置v數(shù)組的長(zhǎng)度1同樣，為了刪除數(shù)組中第i000,則原來(lái)第i個(gè)元素之后的所有元素必須依次向前移動(dòng)一個(gè)位置。如果要?jiǎng)h除數(shù)組最后一個(gè)元素，則很簡(jiǎn)單，不需要移動(dòng)數(shù)組元素；如果要?jiǎng)h除數(shù)組的第一個(gè)元素，則很復(fù)雜，必須將數(shù)組中的所有元素依次向前移動(dòng)一個(gè)位置。在一般情況下，要?jiǎng)h除第個(gè)元素，需要將數(shù)組中第i+1到第n共ni個(gè)元素依次向前移動(dòng)一個(gè)位置。執(zhí)行delet過(guò)程的時(shí)間復(fù)雜度：對(duì)順序存儲(chǔ)的數(shù)組作一次刪除，平均起來(lái)，大約需要移動(dòng)表中一半的元素。綜上所述，數(shù)組的順序分配，其結(jié)構(gòu)比較簡(jiǎn)單，便于隨機(jī)訪問(wèn)數(shù)組中的任一元素

13、。但是如果數(shù)組要保持線性表特征的話（由下標(biāo)指明元素間的有序性），其增刪操作的效率比較低。特別當(dāng)數(shù)組很大時(shí)，插入與刪除運(yùn)算頗為費(fèi)時(shí)。因此，比較小的數(shù)組或元素不常變動(dòng)（很少進(jìn)行插入與刪除運(yùn)算）的數(shù)組可用作線性表，而對(duì)于大的線性表或元素經(jīng)常變動(dòng)的線性表，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。三、數(shù)組的應(yīng)用實(shí)例1、在編程時(shí)（使用任一種高級(jí)語(yǔ)言，不一定是Pascal)如果需要從磁盤(pán)文件中輸入一個(gè)很大的二維數(shù)組（例如1000*1000的double型數(shù)組）按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循環(huán)是關(guān)于列的）相比，在輸入效率上（。）A.沒(méi)有區(qū)別B.有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì)C.按行讀的方式要高一些

14、D.按列讀的方式要高一些E.取決于數(shù)組的存儲(chǔ)方式。12棧棧是一種線性表，對(duì)它的插入和刪除都限制在表的同一端進(jìn)行。這一端叫做棧的“頂”，另一端則叫做棧的“底”。根據(jù)棧的定義，每次刪除的總是當(dāng)前“最年輕”的表目，即最后插入的表目，而最先插入的表后進(jìn)先出表”(LIFOlastinput目則被放在棧的底部，要到最后才能刪除。因此，棧又被稱(chēng)為“firstoutput）。仿佛食堂里的一疊盤(pán)子，每次只許一個(gè)一個(gè)地往上堆，一個(gè)一個(gè)地往下取。通常棧可以用順序的方式存儲(chǔ)，向當(dāng)前棧頂。假設(shè)棧中表目數(shù)的上限為義棧：Const分配一塊連續(xù)的存儲(chǔ)區(qū)域存放棧中的表目，m,所有表目都具有同一類(lèi)型并用一個(gè)變量t指stype,則

15、可以用下列方式定m=棧表目數(shù)的上限；Typestack=array1Dmofstype；Vars：stack；t：integer；mtu1(圖121)棧類(lèi)型棧棧頂指針棧的基本運(yùn)算過(guò)程，一往棧中壓入一個(gè)值為的表目procedurepush(vars：stack；x：stype；vart：integer)；beginift=mthenwriteln(overflow)上溢elsebegintdt+1；stUx；end；elsex入棧end；Push、函數(shù),一從棧中彈出一個(gè)表目functionpop(vars：stack；vart：beginift=0thenwriteln(underflow)el

16、sebeginpopdst；tdend；popinteger)：stype；t-1；end；else下溢棧頂元素出棧函數(shù)，一讀棧頂元素functiontop(s：stack；t：integer)：stype；beginift=0thenwriteln(stackempty)返回棧頂元素）的數(shù)據(jù)結(jié)構(gòu)。elsetopdst；end；top二、棧的應(yīng)用遞歸過(guò)程和函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱(chēng)為（2.設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧，出棧順序?yàn)閎，d，c，f，e，a那么棧容量至少應(yīng)該是（）。AD6BD5CD4DD3ED23.某個(gè)車(chē)站呈狹長(zhǎng)形，寬度只能容下一臺(tái)車(chē)，

17、并且只有一個(gè)出入口。已知某時(shí)刻該車(chē)站狀態(tài)為空，從這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車(chē)輛入站的順序?yàn)?，2，3，則車(chē)輛出站的順序?yàn)椋?。）A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2E.1,4,3,7,54.地面上有標(biāo)號(hào)為A、B、C的3根細(xì)柱,在A柱上放有10個(gè)直徑相同中間有孔的圓盤(pán),從上到下次依次編號(hào)為1,2,3,，將A柱上的部分盤(pán)子經(jīng)過(guò)B柱移入C柱，也可以在B柱上暫存。A叮列BDODODCDDOODU鏈表EDD如果B柱上的操作記錄為：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么，在C柱上，

18、從下到上的盤(pán)子的編號(hào)叮）。C.243176A.243657B.241257E.214375D.2436755.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e依次入棧，以下出棧序列不可能出現(xiàn)的有（）（不定項(xiàng)）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a6.表達(dá)式a*(b+c)-d的后綴表達(dá)式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd1D3隊(duì)列一、隊(duì)列的基本概念隊(duì)列是不同于棧的另一種線性表。在日常生活中，無(wú)論是購(gòu)物、訂票或候車(chē)都有可能要排隊(duì)。排隊(duì)所遵循的原則是“先來(lái)先服務(wù)”日常生活中的排隊(duì)現(xiàn)象抽象出來(lái)的。，后來(lái)者總是加到

19、隊(duì)尾，排頭者總是先離開(kāi)隊(duì)伍。隊(duì)列就是從所謂隊(duì)列，就是允許在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表。允許插入的一端稱(chēng)為隊(duì)尾，通常用一個(gè)隊(duì)尾指針指向隊(duì)尾元素，即總是指向最后被插入的元素；允許刪除的一端稱(chēng)為隊(duì)首，通常也用一個(gè)隊(duì)首指針指向排頭元素的前面。初始時(shí)。 # abcdbcdBcd1e1 一個(gè)隊(duì)列顯然，在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，被刪除，因此隊(duì)列又稱(chēng)為“先進(jìn)先出與棧相似，隊(duì)列的順序存儲(chǔ)空間可以用一維數(shù)組Constm=隊(duì)列元素的上限；隊(duì)列的類(lèi)型定義隊(duì)列隊(duì)尾指針和隊(duì)首指針刪除一個(gè)元素插入一個(gè)元素（圖131）最先插入在元素將是最先被刪除；反之最后插入的元素將最后”（FIFOfirstinfirstout）的

20、線性表。q1Dm模擬：Typeequeue=array1mofqtype；Varq：equeue；r，f：integer； # Q：1m（圖312）二、隊(duì)列的基本運(yùn)算隊(duì)列的運(yùn)算主要有兩種1、過(guò)程ADD(q,x,r)在隊(duì)列procedureADD(varq：q的尾端插入元素xequeue；x：qtype；varr：integer）；beginifr=mthenwriteln(overflow)elsebeginrDr+1；qrDx；end；elseend；ADD后移隊(duì)尾指針并插入元素上溢x2、過(guò)程DEL(q,y,f,r)取出q隊(duì)列的隊(duì)首元素yprocedureDEL(varq：equeue；va

21、ry：qtype；beginiff=rthenwriteln(underflow)elsebeginfDf+1；yDqf；end；elseend；DELvarf：integer)；后移隊(duì)首指針并取出隊(duì)首元素下溢 # #由于隊(duì)列只能在一端插入,在另一端刪除,因此隨著入隊(duì)及出隊(duì)運(yùn)算的不斷進(jìn)行,種有別于棧的情形：隊(duì)列在數(shù)組中不斷地向隊(duì)尾方向移動(dòng),閑存儲(chǔ)區(qū),最后會(huì)導(dǎo)致當(dāng)尾指針指向數(shù)組最后一個(gè)位置（即的前部卻有一片存儲(chǔ)區(qū)無(wú)端浪費(fèi),這種現(xiàn)象稱(chēng)為“就會(huì)出現(xiàn)一假溢出而在隊(duì)首的前面產(chǎn)生一片不能利用的空r=m）而不能再加入元素時(shí)，存儲(chǔ)空間”。例如： # #mmmrDmAm 1fDf，rD321初始時(shí)隊(duì)列空f(shuō)=r=

22、0加入三個(gè)元素f=0r=3刪除三個(gè)元素隊(duì)列空f(shuō)=r=3fD321加入m-3個(gè)元素隊(duì)列滿r=mf=3 #（圖133）三、循環(huán)隊(duì)列及其運(yùn)算所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間供隊(duì)列循環(huán)使用，循環(huán)隊(duì)列的定義如隊(duì)列。 # 只要存儲(chǔ)空間第一個(gè)位置空閑，便采用首尾相接的循環(huán)隊(duì)列結(jié)構(gòu)f=r=m。當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用而要進(jìn)行入隊(duì)運(yùn)算時(shí)，可將元素加入到第一個(gè)位置，即將存儲(chǔ)空間的第一個(gè)位置作為隊(duì)尾。后，可以有效地解決假溢出的問(wèn)題，避免數(shù)據(jù)元素的移動(dòng)。對(duì)循環(huán)隊(duì)列操作有以下幾種狀態(tài)：初始時(shí)隊(duì)列空，隊(duì)首指針和隊(duì)尾指針均指向存儲(chǔ)空間的最后一個(gè)位置，即入隊(duì)運(yùn)算時(shí)，尾

23、指針進(jìn)一，即rdr+1；ifr=m+1thenrd1；這兩條語(yǔ)句可用一條語(yǔ)句替代：rd（r+1）modm；出隊(duì)運(yùn)算時(shí)，首指針進(jìn)一，即fdf+1；iff=m+1thenfd1；這兩條語(yǔ)句可用一條語(yǔ)句替代：fd（f+1）modm；隊(duì)列空時(shí)有f=r。隊(duì)列滿時(shí)有f=（r+1）modm。（為了區(qū)分隊(duì)列空和隊(duì)列滿，改用“隊(duì)尾指針追上隊(duì)首指針”這一特征作為隊(duì)列滿標(biāo)志。這種處理方法的缺點(diǎn)是浪費(fèi)隊(duì)列空間的一個(gè)存儲(chǔ)單元）循環(huán)隊(duì)列的運(yùn)算有兩種：1、過(guò)程ADD2（q,x,r）在循環(huán)隊(duì)列q中插入一個(gè)新元素xprocedureADD（varq：equeue；x：qtype；varr：integer）；begintd（r+

24、1）modm；計(jì)算插入位置ift=fthenwriteln（full）隊(duì)列滿新元素X插入隊(duì)尾elsebeginrDt；qrDx；end；elseend；ADD2TOC o 1-5 h z2過(guò)程DEL2(q,y,f)從循環(huán)隊(duì)列q中取出隊(duì)首元素yprocedureDEL(varq：equeue；vary：qtype；varf：inteqer)；beginiff=rthenwriteln(empty)隊(duì)列空elsebeginfD(f+1)modm；yDqf；取出隊(duì)首元素end；elseend；DEL2四、隊(duì)列的應(yīng)用舉例1.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e,e,e,e,e,e依次通過(guò)棧123456

25、S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若出隊(duì)的順序?yàn)閑,e,e,e,e,e,則棧243651S的容量至少應(yīng)該為（）。A)2B)3C)4D)514串但實(shí)際中我們經(jīng)常要對(duì)一串元素進(jìn)行操前面介紹的線性表的操作都是對(duì)一個(gè)元素進(jìn)行處理的，作。如信息檢查系統(tǒng)、文字編輯系統(tǒng)、自然語(yǔ)言翻譯系統(tǒng)以及音樂(lè)分析程序等等，都是以字符串?dāng)?shù)據(jù)作為處理對(duì)象的。隨著非數(shù)值的廣泛應(yīng)用，字符串的處理將顯得越來(lái)越重要。一、串的基本概念串是由零個(gè)或多個(gè)字符組成的有限序列。一個(gè)串中包含的字符個(gè)數(shù)稱(chēng)為這個(gè)串的長(zhǎng)度。長(zhǎng)度為 #零的串稱(chēng)為空串，它不包含任何字符。x1長(zhǎng)度為2的0123長(zhǎng)度為3的數(shù)0長(zhǎng)度為0的空0包含一個(gè)空白字符（長(zhǎng)度為通常用撇將字

26、符串括起來(lái)。例如1）的非空串 # #假設(shè)si和s2是兩個(gè)串：s1=a1ans2=bibm #其中ai、bi代表字符（0DmDn）。如果存在整數(shù)i(0DiDn-m),使得 bj=ai+jj=1Dms1包含串s2。同時(shí)成立，則稱(chēng)s2是si000,0000中所能包含的字符依賴(lài)于具體機(jī)器的字符集,按字符的字符集中的次序可以規(guī)定字符的大 #小。目前世界上最為廣泛的字符集是ASCII（美國(guó)信息變換標(biāo)準(zhǔn)碼）和EBCDIC（擴(kuò)充的二進(jìn)制編l0碼、十進(jìn)制信息碼)，它們都規(guī)定數(shù)字字符09的字符集是順序排列的，字母字符AZ(az的字符集也是順序排列的，因此用ord函數(shù)計(jì)算字符在字符集中的序號(hào)就有ord(a)ord(

27、b)ord(z)ord(0)ord(1)ord(q)并且對(duì)所有數(shù)字i(0WiW9)滿足i=ord(i)-ord(0)通?？蓪?duì)兩個(gè)字符chi和ch2作比較，所謂chlvch2的含義就是指ord(chl)vord(ch2)，必要時(shí)可以將串按其構(gòu)成的字符用字符順序排列，從而定義兩個(gè)串的大小。例如aabox0121232程序中使用的串可以分成兩種l、串常數(shù)串常數(shù)具有固定的串值，即可以用直接量表示，用以原樣輸出，亦可以給串常數(shù)命名，以便反復(fù)使用時(shí)書(shū)寫(xiě)和修改方便。例如constobject=datastructure；命名串常數(shù)writeln(overflow)原樣輸出串常數(shù)2、串變量串變量的取值是可以改

28、變的，但必須用名字來(lái)識(shí)別，說(shuō)明串變量的方法與其它變量相似。例如vars：string30；上面定義了一個(gè)串變量s,s最多能容納30個(gè)字符，且順序存在一個(gè)字符數(shù)組中，類(lèi)似于vars:array030ofchar；其中s0記載了s的實(shí)際長(zhǎng)度。若string類(lèi)型中省略長(zhǎng)度標(biāo)記，則串長(zhǎng)上限為255個(gè)字符。二、串的基本運(yùn)算PASCAL中提供了一些串運(yùn)算的庫(kù)函數(shù)，我們將作以簡(jiǎn)單的介紹1、連接運(yùn)算函數(shù)concat(sl，s2，sn)其中值參s1,，sn為string類(lèi)型，函數(shù)值為string類(lèi)型。若連接后的串長(zhǎng)大于255，則自動(dòng)截?cái)喑霾糠帧?、求子串函數(shù)copy(s，i，l)其中值參s為string類(lèi)型，

29、i和1為integer類(lèi)型。函數(shù)返回s串中第i個(gè)字符開(kāi)始、長(zhǎng)度為1的子串(string類(lèi)型)。若i大于s的長(zhǎng)度，則回送一個(gè)空串；若l大于第i個(gè)字符開(kāi)始的余串長(zhǎng)度，則僅回送余串。3、刪子串過(guò)程de1ete(vars，i，1)其中變量參數(shù)s為string類(lèi)型，值參i、l為ingteger類(lèi)型。該過(guò)程刪去s中第i個(gè)字符開(kāi)始的長(zhǎng)度為l的子串，并返回剩余串s。若i大于原串s的長(zhǎng)度，則不刪任何字符；若l大于第i個(gè)字符開(kāi)始的余串長(zhǎng)度，則刪去余串。ii4、插入子串過(guò)程變量參數(shù)置處，并返回插入后的結(jié)果insert（si，vars，i）string類(lèi)型，值參s。若插入后si為string類(lèi)型。該過(guò)程將s的串長(zhǎng)大于

30、si子串插入空串255個(gè)字符，則截?cái)喑霾糠?。s的第i個(gè)字符位5、求串長(zhǎng)函數(shù)length（s）值參s為string類(lèi)型。該函數(shù)返回s串的實(shí)際長(zhǎng)度值（integer類(lèi)型）。pos（si，值參si和s2為string類(lèi)型。若si是類(lèi)型）；若si非s2的一個(gè)子串，則返回6、搜索子串位置函數(shù)s2）s2的一個(gè)子串，則返回si中第1個(gè)字符在s2串中的位置integer0。7、數(shù)值轉(zhuǎn)換為數(shù)串過(guò)程值參x為integer類(lèi)型或str（x，real類(lèi)型，變量參數(shù)vars)Is為string類(lèi)型。該過(guò)程將返回?cái)?shù)值x對(duì)應(yīng)的數(shù)串s。8、數(shù)串轉(zhuǎn)換為數(shù)值過(guò)程值參s為string類(lèi)型，變量參數(shù)試將s串轉(zhuǎn)換成數(shù)值val（s，v

31、arv，varc）v為integer類(lèi)型或v。若轉(zhuǎn)換成功，則c為0,并返回對(duì)應(yīng)的數(shù)值real類(lèi)型，變量參數(shù)v；否則integer類(lèi)型。該過(guò)程c為無(wú)效字符的序數(shù)。9、字符的大寫(xiě)轉(zhuǎn)換函數(shù)值參ch為char類(lèi)型。該函數(shù)返回upcase（ch）ch字符的大寫(xiě)皿char類(lèi)型）三、串的應(yīng)用實(shí)例1.字符串“ababacbab”和字符串“abcba”的最長(zhǎng)公共子串是（）。A.abcbaB.cbaC.abcD.abE.bcba2.設(shè)字符串A29S=“Olympic”,S的非空字串的數(shù)目叮B28C16）。D17E第二章鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表第一章所討論的線性表的順序存儲(chǔ)結(jié)構(gòu)具有存儲(chǔ)數(shù)據(jù)元素方便的特點(diǎn),構(gòu)比較簡(jiǎn)單。但

32、是也存在著一些固有的缺點(diǎn)：1在作插入或刪除運(yùn)算時(shí)需要移動(dòng)大量元素；2在給長(zhǎng)度變化較大的線性表預(yù)先分配存儲(chǔ)空間時(shí),必須按最大空間分配,造成內(nèi)存的無(wú)端浪費(fèi)；3表的容量難以擴(kuò)充；線性表的鏈或存儲(chǔ)結(jié)構(gòu)即能夠方便地進(jìn)行插入與刪除操作而不必移動(dòng)大量元素,配內(nèi)存,可以方便地?cái)U(kuò)充表空間。因此,這種存儲(chǔ)結(jié)構(gòu)是線性表的一種有效表示方法。且插入與刪除的算法結(jié)又無(wú)需預(yù)先分 21單鏈表 # 一、單鏈表的基本概念在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素的存儲(chǔ)空間一般是不連續(xù)的。為了能夠完整地表示線性表的邏輯結(jié)構(gòu)，每一個(gè)數(shù)據(jù)元素的表示必須由兩部分信息組成1數(shù)據(jù)元素的值；2數(shù)據(jù)元素在線性表中的邏輯位置；這兩部分信息構(gòu)成線性鏈表的一

33、個(gè)結(jié)點(diǎn)。因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表由若干個(gè)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)有兩個(gè)域：一個(gè)是數(shù)據(jù)域，用以存放數(shù)據(jù)元素的值；另一個(gè)是指針域，用以存放后件的存儲(chǔ)地址。人們一般借助于高級(jí)語(yǔ)言的“指針”數(shù)據(jù)類(lèi)型來(lái)描述這種數(shù)據(jù)結(jié)構(gòu)。TypePointer=Dnodetype；nodetype=recorddata：elementype；數(shù)據(jù)域next：pointer；指針域end；varhead：pointer；head為表的首指針，指向鏈表的第一個(gè)結(jié)點(diǎn)。有時(shí)在鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)在單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址可以任意分配，即表中元素的存儲(chǔ)位置可以不連續(xù)且是無(wú)序的，而它們的邏輯順序由鏈表中的中p指針指向

34、a的結(jié)點(diǎn)，則iDDdata=a.,pDDnextMnext指針確定：假設(shè)線性表pDDnext指針指向值為data=a。i+1aa采用單鏈表的存儲(chǔ)結(jié)構(gòu)，其1na的結(jié)點(diǎn)(pDDnextnil)。換句話說(shuō)i+1稱(chēng)為“哨兵”，head指向“哨兵”。整個(gè)鏈表的存取必須從head指針出發(fā)，沿每個(gè)結(jié)點(diǎn)的next指針順序進(jìn)行，最后一個(gè)結(jié)點(diǎn)的nnext指針為“空”(nil)。因此又稱(chēng)這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為單鏈表。例如存儲(chǔ)地址數(shù)據(jù)域指針域1li437qian1313sun119wangnil25wu37head31zhao73137zheng1943zhou25二、單鏈表的操作1、動(dòng)態(tài)建立單鏈表設(shè)線性表aa。試建立其

35、單鏈表的存儲(chǔ)結(jié)構(gòu)，其中1nProcedurecreat-Link(varhead：pointer)；beginheaddnil；fori：=ndownto1dobeginnew(p)；pDDdatada；ipDDnextdhead；headdp；end；fornew(p)；pDDnextdhead；headdp；end；creak_linkhead指向單鏈表的“哨兵”。建立一個(gè)空表生成一個(gè)值為a的結(jié)點(diǎn)i將新結(jié)點(diǎn)插入單鏈表第1個(gè)結(jié)點(diǎn)之前加“哨兵”2、插入操作在單鏈表的第i個(gè)結(jié)點(diǎn)前插入元素x。head為指向“哨兵”的首指針pocedureinsert_Link(x：elemenetype；i：in

36、teger；beginnew(s)；sDDdatadx；pdhead；jd0；while(pnil)and(ji-1)dobeginpdpDDnext；jdj+1；end；whileifpnilthenbeginsDDnextdpDDnext；pDDnextds；endthenelsewriteln(without)；end；insert_Linkvarhead：pointer）；生成值為x的結(jié)點(diǎn)p指向“哨兵”尋找單鏈表中第i1個(gè)結(jié)點(diǎn)第i1個(gè)結(jié)點(diǎn)后插入元素xi表長(zhǎng)3、刪除操作設(shè)head為指向“哨兵”的首指針。刪除單鏈表的第i個(gè)結(jié)點(diǎn)。Proceduredelet_Link(i：integre；v

37、arhead：pointer)；beginpdhead；jd0；while(pDDnextnil)and(ji1)dobeginpdpDDnext；jdj+1；end；whileifpDDnext=nilthenwriteln(without)elsebeginp指向“哨兵”尋找第i1ODOpi表長(zhǎng)刪除第iODOqqdpDDnext；pDDnextdpDDnextDDnext；dispose(q)；end；elseend；delet_Link4、讀取單鏈表元素設(shè)head為指向“哨兵”的首指針。讀取單鏈表中第i個(gè)數(shù)據(jù)元素。functionget_Link（i：integer；varhead：Po

38、inter）：elementype；beginpDheadDDnext；jD1；p指向表中第1個(gè)結(jié)點(diǎn)while(pnil)and(ji)do順next指針往后尋找第i個(gè)結(jié)點(diǎn)pbeginpDpDDnext；jDj+1；end；whileifp=nili表長(zhǎng)thenwriteln(without)elseget_LinkDpDDdata；取得表中第i個(gè)結(jié)點(diǎn)值end；get_Link三、單鏈表的應(yīng)用舉例2D2雙向循環(huán)鏈表以上討論的線性單鏈表的結(jié)點(diǎn)中，只有一個(gè)指示后件的指針域只能順next指針擴(kuò)后尋查其它結(jié)點(diǎn)。若要尋查某結(jié)點(diǎn)的直接前趨，則需從“哨兵”next。因此，從某結(jié)點(diǎn)出發(fā)，head出發(fā)，另外，對(duì)

39、于空表與第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使得空表與非空表的運(yùn)行不統(tǒng)一。為了克服單鏈表的這個(gè)缺點(diǎn)，我們引入了另一種鏈接方式雙向循環(huán)鏈表。一、雙向鏈表顧名思義，在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼（）；另一個(gè)指向直接前趨（），u述如下：Typedupointer=Dnode；node=recorddata：elementype；數(shù)據(jù)域priou，next：dupointer；前趨指針，后繼指針end；varda：dupointer；雙向鏈表的“哨兵”“哨兵”的priou域?yàn)榭眨╪il）,后繼指針next指向鏈表的第一個(gè)結(jié)點(diǎn)，data域?yàn)榭栈蛘咴O(shè)置特定的值。在雙向鏈表中插入或刪除結(jié)點(diǎn)，需同

40、時(shí)修改兩個(gè)方向的指針二、雙向循環(huán)鏈表所謂雙向循環(huán)鏈表，除了具備雙向鏈表的特征外，還具有下述特點(diǎn)：.雙向循環(huán)鏈表中，“哨兵”的域?yàn)槿我饣蛘吒鶕?jù)需要設(shè)置，域指向線性表的第一個(gè)結(jié)點(diǎn)，域指向線性表的最后一個(gè)結(jié)點(diǎn)，哨兵指針指向“哨兵”；.雙向循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的域指向“哨兵”，即在雙同循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)造了一個(gè)環(huán)狀鏈； # #顯然，雙向循環(huán)鏈表的定義與雙向鏈表一致。對(duì)雙向循環(huán)鏈表來(lái)說(shuō)，有如下幾種操作：1、構(gòu)造雙向循環(huán)鏈表lala為雙向循環(huán)假設(shè)線性表中有n個(gè)數(shù)據(jù)元素a,a。試建立其雙向循環(huán)鏈表存貯結(jié)構(gòu)，1n鏈表的哨兵：procedurecreat_dulist(varla：dupointer

41、)；begin建立空表建立雙向循環(huán)鏈表new(la)；laDDnextdla；laDDpriouDla；qDla；fori：=1tondobeginnew(p)；pDDdataDa；qDDnextDp；ipDDpriouDq；qDp；end；for qDDnextUla；laDDpriouUend；creat_dulistq；首尾相接叮讀取雙向循環(huán)鏈表中第i個(gè)結(jié)點(diǎn)的地址在la為“哨兵”的雙向循環(huán)鏈表中，確定第長(zhǎng)皿，則返回哨兵指針la：functionget_dulist（i，la）：beginpUlaDDnext；jU1；while（pla）and（ji）dobeginpUpDDnext；if

42、i個(gè)結(jié)點(diǎn)的地址。若dupointer；end；j=ithenget_dulistUelseget_dulistUget_dulistpnil；i表長(zhǎng)，返回nil；若i=03、插入操作雙向循環(huán)鏈表的哨兵指針為從第叮結(jié)點(diǎn)開(kāi)始搜索jUj+1；end；whilex：procedureinsert_dulist(x：elementype；i：integer；varla：dupointer)；beginla。在該鏈表的第i個(gè)元素之前插入元素生成新結(jié)點(diǎn)new(s)；sDDdataUx；pUqet_dulist(i,la)；ifpnilthenbegins,尋找雙向循環(huán)鏈表中的第i個(gè)結(jié)點(diǎn)pend；pDDpri

43、ouDDnextUs；在結(jié)點(diǎn)p前插入結(jié)點(diǎn)sDDpriouUpDDpriou；pDDpriouUs；sDDnextUp；end；thenselsewritein(without)；insert_dulist4、刪除操作雙向循環(huán)鏈表的哨兵為la。刪除該鏈表中的第proceduredelet_dulist(i：integer；beginpUget_dulist(i，la)；ifpnilthenbeginpDDpriouDDnextUpDDnext；pDDendelsewriteln(without)；end；delet_dulisti個(gè)結(jié)點(diǎn)varla：qdupointer)；尋找雙向循環(huán)鏈表中的第i

44、個(gè)結(jié)點(diǎn)ppnextDDpriouUpDDpriou；disPose(p)；從雙向循環(huán)鏈表中刪除結(jié)點(diǎn)三雙向循環(huán)鏈表的應(yīng)用實(shí)例1.在帶尾指針（鏈表指針clist指向尾結(jié)點(diǎn)）的非空循環(huán)單鏈表中每個(gè)結(jié)點(diǎn)都以next字段的指針 指向下一個(gè)節(jié)點(diǎn)。假定其中已經(jīng)有2個(gè)以上的結(jié)點(diǎn)。下面哪些說(shuō)法是正確的：A）如果p指向一個(gè)待插入的新結(jié)點(diǎn)，在頭部插入一個(gè)元素的語(yǔ)句序列為：pnext:=clistnext;clistnext:=p;B）如果p指向一個(gè)待插入的新結(jié)點(diǎn)，在尾部插入一個(gè)元素的語(yǔ)句序列為：pA.next:=clist;clistA.next:=p;C）在頭部刪除一個(gè)結(jié)點(diǎn)的語(yǔ)句序列為：p:=clistA.nex

45、t;clistA.next:=clistA.nextA.next;dispose（p）;D）在尾部刪除一個(gè)結(jié)點(diǎn)的語(yǔ)句序列為。p:=clist;clist:=clistA.next;dispose（p）;第三章非線性結(jié)構(gòu)（1）樹(shù)前兩章討論的線性表（包括棧、隊(duì)列、與串）屬于線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，不管其存儲(chǔ)方式如何，數(shù)據(jù)元素的邏輯位置之間呈線性關(guān)系，每一個(gè)數(shù)據(jù)元素通常只有一個(gè)前件（除第一個(gè)元素外）和一個(gè)后件（除最后一個(gè)元素外）。在實(shí)際生活中，可以用線性結(jié)構(gòu)描述數(shù)據(jù)元素之間邏輯關(guān)系的問(wèn)題是很廣泛的，但也有很多問(wèn)題不能依靠線性結(jié)構(gòu)來(lái)解決，因此在這類(lèi)問(wèn)題中，數(shù)據(jù)元素間的邏輯關(guān)系不能用線性結(jié)構(gòu)明確、方便地

46、描述出來(lái)。例如某學(xué)校試圖將學(xué)生成績(jī)表中的百分制成績(jī)轉(zhuǎn)換成五個(gè)等級(jí)，其中成績(jī)0D59分為不及格，60D69分為及格，70D79分為中，如何將他們的成績(jī)轉(zhuǎn)換成五級(jí)分制。一張簡(jiǎn)單的表，已經(jīng)不能用線性結(jié)構(gòu)來(lái)表示。80D89分為良，90D100分為優(yōu)。現(xiàn)有n個(gè)學(xué)生的百分制成績(jī)，（圖31）揭示了一個(gè)百分制成績(jī)的判定轉(zhuǎn)換過(guò)程。對(duì)于這樣因?yàn)楸碇袛?shù)據(jù)元素可能有兩個(gè)后件，它們之間的關(guān)系已經(jīng)不是線性的了。 # #3至少存在一個(gè)結(jié)點(diǎn)（數(shù)據(jù)元素）有多于一個(gè)前件或后件的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為非線性結(jié)構(gòu)。（圖1）中所示的表是一個(gè)非線性結(jié)構(gòu)。由該圖可以看出，雖然每一個(gè)結(jié)點(diǎn)可能有多個(gè)后件，但它們的前件卻只有一個(gè)（第一個(gè)結(jié)點(diǎn)無(wú)前件）。這種

47、非線性結(jié)構(gòu)稱(chēng)為樹(shù)，樹(shù)表示了數(shù)據(jù)元素之間的層次關(guān)系，而這種層次關(guān)系仿佛像一棵倒長(zhǎng)的樹(shù)。下面討論樹(shù)的基本概念，其中重點(diǎn)討論的是二叉樹(shù)。 31樹(shù)的基本概念及其存儲(chǔ)結(jié)構(gòu)一、樹(shù)的概念樹(shù)是一種常見(jiàn)的非線性的數(shù)據(jù)結(jié)構(gòu)。樹(shù)的遞歸定義如下：樹(shù)是n（nO）個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件：有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前件（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱(chēng)為樹(shù)的根；除根外，其余的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前件；除根外，每一個(gè)結(jié)點(diǎn)都通過(guò)唯一的路徑連到根上。這條路徑由根開(kāi)始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后件（兒子結(jié)點(diǎn)）由上述定義可知，樹(shù)結(jié)構(gòu)沒(méi)有封閉的回路。 # #其中除根結(jié)點(diǎn)外，有后件的結(jié)點(diǎn)（圖3D1

48、1（b）中，r為根起點(diǎn)，w，h，e，f，s，m，o,n,j,u為葉結(jié)點(diǎn)；從根r到結(jié)點(diǎn)的唯一路徑為rcti。一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱(chēng)為該結(jié)點(diǎn)的度。在（圖311（b）中，結(jié)點(diǎn)i度為3,結(jié)點(diǎn)t的度為2,結(jié)點(diǎn)b的度為1。顯然,所有樹(shù)葉的度為0。所有結(jié)點(diǎn)中最大的度稱(chēng)為該樹(shù)的度。(圖3D11（b）中的樹(shù)的度為3。在樹(shù)中，一個(gè)結(jié)點(diǎn)包含一個(gè)元素以及所有指向其子樹(shù)的分支，稱(chēng)為分支結(jié)點(diǎn)。而沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為樹(shù)葉。由樹(shù)的定義可知，樹(shù)葉本身也是其父結(jié)點(diǎn)的子樹(shù)。如 #樹(shù)是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層,根的后件在第二層,其余各層依次類(lèi)推。即若某個(gè)結(jié)點(diǎn)在第k層，則該結(jié)點(diǎn)的后件均處在第k+1層。（圖311

49、(b)中的 #樹(shù)共有五層。在樹(shù)中,父結(jié)點(diǎn)在同一層的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系。樹(shù)中最大的層次稱(chēng)為樹(shù)的深度,亦稱(chēng)高度。（圖3D11（b）中樹(shù)的深度為5。 3D1（b）去掉根結(jié)點(diǎn)r,其原來(lái)的三所謂森林,是指若干棵互不相交的樹(shù)的集合。如（圖棵子樹(shù)T,T,T的集合T,T,T就為森林。abcabc所謂有序樹(shù)是指樹(shù)中同層結(jié)點(diǎn)從左而右排列,其次序不容互換,這樣的樹(shù)稱(chēng)為有序樹(shù)。二、樹(shù)的表示方法和存儲(chǔ)結(jié)構(gòu) # #樹(shù)的表示方法很多。例如（圖示法：先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中,3D11）采用的就是自然界的樹(shù)形表示法,常用的還有括號(hào)表然后把它的子樹(shù)按由左而右的順序放入括號(hào)中,而對(duì)子樹(shù)也采 用同樣方法處理：同層子樹(shù)之間用逗號(hào)隔

50、開(kāi)，最后用閉括號(hào)括起來(lái)。同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，ODD3D11（b）可寫(xiě)成如下形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）所n（n為樹(shù)的度）個(gè)指而樹(shù)的存儲(chǔ)結(jié)構(gòu)有多種，其中使用較多的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于樹(shù)中結(jié)點(diǎn)可以有多個(gè)元素，以可以用多重鏈表來(lái)描述比較方便。所謂多重鏈表，就是每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和針域共n+1個(gè)域組成，其表示方法如下：Constnl的度；Type例如DDtreetype=Dnode；node=recorddata：datatype；next：array1Dnoftreetype；end；結(jié)點(diǎn)類(lèi)型數(shù)據(jù)域指向各兒子的指針域Varro

51、ot：treetype；3D11（b）的樹(shù)，其多重鏈表為根結(jié)點(diǎn)指針顯然，取樹(shù)的度作為每個(gè)結(jié)點(diǎn)的鏈域數(shù)（即指向兒子結(jié)點(diǎn)的指針數(shù)造成存儲(chǔ)空間的大量浪費(fèi)。因?yàn)榭赡苡泻芏嘟Y(jié)點(diǎn)中存在空鏈域。容易驗(yàn)證，為K的樹(shù)中必存在n*（k1）+1個(gè)空鏈域，因此需要尋找一種恰當(dāng)?shù)臉?shù)形式，相同、又要盡可能減少存儲(chǔ)空間的浪費(fèi)，方便運(yùn)算。下面將要看到，用二叉樹(shù)來(lái)表示樹(shù)，就能達(dá)到這個(gè)目的。）雖使各種算法簡(jiǎn)化，但會(huì)一棵具有n個(gè)結(jié)點(diǎn)且度即要使每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)一、二叉樹(shù)的基本概念和基本性質(zhì)3D2二叉樹(shù)1、二叉樹(shù)的基本概念二叉樹(shù)是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)后件，右之分D次序不能任意顛倒）。下面給出二叉樹(shù)的遞

52、歸定義：二叉樹(shù)是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件：有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為根；余下的結(jié)點(diǎn)分為互不相交的子集L和R,其中R是根的左子樹(shù)；且其子樹(shù)有左L是根的右子樹(shù)；L和R又是二叉樹(shù)； 由上述定義可以看出，二叉樹(shù)和樹(shù)是兩個(gè)不同的概念：樹(shù)的每一個(gè)結(jié)點(diǎn)可以有任意多個(gè)后件，且子樹(shù)可以不分次序（除有序樹(shù)外）；而二叉樹(shù)中每個(gè)結(jié)點(diǎn)的后件不能超過(guò)2且子樹(shù)有左右之分。我們稱(chēng)二叉樹(shù)中結(jié)點(diǎn)的左后件為左兒子，右后件為右兒子。前面引入的有關(guān)樹(shù)的一些基本術(shù)語(yǔ)對(duì)二叉樹(shù)仍然適用。（圖321）列出二叉樹(shù)的五種基本形態(tài)：滿二叉樹(shù)和完全二叉樹(shù)是二叉樹(shù)的兩個(gè)特殊形態(tài)：滿二叉樹(shù)：如果一棵二叉樹(shù)的任何結(jié)點(diǎn)，或者是樹(shù)葉，或者恰

53、有兩棵非空子樹(shù)，則此二叉樹(shù)稱(chēng)作滿二叉樹(shù)。（例如圖（3D22（a）可以驗(yàn)證具有個(gè)結(jié)點(diǎn)。完全二叉樹(shù)：如果一棵二叉樹(shù)最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于n個(gè)葉結(jié)點(diǎn)的滿二叉樹(shù)共有2，并且最下面一層的結(jié)點(diǎn)2n-1都集中在該層最左邊的若干位置上，則稱(chēng)此二叉樹(shù)為完全二叉樹(shù)（例如（圖2（b）3D22、二叉樹(shù)的基本性質(zhì)下面介紹地叉樹(shù)的三個(gè)主要性質(zhì)性質(zhì)1：在二叉樹(shù)的第iDD1）層上，最多有2i個(gè)結(jié)點(diǎn) #證明數(shù)學(xué)歸納法i=1時(shí)只有一個(gè)根結(jié)點(diǎn)，即2i=2o=1,結(jié)論成立； #假設(shè)第k（i=k）層上最多有2k-i個(gè)結(jié)點(diǎn);考慮i=k+1。由歸納假設(shè)，在二叉樹(shù)第k層上最多有2k-i個(gè)結(jié)點(diǎn)，而每一個(gè)結(jié)點(diǎn)的度數(shù)最大為2，因此在第

54、k+1層上最多有2D2k-i=2（k+i）-i=2i,結(jié)論成立。綜上所述，性質(zhì)1成立。性質(zhì)2：在深度為k（kD1）的二叉樹(shù)中最多有2k-1個(gè)結(jié)點(diǎn)。證明由性質(zhì)1，在二叉樹(shù)第i層上最多有2i個(gè)結(jié)點(diǎn)，因此深度為k的二叉樹(shù)最多有 # #2二2k一1個(gè)結(jié)點(diǎn)。i=i 性質(zhì)3：在任何二叉樹(shù)中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。證明設(shè)n二叉樹(shù)的葉結(jié)點(diǎn)數(shù)；n二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)；01數(shù)；n=n+n+n（1）012由于二叉樹(shù)中除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)分支進(jìn)入。設(shè)n二叉樹(shù)中度為2的結(jié)點(diǎn)2B為進(jìn)入分支的總數(shù)，因此n=B+1又由于所有的進(jìn)入分支是由度為1和度為將（3）代入（比較（1）和（即葉子數(shù)比度為B

55、=n+2n122)得出n=n+2n+1124)，得出n=n+1022的結(jié)點(diǎn)數(shù)多1（2）2的結(jié)點(diǎn)射出的，因此又有（3）（4）二、樹(shù)或森林轉(zhuǎn)換成二叉樹(shù)1、普通有序樹(shù)轉(zhuǎn)換成二叉樹(shù)我們?cè)?1中曾講過(guò)，在用多重鏈表示普通樹(shù)時(shí)，會(huì)浪費(fèi)存儲(chǔ)空間。另外，由于樹(shù)中各結(jié)點(diǎn)的度各不相同，因此對(duì)樹(shù)中各結(jié)點(diǎn)的搜索比較困難。在實(shí)際應(yīng)用中，往往將普通樹(shù)轉(zhuǎn)化成二叉樹(shù)，這種處理是極其有利的。假設(shè)所討論的普通樹(shù)為有序樹(shù)T,則將其轉(zhuǎn)化成二叉樹(shù)T的規(guī)則如下：T中的結(jié)點(diǎn)與T中的結(jié)點(diǎn)一一對(duì)應(yīng)；T中某結(jié)點(diǎn)N的第一個(gè)兒子結(jié)點(diǎn)為N,則在1T中N為對(duì)應(yīng)結(jié)點(diǎn)N的左兒子結(jié)點(diǎn)；1T中某結(jié)點(diǎn)N的第一個(gè)兒子結(jié)點(diǎn)N以后的其它子結(jié)點(diǎn)，在1T中被依次鏈接成一串

56、開(kāi)始于的右兒子結(jié)點(diǎn)；由上述轉(zhuǎn)化規(guī)則可以看出，一棵有序樹(shù)轉(zhuǎn)化成二叉樹(shù)的根結(jié)點(diǎn)是沒(méi)有右子樹(shù)的，并且除保留每個(gè)結(jié)點(diǎn)的最左分支外，其余分支應(yīng)去掉，將（圖323（a）所示的普通有序樹(shù)轉(zhuǎn)換成二叉樹(shù)然后從最左的兒子開(kāi)始依次連接該結(jié)點(diǎn)的全部?jī)鹤?。（圖323（b）例如(3.2-3) # 2、森林轉(zhuǎn)換為二叉樹(shù)設(shè)森林F=T,T由m棵互不相交的普遍有序樹(shù)組成。我們可以按下述規(guī)則將森林F轉(zhuǎn)換成一1m棵二叉樹(shù)B=root，LB，RB:若FOODm=O）,則BDOD；若FOODmD0),則B的根root即為森林中第一棵樹(shù)的根root(T“B的左子樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林F=T,T,T轉(zhuǎn)換而成的二叉樹(shù)；其右子樹(shù)RB是從森林111

57、121kT,T轉(zhuǎn)換成的二叉樹(shù)。3mLB是從T1F=T，22例如 # #由此可見(jiàn)，森林轉(zhuǎn)換成二叉樹(shù)的方法為將各棵樹(shù)的根相連；將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)；以第一棵樹(shù)為軸心，順時(shí)針粗略地旋轉(zhuǎn)9Oo；三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有兩種形式1、順序存儲(chǔ)結(jié)構(gòu)編號(hào)的方法是從根結(jié)點(diǎn)開(kāi)始編將每個(gè)結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號(hào)，號(hào)1，然后由左而右進(jìn)行連續(xù)編號(hào)。每個(gè)結(jié)點(diǎn)的信息包括數(shù)據(jù)值：data父結(jié)點(diǎn)編號(hào)：prt左兒子結(jié)點(diǎn)編號(hào)：lch右兒子結(jié)點(diǎn)編號(hào)：rch滿二叉樹(shù)和完全二叉樹(shù)一般采用順序存儲(chǔ)結(jié)構(gòu)Constm二樹(shù)中結(jié)點(diǎn)數(shù)上限；Typenode=recorddata：datatype；

58、prt,lch,rch：ODm；end；treetype=array1Dmofnode；VarTree：treetype；結(jié)點(diǎn)類(lèi)型數(shù)據(jù)值父結(jié)點(diǎn)、左兒子、右兒子編號(hào)二叉樹(shù)的順序表類(lèi)型二叉樹(shù) # 例如采用數(shù)組tree存儲(chǔ)二叉樹(shù) (a)(b)(圖3.2-5)下面我們將普通有序樹(shù)轉(zhuǎn)換成二叉樹(shù)，并使用順序存儲(chǔ)結(jié)構(gòu)入信息含n行，其中第i行（1DiDn）的元素依次為結(jié)點(diǎn)i的數(shù)據(jù)值a。以后各元素為結(jié)點(diǎn)i的兒子序列，以i結(jié)點(diǎn)i為葉子。例如（圖3DDDDDDD）的多叉樹(shù)對(duì)應(yīng)的輸入信息為r2340a560b70c89100w0 x11120f0s0t13140u0d150e0i1617180j0h0m0o0h0轉(zhuǎn)換

59、過(guò)程如下：fillchar（tree，sizeof（tree），0）；iD1；whileiDndobegin讀結(jié)點(diǎn)i的數(shù)據(jù)值ai；treeiDdataDai；讀結(jié)點(diǎn)i的第一個(gè)兒子序號(hào)j；ifj0thenbegintreeiDlchDj；treejDprtDi；pDj；Tree存儲(chǔ)轉(zhuǎn)換結(jié)果。普通有序樹(shù)的輸0結(jié)束。若a后僅含一個(gè)0，則說(shuō)明i二叉樹(shù)初始化從結(jié)點(diǎn)1開(kāi)始輸入若多叉樹(shù)信息末輸入處理完,則重復(fù)若結(jié)點(diǎn)j非葉子結(jié)點(diǎn)j作為結(jié)點(diǎn)i的左兒子從結(jié)點(diǎn)j出發(fā)轉(zhuǎn)換其它兄弟結(jié)點(diǎn) repeat讀結(jié)點(diǎn)i的下一個(gè)兒子序號(hào)ifj0thenbegintreeprchDj；treejprtDp；pDj；end；thenj；

60、untilj=0；end；theni+1；換行；while3DDDDDDDdataiDend；例如（圖結(jié)點(diǎn)j作為結(jié)點(diǎn)p的右兒子直至處理完結(jié)點(diǎn)i的所有兒子信息準(zhǔn)備輸入結(jié)點(diǎn)i+1的兒子信息tree數(shù)組如下：123456789101112131415161718r，020a153b，274c，380w，206X，5110f,300s，409t，81310u，900d，61512e，1100i，91614j，1300h，1100m，130170，16018n，1700）的多叉樹(shù)經(jīng)上述轉(zhuǎn)換運(yùn)算后得出的prtlchrch2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹(shù)，通常采用鏈?zhǔn)椒峙?，即用二重鏈表表示一般的二叉?shù)。這種