文档介绍：数据结构的选择与算法效率
——从IOI98试题PICTURE谈起
福建师大附中陈宏
【关键字】
数据结构的选择线性结构树形结构
【摘要】
算法+ 数据结构=程序。设计算法与选择合适的数据结构是程序设计中相辅相成的两方面,缺一不可。数据结构的选择一直是程序设计中的重点、难点,正确地应用数据结构,往往能带来意想不到的效果。反之,如果忽视了数据结构的重要性,对某些问题有时就得不到满意的解答。通过对IOI98试题Picture的深入讨论,我们可以看到两种不同的数据结构在解题中的应用,以及由此得到的不同的算法效率。本文以Picture问题为例,探讨数据结构的选择对算法效率的影响。
【正文】
引言
算法通常是决定程序效率的关键,但一切算法最终都要在相应的数据结构上实现,许多算法的精髓就是在于选择了合适的数据结构作为基础。在程序设计中,不但要注重算法设计,也要正确地选择数据结构,这样往往能够事半功倍。
在算法时间与空间效率的两方面,着重分析时间效率,即算法的时间复杂度,因为我们总是希望程序在较短的时间内给出我们所希望的输出。如果在空间上过于“吝啬”而使得时间上无法承受,对解题并无益处。
本文对IOI98的试题Picture作一些分析,通过两种不同数据结构的选择,将了解到数据结构对算法本身及算法效率的影响。
Picture问题及算法设计
Picture问题
Picture问题是IOI98的一道试题,描述如下:
墙上贴着一些海报、照片等矩形,所有的边都为垂直或水平。每个矩形可以被其它矩形部分或完全遮盖,所有矩形合并成区域的边界周长称为轮廓周长。
例如图1的三个矩形轮廓周长为30:

图1
要求编写程序计算轮廓周长。
数据量限制:
0≤矩形数目<5000;
坐标数值为整数,范围是[-10000,10000]。
算法描述
在算法的大体描述中,将不涉及到具体的数据结构,便于数据结构的进一步选择和比较分析。
、轮廓的定义
在描述算法前,我们先明确一下“轮廓”的定义:
1、轮廓由有限条线段组成,线段是矩形边或者矩形边的一部分。
2、组成矩形边的线段不应被任何矩形遮盖。图2与图3分别是遮盖的两种情况。
图2 图3 图4
(AB被遮盖) (CD被遮盖)
、元线段
本题的一大特征是分析矩形的边,而边的端点(即矩形的顶点)坐标为整数,且坐标取值范围已经限定在[-10000,10000]之间。这样,就可以把这个平面理解成为一个网格。由于给出的坐标是整数,所以矩形边一定在网格线上。在网格中,对于一条线段我们最关心其绝对坐标。如图4,我们认为矩形边AB由线段L1、L2、L3组成。像L1、L2、L3这样连接相邻网格顶点的基本线段,称之为“元线段”,这样就把矩形边离散化了。显然,有限的元线段覆盖了所有的网格线,且元线段是组成矩形边乃至组成轮廓的基本单位。一条元线段要么完全属于轮廓,要么完全不属于轮廓。这种定义使我们对问题的研究具体到每一条元线段,这样的离散化处理有利于问题的进一步讨论。
、超元线段
元线段的引入,使问题更加具体。但也应当看到,平面中共有20001*20000*2条元线段,研究的对象过多,而且计算量受到网格大小的影响,如果顶点坐标范围是[-1,000,000,1,000,000],元线段数目将达到8*10^12,这是天文数字。因此有必要对“元线段”进行优化。受到元线段的启发,我们定义一种改进后的元线段——“超元线段”,它将由对平面的“切割”得到。具体做法是,根据每个矩形纵向边的横坐标纵向地对平面进行2*N次切割、根据矩形横向边的纵坐标横向地对矩形进行2*N次切割(N为矩形个数)。显然,经过切割后的平面被分成了(2*N+1)^2个区域,如图5所示:
图5 图6
其中像横向边AB、纵向边CD这样的线段就是“超元线段”。超元线段与元线段有着相似的性质,也是组成轮廓的基本单位。所不同的是,超元线段的数目较少,一般为4*N条左右,且超元线段数目不受网格大小的影响。
基于超元线段的优点,算法最终将研究超元线段。
离散化及算法框架
算法的研究对象是超元线段,但这并不等于逐一枚举,那样耗时过大,而整体考虑又使得问题无从下手。有一种考虑方法是折中的,即既不研究每一条超元线段,也不同时研究所有的超元线段,而是再进一步优化问题的离散化,即将超元线段分组研究。如图6所示,夹在两条纵向分割边的超元线段自然地分为一组,它们的共同点是长度相同,并且端点的横坐标相同。纵向线段也可以进行类似的离散化。
这样的离散化处理后,使得问题规模降低,以此为基础,算法的框架可以基本确定为:
1、对平面进行分割。
2、累加器ans ß 0。
3、研究每组超元线段,检测其中属于轮廓的部分的长度,并把这一长度累