2022年算法合集之《数据结构的在程序设计中的应用》 .pdf

数据结构在程序设计中的应用长沙市一中肖洲第 1 页 共 28 页数据结构的在程序设计中的应用长沙市一中肖洲【关键字】逻辑结构存储结构算法优化【摘要】数据结构作为程序设计的基础，其对算法效率的影响必然是不可忽视的。本文就如何合理选择数据结构来优化算法这一问题，对选择数据结构的原则和方法进行了一些探讨。首先对数据逻辑结构的重要性进行了分析， 提出了选择逻辑结构的两个基本原则；接着又比较了顺序和链式两种存储结构的优点和缺点，并讨论了选择数据存储结构的方法；最后本文从选择数据结构的的另一角度出发，进一步探讨了如何将多种数据结构进行结合的方法。在讨论方法的同时，本文还结合实际，选用了一些较具有代表性的信息学竞赛试题举例进行了分析【正文】一、引论“数据结构算法程序” ， 这就说明程序设计的实质就是对确定的问题选择一种合适的数据结构，加上设计一种好的算法。由此可见，数据结构在程序设计中有着十分重要的地位。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。因为这其中的“关系” ，指的是数据元素之间的逻辑关系，因此数据结构又称为数据的逻辑结构。而相对于逻辑结构这个比较抽象的概念，我们将数据结构在计算机中的表示又称为数据的 存储结构 。建立问题的数学模型， 进而设计问题的算法， 直至编出程序并进行调试通过，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 2 页 共 28 页这就是我们解决信息学问题的一般步骤。我们要建立问题的数学模型，必须首先找出问题中各对象之间的关系，也就是确定所使用的逻辑结构；同时，设计算法和程序实现的过程，必须确定如何实现对各个对象的操作，而操作的方法是决定于数据所采用的存储结构的。因此，数据逻辑结构和存储结构的好坏，将直接影响到程序的效率。二、选择合理的逻辑结构在程序设计中，逻辑结构的选用就是要分析题目中的数据元素之间的关系，并根据这些特定关系来选用合适的逻辑结构以实现对问题的数学描述，进一步解决问题。逻辑结构实际上是用数学的方法来描述问题中所涉及的操作对象及对象之间的关系，将操作对象抽象为数学元素，将对象之间的复杂关系用数学语言描述出来。根据数据元素之间关系的不同特性，通常有以下四种基本逻辑结构：集合、线性结构、树形结构、图状（网状）结构。这四种结构中，除了集合中的数据元素之间只有“同属于一个集合” 的关系外，其它三种结构数据元素之间分别为“一对一” 、 “一对多”、 “多对多”的关系。因此，在选择逻辑结构之前，我们应首先把题目中的操作对象和对象之间的关系分析清楚，然后再根据这些关系的特点来合理的选用逻辑结构。尤其是在某些复杂的问题中，数据之间的关系相当复杂，且选用不同逻辑结构都可以解决这一问题，但选用不同逻辑结构实现的算法效率大不一样。对于这一类问题，我们应采用怎样的标准对逻辑结构进行选择呢？下文将探讨选择合理逻辑结构应充分考虑的两个因素。一、充分利用“可直接使用”的信息。首先，我们这里所讲的“信息” ，指的是元素与元素之间的关系。对于待处理的信息，大致可分为“可直接使用”和“不可直接使用”两类。对于“可直接使用”的信息，我们使用时十分方便，只需直接拿来就可以了。而对于“不可直接使用”的这一类，我们也可以通过某些间接的方式，使之成为可以使用的信息，但其中转化的过程显然是比较浪费时间的。由此可见，我们所需要的是尽量多的“可直接使用”的信息。这样的信息越多，算法的效率就会越高。对于不同的逻辑结构，其包含的信息是不同的，算法对信息的利用也会出现不同的复杂程度。因此，要使算法能够充分利用“可直接使用”的信息，而避免名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 3 页 共 28 页算法在信息由“不可直接使用” 向“可直接使用”的转化过程中浪费过多的时间，我们必然需要采用一种合理的逻辑结构，使其包含更多“可直接使用”的信息。问题一IOI99 的隐藏的码字。问题描述问题中给出了一些码字和一个文本，要求编程找出文本中包含这些码字的所有项目，并将找出的项目组成一个最优的“答案” ，使得答案中各项目所包含的码字长度总和最大。每一个项目包括一个码字，以及该码字在文本中的一个覆盖序列（如 abcadc 就是码字 abac的一个覆盖序列） ，并且覆盖序列的长度不超过1000。同时， “答案”要求其中每个项目的覆盖序列互相没有重叠。问题分析对于此题，一种较容易得出的基本算法是：对覆盖序列在文本中的终止位置进行循环，再判断包含了哪些码字，找出所有项目，并最后使用动态规划的方法将项目组成最优的“答案” 。算法的其它方面我们暂且不做考虑，而先对问题所采用的逻辑结构进行选择。如果我们采用线性的逻辑结构（如循环队列），那么我们在判断是否包含某个码字 t 时，所用的方法为：初始时用指针p 指向终止位置，接着通过p 的不断前移，依次找出码字t 从尾到头的各个字母。例如码字为“ABDCAB ” ，而文本图1-1，终止位置为最右边的箭头符号，每个箭头代表依次找到的码字的各个字母。由于题目规定码字的覆盖序列长度不超过1000，所以进行这样的一次是否包含的判断，其复杂度为O(1000)。由于码字 t 中相邻两字母在文本中的位置，并非只有相邻(如图 1-1 中的D 和 C)这一种关系， 中间还可能间隔了许多的字母(如图 1-1 中C 和A就间隔了 2个字母 )，而线性结构中拥有的信息，仅仅只存在于相邻的两元素之间。通过这样简单的信息来寻找码字的某一个字母，其效率显然不高。如果我们建立一个有向图，其中顶点i(即文本的第i 位)用 52 条弧分别连接a. z, A. Z这 52个字母在 i 位以前最后出现的位置（如图1-2 的连接方式），我们要寻找码字中某个字母的前一个字母，就可以直接利用已连接的边，而不需用枚举的方法。我们也可以把问题看为：从有向图的一个顶点出发，寻找一条长度为 length(t)-1 的路径，并且路径中经过的顶点，按照码字t 中的字母有序。指针 p 的移动方向 A B D C A B C D A C B D C A D C D B A D C C B A D 图 1-1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 4 页 共 28 页通过计算，用图进行记录在空间上完全可以承受(记录 1000 个点 52 条弧 4字节的长整型 =200k 左右)。在时间上，由于可以充分利用第i 位和第 i+1 位弧的连接方式变化不大这一点 (如图 1-2 所示，第 i 位和第 i+1 位只有一条弧的指向发生了变化，即第 i+1 位将其中一条弧指向了第i 位)，所以要对图中的弧进行记录，只需对弧的指向进行整体赋值，并改变其中的某一条弧即可。因此，我们通过采用图的逻辑结构，使得寻找字母的效率大大提高，其判断的复杂度为 O(length(t)，最坏为 O(100)，比原来方法的判断效率提高了10 倍。（附程序 codes.pas ）对于这个例子，虽然用线性的数据结构也可以解决，但由于判断的特殊性，每次需要的信息并不能从相邻的元素中找到，而线性结构中只有相邻元素之间存在关系的这一点， 就成为了一个很明显的缺点。 因此，问题一线性结构中的信息，就属于“不可直接使用” 的信息。相对而言，图的结构就正好满足了我们的需要，将所有可能产生关系的点都用弧连接起来，使我们可以利用弧的关系，高效地进行判断寻找的过程。虽然图的结构更加复杂，但却将“不可直接使用”的信息，转化成为了“可直接使用”的信息，算法效率的提高，自然在情理之中。二、不记录“无用”信息。从问题一中我们看到，由于图结构的信息量大，所以其中的信息基本上都是“可用”的。但是，这并不表示我们就一定要使用图的结构。在某些情况下，图结构中的“可用”信息，是有些多余的。信息都“可用”自然是好事，但倘若其中“无用”（不需要）的信息太多，就只会增加我们思考分析和处理问题时的复杂程度，反而不利于我们解决问题了。问题二湖南省 1997 年组队赛的乘船问题问题描述有 N 个人需要乘船，而每船最多只能载两人，且必须同名或同姓。求最少需要多少条船。问题分析看到这道题，很多人都会想到图的数据结构： 将 N 个人看作无向图的N 个点，C D A C B D C A D C D B A D C C B A D 图 1-2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 5 页 共 28 页凡同名或同姓的人之间都连上边。要满足用船最少的条件，就是需要尽量多的两人共乘一条船，表现在图中就是要用最少的边完成对所有顶点的覆盖。这就正好对应了图论的典型问题：求最小边的覆盖。所用的算法为“求任意图最大匹配”的算法。使用“求任意图最大匹配”的算法比较复杂(要用到扩展交错树，对花的收缩等等)，效率也不是很高。因此，我们必须寻找一个更简单高效的方法。首先，由于图中任两个连通分量都是相对独立的，也就是说任一条匹配边的两顶点，都只属于同一个连通分量。因此，我们可以对每个连通分量分别进行处理，而不会影响最终的结果。同时，我们还可以对需要船只s 的下限进行估计：对于一个包含 Pi个顶点的连通分量，其最小覆盖边数显然为Pi/2。若图中共有 L 个连通分量，则 s=Pi/2(1=i=L) 。然后，我们通过多次尝试，可得出一个猜想：实际需要的覆盖边数完全等于我们求出的下限Pi/2(1=i0) 表示 lcp,i-1 的左儿子，显然 lcp,i 与 p 是同姓的。假设存在某个点q，满足 q s 且 q T。由于 s 是有限集合，因而必然存在某个 lcp,k 无左儿子。则我们可以令lcp,k+1=q，所以 q T，与假设 q T 相矛盾。所以假设不成立，原命题得证。由引理 2.1 的证明方法，我们同理可证引理2.2。【引理 2.2】若二叉树 T 中包含了某个结点p，那么连通分量中所有与p 同名的点一定都在 T 中。有了上面的两个引理，我们就不难得出下面的定理了。【定理一】以连通分量中的任一点p 作为根结点的二叉树，必然能够包含连通分量中的所有顶点。证明：由引理 2.1 和引理 2.2，所有与 p 同姓或同名的点都一定在二叉树中，即连通分量中所有与 p 有边相连的点都在二叉树中。由连通分量中任两点间都存在路径的特性，该连通分量中的所有点都在二叉树中。在证明二叉树中包含了连通分量的所有顶点后，我们接着就需要证明我们的猜想，也就是下面的定理：【定理二】包含 m 个结点的二叉树 Tm，只需要船的数量为 boatm=m/2(mN)。证明：图 2-1-2 图 2-1-1 4 3 8 6 7 2 5 1 2 3 1 7 5 4 6 8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 7 页 共 28 页(i) 当 m=1,m=2,m=3 时命题显然成立。(ii) 假设当 m3)时命题成立，那么当m=k 时，我们首先从树中找到一个层次最深的结点，并假设这个结点的父亲为p。那么，此时有且只有以下三种情况（结点中带有阴影的是p 结点） ：(1) 如图 2-2-1，p 只有一个儿子。此时删去p 和 p 唯一的儿子， Tk就成为了 Tk-2，则 boatk=boatk-2+1=(k-2)/2+1=k/2 。(2) 如图 2-2-2，p 有两个儿子，并且p 是其父亲的左儿子。此时可删去p和 p 的右儿子，并可将p 的左儿子放到 p 的位置上。同样地， Tk成为了 Tk-2，boatk=boatk-2+1=k/2 。(3) 如图 2-2-3，p 有两个儿子，并且p 是其父亲的右儿子。此时可删去p和 p 的左儿子，并可将p 的右儿子放到 p 的位置上。情况与 (2)十分相似，易得此时得boatk=boatk-2+1=k/2 。综合(1)、(2)、(3)，当 m=k 时，boatk=k/2 。最后，综合 (i)、(ii) ，对于一切 m N，boatm=m/2 。由上述证明，我们将问题中数据的图结构转化为树结构后，可以得出求一棵二叉树的乘船方案的算法：proc try(father:integer;var root:integer;var rest:byte); 输出 root 为树根的子树的乘船方案，father=0 表示 root 是其父亲的左儿子，father=1表示 root 是其父亲的右儿子， rest表示输出子树的乘船方案后，是否还剩下一个根结点未乘船 begin visitroot:=true; 标记 root 已访问 找到一个与 root 同姓且未访问的结点j; if jn+1 then try(0,j,lrest); 找到一个与 root 同姓且未访问的结点k; if kn+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; end else if (lrest=1) and (rrest=1) then begin 判断 root 是否有两个儿子 图 2-2-1 图 2-2-2 图 2-2-3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 8 页 共 28 页if father=0 then begin print(rrest,root);root:=j; 情况二 end else begin print(lrest,root);root:=k; 情况三 end; rest:=1; end else rest:=1; end; 这只是输出一棵二叉树的乘船方案的算法，要输出所有人的乘船方案，我们还需再加一层循环，用于寻找各棵二叉树的根结点，但由于每个点都只会访问一次，寻找其左右儿子各需进行一次循环，所以算法的时间复杂度为O(n2)。 （附程序 boat.pas ）最后，我们对两种结构得出不同时间复杂度算法的原因进行分析。其中最关键的一点就是因为二叉树虽然结构相对较简单，但已经包含了几乎全部都 “有用”的信息。由我们寻找乘船方案的算法可知， 二叉树中的所有边不仅都发挥了作用，而且没有重复的使用，可见信息的利用率也是相当之高的。既然采用树结构已经足够，图结构中的一些信息就显然就成为了“无用”的信息。这些多余的“无用”信息，使我们在分析问题时难于发现规律，也很难找到高效的算法进行解决。这正如迷宫中的墙一样，越多越难走。“无用”的信息，只会干扰问题的规律性，使我们更难找出解决问题的方法。小结我们对数据的逻辑结构进行选择，是构造数学模型一大关键，而算法又是用来解决数学模型的。要使算法效率高，首先必须选好数据的逻辑结构。上面已经提出了选择逻辑结构的两个条件（思考方向），总之目的是提高信息的利用效果。利用“可直接使用”的信息，由于中间不需其它操作，利用的效率自然很高；不不记录“无用”的信息，就会使我们更加专心地研究分析“有用”的信息，对信息的使用也必然会更加优化。总之，在解决问题的过程中，选择合理的逻辑结构是相当重要的环节。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 9 页 共 28 页三、选择合理的存储结构数据的存储结构，分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。因为两种存储结构的不同，导致这两种存储结构在具体使用时也分别存在着优点和缺点。这里有一个较简单的例子：我们需要记录一个n n 的矩阵，矩阵中包含的非0 元素为 m 个。此时，我们若采用顺序存储结构，就会使用一个n n 的二维数组，将所有数据元素全部记录下来； 若采用链式存储结构， 则需要使用一个包含m 个结点的链表，记录所有非 0 的 m 个数据元素。由这样两种不同的记录方式，我们可以通过对数据的不同操作来分析它们的优点和缺点。1随机访问矩阵中任意元素。 由于顺序结构在物理位置上是相邻的，所以可以很容易地获得任意元素的存储地址，其复杂度为O(1)；对于链式结构，由于不具备物理位置相邻的特点，所以首先必须对整个链表进行一次遍历，寻找需进行访问的元素的存储地址，其复杂度为O(m)。此时使用顺序结构显然效率更高。2对所有数据进行遍历。两种存储结构对于这种操作的复杂度是显而易见的，顺序结构的复杂度为O(n2)，链式结构为 O(m)。由于在一般情况下m要远小于 n2，所以此时链式结构的效率要高上许多。除上述两种操作外，对于其它的操作，这两种结构都不存在很明显的优点和缺点，如对链表进行删除或插入操作，在顺序结构中可表示为改变相应位置的数据元素。既然两种存储结构对于不同的操作，其效率存在较大的差异，那么我们在确定存储结构时，必须仔细分析算法中操作的需要，合理地选择一种能够“扬长避短”的存储结构。一、合理采用顺序存储结构。我们在平常做题时， 大多都是使用顺序存储结构对数据进行存储。究其原因，一方面是出于顺序结构操作方便的考虑，另一方面是在程序实现的过程中，使用顺序结构相对于链式结构更便于对程序进行调试和查找错误。因此，大多数人习惯上认为，能够使用顺序结构进行存储的问题，最“好”采用顺序存储结构。其实，这个所谓的“好”只是一个相对的标准，是建立在以下两个前提条件之下的：1链式结构存储的结点与顺序结构存储的结点数目相差不大。这种情况下，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 10 页 共 28页由于存储的结点数目比较接近， 使用链式结构完全不能体现出记录结点少的优点，并且可能会由于指针操作较慢而降低算法的效率。更有甚者，由于指针自身占用的空间较大，且结点数目较多，因而算法对空间的要求可能根本无法得到满足。2并非算法效率的瓶颈所在。由于不是算法最费时间的地方，这里是否进行改进，显然是不会对整个算法构成太大影响的，若使用链式结构反而会显得操作过于繁琐。二、必要时采用链式存储结构。上面我对使用顺序存储结构的条件进行了分析，最后就只剩下何时应该采用链式存储结构的问题了。由于链式结构中指针操作确实较繁琐，并且速度也较慢，调试也不方便，因而大家一般都不太愿意用链式的存储结构。但是，这只是一般的观点，当链式结构确实对算法有很大改进时，我们还是不得不进行考虑的。问题三IOI99 的地下城市。问题描述已知一个城市的地图，但未给出你的初始位置。你需要通过一系列的移动和探索，以确定初始时所在的位置。题目的限制是：1不能移动到有墙的方格。2只能探索当前所在位置四个方向上的相邻方格。在这两个限制条件下，要求我们的探索次数（不包括移动）尽可能的少。问题分析由于存储结构要由算法的需要确定，因此我们首先来确定问题的算法。经过对问题的分析，我们得出解题的基本思想：先假设所有无墙的方格都可能是初始位置，再通过探索一步步地缩小初始位置的范围，最终得到真正的初始位置。同时，为提高算法效率，我们还用到了分治的思想，使我们每一次探索都尽量多的缩小初始位置的范围(使程序尽量减少对运气的依赖)。接着，我们来确定此题的存储结构。由于这道题的地图是一个二维的矩阵，所以一般来讲，采用顺序存储结构理所当然。但是，顺序存储结构在这道题中暴露了很大的缺点。我们所进行的最多的操作，一是对初始位置的范围进行筛选，二是判断要选择哪个位置进行探索。而这两种操作，所需要用到的数据，只是庞大地图中很少的一部分。如果采用顺序存储结构 (如图 3-1 中阴影部分表示已标记 )，无论你需要用到多少数据， 始终都要完全的遍历整个地图。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 11 页 共 28页然而，如果我们采用的是链式存储结构(如图 3-2 的链表 )，那么我们需要多少数据，就只会遍历多少数据，这样不仅充分发挥了链式存储结构的优点，而且由于不需单独对某一个数据进行提取，每次都是对所有数据进行判断，从而避免了链式结构的最大缺点。我们使用链式存储结构，虽然没有降低问题的时间复杂度(链式存储结构在最坏情况下的存储量与顺序存储结构的存储量几乎相同)， 但由于体现了前文所述选择存储结构时扬长避短的原则， 因而算法的效率也大为提高。（程序对不同数据的运行时间见表 3-3）（附使用链式存储结构的程序under.pas ）我们选择链式的存储结构，虽然操作上可能稍复杂一些，但由于改进了算法的瓶颈，算法的效率自然也今非昔比。 由此可见，必要时选择链式结构这一方法，其效果是不容忽视的。小结合理选择逻辑结构， 由于牵涉建立数学模型的问题，可能大家都会比较注意。但是对存储结构的选择，由于不会对算法复杂度构成影响，所以比较容易忽视。4 3 2 1 1 2 3 4 图 3-1 head 图 3-2 测试数据编号使用顺序存储结构的程序使用链式存储结构的程序1 0.06s 0.02s 2 1.73s 0.07s 3 1.14s 0.06s 4 3.86s 0.14s 5 32.84s 0.21s 6 141.16s 0.23s 7 0.91s 0.12s 8 6.92s 0.29s 9 6.10s 0.23s 10 17.41s 0.20s 表 3-3 (2,2) (4,1) (2,3) (3,4) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 12 页 共 28页那么，这种不能降低算法复杂度的方法是否需要重视呢？大家都知道，剪枝作为一种常用的优化算法的方法，被广泛地使用，但剪枝同样是无法改变算法的复杂度的。因此，作用与剪枝相似的存储结构的合理选择，也是同样很值得重视的。总之，我们在设计算法的过程中， 必须充分考虑存储结构所带来的不同影响，选择最合理的存储结构。四、多种数据结构相结合上文所探讨的，都是如何对数据结构进行选择，其中包含了逻辑结构的选择和存储结构的选择，是一种具有较大普遍性的算法优化方法。对于多数的问题，我们都可以通过选择一种合理的逻辑结构和存储结构以达到优化算法的目的。但是，有些问题却往往不如人愿，要对这类问题的数据结构进行选择，常常会顾此失彼，有时甚至根本就不存在某一种合适的数据结构。此时，我们是无法选择出某一种合适的数据结构的，以上的方法就有些不太适用了。为解决数据结构难以选择的问题，我们可以采用将多种数据结构进行结合的方法。通过多种数据结构相结合，达到取长补短的作用，使不同的数据结构在算法中发挥出各自的优势。这只是我们将多种数据结构进行结合的总思想，具体如何进行结合，我们可以先看下面的例子。问题四广东省 97 年省赛的最小序列问题。问题描述给定一个 N N（N=100）的正整数矩阵。 需要在矩阵中寻找一条从起始位置到终止位置的路径 (可沿上下左右四个方向 )，并且要求路径中经过的所有数字，其相邻数字之差的绝对值之和最小。问题分析这道题的基本算法很简单， 只要用 Dijkstra 算法求出从起始位置到终止位置的最短路径即可。但这当中存在一个很大的问题：Neec表示首字母为c 的码字不在码字列表中 no:array1.100 of byte; noi-排序后列表中第i 个码字在原列表中的位置 ss,tt:arr1; nn:arr2; ssi,tti,nni分别记录找到的第i 个项目中的覆盖序列的首位置，尾位置和其对应码字在排序后的码字列表中的编号 f:text; b:char; procedure readcod; 读入码字列表并对其进行排序 var f:text; i,j,k,l:integer; st:string; begin assign(f,st11);reset(f); readln(f,n); for i:=1 to n do begin readln(f,ti);noi:=i; end; fillchar(bb,sizeof(bb),1); fillchar(ee,sizeof(ee),0); 初始时 ,令所有 bbceec,以后找到字母c 后再改变bbc 和 eec 的值 for i:=1 to n do begin k:=i; for j:=i+1 to n do 按尾字母进行排序, 在尾字母相同时按码字由长到短排序 if (tj,length(tj)length(tk) then k:=j; if ik then begin st:=ti;ti:=tk;tk:=st; l:=noi;noi:=nok;nok:=l; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 16 页 共 28页 下面的判断为确定对应各尾字母的码字在新列表中的位置 if ti,length(ti)=b then inc(eeb) else begin b:=ti,length(ti);bbb:=i;eeb:=i; end; end; close(f); end; procedure find(st,ed:longint;e:char); 寻找项目的过程 , 已确定其终止位置为ed, 初始位置不小于st ，其包含的码字的尾字母为e var i,k,l:integer; j:longint; can:boolean; begin for k:=bbe to eee do begin j:=ed;i:=length(tk)-1; while (i0) and (j=st) do begin j:=lastj and maxtk,i;dec(i); end; 依次找出码字的各字母 if j=st then begin l:=m;can:=true; while (l0) and (ttl=j) do begin if (ssl=j) and (length(tnnl)=length(tk) then begin can:=false;break; end; dec(l); end; 对找出的项目进行择优，若can=false表示新找到的项目不如以前的 if can then begin inc(m);ssm:=j;ttm:=ed;nnm:=k; end; end; end; end; procedure findanswer; 求最优“答案” var i,j,k:integer; f:text; len,next:arr1; leni表示在前i 个项目 (不必包含i) 中得出的最优“答案”包含的码字长度 leni=max(lenj)+项目 i 的码字长度 (ij0) and (ttj=ssi) do dec(j); if lenj+length(tnni)leni then begin 判断选第i 个项目是否更优 leni:=lenj+length(tnni);nexti:=j; end; end; assign(f,st2);rewrite(f); writeln(f,lenm); 输出“答案”的总和值 k:=m; 寻找“答案”中所包含的各个项目 while k0 do begin while lenk=lenk-1 do dec(k);等式成立时不必选项目k writeln(f,nonnk, ,ssk, ,ttk); k:=nextk; end; close(f); end; begin readcod; new(ss);new(tt);new(nn); assign(f,st12); settextbuf(f,buf); reset(f); fillchar(nearest,sizeof(nearest),0); for i:=0 to max do begin new(lasti);fillchar(lasti,sizeof(lasti),0); end; 初始化 while not seekeoln(f) do begin inc(now); lastnow and max:=nearest; read(f,b);nearestb:=now; 将最后一次出现字母b 的位置更新为now if bbb=1000 then find(now-999,now,b) else find(1,now,b); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 18 页 共 28页 确定起始位置的下限max(now-999,1) ，并对项目进行寻找 end; close(f); findanswer; end. 程序 2乘船问题（采用二叉树结构） ：boat.pas 本题输入文件的格式为：第一行为总人数，以下每行为一个人的姓和名，中间用一个空格分开 ( 姓和名分别为长度不超过5 和 10 的字符串 ) 。 输出文件每行给出了一艘船上坐船的人的姓名，最后一行为需要船只的总数。$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+ $M 65520,0,655360 const Maxn=5000; 最多的人数 type Fnamearr=array1.Maxn of string5; Gnamearr=array1.Maxn of string10; var Fname:Fnamearr; 记录每个人的姓 Gname:Gnamearr; 记录每个人的名 visit:array1.Maxn of boolean; visiti记录第 i 个人是否已访问过 total,n:integer; total-需要船的数目，n- 总人数 fo:text; procedure init; 读入所有人的姓名 var f:text; st,t:string; i,j:integer; begin new(Fname);new(Gname); write(Input file name:);readln(st);assign(f,st);reset(f); readln(f,n); for i:=1 to n do begin readln(f,t); j:=pos( ,t); Fnamei:=copy(t,1,j-1); delete(t,1,j); Gnamei:=t; end; close(f); end; procedure print(i,j:integer); 输出 i 和 j 同坐一条船 var t:integer; begin t:=17-length(Fnamei)-length(Gnamei); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 28 页 - - - - - - - - - 数据结构在程序设计中的应用长沙市一中肖洲第 19 页 共 28页 writeln(fo,Fnamei, ,Gnamei,:t,- ,Fnamej, ,Gnamej); inc(total); end; procedure try(father:integer;var root:integer;var rest:byte); 建立以 root为根结点的子树，并输出在这棵子树中的所有人的乘船方案 father表示 root是其父亲的哪个儿子，0 表示左儿子，1 表示右儿子 rest表示在输出该子树中所有人的乘船方案以后，是否有一个人独坐一船 rest=1表示有，并可将这个独坐一船的人换到子树根结点root的位置上 var j,k:integer; Lrest,Rrest:byte; Lrest和 Rrest 分别表示以root为根的子树中，root的左右两儿子的rest值 begin visitroot:=true; j:=1; while (j=n) and (visitj or (FnamerootFnamej) do inc(j); 寻找一个与root 同姓并且从未访问过的人j Lrest:=0; if j=n then try(0,j,Lrest);以 j 为根建立子树并输出其子树中所有人的乘船方案 k:=1; while (k=n) and (visitk or (GnamerootGnamek) do inc(k); 寻找一个与root 同名并且从未访问过的人k Rrest:=0; if k=n then try(1,k,Rrest);以 j 为根建立子树并输出其子树中所有人的乘船方案 以下按照左右两子树中是否还有人剩下，对乘坐的船进行分配 if (Lrest=1) xor (Rrest=1) then begin 只有一棵子树有人剩下 if Lrest=1 then print(root,j) else print(root,k); 判断是哪棵子树有人剩下，并将那个人与root分配在同一条船上 rest:=0; end else if (Lrest=1) and (Rrest=1) then begin 两子树都有人剩下 以下由 root 和其父亲的关系，在左右两子树间选择与root同船的人， 并将剩下的人移动到根结点root的位置上 if father=0 then begin print(root,k);root:=j; end else begin print(root,j);root:=k end; rest:=1; end else rest:=1; end; 名师资料总结