算法合集之《解决空间规模问题的几种常用的存储结构》

1解决空间规模问题的几种常用的存储结构广西柳州铁路第一中学龙翀【关键字】空间规模、存储结构【摘要】空间规模型问题是近年来国际国内比赛的热点。这类问题对选手们掌握运用各种数据存储结构的能力提出了更高的要求，本文站在解决空间规模型问题的角度，深入分析了几种常用的数据存储结构，在这一类特殊问题当中表现出来的一些新的特点，总结了链式结构中的单链表、双链表和树型结构，矩阵结构各自的长处和短处，特别是通过一题多解比较说明了矩阵结构具有很大的潜力。论文对三道国际国内竞赛题作了详细的分析总结，这对于参加国际或国内比赛的选手来说具有很强的现实意义正文一、引论“规模”一词在《现代汉语词典》里的解释为“某一事物包括的范围”，而在计算机程序设计中，我们可以把它理解为程序运行时在空间和时间等方面的开销。它主要包括两个方面：空间规模和时间规模。它们都是在设计算法、编制程序时经常要考虑到的问题。存储结构，就是数据元素和元素之间的关系在计算机中的表示，它是为解决空间规模问题，或是通过解决空间规模问题间接地解决时间规模问题而总结的一些存储方法。近年来，在信息学竞赛中出现了一类新型问题，这些问题的共同特点就是输入数据非常之大，可达到1M甚至几M，我们不妨称这类问题为空间规模型问题。众所周知，用TurboPascal编程时仅使用最大为640K的常规内存，而仅凭这点有限的内存完全不可能把它们一一都存下来，这给我们对数据存储结构和以及设计算法提出了更高的要求。(见注1)程序是算法和数据结构的有机结合，而本文着重从数据结构的角度出发，针对数据规模型问题，重新研究一下几种常用的存储结构的运用情况和它们体现出来的新的特点。二、几种常用的数据结构通过对国际国内比赛中关于这类问题的存储结构模式进行仔细的研究，我发现解决这类问题常用的存储结构有三类：链式结构、树型结构和矩阵结构。下面2我就这三种结构一一来分析它们在这类问题中的应用情况，并比较它们各自的优点和缺点。１．链式结构在链式结构中常用的两种是单链表和双链表，我们先从一个简单的例子说起。【问题1】最佳游览路线(NOI’97第二试第一题)某游览区街道成网络状，东西向的街道是旅游街，只能由西向东走，并有一定的分值，南北向的街道是林荫道，既可从南向北走，也可从北向南走，没有分值，要求从某一路口开始游览，并在另一路口结束游览，使所走过的街道分值总和最大。其中1≤旅游街道数目≤100，1≤林荫道数目≤20001，-100≤分值≤100。【分析】初看起来，此题规模非常可怕(100*20001=2000100)，我们不可能存下如此庞大的规模。但细想起来，由于只能由西向东走，所以说每一纵行至多只能通过一次，而对于同一纵行的旅游街，我们可以通过林荫道自由到达任意一条旅游街，为了达到题目最佳的要求，我们只需走分值最大的街道就可以了，因此在存储时只需记录每一纵行中最大的分值即可，这样存储结构由二维变成一维，所用空间为20001个shortint。再进一步分析，可以发现：若A-B是一条最佳浏览线路，C是A-B中间一点，那么在子线路A-C上的分值一定非负，否则C-B的分值一定大于A-B的分值。定义Pi为以i结尾的最优路径分值的总和，Ai表示第I纵行的最大分值，我们可以得到一个状态转移方程：边界条件：P0＝0目标：求Max{Pi}通过转化，我们就可以在读文件的同时将二维数据转化为一维，然后先从P1算起，每算一次Pi只需作一次判断，计算完Pi后又立即转入Pi＋1的计算，直至处理完所有元素为止（见程序1）。我们可以把它的结构表示：这就是我们熟知的单链表，它在问题中表现为：对于处理当前的元素，无需回头查找在此之前的元素（因为前边的元素对它影响有限，可直接用几个变量表示出来）。对于这种表现，可以总结出单链表结构对于解决空间规模数据问题的特点：①效率高，用此结构编出来的程序正常情况下一般不会存在时间问题。道理很简单，因为对于每一个元素的处理只进行极有限的几次运算，复杂度较低（见注2）；②由于单链表结构过于简单，在具体算法设计中对元素之间逻辑关系反映不够（只有在相邻元素之间有一条单向边），所以说单链表结构在解题时有很大的局限性，对于难度较大的题目则很难用它来实现。但是作为如此高效的结构，它仍是我们设计程序时努力的一个方向。非负数）（非负数）iiiiiiAPAPAPPi1110(3链式结构中的双向链表也是在程序设计中应用频繁的数据结构，它可以表示为：其中每个单元除了存放元素外，还有一个前趋和后继指针，这在一定程序上解决了单链表表示元素之间的关系过于简单的缺陷，但使用双链表时应当注意尽量控制向前查找的深度，因为此类问题输入数据中包含的元素十分庞大，处理不当会大大增加程序时间规模。因此双向链表也有一定的局限性，为了进一步把它的特点分析透彻，我们将在下文继续论述。２．树型结构树是我们熟悉的数据结构，其中最有代表性的是二叉树，这是一种特殊的非线性结构，在程序设计中有着广泛的应用。【问题2】Contact（IOI’98第一试第一题）从由01串构成的文件中，找出长度介于A和B之间出现次数最多的N个不同频率的子串，子串可以相互覆盖，输出结果必须按子串出现频率的降序排列，频率相同的子串按长度降序排列，频率和长度均相同的子串则按其对应数值降序排列。其中0＜A≤B≤12，0＜N≤20，输入文件可达到2MB。【分析】这道题要求完成以下两步操作：①找出所有满足条件的子串，并统计各子串出现的频率；②把所有不同子串按要求排序输出。其中第①步是关键。让我们先从具体实例开始研究，长度为1的串只有两个：“0”和“1”。长度为2的串有4个：“00”、“01”、“10”、“11”，它们可以看成是在长度为1的子串后添加“0”或“1”得到。同样，长度为3的串又可以看成是在长度为2的子串后添加上“0”或“1”得到，例如“101”是在“10”之后添加“1”得到，以后也可依此类推。这样层层递进的关系使我们想到了树。以下是一棵二叉树，最上的为根结点，定义每个结点的左枝为0右枝为1，这样一个子串可以与这棵二叉树中的一条路径一一对应，如图2-1所示：树中的每个点赋予一定的权值，表示该点对应的子中在文件中出现的频率，那么我们可以得到一些累加规律，例如当A=1，B=3时，某个中间状态对应的二叉树为：4假设现在读到一个串为“011”，其中以“0”开头且长度为1到3的子串有三个：“0”、“01”、“011”，统计时应将这三个子串的频率加1，从图上可以直观地看到，这个操作相当于在对应的01路径上将各结点的频率加1，如下图所示：鉴于对应二叉树的结点很少（最大为2^13-1＝8191），完全可以多次遍历，不难从中找出前N个频率最大的子串，然后按从大到小的顺序输出。（见程序2）由这个问题我们可以看出，比起单链表来，树型结构中每一结点与其它结点的联系是一对多的，这样更有利于我们处理好数据。特别地它在处理空间规模问题表现出来的特点是：①规律性强。如果新代结点与子代结点之间的关系建立得好，那么就可以把庞大的元素安排得井井有条，就可以按照一定的顺序逐层深入，解决当前元素的处理。②可操作性强。我们对树的各种操作方法都较为熟练，在解题当中，只要我们根据题目特点，建立好树的各种关系，其它的操作（如查找、打印）就迎刃而解了。３、矩阵结构我们一般用一个二维数组来表示矩阵结构，它有x、y两个方向，我们在实际操作中常用的表示方法是：x轴表示数据的元素，y轴表示元素各种状态条件。数组内具体的值表示元素在当前状态条件下的表现，一般用数值表示。如图所示：a1,na2,n…am,n状态条件...5y...Am*n=...a1,2a2,2…am,2A1,1a2,1…am,1x数据元素图3-1我们可以按照这种思想对问题２进行进一小的研究：【问题2续】Contact（IOI‘98第一试第一题）【分析2续】我们对此题继续分析还可以发现，每一个仅由0和1组成的子串也可以当作二进制数转化为十进制数来表示。然而每个十进制数与01串之间并不是一一对应的关系，如“01”、“010”和“0010”它们对应的十进制数都是2，这是为什么呢？原来，在二进制中，10、010和0010表示的是同一个数，但字串“10”、“010”“0010”就不是同一字串了，因为这时“0”不是代表没有而是一个字符，它们之间存在着长度的差别，为了把长度不同而转化为十进制数却相同的字串区分开来，又设定了“长度”座标，这样，一维数组变成了二维短阵，简单表示为下图：01串的长度Y对应数字串Am*n=出现的频率X01串对应的十进制数图3-2从表中我们可以查找出频率最大的前N个串，然后按要求输出（见程序3）相比较起来，由于程序3用数组操作，程序2要多次递归，后者比前者简洁，速度也快一些，请看下面列表分析(前2个为国际比赛中较大的2个，后两个自编，略大于2MB)：(见注3)数据程序数据1数据2数据3数据4程序21．4s2．3s5．8s6．0s程序30．5s1．2s3．9s3．5s由于在矩阵结构中结合了数学的二进制计算，使程序效率进一步提高。是不是矩阵结构有着很大的潜力呢？其实，矩阵结构还能结合其它很多数学模型，其中还包括动态规划，我们常常在使用它解决一些难题时收到了意象不到的效果。现在我们不妨再分析一个问题。【问题3】隐藏代码问题codes（I0I’99试题）题目详见IOI’99试题。6【分析】本题主要解决两个重点①找最小右隐藏序列；②找到最小右隐藏序列后，找出包含代码字最大长度和的互相不覆盖的隐藏代码。后一个问题较为简单。定义序Pj为从文本开头到第i个字母止互相不覆盖的隐藏代码包含的代码长度和的最大值。在没有找到以j结尾的隐藏代码时，Pj=0；若当前找到一个以i开头，j结尾的且匹配代码字长度为L的隐藏代码，即可列出如下方程：Pi=max{Pj,Pk+L}1≤kiP0=0目标：max{Pj}1≤j≤文本长度可是，题目给出文本长度不是一百万的吗？其实，最小右隐藏序列不超过10000，所以不同的个数至多也只有一万个，所以我们在实际编程序时，不必以j作为下标就行了。现在，我们集中精力解决最小右隐藏序列问题，实际上，我们还得找出最小右隐藏序列，例如，有两个码字TUN、NIR和一个文本TUNNIR，其实NNIR也是最小右隐藏序列（根据定义）然而我们若按它计算，只能找到TUN或NNIR，所以说，我们在设计算法时必须要按最短的（也就是NIR）计算。继续往下思考，我想出了两种方法，它们使用的是不同的存储结构，现供大家比较分析方法A：我们在读到一个字符时，可以开利用一个数组Pi，它表示是第i种代码字到当前字符时匹配到的最大长度（指还没有匹配完）例如：文本代码字为ALL，AAALAL，我们可以如下实现AAALALP→111223这样到最后一个字符时就有了一个隐藏代码了。但是我们还不能确定它是不是最短最小左隐藏序列，不能确定它的长度是否在1000以内，所以必须回归，也就是说从最后一个字符找起，按次序把从尾到头每一个字符找出来，直到找到第一个字符为止，（最多只回查999个字符，若还没有找完，就说明隐藏代码超过1000）AAALAL1233←这样我们找到的就是最短最小右隐藏序列。经过这样的分析，我们可以知道方法A采用的是双向链表的存储结构，如下图：……12310001001当前元素最大回扫路径图3-3但在此同时，我们也应注意到，在最坏的情况下，回扫深度为1000。我们在前边已经分析过进行双向链表回扫时深度不能太大，然而这道题有它特殊的一面；最小右隐藏序列不超过10000个，所以说回归的次数不会很多，算法理论上来说是可行的，但是从精益求精的角度来说，我们还应继续探求更适合本题的一7种结构。方法B：方法A的双链结构虽然还不是很理想的，但它给了我们不少启示。最重要的，它注意到了应该把目前匹配到的位置记下来，从而我们的查找就有一定的方向，这是必须予以肯定的。然而方法A却忽视了要记录隐藏序列的起始位置。为了找到当前隐藏序列的起始位置，进行了盲目的回扫，极大地浪费时间。我们自然地就想：能不能在匹配当中就把它的起点