树结构在程序设计中的运用

《树结构在程序设计中的运用》由会员分享，可在线阅读，更多相关《树结构在程序设计中的运用（126页珍藏版）》请在金锄头文库上搜索。

1、树结构在 程序设计中的运用,上海市控江中学 王建德,浙江省4年NOI组队赛,目录,引言树结构在程序设计中的运用,2003年竞赛的知识结构分布,2003年竞赛的知识结构分布,2003年竞赛的知识结构分布,试题特点,1、强调基础知识的灵活应用。每一轮竞赛都有基础知识题，但对灵活应用基础知识的要求愈来愈高。例如IOI的路径维护在逐边添入无向图的过程中计算最小生成树；文本编辑器要求设计多样的数据结构。例如线性表、非线性的树和图；NOIP的加分二叉树采用的动态程序设计是递归形式的；NOI的数据生成器必须综合使用前序遍历和后序遍历 2、首次出现了线段树和可以选择类博弈树算法的试题 3、近似算法类的试题增加

2、。例如IOI的猜牛游戏、逆向输出、机器人、NOI的卫星探测、草莓、智破连环阵等。由于这些例题视程序逼近最优解和最优效率的程度给分，因此拓展了选手思维的空间，易启发选手的创造性。但反过来说，由于近似算法类的选题空间比较大，因此有可能使得题目的难度加大。,试题特点,4、树形结构类的问题增多。例如NOI的卫星探测通过二分查找构造一棵隐形的二叉树；草莓和数据生成器使用了人们容易被忽视的后序遍历；IOI的路径维护要求计算最小生成树； 5、可“一题多解”和开放性的试题增多。例如，IOI的逆向输出就是一道没有固定模式和经典算法可套用、需要量身定制合适算法的试题；猜牛游戏既可以采用贪心法，亦可以采用类博弈树的

3、算法；NOIP的栈既可以通过回溯法计算，亦可以通过组合数学的Catalan数计算； 6、出现一些“陷阱题”。例如NOIP的传染病扩展极易诱导选手错误地使用贪心法或动态程序设计，实际上该问题不具备最优子结构的特征，正确的算法是回溯搜索。,启示,培养内省智力 充分利用网络资源 以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训,培养内省智力,入门 自信心 提高 自省力,自信心和自知之明是对立的统一。自信心倘若不是建立在自知之明的基础上，则会变成一种无知的自负，不可能取得持续的成功。,科学精神的核心是怀疑和批评。这种态度既对他人又对自己，“知人者智，自知者明”，“知常

4、曰明” 不能用看书取代上机实践，经常要想“自己怎样面对这个问题的挑战；如果由自己当场独立解题的话，会得到怎样的结果”。“纸上得来终觉浅，绝知此事要躬行”。看懂了不稀奇，会做有灵气，能讲清原理、提出质疑、拓延思路、探索新知才算了不起 在挑选练习题时，既不要因为轻视而放弃基础题；也不要因为畏难而放弃大题难题。,充分利用网络上与信息学活动相关的信息资源,1、由于网络上大量的算法知识和试题的出现，使得学生学习的大部分时间和空间由课堂转移到网上学习，自主性显著提高，学习方式发生了根本性的变化 2、学习的效率取决于如何在浩如烟海的网上信息中选择适应于竞赛需要和个性发展的东西 3、千万不要有“太易了不屑做、

5、太难了不愿做”的主观随意性,充分利用网络上与信息学活动相关的信息资源,编程解题能力是在长期的上机实践中积累起来的。如果长期的无所事事、无所作为，迟早会落得了“小题做不对、大题难题不会做”的可悲结局 应该对试题本身有一个科学的价值判断：“这道题是不是有利于夯实基础，或者这道题是不是引出带规律性的东西，能不能派生出更多类似的问题”，真正从提高自身的算法认知水平和编程能力的高度，来决定练习题的取舍。,以问题为出发点、以自主探究为途径、以构造网络式思维模式为基础、以创新为目的组织集训,第一步：界定问题。即明确试题要求我们做什么,解决什么问题，输出怎样的结果 第二步：明确出发点，即明确试题的初始状态是什

6、么，给出了哪些求解条件，其中哪些是显性的，哪些是隐性的，必须无一漏失。 第三步：寻找怎样做的创意。即要求学生独立思考，尽可能多地收集相关资料，尝试各种组合，调动所有的灵感和思考方式。 第四步：集中测试。每人设计三组测试数据,分别从一般情况、边界情况、扩大问题规模三个角度测试程序的正确性、时间效率和空间效率。然后交流测试数据，学生间进行互测。这样做既能测出自己程序的正确程度，又能在改善程序的时空效率上取长补短。,建立知识信息网络,归纳概括通过对相关问题（即形式不同、本质类似的一类问题）的归纳，揭示内在的联系，概括出解决类似问题的一般规律，并得到高度抽象、概括的模型，为以后分析问题、设计算法进行指

7、导。,触类旁通、联想外推,通过举一反三、由此及彼、触类旁通，从一个问题拓广出许多新问题。在解决这些新问题的过程中，进一步锻炼思维，并通过联想的线索将新问题、新模型、新算法并入知识网,近年来，由于各种竞赛纷纷采用free-pascal，因此对于算法来说，空间效率上的要求降低了，而对时间效率却提出了更高的要求。这使得选手不仅要娴熟地掌握常规算法，而且要大胆创新，构造更高效的算法来解决问题。 在以往的程序设计中，链式结构采用得较多。的确链式结构有编程复杂度低、简单易懂等优点，但有一个致命的弱点：相邻的两个元素间的联系并不明显。而树结构却能很好的做到这一点。 选手对树的先根遍历十分娴熟，但对后根遍历却

8、不能像先根遍历那样应用自如。,树结构在程序设计中的运用,一并查集 二线段树 三解决动态统计的静态方法 四、二叉树应用的拓广 五、先根遍历与后根遍历的应用 小结,并查集,竞赛中会经常遇到这样的题目：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。链结构的并查集树结构的并查集,链结构的并查集,链表被普通用来计算并查集.表中的每个元素设两个指针：一个指向同一集合中的下一个元素；另一个指向表首元素。采用链式存储结构，在进行集合查找时的算法复杂度仅为O（1）；但合并集合时的算法复杂度却达到了O（n

9、）。如果我们希望两种基本操作的时间效率都比较高的话，链式存储方式就“力不从心”了。,树结构的并查集,采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面我介绍一下树结构的并查集的两种运算方式直接在树中查询 边查询边“路径压缩”,对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低；时间效率高。返回,直接在树中查询,集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O（1）时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为

10、O（logN）。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O（N）。,边查询边“路径压缩”,其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数（x）。对于可以想象到的n，（n）都是在5之内的。,银河英雄传说,【问题描述】公元五八一年，地球居民迁移至金牛座第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队

11、司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1， 2， ， 30000。之后，他把自己的战舰也依次编号为1， 2， ， 30000，让第i号战舰处于第i列(i = 1， 2， ， 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为Mij，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战

12、舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：Cij。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。最终的决战已经展开，银河的历史又翻过了一页,【输入文件】 输入文件galax

13、y.in的第一行有一个整数T（1T500，000），表示总共有T条指 以下有T行，每行有一条指令。指令有两种格式： 1. Mij：i和j是两个整数（1i ， j30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 2.Cij：i和j是两个整数（1i ， j30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。 【输出文件】 输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理： 如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任

14、何信息； 如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。,设 varFather，Count，Behind：array1maxn of integer； 在同一队列中的战舰组成一个树型结构的并查集。 Fatherx 战舰x的父指针。Fatherx=x，表明战舰x为根节点。路径压缩后，树中所有子节点的父指针指向根节点； Countx 以节点x为根的树的节点数； Behindx 战舰x在列中的相对位置； 初始时，我们为每一艘战舰建立一个集合，即 Fatherx=x

15、Countx=1 Behindx=0（1x30000),1、查找根节点并进行路径压缩,function Find_Father(x：integer)：integer；查找节点x所在树的根节点，并进行路径压缩 var i，j，f，next：integer； beginix； 找出节点x所在树的根节点fwhile Fatherii do iFatheri； fi；ix；while if do 按照自下而上的顺序处理x的祖先节点beginnextFatheri；FatherIf；把节点i的父节点设为f，完成路径压缩jnext；repeatBehindiBehindi+Behindj；迭代求出路径上每

16、一个子节点相对于f的相对位置jFatherj；until Fatherj=j；inext；end；whilefind_Fatherf； 返回x所在树的根节点 end； Find_Father ,2、计算合并指令,procedure MoveShip(x，y：integer)；把x所在的集合合并入y所在的集合 var fx，fy：integer； beginfxfind_Father(x)；计算x所在树的根节点fxfyfind_Father(y)；计算y所在树的根节点fyFatherfxfy；将fx的父节点设为fy BehindfxCountfy；计算fx的相对位置为CountfyCountfyCountfy+Countfx；计算新集合的节点数 end； MoveShip ,