數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率

1、數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率從IOI98試題PICTURE談起- PAGE 36 -IOI99中國集訓(xùn)隊優(yōu)秀論文選IOI99中國集訓(xùn)隊優(yōu)秀論文選- PAGE 35 -IOI99中國集訓(xùn)隊優(yōu)秀論文選- PAGE 21 -數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇與算法法效率從IIOI998試題題PICCTURRE談起起 【關(guān)鍵字字】數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇 線性結(jié)結(jié)構(gòu) 樹形形結(jié)構(gòu)【摘要】算法 + 數(shù)據(jù)據(jù)結(jié)構(gòu)=程序。設(shè)計算算法與選選擇合適適的數(shù)據(jù)據(jù)結(jié)構(gòu)是是程序設(shè)設(shè)計中相相輔相成成的兩方方面，缺缺一不可可。數(shù)據(jù)據(jù)結(jié)構(gòu)的的選擇一一直是程程序設(shè)計計中的重重點、難難點，正正確地應(yīng)應(yīng)用數(shù)據(jù)據(jù)結(jié)構(gòu)，往往能能帶來意意想不到到的效果果。反之之，如

2、果果忽視了了數(shù)據(jù)結(jié)結(jié)構(gòu)的重重要性，對某些些問題有有時就得得不到滿滿意的解解答。通通過對IIOI998試題題Piccturre的深深入討論論，我們們可以看看到兩種種不同的的數(shù)據(jù)結(jié)結(jié)構(gòu)在解解題中的的應(yīng)用，以及由由此得到到的不同同的算法法效率。本文以以Piccturre問題題為例，探討數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇對算法法效率的的影響?！菊摹恳运惴ㄍǔ３Ｊ菦Q定定程序效效率的關(guān)關(guān)鍵，但但一切算算法最終終都要在在相應(yīng)的的數(shù)據(jù)結(jié)結(jié)構(gòu)上實實現(xiàn)，許許多算法法的精髓髓就是在在于選擇擇了合適適的數(shù)據(jù)據(jù)結(jié)構(gòu)作作為基礎(chǔ)礎(chǔ)。在程程序設(shè)計計中，不不但要注注重算法法設(shè)計，也要正正確地選選擇數(shù)據(jù)據(jù)結(jié)構(gòu)，這樣往往往能夠夠事半功功倍。

3、在算法時時間與空空間效率率的兩方方面，著著重分析析時間效效率，即即算法的的時間復(fù)復(fù)雜度，因為我我們總是是希望程程序在較較短的時時間內(nèi)給給出我們們所希望望的輸出出。如果果在空間間上過于于“吝嗇嗇”而使使得時間間上無法法承受，對解題題并無益益處。本文對IIOI998的試試題Piictuure作作一些分分析，通通過兩種種不同數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇，將了了解到數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)對算法法本身及及算法效效率的影影響。Pictturee問題及及算法設(shè)設(shè)計Pictturee問題Pictturee問題是是IOII98的一一道試題題，描述述如下：墻上貼著著一些海海報、照照片等矩矩形，所所有的邊邊都為垂垂直或水水平。每每個

4、矩形形可以被被其它矩矩形部分分或完全全遮蓋，所有矩矩形合并并成區(qū)域域的邊界界周長稱稱為輪廓廓周長。例如圖11的三個個矩形輪輪廓周長長為300： 圖1要求編寫寫程序計計算輪廓廓周長。數(shù)據(jù)量限限制：0矩形形數(shù)目 11)的一一般區(qū)間間。一般般情況下下，線段段樹的結(jié)結(jié)點類型型定義如如下： TyypeLinees_TTreee = Objjectt i, j : inttegeer; 結(jié)點表表示的區(qū)區(qū)間的頂頂點標號號I, J coountt : iinteegerr; 覆蓋這這一結(jié)點點的區(qū)間間數(shù) leeftcchilld, riighttchiild : Linnes_Treee; 二叉叉樹的兩兩個子結(jié)

5、結(jié)點end關(guān)于Liiness_Trree的的其它數(shù)數(shù)據(jù)域與與定義的的運算將將陸續(xù)添添加。圖圖8是一棵棵線段樹樹，描述述的區(qū)間間端點可可以有110種取取值。其其中記錄錄著一個個區(qū)間3，6，它它用紅色色的33，5及5，6的并并采表示示。圖中中紅色結(jié)結(jié)點的ccounnt域值值為1，黑色色結(jié)點的的couunt域域值為00。圖8直觀地看看，子結(jié)結(jié)點就是是父結(jié)點點區(qū)間平平均分成成兩部分分。設(shè)LL, RR是父結(jié)結(jié)點的區(qū)區(qū)間端點點，我們們可以增增加Liiness_Trree.Buiild(l, r : inntegger)遞歸地地定義線線段樹如如下:Procceduure Liiness_trree.Buii

6、ld(l, r : inttegeer)I ll 左端點點J rr 右端端點Counnt 00 初始化化If r - l 1 是否否需要生生成子結(jié)結(jié)點，若若r-ll=1則則是初等等區(qū)間 thhen kk (ll + rr) 平均分分為兩部部分 nnew(lefftchhildd) llefttchiild.Buuildd(l, k) 建建立左子子樹 nnew(rigghtcchilld) rrighhtchhildd.Buuildd(k, r) 建立立右子樹樹 ellse llefttchiild nill riighttchiild nill設(shè)根結(jié)點點是Rooot，建樹需需要執(zhí)行行Rooot

7、.BBuilld。由遞歸定定義看出出，線段段樹是一一棵平衡衡樹，高高度為loggN。建立立整棵樹樹需要的的時間為為O(NN)。以上著重重說明了了線段樹樹的存儲儲原理，我們還還應(yīng)建立立線段樹樹的基本本運算。線段樹可可以存儲儲多個區(qū)區(qū)間，所所以支持持區(qū)間插插入運算算Linnes_Treee.IInseert(l, r : inntegger)，定義義如下：Procceduure Liiness_Trree.Inssertt(l, r : inntegger) l, rr是待待插入?yún)^(qū)區(qū)間，ll、r都是原原始頂點點坐標if (l = aai) andd (aj = rr) thhen coountt

8、coountt + 11 蓋滿整整個結(jié)點點區(qū)間 ellse iff ll aa(ii + jj) ddiv 2 是否否能覆蓋蓋到右孩孩子結(jié)點點區(qū)間 theen rigghtcchilld.Innserrt(ll, r) 向向右孩子子插入類似地，線段樹樹支持區(qū)區(qū)間的刪刪除Liiness_Trree.Delletee(l, r : iinteegerr)，定定義如下下：Procceduure Liiness_Trree.Delletee(l, r : inntegger) l, rr是待待刪除區(qū)區(qū)間，ll、r都是原原始頂點點坐標if (l = aai) andd (aj = rr) thhen c

9、oountt coountt - 11 蓋滿整整個結(jié)點點區(qū)間 ellse iff ll aa(ii + jj) divv 22 是否否能覆蓋蓋到右孩孩子結(jié)點點區(qū)間 theen rigghtcchilld.Deelette(ll, rr) 向右右孩子刪刪除執(zhí)行Liiness_Trree.Delletee(l, r : iinteegerr) 的先決決條件是是區(qū)間l, r曾曾被插入入且還未未刪除。如果建建樹后插插入?yún)^(qū)間間2，5而刪刪除區(qū)間間3，4是非非法的。通過分析析插入與與刪除的的路徑，可知LLinees_TTreee.Innserrt與Linnes_Treee.DDeleete的的時間復(fù)復(fù)雜度

10、均均為O(loggN)。(詳見附錄1)由于線段段樹給每每一個區(qū)區(qū)間都分分配了結(jié)結(jié)點，利利用線段段樹可以以求區(qū)間間并后的的測度與與區(qū)間并并后的連連續(xù)段數(shù)數(shù)。測度由于線段段樹結(jié)構(gòu)構(gòu)遞歸定定義，其其測度也也可以遞遞歸定義義。增加加數(shù)據(jù)域域Linnes_Treee.MM表示以以該結(jié)點點為根的的子樹的的測度。M取值如如下： aaj aii 該結(jié)點點Couunt0M = 0 該結(jié)點點為葉結(jié)結(jié)點且CCounnt=00 LLefttchiild.M + RRighhtchhildd.M 該結(jié)點點為內(nèi)部部結(jié)點且且Couunt=0據(jù)此，可可以用LLinees_TTreee.UppDatta來動動態(tài)地維維護Liin

11、ess_Trree.M。UpDDataa在每一一次執(zhí)行行Inssertt或Delletee之后執(zhí)執(zhí)行。定定義如下下：Procceduure Liiness_Trree.UpDDataaif couunt 0 thhen M ajj i 蓋滿區(qū)區(qū)間，測測度為aaj aii ellse iff jj - ii = 11 是否否葉結(jié)點點 theen M 00 該結(jié)點點是葉結(jié)結(jié)點 elsse M LLefttchiild.M + Riighttchiild.M 內(nèi)部結(jié)結(jié)點UpDaata的的復(fù)雜度度為O(1)，則用UUpDaata來來動態(tài)維維護測度度后執(zhí)行行根結(jié)點點的Innserrt與Delletee的

12、復(fù)雜雜度仍為為O(llogNN)。連續(xù)段數(shù)數(shù)這里的連連續(xù)段數(shù)數(shù)指的是是區(qū)間的的并可以以分解為為多少個個獨立的的區(qū)間。如11，22，335，6可以以分解為為兩個區(qū)區(qū)間11，3與5，6，則則連續(xù)段段數(shù)為22。增加加一個數(shù)數(shù)據(jù)域LLinees_TTreee.liine表表示該結(jié)結(jié)點的連連續(xù)段數(shù)數(shù)。Liine的的討論比比較復(fù)雜雜，內(nèi)部部結(jié)點不不能簡單單地將左左右孩子子的Liine相相加。所所以再增增加Liiness_Trree.lbdd與Linnes_Treee.rrbd域域。定義義如下： 11 左端端點I被描述述區(qū)間蓋蓋到lbd = 00 左端點點I不被描描述區(qū)間間蓋到 11 右右端點JJ被描述述區(qū)

13、間蓋蓋到rbd = 00 右端端點J不被描描述區(qū)間間蓋到lbd與與rbdd的實現(xiàn)現(xiàn)： 1 該結(jié)點點couunt 00lbd = 0 該結(jié)點點是葉結(jié)結(jié)點且ccounnt = 0 lefftchhildd.lbbd 該該結(jié)點是是內(nèi)部結(jié)結(jié)點且CCounnt=00 1 該結(jié)點點couunt 00rbd = 0 該結(jié)點點是葉結(jié)結(jié)點且ccounnt = 0 rigghtcchilld.rbbd 該結(jié)結(jié)點是內(nèi)內(nèi)部結(jié)點點且Coountt=0有了lbbd與rbdd，Linne域就就可以定定義了： 1 該結(jié)結(jié)點coountt 0Linee = 00 該該結(jié)點是是葉結(jié)點點且coountt = 0 Lefftchhi

14、ldd.Liine + Riighttchiild.Liine - 1 當該結(jié)結(jié)點是內(nèi)內(nèi)部結(jié)點點且Coountt=0，Lefftchhildd.rbbd = 1且且Rigghtcchilld.lbbd = 1 LLefttchiild.Liine + Riighttchiild.Liine 當該該結(jié)點是是內(nèi)部結(jié)結(jié)點且CCounnt=00，Lefftchhildd.rbbd與Rigghtcchilld.lbbd不都都為1據(jù)此，可可以定義義UpDDataa動態(tài)態(tài)地維護護Linne域。與UppDatta相似似，UppDatta也也在每一一次執(zhí)行行Inssertt或Delletee后執(zhí)行行。定義義如下

15、：Procceduure Liiness_Trree.UpDDataaif couunt 0 是否蓋蓋滿結(jié)點點表示的的區(qū)間 thhen lbbd 1 rbdd 1 Linne 11 ellse iff j - i = 1 是否否為葉結(jié)結(jié)點 theen lbdd 00 進行行到這一一步，如如果為葉葉結(jié)點， couunt = 00 rbdd 0 linne 00 elsse linne Lefftchhildd.liine + Riighttchiild.liine - LLefttchiild.rbbd * Riighttchiild.lbbd 用乘法法確定LLefttchiild.rbbd與R

16、igghtcchilld.lbbd是否否同時為為1同時，由由于增加加了Liine、M等幾個個數(shù)據(jù)域域，在建建樹Liiness_Trree.Buiild時時要將新新增的域域初始化化。至此，線線段樹構(gòu)構(gòu)造完畢畢，完整整的線段段樹定義義如下：Linees_TTreee = objjectt i, j : inntegger; coountt : inntegger; liine : inntegger; lbbd, rbdd : bbytee; m : iinteegerr; leeftcchilld, riighttchiild : Linnes_treee; prroceedurre Buiil

17、d(l, r : inntegger); prroceedurre Inssertt(l, r : iinteegerr); prroceedurre Delletee(l, r : iinteegerr); prroceedurre UpDDataa; prroceedurre UpDDataa;end有了線段段樹這個個工具，可以考考慮利用用樹形結(jié)結(jié)構(gòu)來描描述一組組超元線線段的狀狀態(tài)。Pictturee問題的的數(shù)據(jù)結(jié)結(jié)構(gòu)選擇擇之二：樹形結(jié)結(jié)構(gòu)采用線性性結(jié)構(gòu)描描述一組組超元線線段的狀狀態(tài)并不不能帶來來太高的的效率，其中主主要原因因是各組組超元線線段聯(lián)系系不緊。如圖99所示，超元線線段CDD與E

18、F被矩矩形AGGHB遮遮蓋，不不屬于輪輪廓；而而與之相相鄰DDD與FF則“擺擺脫”了了矩形的的遮蓋，屬于輪輪廓的一一部分。 圖9 圖圖10由此類推推，可以以看出相相鄰的超超元線段段組都有有類似的的問題。如圖99，DD與FF不被遮遮蓋，可可以這樣樣分析：從左往往右，CCD、EF首先先被遮蓋蓋，但隨隨著BFF的出現(xiàn)現(xiàn)，對DDD、FF的遮蓋蓋自然消消失。這這一點，正是相相鄰超元元線段組組的內(nèi)在在聯(lián)系。用線性性結(jié)構(gòu)無無法表示示出這一一聯(lián)系，因為各各組的累累計掃描描過程是是獨立的的?，F(xiàn)在在我們用用樹形結(jié)結(jié)構(gòu)來表表示將較較好地解解決這一一問題，因為線線段樹支支持插入入與刪除除及動態(tài)態(tài)維護，可以有有機聯(lián)系系

19、各組超超元線段段的狀態(tài)態(tài)。我們們把“從從左往右右”當作作一個掃掃描的過過程，若若將其嚴嚴格地描描述，可可以得到到一個稱稱為線段段掃描的的過程：設(shè)立掃描描線段LL。L從左往往右掃描描，停留留在每一一超元線線段組上上。如圖圖10所示示。L的狀態(tài)態(tài)用線段段樹來表表示，每每一條縱縱向的矩矩形邊看看作一個個待合并并區(qū)間。線段樹樹的連續(xù)續(xù)段數(shù)*2表示示該組超超元線段段屬于輪輪廓的線線段數(shù)目目。如圖圖10，L的狀態(tài)態(tài)首先是是G,AAE,C，連續(xù)線線段數(shù)是是1，所以以1*22=2是是該組超超元線段段屬于輪輪廓的數(shù)數(shù)目。接接著L進一步步掃描，狀態(tài)改改變?yōu)镋,CC, 連續(xù)線線段數(shù)是是1，所以以該組超超元線段段屬于

20、輪輪廓的數(shù)數(shù)目也是是1*22=2。這樣，上文所所說的“超元線線段樹”就用線線段樹來來實現(xiàn)。為了統(tǒng)統(tǒng)一起見見，以后后仍稱線線段樹。掃描過程程中動態(tài)態(tài)地維護護L的狀態(tài)態(tài)。參看看圖100，L狀態(tài)的的轉(zhuǎn)換是是在線段段樹中刪刪去區(qū)間間H,BB即G,A造造成的。歸納一一下，有有以下結(jié)結(jié)論：L初始化化為空，即線段段樹剛建建好時的的情形。掃描時，遇到矩矩形左邊邊，將其其插入（Inssertt）線段段樹。掃描時，遇到矩矩形右邊邊，將其其從線段段樹中刪刪除（DDeleete）。由于于從左往往右掃描描，事先先插入了了該矩形形的左邊邊，所以以刪除合合法。參看算式式，以上上的線段段掃描過過程可以以得到每每一組超超元線段

21、段的Beelonng(ss)，進進一步得得到整個個圖形輪輪廓的橫橫向邊長長。同時時，線段段掃描過過程還可可以在一一次從左左到右的的掃描中中求得圖圖形輪廓廓的縱向向邊長。還以圖圖10為例例。在掃掃描線狀狀態(tài)改變變之前，L是G,AAE,C；改變狀狀態(tài)之后后，HH,F、D,B就就“露”了出來來，成為為輪廓一一部分。G,AAE,C正正是L改變前前后測度度的差。如果描描述相鄰鄰的掃描描線狀態(tài)態(tài)的線段段樹分別別為Trree11、Treee2，則掃描描過程中中“露出出”的縱縱向邊長長度為|Treee1.M Trree22.M|。在掃描過過程中，遇到的的插入或或刪除稱稱為“事事件”，待插入入或刪除除的線段段稱

22、為“事件線線段”。在掃描描之前，應(yīng)將事事件按橫橫坐標從從小到大大排序。（詳見見附錄2）通過以上上分析，得到較較之線性性結(jié)構(gòu)的的累計掃掃描過程程改進的的線段掃掃描過程程的算法法：以矩形頂頂點坐標標切割平平面，實實現(xiàn)橫縱縱坐標的的離散化化并建立立映射XX_Maap、Y_MMap。事件排序序Roott.Buuildd(1, N*2)Nowmm 0NowLLinee 0Ans 0for II 1 too 事事件的最最大編號號 doo if I是是插入事事件 theen Rooot.IInseert(Y_MMap.Cooord事件線線段頂點點1， Y_Mapp.Cooordd事件件線段頂頂點2) els

23、se Rooot.DDeleete(Y_MMap.Cooord事件線線段頂點點1， Y_MMap.Cooord事件線線段頂點點2) noowM RRoott.M noowLiine Rooot.LLinee anns anns + lasstLiine * 22 * (X_MappI Y_MMapI-11) anns anss + |nowwM laastMM| laasM nowwM laastLLinee nnowLLinee排序的時時間復(fù)雜雜度為OO(NllogNN)。事事件的最最大編號號為N*2，插插入或刪刪除的復(fù)復(fù)雜度為為O(llogNN)，所所以整個個過程效效率為OO(NllogN

24、N)。至至此，以以樹形數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)為基礎(chǔ)礎(chǔ)的算法法模式確確立，時時間效率率是令人人較為滿滿意的。兩種實現(xiàn)現(xiàn)方法的的比較兩種數(shù)據(jù)據(jù)結(jié)構(gòu)的的不同之之處不僅僅在于它它們本身身的存儲儲差異、定義的的運算差差異，還還在于它它們對算算法時間間復(fù)雜度度產(chǎn)生的的影響。線性結(jié)結(jié)構(gòu)產(chǎn)生生的復(fù)雜雜度為OO(N2)，而樹形形結(jié)構(gòu)產(chǎn)產(chǎn)生的復(fù)復(fù)雜度為為O(NNloggN)。以下是是一組數(shù)數(shù)據(jù)，將將兩種數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)實現(xiàn)程程序的運運行時間間作一個個對比，可以感感性地認認識它們們之間的的效率差差異：數(shù)據(jù)實現(xiàn)一：線性結(jié)結(jié)構(gòu)實現(xiàn)二：樹形結(jié)結(jié)構(gòu)Dataa_4_1.TTxt1秒以內(nèi)內(nèi)1秒以內(nèi)內(nèi)Dataa_4_2.TTxtDataa_4

25、_3.TTxt30秒左左右Dataa_4_4.TTxtDataa_4_5.TTxt注：以上上程序在在賽揚3300/Borrlannd PPasccal下下運行。（程序序清單見見程序1線性結(jié)結(jié)構(gòu)及程序2樹形結(jié)結(jié)構(gòu)）Pictturee問題的的推廣基于對PPictturee問題特特征的分分析及樹樹形結(jié)構(gòu)構(gòu)的應(yīng)用用，可以以使問題題得到推推廣。離散化思思想可以以使頂點點坐標由由整數(shù)實實數(shù)。在在算法及及數(shù)據(jù)結(jié)結(jié)構(gòu)的選選擇中，我們已已不再使使用數(shù)據(jù)據(jù)類型為為整數(shù)的的特性。所以PPictturee問題的的數(shù)據(jù)類類型可以以推廣到到實型。為了適適應(yīng)這一一變化，要將MMappped.Cooord的的基類型型改為實實型，同同時將LLinees_TTreee.M改改為實型型，線段段掃描算算法中的的累加器器anss等涉及及到頂點點坐標的的類型也也要改為為實型。更重要的的是，PPictturee問題