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

1、解决空间规模问题的几种常用的存储结构广西柳州铁路第一中学龙种【关键字】空间规模、存储结构【摘要】空间规模型问题是近年来国际国内比赛的热点。这类问 题对选手们掌握运用各种数据存储结构的能力提出了更高的要 求，本文站在解决空间规模型问题的角度，深入分析了几种常用 的数据存储结构，在这一类特殊问题当中表现岀来的一些新的特 点，总结了链式结构中的单链表、双链表和树型结构，矩阵结构 各自的长处和短处，特别是通过一题多解比较说明了矩阵结构具 有很大的潜力。论文对三道国际国内竞赛题作了详细的分析总 结，这对于参加国际或国内比赛的选手来说具有很强的现实意义正文一、引论“规模” 一词在现代汉语词典里的解释为“某

2、一事物包描的范围”，而 在计算机程序设计屮，我们可以把它理解为程序运行时在空间和时间等方面的开 销。它主耍包括两个方而：空间规模和时间规模。它们都是在设计算法、编制程 序时经常要考虑到的问题。存储结构，就是数据元素和元素z间的关系在计算机 中的表示，它是为解决空间规模问题，或是通过解决空间规模问题间接地解决时 间规模问题而总结的一些存储方法。近年來，在信息学竞赛中出现了一类新型问题，这些问题的共同特点就是输 入数据非常之大，可达到1m甚至几m,我们不妨称这类问题为空间规模型问题。 众所周知，用turbo pascal编程时仅使用最大为640k的常规内存，而仅凭这点 有限的内存完全不可能把它们一

3、一都存下来，这给我们对数据存储结构和以及设 计算法提出了更高的要求。（见注|）程序是算法和数据结构的有机结合，而本文着重从数据结构的角度出发，针 对数据规模型问题，重新研究一下儿种常用的存储结构的运用情况和它们体现出 来的新的特点。二、几种常用的数据结构通过对国际国内比赛屮关于这类问题的存储结构模式进行仔细的研究，我发 现解决这类问题常用的存储结构有三类：链式结构、树型结构和矩阵结构。下面我就这三种结构一一来分析它们在这类问题中的应用悄况，并比较它们各自的优 点和缺点。1 链式结构在链式结构中常用的两种是单链表和双链表，我们先从一个简单的例子说 起。【问题1】最佳游览路线（n0l97第二试第一

4、题）某游览区街道成网络状，东西向的街道是旅游街，只能由西向东走，并有一 定的分值，南北向的街道是林前道，既可从南向北走，也可从北向南走，没有分 值，要求从某一路口开始游览，并在另一路口结束游览，使所走过的街道分值总 和最大。其中1w旅游街道数冃w100, 1w林荫道数fl <20001, -100w分值w 100c【分析】初看起来，此题规模非常可怕（100*20001二2000100）,我们不可能 存下如此庞大的规模。但细想起来，由于只能由西向东走，所以说每一纵行至多 只能通过一次，而对于同一纵行的旅游街，我们可以通过林荫道自由到达任意一 条旅游街，为了达到题目最佳的要求，我们只需走分值

5、最大的街道就可以了，因 此在存储时只需记录每一纵行中最人的分值即可，这样存储结构由二维变成一 维，所用空间为20001个shortint。再进一步分析，可以发现：若a-b是一条 最佳浏览线路，c是a->b中间一点，那么在子线路a->c±的分值一定非负，否 则c->b的分值一定大于a->b的分值。定义pi为以i结尾的最优路径分值的总和，ai表示第i纵行的最人分值， 我们可以得到一个状态转移方程：严=卩+儿化+人非负数）0（片+4非负数）边界条件：p0 = 0目标：求max pi通过转化，我们就可以在读文件的同时将二维数据转化为一维，然后先从p1 算起，每算一次p

6、i只需作一次判断，计算完pi后又立即转入pi + i的计算，直 至处理完所有元素为止（见程序1）。我们可以把它的结构表示：an图1-1这就是我们熟知的单链表，它在问题中表现为：对于处理当前的元素，无需 冋头查找在此之前的元素（因为前边的元素对它影响有限，可直接用几个变量表 示出来）。对于这种表现，可以总结出单链表结构对于解决空间规模数据问题的 特点.' 效率高，用此结构编出来的程序正常情况下一般不会存在时间问题。道 理很简单，因为对于每一个元素的处理只进行极有限的几次运算，复杂度较低（见 注2）； 由于单链表结构过于简单，在具体算法设计中对元素之间逻辑关系反映 不够（只有在和邻元素之间

7、有一条单向边），所以说单链表结构在解题时有很大 的局限性，对于难度较大的题日则很难用它来实现。但是作为如此高效的结构， 它仍是我们设计程序时努力的一个方向。链式结构中的双向链表也是在程序设计中应用频繁的数据结构，它可以表示图1-2为:其中每个单元除了存放元素外，述有一个前趋和后继指针，这在一定程序上 解决了单链表表示元素之间的关系过于简单的缺陷，但使用双链表时应当注意尽 量控制向前查找的深度，因为此类问题输入数据中包含的元素十分庞大，处理不 当会大大增加程序时间规模。因此双向链表也有一定的局限性，为了进一步把它 的特点分析透彻，我们将在下文继续论述。2 树型结构树是我们熟悉的数据结构，具中最有

8、代表性的是二义树，这是一种特姝的非 线性结构，在程序设计中有着广泛的应用。【问题2 contact （101 ' 98第一试第一题）从由01串构成的文件屮，找出长度介于a和b之间岀现次数最多的n个不 同频率的子串，子串可以相互覆盖，输出结果必须按子串出现频率的降序排列， 频率相同的子串按长度降序排列，频率和长度均相同的子串则按其对应数值降序 排列。其中0vawbw12, 0vnw20,输入文件可达到2mb。【分析】这道题要求完成以下两步操作： 找出所有满足条件的子串，并统计各子串出现的频率； 把所有不同子串按要求排序输出o其中第步是关键。让我们先从具体实例开始研究，长度为1的串只有两个

9、: “0”和“1”。长度为2的串有4个：“00”、“01”、“10”、“11”，它们可以看成 是在长度为1的子串后添加“0”或“1”得到。同样，长度为3的串又可以看成是在长度为2的了串后添加上“0” 或“1 ”得到，例如“ 101 ”是在“ 10”z后添加“1”得到，以后也可依此 类推。这样层层递进的关系使我们想 到了树。以下是一棵二叉树，最上的 为根结点，定义每个结点的左枝为0 右枝为1,这样一个子串可以与这棵 二叉树中的一条路径 对应，如图 2-1所示：树中的每个点赋予一定的权值， 表示该点对应的子中在文件中出现 的频率，那么我们可以得到一些累加规律，例如当21, b二3时，某个中间状态

10、对应的二叉树为：假设现在读到一个串为“011”，其中以“0”开头且长度为1到3的子串有 三个：“0”、“01”、“011”，统计时应将这三个子串的频率加1,从图上可以直观 地看到，这个操作相当于在对应的01路径上将齐结点的频率加1,如下图所示:鉴于对应二叉树的结点很少（最大为213-1=8191）,完全可以多次遍历，图2-3不难从屮找出前n个频率最大的子串，然后按从大到小的顺序输出。（见程序2） 由这个问题我们可以看出，比起单链表来，树型结构小每一结点与其它结点 的联系是一对多的，这样更有利于我们处理好数据。特别地它在处理空间规模问 题表现出来的特点是： 规律性强。如果新代结点与子代结点之间的

11、关系建立得好，那么就可以把 庞大的元素安排得井井有条，就可以按照一定的顺序逐层深入，解决当前元素的 处理。 可操作性强。我们对树的各种操作方法都较为熟练，在解题当屮，只耍我 们根据题冃特点，建立好树的各种关系，其它的操作（如查找、打印）就迎刃而 解了。3、矩阵结构我们一般用一个二维数组来表示炬阵结构，它有x、y两个方向，我们在实 际操作中常用的表示方法是：x轴表示数据的元索，y轴表示元素各种状态条件。 数组内具体的值表示元素齊当前状态条件下的表眄一般用数值表示。如图所示:al, n a2, n . am, n状态条件yaam*n 二al, 2 a2, 2 . am, 2al, 1 a2, 1

12、. am, 1 x数据元素图3-1我们可以按照这种思想对问题2进行进一小的研究：【问题2续contact （101 '98第一试第一题）【分析2续】我们对此题继续分析述可以发现，每一个仅由0和1组成的子串 也可以当作二进制数转化为十进制数来表示。然而每个十进制数与01串z间并 不是一一对应的关系，如“01”、“010”和“0010”它们对应的十进制数都是2, 这是为什么呢？原來，在二进制中，10、010和0010表示的是同一个数，但字 串“10”、“010” “0010”就不是同一字串了，因为这时“0”不是代表没有而是 一个字符，它们之间存在着长度的差别，为了把长度不同而转化为十进制数

13、却相 同的字串区分开来，又设定了 “长度”座标，这样，一维数组变成了二维短阵， 简单表示为下图：01串的长度am*n= a对应数字串出现的频率01串对应的十进制数图3-2从表屮我们可以查找出频率最人的前n个串，然后按要求输出（见程序3） 相比较起來，由于程序3用数组操作，程序2要多次递归，后者比前者简洁, 速度也快一些，请看下面列表分析（前2个为国际比赛中较大的2个，后两个口 编，略大于2mb）：（见注3）程序数据1数据2数据3数据4程序21. 4s23s5. 8s6. os程序30. 5s1. 2s3. 9s3. 5s由于在矩阵结构中结合了数学的二进制计算，使程序效率进一步提高。是不 是矩阵

14、结构有着很大的潜力呢？其实，矩阵结构还能结合其它很多数学模型，其 屮还包括动态规划，我们常常在使用它解决一些难题时收到了意象不到的效果。 现在我们不妨再分析一个问题。【问题3】隐藏代码问题codes （tot, 99试题）题目详见99试题。【分析】本题主要解决两个重点 找最小右隐藏序列； 找到最小右隐藏序列后，找出包含代码字最大长度和的互相不覆盖的隐 藏代码。后一个问题较为简单。定义序pj为从文本开头到第i个字母止互相不覆盖的 隐藏代码包含的代码长度和的最大值。在没有找到以j结尾的隐藏代码时，pj=o；若当前找到一个以i开头，j结尾的且匹配代码字长度为l的隐藏代码，即 可列出如下方程：pi=m

15、axpj, pk+l lwki p0=0h标：maxpj lwjw文木长度可是，题日给出文本长度不是一百万的吗？其实，最小右隐藏序列不超过 10000,所以不同的个数至多也只有一万个，所以我们在实际编程序时，不必以 j作为下标就行了。现在，我们集中精力解决最小右隐藏序列问题，实际上，我们还得找出最小 右隐藏序列，例如，有两个码字tun、nir和一个文本tunntr,其实nnir也是 最小右隐藏序列（根据定义）然而我们若按它计算，只能找到tun或nnir,所 以说，我们在设计算法时必须要按最短的（也就是nir）计算。继续往下思考，我想出了两种方法，它们使用的是不同的存储结构，现供大 家比较分析方

16、法a：我们在读到一个字符时，可以开利用一个数组pi,它表示是 第i种代码字到当前字符时匹配到的最大长度（指述没有匹配完）例如：文本 代码字为all, aaalal,我们可以如下实现aaalalp->111223这样到最后一个字符时就有了一个隐藏代码了。但是我们还不能确定它是不 是最短最小左隐藏序列，不能确定它的长度是否在1000以内，所以必须冋归， 也就是说从最后一个字符找起，按次序把从尾到头每一个字符找出来，直到找到 第一个字符为止，（最多只冋杳999个字符，若还没有找完，就说明隐藏代码超 过1000）aaalal1233 这样我们找到的就是最短最小右隐藏序列。经过这样的分析，我们可以

17、知道方法a采用的是双向链表的存储结构，如下图:i/nv'/ini/lkii/lkiv f1000 1001当前元素最人回扫路径图3_3但在此同时，我们也应注意到，在最坏的情况下，回扫深度为1000c我们 在前边己经分析过进行双向链表回扫时深度不能太人，然而这道题有它特殊的一 面；最小右隐藏序列不超过10000个，所以说回归的次数不会很多，算法理论上 来说是可行的，但是从精益求精的角度来说，我们还应继续探求更适合本题的一种结构。方法方法a的双链结构虽然还不是很理想的，但它给了我们不少启示。 最重要的，它注意到了应该把目前匹配到的位置记下來，从而我们的查找就有一 定的方向，这是必须予以肯定

18、的。然而方法a却忽视了要记录隐藏序列的起始位 置。为了找到当前隐藏序列的起始位置，进行了盲目的回扫，极人地浪费时间。 我们自然地就想：能不能在匹配当中就把它的起点记下来呢？这也许行得通。那 么，记下了起始位置的同时，还要不要像方法a样述把当前匹配到的代码字位 置记下来？我们注意到了在介绍方法a时用的例子aaala,若在后边再加一个l, 变成malall,那么这出文本就有了两个最短最小右隐藏代码malall,具中第 二个l就有双垂身份：在alal中代表代码字的第三个字符，在all中代表代码 字的第二个字符，这样，同一个文本中的同一个字符由对对应的隐藏代码起始位 置不同，在同一个代码字屮就有了不同

19、的对应状态，这也是方法a没有处理好的。 那么，该怎样处理了，在矩阵结构的分析当中我们曾经介绍过，矩阵中的y轴方 向一般是用来表示元素在不同的状态下的，我们也不妨这样定义：x轴为各代码字编号，y轴为各代码匹配到的位置（即第几个字母），px,y 表示离当前读到的示符最近的会有第1种代码字前1个字母的最短最小隐藏方列 在整个文述中的起始位置。注意：现在的x轴已经依题意有所变动，表示的不再是当前读到的字符了。同时，我们也清楚,此时矩阵中同一纵行元素之间关系 密切，而同一横行的元素之间没多大联系，我们就可以这样表示：代码字图3-4有了存储结构，我们就可以试着推导一下算法。pm, npm, 2pm, 1p

20、x, y表示定义：pi, j表示离当前读到的字符最近的含有第i种代码字前j个字母的最 短最小右隐藏序列在整个文本中的起始位置，当还未找到时,pi.j-oo> l<i<=n, l<=j<=length（i）, length （i）表示第i个代码字的长度。根据定义，第i个代码字的pi.j的值可以前jl个的值（即pji）决定，而条件是 文本小读过的字母已经与该代码字的前jl个字母匹配，同时当前读取的字母又 与代码字的第j个字母相等，这样可以对pi.j的值进行修改。假设:aij表示第i种代码字的第j个字母（1 <=i<=n,l <=j<=lengt

21、h（i） o nowchar 表示当询文本中读到的字母，nownum表示当前读到的文本字母的序号。若满足以下关系： ai,j=nowchar（即当前读取的字母乂与第i个代码字的第j个字母相等）且 j= 1 （即是代码字的第一个字母）或 j>l（即不是代码字的第一个字母）月.pij-i>0（即文木屮读过的字母已经与 该代码孕的前jl个字母匹配）且nownum+ pij-i+l<=1000（e|j隐藏序列长度不超过 1000）o则有下式成立： 当 j=l 时，pi,j=nownum； 当 j>l 时，pi,j= pij-lo当pi,ixngth（i）<>0,即当

22、j推到length（i）时，就找到了一个合乎要求的“最短最 小右隐藏序列”，其编号为i,起始位置为pi,length,终点位置为nownumo 同时，当我们从文本中读到一个字符时，要知道它在各个代码字屮的位置， 可以在所有的代码字屮一个一个的查找，但这样效率不高，考虑到所有代码字的 字符总数最多只有100*100个，因此可以按照字母的各类，把含有该字母的代码 字的编号记录下来，这样查找可大大提高效率。在推算过程中我们发现，在任一码匹配中，总是先从第一个开始匹配，第一 个匹配到了，再考虑第二个这样，我们容易看出，在每一纵行之间的关系 实际上是单链表结构pi,n相当于pi, 2pi, 1图3-5我

23、们在前边还说过，使用单链表的效率一般是很高的，方法b应用了单链表 组成的矩阵，推导出了动态规划递推公式，免去冋扫的复朵度，值得我们再编一 次程序（见程序4）。运行结果也在我们的意料z中，方法b远优于方法a。以下 是种方法对应测试数据的运行时间（前3个为国际比赛中最后3个数据）。数据1数据2数据3数据4方法a3. 4 s2. 8 s40 s9. 9 s方法b0. 5 s0. 3 s11 s5. 1 s根据上面两个例子，我们对矩阵结构有了较深刻的理解。那么，为什么使用 矩阵结构解决空间规模问题有着很人的潜力呢？我们在题冃的分析中已经看出 了不少，现在把它作一下归纳总结： 矩阵结构发扬了链式结构简单

24、明了地表示元素状态的优点。它使用数组 操作，而一般的数组操作速度与链表一样是很快的。 矩阵结构也很好地反映了树型结构清晰地反映元素之间的联系的思想， 同时具有一些树型结构没有的优点。a、（x、y）坐标的查找远比树的遍历方便b、 x、y轴的意义可以更好地结合数学方法定义。这样使用矩阵结构就具有更广阔 的思维空间。 矩阵结构能够通过综合的方法把链表等其它结构嵌套在内部，从而加强 它解题的灵活性，而这一点是非常重要的。所以说，我们在设计存储结构、算法时，矩型结构是不能忽视的，不过也不 能说矩阵结构是万能的，不能忽视其它结构在解题当屮的运用。三、小结要用一个小小的程序解决几兆的数据处理问题，确实不易，

25、而要编程序解决 国际国内这些带有隐蔽性条件约人数据处理问题，那就更不容易了。不过，通过 上面的分析我们可以发现，这类问题还是有一定规律性的，我们应该在平时做到, 对关于数据结构的各种算法精益求精，不能光拘泥于一般的处理算法，更要研究 每种存储结构在某些特殊问题中的特殊处理方法，并且要多多总结每种结构在不 同情况下表现出来的优缺点，培养自己判断分析的能力和权衡得失的能力。这样, 我们的思路才会更加开阔，编程的效果才会更好。最后，我们再把这几种解决空间规模问题常用的存储 结构的特点总结一下 (均指在一般情况下)结构类别所需 空间操作 速度体现元 素联系应用 范围在空间规模型问题屮对应的处 理手段链

26、式 结构单链表少快少窄直接一步递推，不需回扫双向链表少较慢多较广冋头查看与当前读到元素有关信 息树型结构多一般多较广把元素之间联系具体化，一般 用递归手段矩阵结构多较快很多广递推(包扌占动态规划)必要时进 行一定的回查附录注1、因为n值很大，任何在处理一个个数据元素时的延时手段都能产生积累 效应，而使程序异常地慢，所以我们应对平时一段的数据操作算法精益求精。注2、这里不用常用的0(2k)作算法复杂度的衡量，因为数据规模(即n值)很 大，0(pt2)的时间复杂度显然就不能承受了，更重要的，即使是o(k*n)当k值 很人时，程序也不能在规定时间内通过。注3、所有运行指标在pitt450 ±

27、;得到。程序分析以下4个程序的输入、输出文件名及格式均是按照原试题的要求设置的程序1：$a+, b-, d+, e+, f-, g-, i+, l+, n-, 0-, p-, q-, r-, s-, t-, v+, x+$m 65520,0,655360)var m旅行街, n林荫道 : integer;a当前游览分值(用于递推) ,b 最人游览分值 : 1 ongint;t:array1. 20001 of integer; 存放各纵行最大值procedure input; 输入数据，存下各纵行最大值var f:text;i, j, k: integer;beginassign(f,'

28、; input txt'); reset (f);read (f, m, n) ; dec (n);for i : = 1 to n do ti :=-maxint; 设置最小值，开始寻找for i:=1 to m dofor j:=l to n dobeginread (f, k);if k>tj then tj :=k; 各纵行只保留最大值end;close(f);end;procedure main; 递推求出结果var i,j:integer;begina:=0; b:=0;for i:=1 to n dobegininc(a, longint(ti); 累加 aif a

29、<0 then a:=0; 若a为负，舍去以前所有状态，清零if a>b then b:=a; 若a优于b,用a的值作为当前b的最优值 end;end;procedure print; 打印结果var f:text;beginassign(f,' output, txt');rewrite (f);write in (f, b);close(f);end;begininput; 输入数据，存下各纵行最大值main; 递推求出结果print; 打印结果end.程序2：$a+, b-, d+, e+, f-, g-, i+,l+, n-, 0-, p-, q-, r-,

30、 s-, t-, v+, x+$m 65520, 0, 655360const inputfi1e = 5 contactin'outfile = ? contact. out，;tc: array 1. 13 of integer= (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096); 对应的二进制数分别为1、10、100、1000便于取位查找type r= rr;rr=recordzero前字符是0时刈应的轨迹方向, one当前字符是1时刈应的轨迹方向 : r; num当前轨迹对应子串出现的频率数:longint;en

31、d;ar=string12; 子串的具体方案var t:array1. 21 of longint; ft大的前20个频率数(为了排列方便设置第21个) tch:array1. 1024 of char; 缓存设置tree:r; 状态树的根结点inf,outf:text;a, 13小题口规定的输入变量,long当前处理的有效子串长度, now 排列总数时记录当 前已有的不同的频率数,which当询要查找输出的频率数所在位置, where在第儿层中查找 :byte; 丫讥截収有效长度的标准, m有效子串的表达 : integer;procedure maketree(floor:byte; 当前

32、层数(根结点为第0层) var卩:讥当前指针)；生 成空树beginnum:=0; 总数初始值为零if floor=b已牛成到叶子结点 thenbeginp" zero:=nil;p one:二n订;左右指针均为空enclelsebeginnew (pl zero) ; 生成它的孩子结点maketree (floor+1, p zero);new(p one);maketree (f loor+1, p one);end;end;procedure i ni t; 程序初始化beginreadln(inf, a, b, n) ; 输入 a、b、n 值，便于建树new(tree) ;

33、设置树的根结点maketree (0, tree) ; 生成空树end;procedure add (floor: byte; 层数 var p:r 当前指针所在处) ; 逐层累加begininc (p num) ; 总数累加if floor<long then判断是否已走到头if (m and tclong-floor)=0) 判断当前位置对应的值,决定下一步的指针轨迹 then add(floor+l, p zero)else add(floor+l, p"onc);end;procedure main; 读入数据，累加子串出现的数livar ch:char; 当前读到的字

34、符i:byte; 循环变量beginlong:=0;尚未读到数据，有效长度为零m:=0; 有效串初始值为空yu:=tcb+l;例如,有效长度为2,有效子串就是除以4(二进制为100)的余数所对应的 二进制串repeatread (inf, ch);辻ch二'2' then文件已读完beginfor i :=long down to 1 do 处理剩下的长度不足b的子串beginadd(0, tree);dec(long);end;exit;end;m: = (m*2+tzch) mod yu; 生成当前有效子串inc (long);if long二b then若长度为b则进行逐

35、层累加beginadd(0, tree);dec (long) ; 控制有效长度end;until false;end;procedure find(floor:byte; p:r) ; 排列出最大的 20 个频率数var i, j:byte; 循环变量beginif floor>=a长度在要求范围之内 thenbegin插入排序法j:=now;while (j>0) and (tj<p num) do dec(j);if jn thenbeginif (j=0) or (tj>p num) thenbeginif now<n then inc (now);for

36、 i:=now-l downto j+1 do ti+l:二ti;t j+1 :=p num;end;if floor<b then继续寻找beginfind (floor+1, p zero);find(floor+1, pl one);end;end;endel sebcgin继续寻找find(floor+l, p zero);find(floor+l, p one);end;end;procedure look_up(floor:byte; 层数 p:r; 指针 ss:aro前子串状态) ; 按顺序输出 符合要求的子串beginif (floor二where) and (p num

37、=twhich) then满足层数、频率要求的就打印write(outf,' ', ss);if (floor<where) and (p. num>=t which) then继续往下寻找begin相同频率、相同长度的子串按数值从大到小输出look_up (floor+1, p one, ss+ v );look_up(floor+l, p zero, ss+ o');end;end;procedure print; 输出具体方案 beginnow:=0;fillchar(t, sizeof(t), 0);find(0, tree); 排列出最大的20个频

38、率数assign(outf, outfile);rewrite(outf);scttextbuf (outf, tch);for which:=l to n do按频率数从人到小的顺序输出beginwrite(outf, twhich);for where :=b down to a do相同频率数的子串按长度从人到小输出beginlook up(l, treel one, t)；look up(l, treel zero,' 0)；end;writeln(outf);end;close(outf);end;beginassigr)(inf, inputfi 1c);reset (in

39、f);settextbuf(inf, tch);init; 程序初始化main;读入数据,累加子串出现的数目close (inf);print; 输出具体方案encl.程序3：$a+, b-, d+, e+, f-, g-, i+, l+, n-, 0-, p-, q-, r-, s-, t-, v+, x+$m 65520,0,655360const inputf ile = 'co nt act. in'outfile = j contact, o；tc : array 1. . 13 of integer二(1, 2, 4, 8, 16, 32, 64, 12&

40、256, 512, 1024, 2048, 4096);对应的二进制数分别为1、10、100、1000便于取位查找put:array1. . 12 of integer=(l, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095);对应的二进制数分别为1、11、ilk 1111便于取字串的后1、2、3位tz: array * 0' .' 1' of byte= (0, 1) ; 字符转数值type ar=array04095 of iongint; var t :arrayl. . 21 of longint; 最大的20

41、个频率数(为了排列方便设置第21个) tk :array1. 12 of "ar; 保存各种子串出现次数tch:array1. . 1024 of char; 缓存设置inf, outf:text;a,b,n题目规定的输入变m,long当前处理的有效子串长度,kind排列吋记录当前己有的不同的频率数 :byte;yu: integer; 截取有效长度的标准procedure init; 程序初始化var i : byte; 循环变量beginreadln(inf, a, b, n) ; 输入 a、b、n 值,便于初始化for i : = 1 to b do 初始清零begi nnew

42、(tki);fillchar(tki sizeof(tki ), 0);end;end;procedure main; 读入数据，累加子串出现的数目var i:byte; 循环变量ch:char; 当前读到的字符m: integer; 有效子串的表达beginm:二0;有效串初始值为空 long:二0;尚未读到数据，有效长度为零yu:二tcb+l;例如,有效长度为2,有效子串就是除以4(二进制为100)的余数所对应的 二进制串repeatread (inf, ch);if ch二'2' then exit; 文件已读完,退出m: = (m*2+tzch) mod yu; 生成当

43、前有效子串if long<b then inc (long); 计算当前有效子串长度for i :=1 to long do inc (tk i" m and puti);累加以当前读到的字符结尾的有效 子串长度until false;end;procedure sort; 排列出最人的20个频率数var i, j, k, ii: integer; 循环变量beginfillchar(t, sizeof (t), 0);kind:=0;将所有可能的子串一一寻找for i:=a to b dofor j:=0 to puti dobegink:=kind;插入排序法whi 1 e

44、 (k>0) and (tki" j>t k) dodec (k);if (k<n) and (k=0) or (tki厂j>tk) thenbeginif kind<n then inc(kind);for i i:=k ind downto k+1 dotii+l:=tii;tk+l:二tki" j;end;end;end;procedure print; 按要求输出结果var ii, i, j, 1 循环变量, p生成具体方案的过渡变量 : integer; beginassign(outf, outf i lc);rewrite (ou

45、tf);settextbuf (outf, tch);for ii:=l to n(10按频率数从大到小的顺序输!11beginwrite (outf,t i i);for i :=b downto a do相同频率的子串按长度从大到小输出for j:=puti downto 0 do相同长度的子串按数值从大到小输出 if tki厂j二tii thenbeginwri te(outf,'');p：=j；for 1 :=1 to i do打印具体子串beginwrite(outf, p div tci+lt);p:=p mod tci + lt;end;end;writein(o

46、utf);end;close (outf);encl;beginassign(inf, inputfile);reset (inf);settextbuf (inf, tch);init; 程序初始化main;读入数据,累加子串出现的数目close(inf);sort; 排列出最大的20个频率数print; 按要求输出结果end.程序4：$a+, b-, d+, e+, f-, g-, i+, l+, n-, 0-, p- q-, r-, s-, t-, v+, x+$m 65520, 0, 655360const inputfile = 'words, inp'textfi

47、le = text. inp，;outfile= 'codes.out'type rrr=动态规划存储数据recordnum:byte; 代码字编号叩前一代码字 : integer;tot 当前最大代码字长度和, start, finish起止位置 : longint;end;ar=array1. 100 of longint; 存放当前的代码字与文本的匹配情况aaa= aar;aar=record 字符在各代码字中的出现情况num代码字编号,ci此字符在代码字中的iii现位置:byte;next:aaa;end;var inf,outf:text;rm 隐藏代码数tl, 口代

48、码字数tl, findwz最大值出现的最末尾位置 : integer; m当前读到的文木位置, findmax最大代码字长度和 : longint;tn:array1. 10000 of "rrr;start:arrayl100 of "ar;tl:array1. 100 of byte; 各代码字长度tv:array1. 1024 of char;t: array f al ' z" of aaa;pp:aaa;procedure put in(cch:char; 具体字符 nnum代码字编号, nci :byte 出现位置) ； 记下字符所在位置beg

49、innew(pp);pp next: =t cch i next;t cchl n ext:二 pp;wi th pp" dobeginnum:=nnum;ci:二nci;encl;end;procedure init; 读代码字文件,初始化 var i, j:byte; 循环变量ii ：char; 循环变量s:string; 过渡变量beginassign(inf, inputfi 1 e);reset (inf);settextbuf (inf,tv);read ln(i nf, n);for ii:二'a' to，7! do t 数组初始化if ii in la

50、. z, a., z thenbeginnew(tii);t ii厂.next :二nil;end;for i: = l to n do初始化、存放数据beginnew(start i);fi 1 lchar (start i : sizeof (start i 厂)，0); readln(inf, s);tl 订:=ord(s0);for j : = 1 to tl i do 记下字符所在位置 put_in(sj, i, j);end;close(inf);end;procedure clear(snum:byte) ; 同值淸零var i:byte;now: longint 过渡变量;be

51、ginnow:二startsnum"tlsnum;startsnum八t1snum:=0;for i:=tlsnum-l downto 1 doif startsnum"i>now then exitel sestartsnum”i:二0;end;procedure cl (sstart: longint; snum:byte); 用动态规划来计算当前匹配到的最大值 var i, j, k, maxwz在当前隐藏代码之前的最大值所在位置 : integer;maxtot 在当前隐藏代码之前的最大值, pnow当前目标最大值 : longint;b:boolean; 布尔标记beginmaxtot:=0; maxwz:=0;i:二 1;while (i<