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

1、數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率從IOI98試題PICTURE談起福建師大附中陳宏【關(guān)鍵字】數(shù)據(jù)結(jié)構(gòu)的選擇線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)【摘要】算法 + 數(shù)據(jù)結(jié)構(gòu)=程序。設(shè)計(jì)算法與選擇合適的數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)中相輔相成的兩方面,缺一不可。數(shù)據(jù)結(jié)構(gòu)的選擇一直是程序設(shè)計(jì)中的重點(diǎn)、難點(diǎn),正確地應(yīng)用數(shù)據(jù)結(jié)構(gòu),往往能帶來(lái)意想不到的效果。反之,如果忽視了數(shù)據(jù)結(jié)構(gòu)的重要性,對(duì)某些問(wèn)題有時(shí)就得不到滿意的解答。通過(guò)對(duì)IOI98試題Picture的深入討論,我們可以看到兩種不同的數(shù)據(jù)結(jié)構(gòu)在解題中的應(yīng)用,以及由此得到的不同的算法效率。本文以Picture問(wèn)題為例,探討數(shù)據(jù)結(jié)構(gòu)的選擇對(duì)算法效率的影響。【正文】引言算法通常是決定程序效率的關(guān)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、bd = 0 該結(jié)點(diǎn)是葉結(jié)點(diǎn)且count = 0leftchild.lbd 該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且Count=01 該結(jié)點(diǎn)count > 0rbd = 0 該結(jié)點(diǎn)是葉結(jié)點(diǎn)且count = 0rightchild.rbd 該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且Count=0有了lbd與rbd,Line域就可以定義了:1 該結(jié)點(diǎn)count > 0Line = 0 該結(jié)點(diǎn)是葉結(jié)點(diǎn)且count = 0Leftchild.Line + Rightchild.Line - 1當(dāng)該結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)且Count=0,Leftchild.rbd = 1且Rightchild.lbd = 1Leftchild.Line + R

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

36、tchild.line + Rightchild.line -Leftchild.rbd * Rightchild.lbd用乘法確定Leftchild.rbd與Rightchild.lbd是否同時(shí)為1同時(shí),由于增加了Line、M等幾個(gè)數(shù)據(jù)域,在建樹(shù)Lines_Tree.Build時(shí)要將新增的域初始化。至此,線段樹(shù)構(gòu)造完畢,完整的線段樹(shù)定義如下: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有了線段樹(shù)這個(gè)工具,可以考慮利用樹(shù)形結(jié)構(gòu)來(lái)描述一組超元線段的狀態(tài)。二、Picture問(wèn)題的數(shù)據(jù)結(jié)構(gòu)選擇之二:樹(shù)形結(jié)構(gòu)采用線性結(jié)構(gòu)描述一組超元線段的狀態(tài)并不能帶來(lái)太高的效率,其中主要原因是各組超元線段聯(lián)系不緊。如圖9所示,超元線段CD與EF被矩形AGHB遮蓋,不屬于輪廓;而與之相鄰DD與FF則“擺脫”了矩形的遮蓋,屬于輪廓的一部分。圖9

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

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

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

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