算法合集之《數(shù)據(jù)結構的選擇與算法效率》-

1、數(shù)據(jù)結構的選擇與算法效率從IOI98試題PICTURE談起福建師大附中陳宏【關鍵字】數(shù)據(jù)結構的選擇線性結構樹形結構【摘要】算法 + 數(shù)據(jù)結構=程序。設計算法與選擇合適的數(shù)據(jù)結構是程序設計中相輔相成的兩方面,缺一不可。數(shù)據(jù)結構的選擇一直是程序設計中的重點、難點,正確地應用數(shù)據(jù)結構,往往能帶來意想不到的效果。反之,如果忽視了數(shù)據(jù)結構的重要性,對某些問題有時就得不到滿意的解答。通過對IOI98試題Picture的深入討論,我們可以看到兩種不同的數(shù)據(jù)結構在解題中的應用,以及由此得到的不同的算法效率。本文以Picture問題為例,探討數(shù)據(jù)結構的選擇對算法效率的影響?！菊摹恳运惴ㄍǔＪ菦Q定程序效率的關

2、鍵,但一切算法最終都要在相應的數(shù)據(jù)結構上實現(xiàn),許多算法的精髓就是在于選擇了合適的數(shù)據(jù)結構作為基礎。在程序設計中,不但要注重算法設計,也要正確地選擇數(shù)據(jù)結構,這樣往往能夠事半功倍。在算法時間與空間效率的兩方面,著重分析時間效率,即算法的時間復雜度,因為我們總是希望程序在較短的時間內給出我們所希望的輸出。如果在空間上過于“吝嗇”而使得時間上無法承受,對解題并無益處。本文對IOI98的試題Picture作一些分析,通過兩種不同數(shù)據(jù)結構的選擇,將了解到數(shù)據(jù)結構對算法本身及算法效率的影響。Picture問題及算法設計一、Picture問題Picture問題是IOI98的一道試題,描述如下:墻上貼著一些海

3、報、照片等矩形,所有的邊都為垂直或水平。每個矩形可以被其它矩形部分或完全遮蓋,所有矩形合并成區(qū)域的邊界周長稱為輪廓周長。例如圖1的三個矩形輪廓周長為30:圖1要求編寫程序計算輪廓周長。數(shù)據(jù)量限制:0矩形數(shù)目<5000;坐標數(shù)值為整數(shù),范圍是-10000,10000。二、算法描述在算法的大體描述中,將不涉及到具體的數(shù)據(jù)結構,便于數(shù)據(jù)結構的進一步選擇和比較分析。(一、輪廓的定義在描述算法前,我們先明確一下“輪廓”的定義:1、輪廓由有限條線段組成,線段是矩形邊或者矩形邊的一部分。2、組成矩形邊的線段不應被任何矩形遮蓋。圖2與圖3分別是遮蓋的兩種情況。圖2 圖3 圖4(AB 被遮蓋 (CD 被遮

4、蓋(二、元線段本題的一大特征是分析矩形的邊,而邊的端點(即矩形的頂點坐標為整數(shù),且坐標取值范圍已經(jīng)限定在-10000,10000之間。這樣,就可以把這個平面理解成為一個網(wǎng)格。由于給出的坐標是整數(shù),所以矩形邊一定在網(wǎng)格線上。在網(wǎng)格中,對于一條線段我們最關心其絕對坐標。如圖4,我們認為矩形邊AB 由線段L 1、L 2、L 3組成。像L 1、L 2、L 3這樣連接相鄰網(wǎng)格頂點的基本線段,稱之為“元線段”,這樣就把矩形邊離散化了。顯然,有限的元線段覆蓋了所有的網(wǎng)格線,且元線段是組成矩形邊乃至組成輪廓的基本單位。一條元線段要么完全屬于輪廓,要么完全不屬于輪廓。這種定義使我們對問題的研究具體到每一條元線段

5、,這樣的離散化處理有利于問題的進一步討論。(三、超元線段 A B L1L3L2B A D C元線段的引入,使問題更加具體。但也應當看到,平面中共有20001*20000*2條元線段,研究的對象過多,而且計算量受到網(wǎng)格大小的影響,如果頂點坐標范圍是-1,000,000,1,000,000,元線段數(shù)目將達到8*1012,這是天文數(shù)字。因此有必要對“元線段”進行優(yōu)化。受到元線段的啟發(fā),我們定義一種改進后的元線段“超元線段”,它將由對平面的“切割”得到。具體做法是,根據(jù)每個矩形縱向邊的橫坐標縱向地對平面進行2*N 次切割、根據(jù)矩形橫向邊的縱坐標橫向地對矩形進行2*N 次切割(N 為矩形個數(shù)。顯然,經(jīng)過

6、切割后的平面被分成了(2*N+12個區(qū)域,如圖5所示: 圖5 圖6其中像橫向邊AB 、縱向邊CD 這樣的線段就是“超元線段”。超元線段與元線段有著相似的性質,也是組成輪廓的基本單位。所不同的是,超元線段的數(shù)目較少,一般為4*N 條左右,且超元線段數(shù)目不受網(wǎng)格大小的影響?；诔€段的優(yōu)點,算法最終將研究超元線段。(一、 離散化及算法框架算法的研究對象是超元線段,但這并不等于逐一枚舉,那樣耗時過大,而整體考慮又使得問題無從下手。有一種考慮方法是折中的,即既不研究每一條超元線段,也不同時研究所有的超元線段,而是再進一步優(yōu)化問題的離散化,即將超元線段分組研究。如圖6所示,夾在兩條縱向分割邊的超元線段

7、自然地分為一組,它們的共同點是長度相同,并且端點的橫坐標相同?？v向線段也可以進行類似的離散化。這樣的離散化處理后,使得問題規(guī)模降低,以此為基礎,算法的框架可以基本確定為:1、對平面進行分割。2、累加器ans 0。3、研究每組超元線段,檢測其中屬于輪廓的部分的長度,并把這一長度累加入ans 。4、輸出ans 的值。以上只是算法的基本框架,還很粗糙,求精部分有賴于數(shù)據(jù)結構的具體選擇。三、Picture 問題的數(shù)據(jù)結構選擇之一:線性結構(一、 映射結構的建立算法的基礎是問題的離散化,要進行平面“分割”,一般需要記錄分割點,D A BC通常采用映射來記錄分割點。直觀的做法是采用一維數(shù)組形式,下標表示分

8、割點的編號,數(shù)組元素表示分割點的坐標。利用下標與數(shù)組元素的自然對應,實現(xiàn)映射。應該說,這樣表示是比較自然的,實現(xiàn)也比較方便。數(shù)組的優(yōu)點主要是存取方便,且可以在O(NlogN時間內排序。映射結構定義如下:TypeMapped_TYPE = ObjectLen : 0.Max; 記下分割點的個數(shù)Coord : array1.Max of integer; 記下分割點坐標Procedure Creat; 映射初始化Procedure Insert(X : integer; 插入分割坐標XProcedure Sort; 對坐標排序End以下是三個過程的描述與解釋:Procedure Mapped_TY

9、PE.Creat1Len 0Creat 用于初始化該映射Procedure Mapped_TYPE.Insert(X : Integer1Len Len + 12CoordLen XInsert 用于插入一個分割坐標,此時坐標之間是無序的Procedure Mapped_TYPE.Sort略Sort 用于將Len個坐標排序。由于Coord是一維數(shù)組,Sort 容易實現(xiàn),例如快速排序。設N = Len,Sort 效率可達O(NlogN。針對整數(shù),也可以采用筒排序得到更好的效率,但這不是問題的關鍵部分。VarX_map, Y_map : Mapped_TYPE 分別記錄橫縱坐標的映射以橫坐標為例,

10、在程序處理時,首先執(zhí)行X_map.Creat初始化映射。而后通過X_map.Insert將每個矩形縱向邊的橫坐標作為分割坐標插入X_map.Coord,最后執(zhí)行X_map.Sort進行排序。至此,映射建立完畢。應該說,這一部分完全可以滿足算法要求,且執(zhí)行效率較高。三個過程中的Creat與Insert耗時均為O(1,Sort耗時為O(NlogN,但它只需執(zhí)行一次。(二、線性結構的建立映射建立后,相當于完成了對平面的切割?，F(xiàn)在的主要問題是如何描述一組超元線段的狀態(tài)。由于最終要計算輪廓周長,我們最關心的是一組超元線段中究竟有多少條屬于輪廓。由分組的方法可知,每組超元線段長度相同。以下均以橫向超元線段

11、為例進行說明。設:超元線段組編號1N*2-1(N是矩形數(shù)目編號為S 的超元線段組中的線段長度為Length(S編號為S 的超元線段組中屬于圖形輪廓的超元線段數(shù)目為Belong(S則:其中Lenth(s容易求得。如果超元線段組編號以網(wǎng)格中從左到右為原則,那么Length(s就可以表示為: X_Map.coords X_map.Coords-1,算式只需求得Belong (s 即可。如圖6,可以看到在問題的離散化之后,一組橫向超元線段從上到下,數(shù)目是有限的,約有N*2條。這使得我們很容易想到線性結構。例如用一維數(shù)組來描述這么一組線段,用數(shù)組下標表示該線段從上到下的編號。數(shù)組雛形定義如下 VarA

12、: array1.MaxSize of integer基于對一維數(shù)組的使用,可以得到一個稱為“累計掃描”的過程,來求解Belong(s。累計掃描的思想是,將一維數(shù)組的元素看作計數(shù)器,計數(shù)器AI的內容是覆蓋超元線段I 的矩形上邊的數(shù)目 覆蓋超元線段I 的矩形下邊的數(shù)目。形象表示如圖7:圖7同時,設立累加器add ,從上至下掃描超元線段,累加aI的值。由圖7中可以看出,一條超元線段I 屬于輪廓的情況有兩種:1、AI0且掃描到該超元線段未累加時add = 0(超元線段I 是矩形上邊的情況2、AI0且掃描到該超元線段累加之后add = 0(超元線段I 是矩形下邊的情況這樣,對于一組超元線段求解Belo

13、ng(s可以分為兩部分:1、對AI賦值,即累計過程。2、從上至下掃描一組超元線段并累加add ,即掃描過程。Belong(s的值在掃描過程中得到。至此,描述一組超元線段狀態(tài)的數(shù)據(jù)結構基本確立,存儲結構是線性一維數(shù)a1=1a6=-1a4=1a5=-1a2=1a3=-1add=0add=1add=2add=1add=2add=1add=0-=12*1(*(N S s Belong s Length 輪廓橫向邊周長ANS = 算式組,定義的操作包括累計與掃描兩個部分。定義如下:TypeGroup_TYPE = ObjectA : array1.MaxSize of Integer; 線性地記錄一組超

14、元線段的信息,如圖7Procedure Count; 累計的過程Function Adding; 掃描的過程,即求解Belong(s的過程EndProcedure Group_TYPE.Count 累計的過程1數(shù)組A清零2for I 1 to N3do if 矩形I跨越了超元線段組S即矩形的左右邊分別在線段兩側 4then A矩形I的上邊 A矩形I的上邊 + 15A矩形I的下邊 A矩形I的下邊 - 1所謂“矩形I的上邊”指矩形I上邊縱坐標的映射編號,“矩形I的下邊”同F(xiàn)unction Group_TYPE.Adding 掃描的過程,函數(shù)值即為Belong(S的值 1調用Count2add 03

15、sum 04for I 1 to 縱坐標的最大映射編號5do if aI 06then if add = 07then sum sum + 1該線段是矩形的上邊8add add + aI9if add = 010then sum sum + 1該線段是矩形的下邊11return sumCount與Adding用于一組超元線段的累計掃描VarScan : Group_TYPE數(shù)據(jù)結構確立后,Belong(s通過調用Scan.Adding來計算,算式得以實現(xiàn)。以上的操作針對一維數(shù)組而設計,用于進行一組超元線段的累計掃描過程。執(zhí)行Scan.Adding的時間復雜度為O(N。橫向超元線段分為2*N-1

16、組,固求解橫向輪廓周長的算法時間復雜度為O(N2。同理,求解縱向輪廓周長的復雜度也為O(N2,則Picture問題的算法時間復雜度為O(N2。雖然這是一個多項式階,但在最壞情況下(N接近5000時還有一定的計算量。對數(shù)據(jù)結構選擇的進一步分析累計掃描過程體現(xiàn)了一種認識和思維方式,以一維數(shù)組作為數(shù)據(jù)結構基礎,這里是否有更好的做法,我們將作進一步分析。通過求解問題對數(shù)據(jù)結構選擇作的分析中,我們注意到在選擇數(shù)據(jù)結構需要考慮的幾個方面:1、數(shù)據(jù)結構要適應問題的狀態(tài)描述。解決問題時需要對狀態(tài)進行描述,在程序中,要涉及到狀態(tài)的存儲、轉換等。選擇的數(shù)據(jù)結構必需先適用于描述狀態(tài),并使對狀態(tài)的各種操作能夠明確地定

17、義在數(shù)據(jù)結構上。在Picture問題中,涉及到算法的狀態(tài)是關于一組“超元線段”的描述,目的是要確定該組超元線段的數(shù)目,我們選擇了線性結構,采用計數(shù)掃描的方法,統(tǒng)計超元線段屬于輪廓的數(shù)目。這種表示法直觀、易于實現(xiàn),可以說基本適用于描述狀態(tài)。但采用一維數(shù)組,效率并不高,一次掃描耗時較大。其中主要的原因是各組超元線段的掃描分別獨立,后面的掃描并不能利用前面的結論。2、數(shù)據(jù)結構應與所選擇的算法相適應。數(shù)據(jù)結構是為算法服務的,其選擇要充分考慮算法的各種操作,同時數(shù)據(jù)結構的選擇也影響著算法的設計。我們有這樣的認識和經(jīng)歷,如果算法是對一個隊列進行堆排序,就應當選擇能夠迅速定位的數(shù)據(jù)結構,如一維數(shù)組等,而不應

18、選擇像鏈表這樣定位耗時的數(shù)據(jù)結構,反之,如果要對一個鏈表進行排序,則基于鏈表結構的基數(shù)排序應當是首選對象。Picture問題的算法思想基于問題的離散化,需要對平面進行分割,記錄分割點的坐標。通常,使用映射來記錄分割點。采用數(shù)組形式,利用其下標與數(shù)組元素的自然對應,實現(xiàn)映射,直截了當。這樣選擇基本可以滿足算法要求。同時,在選擇數(shù)據(jù)結構時,也要考慮其對算法的影響。數(shù)據(jù)結構對算法的影響主要在兩方面:數(shù)據(jù)結構的存儲能力。如果數(shù)據(jù)結構存儲能力強、存儲信息多,算法將會較好設計。反之對于過于簡單的數(shù)據(jù)結構,可能就要設計一套比較復雜的算法了。在這一點上,經(jīng)常體現(xiàn)時間與空間的矛盾,往往存儲能力是與所使用的空間大

19、小成正比的。定義在數(shù)據(jù)結構上的操作?！皵?shù)據(jù)結構”一詞之所以不同于“變量”,主要在于數(shù)據(jù)結構上定義了基本操作,這些操作都有較強的實際意義。這些操作就好比工具,有了好的工具,算法設計也會比較輕松。Picture問題中選擇了線性結構,它定義的操作比較簡單,因此無法很好地將不同組的超元線段統(tǒng)計聯(lián)系起來。3、數(shù)據(jù)結構的選擇同時要兼顧編程的方便。許多復雜的數(shù)據(jù)結構能夠得到較好的效率,但編程復雜,不易實現(xiàn)且容易出錯。在這種情況下,如果能夠選擇一種我們較為熟悉的又不會過多地降低程序效率的數(shù)據(jù)結構,倒不失為一種折中的辦法。如Picture問題中的Group_TYPE.Count過程的4、5兩步,要求出某個矩形邊

20、對應的映射編號。我們定義的映射僅僅是編號坐標值,并不是坐標值編號。如果再實現(xiàn)這一映射,勢必增加編程難度。所以編程求精時,可以認為以整數(shù)而不是以頂點坐標對平面進行橫向切割。這樣映射關系很好建立,坐標值本身就是編號,減少了編程難度。如果進一步以頂點坐標作橫向切割,當然會提高程序效率,但效果并不明顯掃描計數(shù)仍需要O(N的時間,這是很昂貴的,所以進一步切割并不影響算法主要部分的效率,另一方面,編程難度卻會大大提高,得不償失。由此看出,在算法效率“大局已定”的情況下,有時也需要適當?shù)貭奚绦蛐蕘頊p少編程不必要的麻煩。4、靈活應用已有知識。我們對編程都積累了一定的經(jīng)驗,對以后的解題有很大幫助。一個“新問

21、題”有時與“舊問題”有許多內在的聯(lián)系,往往能夠將新問題轉化為所學過的知識,或者由所學過的知識得到啟發(fā),從而解決問題。所謂“新”數(shù)據(jù)結構的構造,有時可以是幾種基本數(shù)據(jù)結構的有機結合,或者由基本數(shù)據(jù)結構得到啟發(fā)而得到。做到“溫故而知新”,是對算法設計者創(chuàng)新意識的要求。當然,對一個問題,要首先考慮現(xiàn)成的、經(jīng)典的數(shù)據(jù)結構。如隊列、棧、鏈表等等,其標準結構與標準運算已經(jīng)有了“公論”,程序實現(xiàn)也經(jīng)過了“千錘百煉”,效率已經(jīng)很完美。如果找到一種可行的經(jīng)典數(shù)據(jù)結構,那么算法實現(xiàn)一般來說就比較輕松。要做到這一點,要求我們有扎實的基礎知識,對各種算法及數(shù)據(jù)結構了然于胸。在計數(shù)掃描過程中采用了經(jīng)典的線性一維數(shù)組,是

22、一個很自然的考慮方向,并且可以很容易上機實現(xiàn),不足之處在于其效率較低?？偟貋碚f,Picture問題算法思想的方向還是基本正確的。Picture問題最大數(shù)據(jù)應包含近5000個矩形,這樣大的數(shù)據(jù)量決定了要降低規(guī)模是“大勢所趨”,所以對問題的離散化處理是合理的選擇。至于效率不高,應當是線性數(shù)據(jù)結構的選擇造成的。由此,我們可以看到使用線性結構來實現(xiàn)Picture問題還有一些缺陷,其中最主要的是各組超元線段的統(tǒng)計相互獨立,聯(lián)系不緊,這是算法效率不高的“瓶頸”。為了解決這個問題,我們嘗試用其它的數(shù)據(jù)結構來實現(xiàn)算法,像前面一樣,這個數(shù)據(jù)結構應該符合以下的條件:1、同線性結構一樣,新數(shù)據(jù)結構要適用于描述一組超

23、元線段的狀態(tài)。至少,新結構要合理地表示一組超元線段屬于輪廓的部分,或者說它要能準確地且較快地計算出算式中Belong(s的值。2、新結構也要與基本算法相適應。新結構仍然以問題的離散化為基礎,映射結構應當保留事實上映射結構在時間效率上并沒有缺點。新結構在描述超元線段組時則要設法將不同組超元線段的統(tǒng)計有機結合起來。3、新結構還要兼顧編程的方便。如果選擇的數(shù)據(jù)結構編程難度太大,以至于無法上機實現(xiàn),或者只是理論上的“高效率”,對解題沒有實際意義。這么說也許太夸張,但實際上也常常存在“魚與熊掌不可兼得”的情況。大部分高級數(shù)據(jù)結構的實現(xiàn)都需要一定的編程技巧。就像問題在時間效率與空間效率上的矛盾一樣,算法效

24、率與編程難度也有矛盾,一般來說算法效率越高,編程難度也會越大?？紤]新結構時希望能找到實現(xiàn)較為容易的數(shù)據(jù)結構。綜合以上分析,由于線性結構并不能給我們帶來令人滿意的效率,所以我們嘗試用樹形結構來描述一組超元線段的狀態(tài),實現(xiàn)Picture問題的基本算法。為了提高效率,采用的樹結構必需是平衡樹,我們姑且稱之為“超元線段樹”。Picture問題的深入討論基于對數(shù)據(jù)結構選擇的進一步分析,我們來重新考慮一下Picture問題的數(shù)據(jù)結構的選擇,即采用樹形結構來描述一組超元線段的狀態(tài)。一、線段樹受到累計掃描過程的啟發(fā),一組超元線段屬于輪廓的數(shù)目,它與跨越該組超元線段的矩形的縱向邊位置關系密切。不妨把矩形的縱向邊

25、投影到Y軸上,這樣就把矩形的縱向邊看作閉區(qū)間,并稱之為閉區(qū)間Q。我們以“線段樹”的樹形數(shù)據(jù)結構來描述閉區(qū)間Q。作為工具,先簡單研究線段樹的特點。線段樹是描述單個或若干區(qū)間并的樹形結構,屬于平衡樹的一種。使用線段樹要求知道所描述的區(qū)間端點可能取到的值。換句話說,設A1.N是從小到大排列的區(qū)間端點集合,對于任意一個待描述的閉區(qū)間P=x,y,存在1ijN 使得x=ai且y=aj,這里i, j稱為x,y的編號?？梢钥吹?即使是實數(shù)坐標,在線段樹中也只有整數(shù)含義。以下所說的區(qū)間x, y如無特殊說明,x、y均是整數(shù),即原始區(qū)間頂點坐標的編號。線段樹是一棵二叉樹,將數(shù)軸劃分成一系列的初等區(qū)間I, I+1 (

26、I=1N-1。每個初等區(qū)間對應于線段樹的一個葉結點。線段樹的內部結點對應于形如 I, J (J I > 1的一般區(qū)間。一般情況下,線段樹的結點類型定義如下:TypeLines_Tree = Objecti, j : integer; 結點表示的區(qū)間的頂點標號I, Jcount : integer; 覆蓋這一結點的區(qū)間數(shù)leftchild, rightchild : Lines_Tree; 二叉樹的兩個子結點end關于Lines_Tree的其它數(shù)據(jù)域與定義的運算將陸續(xù)添加。圖8是一棵線段樹,描述的區(qū)間端點可以有10種取值。其中記錄著一個區(qū)間3,6,它用紅色的3, 5及5,6的并采表示。圖中

27、紅色結點的count域值為1,黑色結點的count域值為0。1,101,55,101,33,55,77,101,22,33,44,55,66,77,88,10 8,99,10圖8直觀地看,子結點就是父結點區(qū)間平均分成兩部分。設L, R是父結點的區(qū)間端點,我們可以增加Lines_Tree.Build(l, r : integer遞歸地定義線段樹如下: Procedure Lines_tree.Build(l, r : integer1I l 左端點2J r 右端點3Count 0 初始化4If r - l > 1 是否需要生成子結點,若r-l=1則是初等區(qū)間 5then k (l + r

28、平均分為兩部分6new(leftchild7leftchild.Build(l, k 建立左子樹8new(rightchild9rightchild.Build(k, r 建立右子樹10else leftchild nil11rightchild nil設根結點是Root,建樹需要執(zhí)行Root.Build。由遞歸定義看出,線段樹是一棵平衡樹,高度為logN。建立整棵樹需要的時間為O(N。以上著重說明了線段樹的存儲原理,我們還應建立線段樹的基本運算。線段樹可以存儲多個區(qū)間,所以支持區(qū)間插入運算Lines_Tree.Insert(l, r : integer,定義如下:Procedure Line

29、s_Tree.Insert(l, r : integerl, r是待插入?yún)^(qū)間,l、r都是原始頂點坐標1if (l <= ai and (aj <= r2then count count + 1 蓋滿整個結點區(qū)間3else if l < a(i + j div 2 是否能覆蓋到左孩子結點區(qū)間 4then leftchild.Insert(l, r 向左孩子插入5if r > a(i + j div 2 是否能覆蓋到右孩子結點區(qū)間 6then rightchild.Insert(l, r 向右孩子插入類似地,線段樹支持區(qū)間的刪除Lines_Tree.Delete(l, r

30、: integer,定義如下: Procedure Lines_Tree.Delete(l, r : integerl, r是待刪除區(qū)間,l、r都是原始頂點坐標1if (l <= ai and (aj <= r2then count count - 1 蓋滿整個結點區(qū)間3else if l < a(i + j div 2 是否能覆蓋到左孩子結點區(qū)間4then leftchild.Delete(l, r 向左孩子刪除5if r > a(i + j div 2 是否能覆蓋到右孩子結點區(qū)間6then rightchild.Delete(l, r 向右孩子刪除執(zhí)行Lines_T

31、ree.Delete(l, r : integer 的先決條件是區(qū)間l, r曾被插入且還未刪除。如果建樹后插入?yún)^(qū)間2,5而刪除區(qū)間3,4是非法的。通過分析插入與刪除的路徑,可知Lines_Tree.Insert與Lines_Tree.Delete的時間復雜度均為O(logN。(詳見附錄1由于線段樹給每一個區(qū)間都分配了結點,利用線段樹可以求區(qū)間并后的測度與區(qū)間并后的連續(xù)段數(shù)。(一、測度由于線段樹結構遞歸定義,其測度也可以遞歸定義。增加數(shù)據(jù)域Lines_Tree.M 表示以該結點為根的子樹的測度。M取值如下:aj ai 該結點Count>0M = 0 該結點為葉結點且Count=0Leftc

32、hild.M + Rightchild.M 該結點為內部結點且Count=0據(jù)此,可以用Lines_Tree.UpData來動態(tài)地維護Lines_Tree.M。UpData在每一次執(zhí)行Insert或Delete之后執(zhí)行。定義如下:Procedure Lines_Tree.UpData1if count > 02then M aj i 蓋滿區(qū)間,測度為aj ai3else if j - i = 1 是否葉結點4then M 0 該結點是葉結點5else M Leftchild.M + Rightchild.M內部結點 UpData的復雜度為O(1,則用UpData來動態(tài)維護測度后執(zhí)行根結點

33、的Insert 與Delete的復雜度仍為O(logN。(二、連續(xù)段數(shù)這里的連續(xù)段數(shù)指的是區(qū)間的并可以分解為多少個獨立的區(qū)間。如1,22,35,6可以分解為兩個區(qū)間1,3與5,6,則連續(xù)段數(shù)為2。增加一個數(shù)據(jù)域Lines_Tree.line表示該結點的連續(xù)段數(shù)。Line的討論比較復雜,內部結點不能簡單地將左右孩子的Line相加。所以再增加Lines_Tree.lbd與Lines_Tree.rbd 域。定義如下:1 左端點I被描述區(qū)間蓋到lbd =0 左端點I不被描述區(qū)間蓋到1 右端點J被描述區(qū)間蓋到rbd =0 右端點J不被描述區(qū)間蓋到lbd與rbd的實現(xiàn):1 該結點count > 0l

34、bd = 0 該結點是葉結點且count = 0leftchild.lbd 該結點是內部結點且Count=01 該結點count > 0rbd = 0 該結點是葉結點且count = 0rightchild.rbd 該結點是內部結點且Count=0有了lbd與rbd,Line域就可以定義了:1 該結點count > 0Line = 0 該結點是葉結點且count = 0Leftchild.Line + Rightchild.Line - 1當該結點是內部結點且Count=0,Leftchild.rbd = 1且Rightchild.lbd = 1Leftchild.Line + R

35、ightchild.Line當該結點是內部結點且Count=0,Leftchild.rbd與Rightchild.lbd不都為1據(jù)此,可以定義UpData動態(tài)地維護Line域。與UpData相似,UpData也在每一次執(zhí)行Insert或Delete后執(zhí)行。定義如下:Procedure Lines_Tree.UpData1if count > 0 是否蓋滿結點表示的區(qū)間2then lbd 13rbd 14Line 15else if j - i = 1 是否為葉結點6then lbd 0 進行到這一步,如果為葉結點,count = 0 7rbd 08line 09else line Lef

36、tchild.line + Rightchild.line -Leftchild.rbd * Rightchild.lbd用乘法確定Leftchild.rbd與Rightchild.lbd是否同時為1同時,由于增加了Line、M等幾個數(shù)據(jù)域,在建樹Lines_Tree.Build時要將新增的域初始化。至此,線段樹構造完畢,完整的線段樹定義如下:Lines_Tree = objecti, j : integer;count : integer;line : integer;lbd, rbd : byte;m : integer;leftchild,rightchild : Lines_tree;

37、procedure Build(l, r : integer;procedure Insert(l, r : integer;procedure Delete(l, r : integer;procedure UpData;procedure UpData;end有了線段樹這個工具,可以考慮利用樹形結構來描述一組超元線段的狀態(tài)。二、Picture問題的數(shù)據(jù)結構選擇之二:樹形結構采用線性結構描述一組超元線段的狀態(tài)并不能帶來太高的效率,其中主要原因是各組超元線段聯(lián)系不緊。如圖9所示,超元線段CD與EF被矩形AGHB遮蓋,不屬于輪廓;而與之相鄰DD與FF則“擺脫”了矩形的遮蓋,屬于輪廓的一部分。圖9

38、 圖10由此類推,可以看出相鄰的超元線段組都有類似的問題。如圖9,DD與FF不被遮蓋,可以這樣分析:從左往右,CD 、EF 首先被遮蓋,但隨著BF 的出現(xiàn),對DD、FF的遮蓋自然消失。這一點,正是相鄰超元線段組的內在聯(lián)系。用線性結構無法表示出這一聯(lián)系,因為各組的累計掃描過程是獨立的?，F(xiàn)在我們用樹形結構來表示將較好地解決這一問題,因為線段樹支持插入與刪除及動態(tài)維護,可以有機聯(lián)系各組超元線段的狀態(tài)。我們把“從左往右”當作一個掃描的過程,若將其嚴格地描述,可以得到一個稱為線段掃描的過程:1. 設立掃描線段L 。2. L 從左往右掃描,停留在每一超元線段組上。如圖10所示。3. L 的狀態(tài)用線段樹來表

39、示,每一條縱向的矩形邊看作一個待合并區(qū)間。線段樹的連續(xù)段數(shù)*2表示該組超元線段屬于輪廓的線段數(shù)目。如圖10,L 的狀態(tài)首先是G ,AE,C,連續(xù)線段數(shù)是1,所以1*2=2是該組超元線段屬于輪廓的數(shù)目。接著L 進一步掃描,狀態(tài)改變?yōu)镋,C, 連續(xù)線段數(shù)是1,所以該組超元線段屬于輪廓的數(shù)目也是1*2=2。這樣,上文所說的“超元線段樹”就用線段樹來實現(xiàn)。為了統(tǒng)一起見,以后仍稱線段樹。4. 掃描過程中動態(tài)地維護L 的狀態(tài)。參看圖10,L 狀態(tài)的轉換是在線段樹中刪去區(qū)間H,B即G ,A造成的。歸納一下,有以下結論: L 初始化為空,即線段樹剛建好時的情形。 掃描時,遇到矩形左邊,將其插入(Insert

40、線段樹。 掃描時,遇到矩形右邊,將其從線段樹中刪除(Delete 。由于從左往右掃描,事先插入了該矩形的左邊,所以刪除合法。參看算式,以上的線段掃描過程可以得到每一組超元線段的Belong(s,進一步得到整個圖形輪廓的橫向邊長。同時,線段掃描過程還可以在一次從左到右的掃描中求得圖形輪廓的縱向邊長。還以圖10為例。在掃描線狀態(tài)改變之前,L 是G ,AE,C;改變狀態(tài)之后,H,F、D,B就“露”了出來,成為輪廓一部分。G ,AE,C正是L 改變前后測度的差。如果描述相鄰的掃描線狀態(tài)的線段樹分別為Tree1、Tree2,則掃描過程中“露出”的縱向邊長度為|Tree1.M Tree2.M|。在掃描過程

41、中,遇到的插入或刪除稱為“事件”,待插入或刪除的線段稱為“事件線段”。在掃描之前,應將事件按橫坐標從小到大排序。(詳見附錄2通過以上分析,得到較之線性結構的累計掃描過程改進的線段掃描過程的算法:F'D'H G F E D C B A L L F'D'H G F E D C B A1. 以矩形頂點坐標切割平面,實現(xiàn)橫縱坐標的離散化并建立映射X_Map 、Y_Map 。2. 事件排序3. Root.Build(1, N*24. Nowm 05. NowLine 06. Ans 07. for I 1 to 事件的最大編號8. do if I 是插入事件9. then Root.Insert(Y_Map.Coord事件線段頂點1,Y_Map.Coord事件線段頂點210. else Root.Delete(Y_Map.Coord事件線段頂點1,Y_Map.Coord事件線段頂點211. nowM Root.M12. nowLine Ro