数据结构的选择与算法效率

1、数据结构的选择与算法效率从IOI98试题PICTURE谈起- PAGE 36 -IOI99中国集训队优秀论文选IOI99中国集训队优秀论文选- PAGE 35 -IOI99中国集训队优秀论文选- PAGE 21 -数据结构构的选择择与算法法效率从IIOI998试题题PICCTURRE谈起起 【关键字字】数据结构构的选择择 线性结结构 树形形结构【摘要】算法 + 数据据结构=程序。设计算算法与选选择合适适的数据据结构是是程序设设计中相相辅相成成的两方方面，缺缺一不可可。数据据结构的的选择一一直是程程序设计计中的重重点、难难点，正正确地应应用数据据结构，往往能能带来意意想不到到的效果果。反之之，如

2、果果忽视了了数据结结构的重重要性，对某些些问题有有时就得得不到满满意的解解答。通通过对IIOI998试题题Piccturre的深深入讨论论，我们们可以看看到两种种不同的的数据结结构在解解题中的的应用，以及由由此得到到的不同同的算法法效率。本文以以Piccturre问题题为例，探讨数数据结构构的选择择对算法法效率的的影响。【正文】引言算法通常常是决定定程序效效率的关关键，但但一切算算法最终终都要在在相应的的数据结结构上实实现，许许多算法法的精髓髓就是在在于选择择了合适适的数据据结构作作为基础础。在程程序设计计中，不不但要注注重算法法设计，也要正正确地选选择数据据结构，这样往往往能够够事半功功倍。

3、在算法时时间与空空间效率率的两方方面，着着重分析析时间效效率，即即算法的的时间复复杂度，因为我我们总是是希望程程序在较较短的时时间内给给出我们们所希望望的输出出。如果果在空间间上过于于“吝啬啬”而使使得时间间上无法法承受，对解题题并无益益处。本文对IIOI998的试试题Piictuure作作一些分分析，通通过两种种不同数数据结构构的选择择，将了了解到数数据结构构对算法法本身及及算法效效率的影影响。Pictturee问题及及算法设设计Pictturee问题Pictturee问题是是IOII98的一一道试题题，描述述如下：墙上贴着着一些海海报、照照片等矩矩形，所所有的边边都为垂垂直或水水平。每每个

4、矩形形可以被被其它矩矩形部分分或完全全遮盖，所有矩矩形合并并成区域域的边界界周长称称为轮廓廓周长。例如图11的三个个矩形轮轮廓周长长为300： 图1要求编写写程序计计算轮廓廓周长。数据量限限制：0矩形形数目 11)的一一般区间间。一般般情况下下，线段段树的结结点类型型定义如如下： TyypeLinees_TTreee = Objjectt i, j : inttegeer; 结点表表示的区区间的顶顶点标号号I, J coountt : iinteegerr; 覆盖这这一结点点的区间间数 leeftcchilld, riighttchiild : Linnes_Treee; 二叉叉树的两两个子结

5、结点end关于Liiness_Trree的的其它数数据域与与定义的的运算将将陆续添添加。图图8是一棵棵线段树树，描述述的区间间端点可可以有110种取取值。其其中记录录着一个个区间3，6，它它用红色色的33，5及5，6的并并采表示示。图中中红色结结点的ccounnt域值值为1，黑色色结点的的couunt域域值为00。图8直观地看看，子结结点就是是父结点点区间平平均分成成两部分分。设LL, RR是父结结点的区区间端点点，我们们可以增增加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 是否否需要生生成子结结点，若若r-ll=1则则是初等等区间 thhen kk (ll + rr) 平均分分为两部部分 nnew(lefftchhildd) llefttchiild.Buuildd(l, k) 建建立左子子树 nnew(rigghtcchilld) rrighhtchhildd.Buuildd(k, r) 建立立右子树树 ellse llefttchiild nill riighttchiild nill设根结点点是Rooot，建树需需要执行行Rooot

7、.BBuilld。由递归定定义看出出，线段段树是一一棵平衡衡树，高高度为loggN。建立立整棵树树需要的的时间为为O(NN)。以上着重重说明了了线段树树的存储储原理，我们还还应建立立线段树树的基本本运算。线段树可可以存储储多个区区间，所所以支持持区间插插入运算算Linnes_Treee.IInseert(l, r : inntegger)，定义义如下：Procceduure Liiness_Trree.Inssertt(l, r : inntegger) l, rr是待待插入区区间，ll、r都是原原始顶点点坐标if (l = aai) andd (aj = rr) thhen coountt

8、coountt + 11 盖满整整个结点点区间 ellse iff ll aa(ii + jj) ddiv 2 是否否能覆盖盖到右孩孩子结点点区间 theen rigghtcchilld.Innserrt(ll, r) 向向右孩子子插入类似地，线段树树支持区区间的删删除Liiness_Trree.Delletee(l, r : iinteegerr)，定定义如下下：Procceduure Liiness_Trree.Delletee(l, r : inntegger) l, rr是待待删除区区间，ll、r都是原原始顶点点坐标if (l = aai) andd (aj = rr) thhen c

9、oountt coountt - 11 盖满整整个结点点区间 ellse iff ll aa(ii + jj) divv 22 是否否能覆盖盖到右孩孩子结点点区间 theen rigghtcchilld.Deelette(ll, rr) 向右右孩子删删除执行Liiness_Trree.Delletee(l, r : iinteegerr) 的先决决条件是是区间l, r曾曾被插入入且还未未删除。如果建建树后插插入区间间2，5而删删除区间间3，4是非非法的。通过分析析插入与与删除的的路径，可知LLinees_TTreee.Innserrt与Linnes_Treee.DDeleete的的时间复复杂度

10、均均为O(loggN)。(详见附录1)由于线段段树给每每一个区区间都分分配了结结点，利利用线段段树可以以求区间间并后的的测度与与区间并并后的连连续段数数。测度由于线段段树结构构递归定定义，其其测度也也可以递递归定义义。增加加数据域域Linnes_Treee.MM表示以以该结点点为根的的子树的的测度。M取值如如下： aaj aii 该结点点Couunt0M = 0 该结点点为叶结结点且CCounnt=00 LLefttchiild.M + RRighhtchhildd.M 该结点点为内部部结点且且Couunt=0据此，可可以用LLinees_TTreee.UppDatta来动动态地维维护Liin

11、ess_Trree.M。UpDDataa在每一一次执行行Inssertt或Delletee之后执执行。定定义如下下：Procceduure Liiness_Trree.UpDDataaif couunt 0 thhen M ajj i 盖满区区间，测测度为aaj aii ellse iff jj - ii = 11 是否否叶结点点 theen M 00 该结点点是叶结结点 elsse M LLefttchiild.M + Riighttchiild.M 内部结结点UpDaata的的复杂度度为O(1)，则用UUpDaata来来动态维维护测度度后执行行根结点点的Innserrt与Delletee的

12、复杂杂度仍为为O(llogNN)。连续段数数这里的连连续段数数指的是是区间的的并可以以分解为为多少个个独立的的区间。如11，22，335，6可以以分解为为两个区区间11，3与5，6，则则连续段段数为22。增加加一个数数据域LLinees_TTreee.liine表表示该结结点的连连续段数数。Liine的的讨论比比较复杂杂，内部部结点不不能简单单地将左左右孩子子的Liine相相加。所所以再增增加Liiness_Trree.lbdd与Linnes_Treee.rrbd域域。定义义如下： 11 左端端点I被描述述区间盖盖到lbd = 00 左端点点I不被描描述区间间盖到 11 右右端点JJ被描述述区

13、间盖盖到rbd = 00 右端端点J不被描描述区间间盖到lbd与与rbdd的实现现： 1 该结点点couunt 00lbd = 0 该结点点是叶结结点且ccounnt = 0 lefftchhildd.lbbd 该该结点是是内部结结点且CCounnt=00 1 该结点点couunt 00rbd = 0 该结点点是叶结结点且ccounnt = 0 rigghtcchilld.rbbd 该结结点是内内部结点点且Coountt=0有了lbbd与rbdd，Linne域就就可以定定义了： 1 该结结点coountt 0Linee = 00 该该结点是是叶结点点且coountt = 0 Lefftchhi

14、ldd.Liine + Riighttchiild.Liine - 1 当该结结点是内内部结点点且Coountt=0，Lefftchhildd.rbbd = 1且且Rigghtcchilld.lbbd = 1 LLefttchiild.Liine + Riighttchiild.Liine 当该该结点是是内部结结点且CCounnt=00，Lefftchhildd.rbbd与Rigghtcchilld.lbbd不都都为1据此，可可以定义义UpDDataa动态态地维护护Linne域。与UppDatta相似似，UppDatta也也在每一一次执行行Inssertt或Delletee后执行行。定义义如下

15、：Procceduure Liiness_Trree.UpDDataaif couunt 0 是否盖盖满结点点表示的的区间 thhen lbbd 1 rbdd 1 Linne 11 ellse iff j - i = 1 是否否为叶结结点 theen lbdd 00 进行行到这一一步，如如果为叶叶结点， 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等几个个数据域域，在建建树Liiness_Trree.Buiild时时要将新新增的域域初始化化。至此，线线段树构构造完毕毕，完整整的线段段树定义义如下：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有了线段段树这个个工具，可以考考虑利用用树形结结构来描描述一组组超元线线段的状状态。Pictturee问题的的数据结结构选择择之二：树形结结构采用线性性结构描描述一组组超元线线段的状状态并不不能带来来太高的的效率，其中主主要原因因是各组组超元线线段联系系不紧。如图99所示，超元线线段CDD与E

18、F被矩矩形AGGHB遮遮盖，不不属于轮轮廓；而而与之相相邻DDD与FF则“摆摆脱”了了矩形的的遮盖，属于轮轮廓的一一部分。 图9 图图10由此类推推，可以以看出相相邻的超超元线段段组都有有类似的的问题。如图99，DD与FF不被遮遮盖，可可以这样样分析：从左往往右，CCD、EF首先先被遮盖盖，但随随着BFF的出现现，对DDD、FF的遮盖盖自然消消失。这这一点，正是相相邻超元元线段组组的内在在联系。用线性性结构无无法表示示出这一一联系，因为各各组的累累计扫描描过程是是独立的的。现在在我们用用树形结结构来表表示将较较好地解解决这一一问题，因为线线段树支支持插入入与删除除及动态态维护，可以有有机联系系

19、各组超超元线段段的状态态。我们们把“从从左往右右”当作作一个扫扫描的过过程，若若将其严严格地描描述，可可以得到到一个称称为线段段扫描的的过程：设立扫描描线段LL。L从左往往右扫描描，停留留在每一一超元线线段组上上。如图图10所示示。L的状态态用线段段树来表表示，每每一条纵纵向的矩矩形边看看作一个个待合并并区间。线段树树的连续续段数*2表示示该组超超元线段段属于轮轮廓的线线段数目目。如图图10，L的状态态首先是是G,AAE,C，连续线线段数是是1，所以以1*22=2是是该组超超元线段段属于轮轮廓的数数目。接接着L进一步步扫描，状态改改变为E,CC, 连续线线段数是是1，所以以该组超超元线段段属于

20、轮轮廓的数数目也是是1*22=2。这样，上文所所说的“超元线线段树”就用线线段树来来实现。为了统统一起见见，以后后仍称线线段树。扫描过程程中动态态地维护护L的状态态。参看看图100，L状态的的转换是是在线段段树中删删去区间间H,BB即G,A造造成的。归纳一一下，有有以下结结论：L初始化化为空，即线段段树刚建建好时的的情形。扫描时，遇到矩矩形左边边，将其其插入（Inssertt）线段段树。扫描时，遇到矩矩形右边边，将其其从线段段树中删删除（DDeleete）。由于于从左往往右扫描描，事先先插入了了该矩形形的左边边，所以以删除合合法。参看算式式，以上上的线段段扫描过过程可以以得到每每一组超超元线段

21、段的Beelonng(ss)，进进一步得得到整个个图形轮轮廓的横横向边长长。同时时，线段段扫描过过程还可可以在一一次从左左到右的的扫描中中求得图图形轮廓廓的纵向向边长。还以图图10为例例。在扫扫描线状状态改变变之前，L是G,AAE,C；改变状状态之后后，HH,F、D,B就就“露”了出来来，成为为轮廓一一部分。G,AAE,C正正是L改变前前后测度度的差。如果描描述相邻邻的扫描描线状态态的线段段树分别别为Trree11、Treee2，则扫描描过程中中“露出出”的纵纵向边长长度为|Treee1.M Trree22.M|。在扫描过过程中，遇到的的插入或或删除称称为“事事件”，待插入入或删除除的线段段称

22、为“事件线线段”。在扫描描之前，应将事事件按横横坐标从从小到大大排序。（详见见附录2）通过以上上分析，得到较较之线性性结构的的累计扫扫描过程程改进的的线段扫扫描过程程的算法法：以矩形顶顶点坐标标切割平平面，实实现横纵纵坐标的的离散化化并建立立映射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排序的时时间复杂杂度为OO(NllogNN)。事事件的最最大编号号为N*2，插插入或删删除的复复杂度为为O(llogNN)，所所以整个个过程效效率为OO(NllogN

24、N)。至至此，以以树形数数据结构构为基础础的算法法模式确确立，时时间效率率是令人人较为满满意的。两种实现现方法的的比较两种数据据结构的的不同之之处不仅仅在于它它们本身身的存储储差异、定义的的运算差差异，还还在于它它们对算算法时间间复杂度度产生的的影响。线性结结构产生生的复杂杂度为OO(N2)，而树形形结构产产生的复复杂度为为O(NNloggN)。以下是是一组数数据，将将两种数数据结构构实现程程序的运运行时间间作一个个对比，可以感感性地认认识它们们之间的的效率差差异：数据实现一：线性结结构实现二：树形结结构Dataa_4_1.TTxt1秒以内内1秒以内内Dataa_4_2.TTxtDataa_4

25、_3.TTxt30秒左左右Dataa_4_4.TTxtDataa_4_5.TTxt注：以上上程序在在赛扬3300/Borrlannd PPasccal下下运行。（程序序清单见见程序1线性结结构及程序2树形结结构）Pictturee问题的的推广基于对PPictturee问题特特征的分分析及树树形结构构的应用用，可以以使问题题得到推推广。离散化思思想可以以使顶点点坐标由由整数实实数。在在算法及及数据结结构的选选择中，我们已已不再使使用数据据类型为为整数的的特性。所以PPictturee问题的的数据类类型可以以推广到到实型。为了适适应这一一变化，要将MMappped.Cooord的的基类型型改为实实型，同同时将LLinees_TTreee.M改改为实型型，线段段扫描算算法中的的累加器器anss等涉及及到顶点点坐标的的类型也也要改为为实型。更重要的的是，PPictturee问题