文档介绍：数据结构的提炼与压缩摘要吋间复杂度和空间复杂度是衡量一个数据结构的重要指标,往往,简单存储结构和小存储规模的数据结构会带来较低的吋空复杂度。因此在程序设计屮就需要仔细分析问题,化简存储结构,减少存储规模。关键字化简存储结构、减少存储规模、“提炼”、“压”、“缩”、DFS序、BFS序引言作为程序设计的一部分,数据结构在现在的信息学竞赛屮起着越来越大的作用。一•方面,一个好的数据结构是高效实现算法的基础,例如当算法设计动态序关系吋,通过平衡排序二叉树维护序关系就要比普通线性结构高效的多;另一方而,的信息学竞赛屮已经涌现出一•大批“赤裸裸”的数据结构题,即题H所需要的,就是设计一•个能维护特定数据关系,能高效完成特定操作的数据结构,例如NOI2007necklace>CEOI2007necklace都是这样的问题。衡量一个程序的优劣,有四个主要的参考度量:吋间复杂度,空间复杂度,求解精确度,编程复杂度。时间复杂度衡量程序运行的时间,往往用一个相对输入规模的阶表示,例如冒泡排序的时间复杂度是0(();空间复杂度用来衡量程序所需的除读入外的额外内存空间,往往也用一个和对输入规模的阶表示,例如KMP算法的空间复杂度是O(n);求解精确度衡量程序输岀解的质量,往往用与最优解之间的相对或绝对误差来描述,现在的信息学竞赛屮大多数问题不允许有误差,而另一些问题将求解精确度作为评分尺度之一;编程复杂度衡量正确编程和程序调试的困难程度。而作为对数据结构优劣的评判,(在编程复杂度不过分高的前提下)一个数据结构的吋空复杂度就显得最为重要。木文将主要讨论的通过“化繁为简”的手段优化数据结构的时空复杂度。“化繁为简”作为一个可以广泛应用的方法,它能给程序设计带來以下两方面的优势。一方而,直观地看,在规模小、结构简单的数据丄进行操作,时空耗费比起规模大、结构复杂的数据在操作规模上“天生”就有着无与伦比的优势。例如,图结构的存储无论是采取邻接矩阵还是邻接表,空间都是0(m+n),只要不是稀疏图,就会占用平方阶的空问,同时,所有基本操作的吋间复杂度也在平方阶之±;但对于树结构而言,常用的左儿子右兄弟表示法只需要O(n)的空间复杂度,像遍历这样的基木操作,吋间复杂度也是0(n)。另一方而,一个简单的数据结构可以有更多的处理手段,也适应于更多的算法。例如,在图结构丄,一般只能进行连通性判断,流算法(事实上,流算法实现小利用到了树结构)等;而在树结构上,就可以实施树型动态规划;更进一步,对于线性结构而言,DP(DynamicProgramming,动态规划)的形式更加灵活,而且还可以使用线段树,树状数组等工具;另外,如果线性结构辅助序关系,那么各种平衡BST(BinarySearchTree,二叉搜索树)也能有用武之地。本文将提出三种常见的化繁为简的手段提炼:忽略无效信息,减少存储规模(H)压:调整存储方式,化简存储结构(iii)缩:合并重复信息,,其一:两维对称,即矩阵的情况;其二:两维不对称,即一个线性表,它的每个元素都是一维结构,审数组是常见的情况。下而我们分别就这两种情况举个例子。问题一:ural1568Traincarsorting问题描述:对于一个序列仏},定义一种操作,将a变成b,使得:h}=aX},b2=a心…bs=抵,®+2=ay2...bs+t=ay,□其中s+t=n,<x2<...< ,<y2<...<yt,{x,,x2...xs,y},y2... }={L2,3…n}。例如:12345可转化为13524o给出「-个序列{爲}(满足{爲}是1到n的-个排列),求…种方案,通过最少的操作次数是它变成升序序列。这一题从题面看,操作的定义比较复杂,没有一个明显的切入点,很难设计出一个能有效解决它的算法。其实只要找到题FI屮涉及的操作对应的不变量,问题就能迎刃而解。为算法刻画和证明的方便,引入以下定义:称一个pxq的矩阵A为序列{%}的母矩阵,当且仅当,矩阵A中的所有非零元素,自上到下自左到右逐列读出得到{色},自左到右自下到上逐行读出得到升序序列。称序列{〜}的所有母矩阵中,行数列数都最小的那个矩阵为序列{%}的最简母矩阵。‘50、例如:当n=5时,{5,3,2,4,1}的最简母矩阵为寸fH1丿本题的算法只需要完成以下步骤即可。⑴判断半前{色}是否是升序序列,若是则打印输出结束程序,若否转(ii)计算{。“}的最简母矩阵A(设A是一个pxg的矩阵)对{%}进行如下题意屮的操作:A的偶数行全部非零元索自左到右自上到下逐行读出得到小・・心,A的奇数行全部菲零元素口左到右口上到下逐行读出得到勺+訥+2・・0+$。重复⑴。算法证明如下:行的矩阵。只需证明:算法屮给出的解是最优的,即操作步骤最少的。首先:"Xq的