text: 数据结构的在程序设计中的应用
  【关键字】 逻辑结构 存储结构 算法优化
  数据结构作为程序设计的基础，其对算法效率的影响必然是
  本文就如何合理选择数据结构来优化算法这一问题，
  对选择数据结构的原则和方法进行了一些探讨。
  结构的重要性进行了分析，提出了选择逻辑结构的两个基本原则;
  接着又比较了顺序和链式两种存储结构的优点和缺点，并讨论了
  选择数据存储结构的方法;最后本文从选择数据结构的的另一角
  度出发，进一步探讨了如何将多种数据结构进行结合的方法。
  讨论方法的同时，本文还结合实际，选用了一些较具有代表性的
  信息学竞赛试题举例进行了分析。
  "数据结构+算法=程序"，这就说明程序设计的实质就是对确定的问题选择
  一种合适的数据结构，加上设计一种好的算法。
  由此可见，数据结构在程序设计
  因为这其
  中的"关系"，指的是数据元素之间的逻辑关系，因此数据结构又称为数据的逻辑
  而相对于逻辑结构这个比较抽象的概念，我们将数据结构在计算机中的表
  建立问题的数学模型，进而设计问题的算法，直至编出程序并进行调试通过，
  我们要建立问题的数学模型，必须首先
  找出问题中各对象之间的关系，也就是确定所使用的逻辑结构;同时，设计算法
  和程序实现的过程，必须确定如何实现对各个对象的操作，而操作的方法是决定
  因此，数据逻辑结构和存储结构的好坏，将直接影
  响到程序的效率。
  二、选择合理的逻辑结构
  在程序设计中，逻辑结构的选用就是要分析题目中的数据元素之间的关系，
  并根据这些特定关系来选用合适的逻辑结构以实现对问题的数学描述，进一步解
  逻辑结构实际上是用数学的方法来描述问题中所涉及的操作对象及对象
  之间的关系，将操作对象抽象为数学元素，将对象之间的复杂关系用数学语言描
  根据数据元素之间关系的不同特性，通常有以下四种基本逻辑结构:集合、
  这四种结构中，除了集合中的数据元
  素之间只有"同属于一个集合"的关系外，其它三种结构数据元素之间分别为"一
  对一"、"一对多"、"多对多"的关系。
  因此，在选择逻辑结构之前，我们应首先把题目中的操作对象和对象之间的
  关系分析清楚，然后再根据这些关系的特点来合理的选用逻辑结构。
  尤其是在某
  些复杂的问题中，数据之间的关系相当复杂，且选用不同逻辑结构都可以解决这
  一问题，但选用不同逻辑结构实现的算法效率大不一样。
  对于"不可直接使用"的这一类，我们也可以通过某些间接的方式，使之成为可
  以使用的信息，但其中转化的过程显然是比较浪费时间的。
  由此可见，我们所需要的是尽量多的"可直接使用"的信息。
  这样的信息越
  多，算法的效率就会越高。
  对于不同的逻辑结构，其包含的信息是不同的，算法对信息的利用也会出现
  不同的复杂程度。
  因此，要使算法能够充分利用"可直接使用"的信息，而避免
  算法在信息由"不可直接使用"向"可直接使用"的转化过程中浪费过多的时间，
  〖问题一〗 IOI99 的《隐藏的码字》。
  〖问题描述〗
  问题中给出了一些码字和一个文本，要求编程找出文本中包含这些码字的所
  有项目，并将找出的项目组成一个最优的"答案"，使得答案中各项目所包含的码
  字长度总和最大。
  每一个项目包括一个码字，以及该码字在文本中的一个覆盖序
  列(如'abcadc'就是码字'abac'的一个覆盖序列)，并且覆盖序列的长度不超过
  同时，"答案"要求其中每个项目的覆盖序列互相没有重叠。
  〖问题分析〗
  对于此题，一种较容易得出的基本算法是:对覆盖序列在文本中的终止位置
  进行循环，再判断包含了哪些码字，找出所有项目，并最后使用动态规划的方法
  将项目组成最优的"答案"。
  算法的其它方面我们暂且不做考虑，而先对问题所采用的逻辑结构进行选择。
  如果我们采用线性的逻辑结构(如循环队列)，那么我们在判断是否包含某个
  移，依次找出码字 t 从尾到头的各个字母。
  例如码字为"ABDCAB"，而文本图
  1-1，终止位置为最右边的箭头符号，每个箭头代表依次找到的码字的各个字母。
  由于题目规定码字的覆盖序列长度不超过1000，所以进行这样的一次是否包
  含的判断，其复杂度为O(1000)。
  个字母)，而线性结构中拥有的信息，仅仅只存在于相邻的两元素之间。
  简单的信息来寻找码字的某一个字母，其效率显然不高。
  我们要寻找码字中某个字母的前一个字母，就可以直接利用已连接的边，而不需
  用枚举的方法。
  我们也可以把问题看为:从有向图的一个顶点出发，寻找一条长
  度为length(t)-1 的路径，并且路径中经过的顶点，按照码字t 中的字母有序。
  指针p 的移动方向
  通过计算，用图进行记录在空间上完全可以承受(记录 1000 个点×52 条弧×4
  字节的长整型=200k 左右)。
  只需对弧的指向进行整体赋值，并改变其中的某一条弧即可。
  因此，我们通过采用图的逻辑结构，使得寻找字母的效率大大提高，其判断
  的复杂度为O(length(t))，最坏为O(100)，比原来方法的判断效率提高了10 倍。
  (附程序codes.pas)
  对于这个例子，虽然用线性的数据结构也可以解决，但由于判断的特殊性，
  每次需要的信息并不能从相邻的元素中找到，而线性结构中只有相邻元素之间存
  在关系的这一点，就成为了一个很明显的缺点。
  因此，问题一线性结构中的信息，
  相对而言，图的结构就正好满足了我们的需要，
  将所有可能产生关系的点都用弧连接起来，使我们可以利用弧的关系，高效地进
  行判断寻找的过程。
  虽然图的结构更加复杂，但却将"不可直接使用"的信息， 二、 不记录"无用"信息。
  从问题一中我们看到，由于图结构的信息量大，所以其中的信息基本上都是
  "可用"的。
  在某些情况下，图
  结构中的"可用"信息，是有些多余的。
  信息都"可用"自然是好事，但倘若其中"无用"(不需要)的信息太多，就
  只会增加我们思考分析和处理问题时的复杂程度，反而不利于我们解决问题了。
  〖问题二〗 湖南省1997 年组队赛的《乘船问题》
  有N 个人需要乘船，而每船最多只能载两人，且必须同名或同姓。
  求最少需
  要多少条船。
  看到这道题，很多人都会想到图的数据结构:将N 个人看作无向图的N 个点，
  凡同名或同姓的人之间都连上边。
  要满足用船最少的条件，就是需要尽量多的两人共乘一条船，表现在图中就
  是要用最少的边完成对所有顶点的覆盖。
  这就正好对应了图论的典型问题:求最
  小边的覆盖。
  所用的算法为"求任意图最大匹配"的算法。
  使用"求任意图最大匹配"的算法比较复杂(要用到扩展交错树，对花的收缩
  等等)，效率也不是很高。
  首先，由于图中任两个连通分量都是相对独立的，也就是说任一条匹配边的
  因此，我们可以对每个连通分量分别进行处
  同时，我们还可以对需要船只s 的下限进行估计:
  对于一个包含P
  个顶点的连通分量，其最小覆盖边数显然为[P
  若图中共
  然后，我们通过多次尝试，可得出一个猜想:
  实际需要的覆盖边数完全等于我们求出的下限∑[P
  要用图的结构对上述猜想进行证明，可参照以下两步进行:
  2.从图中删去度为1 的点及其相邻的点，或删去回路中的任何一边，连通分
  量依然连通，即连通分量必然存在非桥边。
  由于图的方法不是这里的重点，所以具体证明不做详述。
  而由采用图的数据
  结构得出的算法为:每次输出一条非桥的边，并从图中将边的两顶点删去。
  此算
  法的时间复杂度为O(n
  (寻找一条非桥边的复杂度为O(n
  2
  )，寻找覆盖边操作的
  复杂度为O(n))
  由于受到图结构的限制，时间复杂度已经无法降低，所以如果我们要继续对
  算法进行优化，只有考虑使用另一种逻辑结构。
  这里，我想到了使用二叉树的结
  构，具体说就是将图中的连通分量都转化为二叉树，用二叉树来解决问题。
  首先，我们以连通分量中任一个顶点作为树根，然后我们来确定建树的方法。
  树根建立子树。
  中的二叉树的结构(以结点1 为根)。
  (两点间用实线表示同姓，虚线表示同名)
  接着，我就来证明这棵树一定包含了连通分量中的所有顶点。
  【引理2.1】
  在T 中。
  由于 s 是有限集合，因而必然存在某
  个lc无左儿子。
  【引理2.2】
  有了上面的两个引理，我们就不难得出下面的定理了。
  【定理一】
  以连通分量中的任一点 p 作为根结点的二叉树，必然能够包含连通分量中的
  分量中所有与p 有边相连的点都在二叉树中。
  由连通分量中任两点间都存在路径
  在证明二叉树中包含了连通分量的所有顶点后，我们接着就需要证明我们的
  猜想，也就是下面的定理:
  【定理二】包含m个结点的二叉树T
  ，只需要船的数量为boat=(mN)。
  层次最深的结点，并假设这个结点的父亲为 p。
  那么，此时有且只有以下
  三种情况(结点中带有阴影的是p 结点):
  ，则boat=boat+1=+1=。
  此时可删去 p
  同样地，T
  ，boat=boat+1=。
  情况与(2)十分相
  似，易得此时得boat=boat+1=。
  最后，综合(i)、(ii)，对于一切mN，boat=。
  由上述证明，我们将问题中数据的图结构转化为树结构后，可以得出求一棵
  二叉树的乘船方案的算法:
  proc try(father:integer;var root:integer;var rest:byte);
  {输出root 为树根的子树的乘船方案，father=0 表示root 是其父亲的左儿子，
  father=1 表示root 是其父亲的右儿子，rest 表示输出子树的乘船方案后，
  是否还剩下一个根结点未乘船}
  visit:=true; {标记root 已访问}
  找到一个与root 同姓且未访问的结点j;
  if j<>n+1 then try(0,j,lrest);
  找到一个与root 同姓且未访问的结点k;
  if k<>n+1 then try(1,k,rrest);
  if (lrest=1) xor (rrest=1) then begin {判断root 是否只有一个儿子，情况一}
  if lrest=1 then print(lrest,root) else print(rrest,root);
  rest:=0;
  else if (lrest=1) and (rrest=1) then begin {判断root 是否有两个儿子}
  if father=0 then begin
  print(rrest,root);root:=j; {情况二}
  print(lrest,root);root:=k; {情况三}
  rest:=1;
  else rest:=1;
  这只是输出一棵二叉树的乘船方案的算法，要输出所有人的乘船方案，我们
  还需再加一层循环，用于寻找各棵二叉树的根结点，但由于每个点都只会访问一
  次，寻找其左右儿子各需进行一次循环，所以算法的时间复杂度为 O(n
  (附程
  序boat.pas)
  最后，我们对两种结构得出不同时间复杂度算法的原因进行分析。
  键的一点就是因为二叉树虽然结构相对较简单，但已经包含了几乎全部都"有用"
  由我们寻找乘船方案的算法可知，二叉树中的所有边不仅都发挥了作用，
  而且没有重复的使用，可见信息的利用率也是相当之高的。
  既然采用树结构已经足够，图结构中的一些信息就显然就成为了"无用"的
  这些多余的"无用"信息，使我们在分析问题时难于发现规律，也很难找
  到高效的算法进行解决。
  这正如迷宫中的墙一样，越多越难走。
  "无用"的信息，
  只会干扰问题的规律性，使我们更难找出解决问题的方法。
  我们对数据的逻辑结构进行选择，是构造数学模型一大关键，而算法又是用
  来解决数学模型的。
  要使算法效率高，首先必须选好数据的逻辑结构。
  提出了选择逻辑结构的两个条件(思考方向)，总之目的是提高信息的利用效果。
  利用"可直接使用"的信息，由于中间不需其它操作，利用的效率自然很高;不
  不记录"无用"的信息，就会使我们更加专心地研究分析"有用"的信息，对信
  息的使用也必然会更加优化。
  总之，在解决问题的过程中，选择合理的逻辑结构是相当重要的环节。
  三、 选择合理的存储结构
  数据的存储结构，分为顺序存储结构和链式存储结构。
  顺序存储结构的特点
  是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;链式存储结
  构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
  因为两种存储结构的不同，导致这两种存储结构在具体使用时也分别存在着
  这里有一个较简单的例子:我们需要记录一个 n×n 的矩阵，矩阵中包含的非
  0 元素为m个。
  此时，我们若采用顺序存储结构，就会使用一个 n×n 的二维数组，将所有数
  据元素全部记录下来;若采用链式存储结构，则需要使用一个包含m个结点的链
  表，记录所有非0 的m个数据元素。
  由这样两种不同的记录方式，我们可以通过
  对数据的不同操作来分析它们的优点和缺点。
  由于顺序结构在物理位置上是相邻的，所以可
  以很容易地获得任意元素的存储地址，其复杂度为O(1);对于链式结构，
  由于不具备物理位置相邻的特点，所以首先必须对整个链表进行一次遍
  历，寻找需进行访问的元素的存储地址，其复杂度为 O(m)。
  此时使用顺
  序结构显然效率更高。
  2.对所有数据进行遍历。
  两种存储结构对于这种操作的复杂度是显而易见
  的，顺序结构的复杂度为O(n
  2
  )，链式结构为O(m)。
  由于在一般情况下m
  要远小于n
  ，所以此时链式结构的效率要高上许多。
  除上述两种操作外，对于其它的操作，这两种结构都不存在很明显的优点和
  缺点，如对链表进行删除或插入操作，在顺序结构中可表示为改变相应位置的数
  既然两种存储结构对于不同的操作，其效率存在较大的差异，那么我们在确
  定存储结构时，必须仔细分析算法中操作的需要，合理地选择一种能够"扬长避
  短"的存储结构。
  一、合理采用顺序存储结构。
  我们在平常做题时，大多都是使用顺序存储结构对数据进行存储。
  一方面是出于顺序结构操作方便的考虑，另一方面是在程序实现的过程中，使用
  顺序结构相对于链式结构更便于对程序进行调试和查找错误。
  因此，大多数人习
  惯上认为，能够使用顺序结构进行存储的问题，最"好"采用顺序存储结构。
  其实，这个所谓的"好"只是一个相对的标准，是建立在以下两个前提条件
  之下的:
  由于存储的结点数目比较接近，使用链式结构完全不能体现出记录结点少
  的优点，并且可能会由于指针操作较慢而降低算法的效率。
  更有甚者，由
  于指针自身占用的空间较大，且结点数目较多，因而算法对空间的要求可
  能根本无法得到满足。
  2.并非算法效率的瓶颈所在。
  由于不是算法最费时间的地方，这里是否进行
  改进，显然是不会对整个算法构成太大影响的，若使用链式结构反而会显
  得操作过于繁琐。
  二、必要时采用链式存储结构。
  上面我对使用顺序存储结构的条件进行了分析，最后就只剩下何时应该采用
  链式存储结构的问题了。
  由于链式结构中指针操作确实较繁琐，并且速度也较慢，调试也不方便，因
  而大家一般都不太愿意用链式的存储结构。
  但是，这只是一般的观点，当链式结
  构确实对算法有很大改进时，我们还是不得不进行考虑的。
  〖问题三〗 IOI99 的《地下城市》。
  已知一个城市的地图，但未给出你的初始位置。
  你需要通过一系列的移动和
  探索，以确定初始时所在的位置。
  题目的限制是:
  1.不能移动到有墙的方格。
  2.只能探索当前所在位置四个方向上的相邻方格。
  在这两个限制条件下，要求我们的探索次数(不包括移动)尽可能的少。
  由于存储结构要由算法的需要确定，因此我们首先来确定问题的算法。
  经过对问题的分析，我们得出解题的基本思想:先假设所有无墙的方格都可
  能是初始位置，再通过探索一步步地缩小初始位置的范围，最终得到真正的初始
  同时，为提高算法效率，我们还用到了分治的思想，使我们每一次探索都
  尽量多的缩小初始位置的范围(使程序尽量减少对运气的依赖)。
  接着，我们来确定此题的存储结构。
  由于这道题的地图是一个二维的矩阵，所以一般来讲，采用顺序存储结构理
  我们所进行的最多
  的操作，一是对初始位置的范围进行筛选，二是判断要选择哪个位置进行探索。
  而这两种操作，所需要用到的数据，只是庞大地图中很少的一部分。
  如果采用顺
  序存储结构(如图3-1 中阴影部分表示已标记)，无论你需要用到多少数据，始终都
  要完全的遍历整个地图。
  然而，如果我们采用的是链式存储结构(如图3-2 的链表)，那么我们需要多少
  数据，就只会遍历多少数据，这样不仅充分发挥了链式存储结构的优点，而且由
  于不需单独对某一个数据进行提取，每次都是对所有数据进行判断，从而避免了
  链式结构的最大缺点。
  我们使用链式存储结构，虽然没有降低问题的时间复杂度(链式存储结构在最
  坏情况下的存储量与顺序存储结构的存储量几乎相同)，但由于体现了前文所述选
  择存储结构时扬长避短的原则，因而算法的效率也大为提高。
  (程序对不同数据的
  运行时间见表3-3)
  (附使用链式存储结构的程序under.pas)
  我们选择链式的存储结构，虽然操作上可能稍复杂一些，但由于改进了算法
  的瓶颈，算法的效率自然也今非昔比。
  由此可见，必要时选择链式结构这一方法，
  其效果是不容忽视的。
  合理选择逻辑结构，由于牵涉建立数学模型的问题，可能大家都会比较注意。
  但是对存储结构的选择，由于不会对算法复杂度构成影响，所以比较容易忽视。
  测试数据编号 使用顺序存储结构的程序 使用链式存储结构的程序
  6 141.16s 0.23s
  10 17.41s 0.20s
  那么，这种不能降低算法复杂度的方法是否需要重视呢
  大家都知道，剪枝作为一种常用的优化算法的方法，被广泛地使用，但剪枝
  同样是无法改变算法的复杂度的。
  因此，作用与剪枝相似的存储结构的合理选择，
  也是同样很值得重视的。
  总之，我们在设计算法的过程中，必须充分考虑存储结构所带来的不同影响，
  四、 多种数据结构相结合
  上文所探讨的，都是如何对数据结构进行选择，其中包含了逻辑结构的选择
  和存储结构的选择，是一种具有较大普遍性的算法优化方法。
  对于多数的问题，
  我们都可以通过选择一种合理的逻辑结构和存储结构以达到优化算法的目的。
  但是，有些问题却往往不如人愿，要对这类问题的数据结构进行选择，常常
  会顾此失彼，有时甚至根本就不存在某一种合适的数据结构。
  此时，我们是无法
  选择出某一种合适的数据结构的，以上的方法就有些不太适用了。
  为解决数据结构难以选择的问题，我们可以采用将多种数据结构进行结合的
  通过多种数据结构相结合，达到取长补短的作用，使不同的数据结构在算
  法中发挥出各自的优势。
  这只是我们将多种数据结构进行结合的总思想，具体如何进行结合，我们可
  以先看下面的例子。
  〖问题四〗 广东省97 年省赛的《最小序列》问题。
  需要在矩阵中寻找一条从起始位置
  到终止位置的路径(可沿上下左右四个方向)，并且要求路径中经过的所有数字，
  其相邻数字之差的绝对值之和最小。
  这道题的基本算法很简单，只要用Dijkstra 算法求出从起始位置到终止位置的
  但这当中存在一个很大的问题:N<=100。
  这就是说图中点的数目
  可能多达10000 个。
  此时复杂度为O(n
  2
  )的Dijkstra 算法就显得有些力不从心了。
  我们继续对算法进行分析。
  由于Dijstra 算法通常采用的是线性的数组结构，
  所以当我们每次寻找下一条最短路径时，有两步需要进行:
  1.找出一个不在最短路径起点集合内，并且到终点距离最短的顶点 i。
  步的复杂度显然为O(n)。
  2.修改从与i 相邻的顶点到终点的路径长度。
  由于最多只有4 个点(四个方向)
  这两步中，虽然第二步最多只改变了到 4 个点的路径长度，但是第一步却还
  是需要枚举所有的数组元素，这显然很浪费时间。
  出于对第一步进行改进的考虑，
  我们可以想到树结构中二叉堆的结构。
  堆结构的优点是:根结点就是最优的结点，
  并且改变堆中某个结点的值以后，只需 O(log
  n)的复杂度就可以完成堆化的过程
  (可分为从二叉树中自下而上和自上而下两种堆化方法，并且复杂度都一样)，使
  堆的结构发生改变后，通过堆化仍然能够保留堆的性质。
  如果我们采用二叉堆的结构存储距离，第一步就只需将根结点取出，并且用
  堆中的另一结点代替后进行一次自上而下的堆化。
  因而第一步的复杂度可降为
  但是，此时的堆结构在进行第二步时暴露了很大的缺点:无法预知 i
  点的相邻点在堆中的位置。
  如果我们用对堆进行遍历来寻找 i 的相邻点，第二步
  的复杂度又成为了O(n)。
  我们从这两种数据结构中不难发现这样规律:采用线性结构的数组，易于进
  行第二步;采用树结构的二叉堆，做第一步时效果比较理想。
  那么，我们是否可以将这两种数据结构进行结合，取长补短呢
  我们可以采用映射的方法，将线性结构中的元素与堆中间的结点一一对应起
  来，若线性的数组中的元素发生变化，堆中相应的结点也接着变化，堆中的结点
  发生变化，数组中相应的元素也跟着变化。
  将两种结构进行结合后，无论是第一步还是第二步，我们都不需对所有元素
  进行遍历，只需进行常数次复杂度为 O(log
  n)的堆化操作。
  这样，整个时间复杂
  度就成为了O(nlog
  n)，算法效率无疑得到了很大提高。
  这个例子只是对逻辑结构的结合进行了分析，对于存储结构的结合，实际上
  我们同样可以在链式存储结构和顺序存储结构中建立对应的关
  系，并且将链式存储结构中插入和删除的操作，与顺序结构中数据元素标志的改
  变同时进行。
  这样，我们在访问数据元素时，如果需要进行遍历，就使用链式结
  构;如果只需要判断某一个元素，就直接访问其在顺序结构中的标记。
  通过存储
  结构的结合，我们就将两种存储结构的优点完全发挥了出来。
  由此，我们又得到了在各种数据结构优劣难辩、难以取舍时，选择和使用各
  种数据结构的方法:用映射来达到对各数据结构进行结合的目的。
  这无疑又增加
  了一种数据结构的使用方法和技巧。
  我们平常使用数据结构，往往只将其作为建立模型和算法实现的工具，而没
  有考虑这种工具对程序效率所产生的影响。
  信息学问题随着难度的不断增大，对
  算法时空效率的要求也越来越高，而算法的时空效率，在很大程度上都受到了数
  据结构的制约。
  因此，数据结构作为信息学竞赛的基础，也是大家最为熟悉的内容，其对算
  法时间和空间都起到了至关重要的作用。
  我们惟有对数据结构优化算法的方法从
  结合方法，才能更加有效地对算法进行改进。
  随着数据结构的不断发展，人们对数据结构的认识也不断深入。
  本文只是对
  数据结构进行了初步的探讨，要对数据结构进行全面的了解和掌握，还需要我们
  更进一步的进行分析和总结。
  正所谓"养兵千日，用兵一时"，我们只有在平常打
  好基础，总结经验，才能在信息学竞赛中运用自如。
  本文对数据结构的定义，是采用的《数据结构(第二版)》中的定义，而
  在其它书中，数据结构的定义可能会有所不同。
  由于本文的重点是数据结构而不是算法，所以文中对问题进行分析时，
  可能未十分详尽地写出每个问题的算法推导过程。
  在对《地下城市》中使用顺序存储结构和链式存储结构的程序进行比较
  时，所选用数据为IOI99 的标准数据。
  测试机型为6x86 200MHz。
  本文由于是对数据结构的选择方法进行探讨，所以举例分析时大多采用了对
  不同数据结构进行比较的方法。
  以下仅给出了采用较好的数据结构的程序。
  〖程序1〗隐藏的码字(使用有向图的结构):codes.pas
  出于提高程序效率的目的，程序中还进行了其它的一些优化措施，如对码字排序、对求
  出的项目择优存储等。
  程序的输入输出都按照试卷的标准格式。
  {$M 2048,0,655360}
  const st11='words.inp'; {记录码字的文件名}
  st12='text.inp'; {记录文本的文件名}
  st2='codes.out'; {输出文件名}
  max=1023; {使用循环队列记录的字母数目上限}
  type arr1=array of longint;
  arr2=array of shortint;
  arr3=array of longint;
  var i,j,now:longint; {now--标志已读到文本的第now 位}
  m,n:integer; {n--码字的个数,m-得出的项目个数}
  buf:array of char; {输入文件的缓冲区}
  t:array of string; {t--记录各个码字}
  last:array of ^arr3;
  nearest:arr3; {nearest--当前读入的第now 位之前最后出现字母c 的位置}
  bb,ee:array of byte;
  no:array of byte; {no--排序后列表中第i 个码字在原列表中的位置}
  ss,tt:^arr1;
  nn:^arr2;
  尾位置和其对应码字在排序后的码字列表中的编号}
  b:char;
  procedure readcod; {读入码字列表并对其进行排序}
  var f:text;
  i,j,k,l:integer;
  assign(f,st11);reset(f);
  readln(f,t);no:=i;
  fillchar(bb,sizeof(bb),1);
  fillchar(ee,sizeof(ee),0);
  if (tlength(t)) then k:=j;