信息技术竞赛培训教程.docx

信息技术竞赛培训教程信息技术竞赛培训教程目录第二局部第二局部数据构造数据构造一栈二队列三链表四迭代及递推五递归六搜索及回溯七树及二叉树八排序算法九查找算法十图论根底知识广度优先搜索广度优先搜索第二局部第二局部 算法和数据构造算法和数据构造一一栈栈说到学习和掌握数据构造，很容易让人想到的就是其最本的数据构造模式：栈、队这一讲，我们就来谈谈“栈。“栈的应用很广泛，大家在程序设计中，常遇的一种错误就是“栈超界，那么，“栈为何物呢？栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进展，底部一般是不动的。栈就是一种类似桶堆积物品的数据构造，进展删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈，删除那么称为退栈。栈也称为后进先出表表。一个栈可以用定长为的数组来表示，用一个栈指针指向栈顶。假设，表示栈空，时栈满。进栈时加。退栈时减。当时为下溢。栈指针在运算中永远指向栈顶。、进栈算法假设时，那么给出溢出信息，作出错处理进栈前首先检查栈是否已满，满那么溢出；不满那么作；置栈指针加，指向进栈地址；()，完毕为新进栈的元素；、退栈算法假设，那么给出下溢信息，作出错处理(退栈前先检查是否已为空栈，空那么下溢；不空那么作)；()，退栈后的元素赋给；，完毕栈指针减，指向栈顶。进栈、出栈的实现过程程序：;();入栈();();出栈();对于出栈运算中的“下溢，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢，那么是一种致命的错误，将使程序无法继续运行，所以要设法防止。堆栈的数组模拟十进制数和其它进制数的转换是实现计算的根本问题，解决方法很多，下面给出一中算法原理：()其中为整除运算，为求余运算。例如：()()运算过程如下：、1、填空：()()()()、下面的程序实现这个转换过程，请补充完整。数制转化程序【】;():);();():);();();();.、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。、1、如果进站的车厢序列为，那么可能的出战车厢序列是什么？、2、如果进展进站的车厢序列为，问能否得到和的出站序列。栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。源程序编译中，假设要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句:;(式)其正确的计算结果应该是，但假设在编译程序中简单地按自左向右扫描的原那么进展计算，那么为：这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规那么。通常采用运算符优先数法。一般表达式中会遇到操作数、运算符和语句完毕符等，以算术运算符为例，对每种运算赋予一个优先数，如：运算符：优先数：语句完毕符“；的优先数为零在运算过程中，优先数高的运算符应先进展运算但遇到括号时，应另作处理。按这样的规定，对式自左向右进展运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进展编译时，一般设立两个栈，一个称为运算符栈，另一个称为操作数栈，以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句完毕，其处理原那么是：凡遇到操作数，一律进入操作数栈；当遇到运算符时，那么将运算符的优先数及运算符栈中的栈顶元素的优先数相比拟；假设该运算符的优先数大，那么进栈；反之，那么取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进展运算，并将运算结果存入操作数栈，然后继续比拟该运算符及栈顶元素的优先数。例如式中，当扫描到“和“时都要将运算符入栈。接着扫描到“号，其优先数小于乘号所以乘号退栈，并执行，将结果再存入操作数栈。再将“号的优先数及运算符栈的栈顶元素“号的优先数相比拟，两者相等，所以再将加号退栈，进展，结果为，再入栈，接着，由于运算栈已空，所以减号入栈。当扫描到“时，操作数入栈。当扫描到“；时，其优先数最低，所以减号退栈并执行，结果为并入栈。因已扫描到语句完毕符，所以表达式的求值完毕，结果为。例题模拟计算机处理算术表达式过程。从键盘上输入算术表达式串只含、运算符，充许含括号，输出算术表达式的值。设输入的表达式串是合法的。分析:建立两个栈，一个是操作数栈，一个是运算符栈，根据运算符的优先级对两个栈进展相应的操作。源程序;:;:;,:;,:;算符入栈运算();运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算();:(,);:(,);*:*;:;:;判断运算符的优先级别,建立标志函数;(,)();(*,)(*,);(:);();();()出站进站(左括号处理;();取数入操作数栈();();(,);(,);)右括号处理 (;();根据标志函数值作运算符入栈或出栈运算处理;();()();(,);.练习题：、读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.完毕)如果含有其他的字符，那么只要求输出错误信息及错误类型。含有大写字母 错误类型数字 错误类型其他非法字符 错误类型如 输入：!输出：输入：输出：、2、编码解码：从键盘输入一个英文句子，设计一个编码、解码程序。()编码过程：先键入一个正整数()()当两个表均不空时比拟两表指针指向的项指数,输出指数小的项系数和指数,同时改变该表指针 ();(,);();();(,);();假设两表指针指向的项指数相等,那么两系数相加输出,两表指针同时改变 假设有一表空,那么输出另一表的剩余项 ();(,);();();.源程序二：多项式相加的链表实现;,:;:;,:;:;(:);建立多项式系数、指数链表:;:;();(,);();(,);(:);();();(:);();();();()()();(,);();(,);();(,);();(,);)()(;直至队空为止;();(:)();()();();();()();();();在矩阵中寻找细胞();.四四迭代及递推迭代及递推本次我们想及大家共同探讨一下迭代及递推。在计算机数值程序设计中，迭代及递推是两个重要的根底算法。一、迭代许多的实际问题都能转化为解方程()的实数解的问题。求根可以直接从方程出发，逐步缩小根的存在区间，把根的近似值逐步准确到要以满足具体实际问题的需要为止，该算法称为迭代。迭代的一般原那么可以用一个数学模型来描述，现要求出方程()的解：先设()()，那么方程()可化为()，这就产生了一个迭代算法的数学模型：从某一个数出发，按此迭代模型，求出一个序列：，当小于一个特定值误差许可值时，这时可认定()。也就是说，求出的已经可以作为原方程()根的近似值了。设误差许可值为，那么迭代算法的图如图。图 迭代算法框图迭代算法的关键在于确定迭代函数()。确定()时需保证产生的迭代序列 是否能使两个相邻的数之间的差距越来越小即两数的差值越靠近误差值，我们称这样的序列为收敛序列，因为只有这样才能使根的存在范围越来越小，从而为根的取得创造条件。例 求的算术平方根不使用内部函数。分析:使用迭代算法来解决这个问题，使用迭代法可以先设()，那么求 的算术平方根的近似值就可以转化为求()的正根。列出等价方程()，以()为迭代函数，以为初始近似值，误差值设定为，那么程序可写成：;();()();将的值转为的算术平方根();.程序的输出结果如下：()开场时，迭代函数的根的近似值设定在之间，由于区间宽度大于给定误差许可值，于是再进展迭代运算，产生下一个区间；其宽度仍然大于误差许可值，再产生下一个区间；如此反复，直到区间的宽度小于误差给定值时，那么说明在该区间中，任意选择一个数都可以满足根的近似值要求了。为方便起见，取下该区间的边界置作为近似值。这就是迭代算法的一般原那么的表达了。二、.递推对于一个的序列来说，如果它的通项公式即表达位置及位置上的数据的关系的公式，那么，要求出数列中某项之值是十分容易的。但是，在许多情况下，要得到数列的通项公式是很困难的，甚至无法得到。然而，一个有规律的数列的相邻位置上的数项之间通常存在着一定的关系，我们可以借助的项，利用特定的关系逐项推算出它的后继项的值，如此反复，直到找到所需的那一项为止，这样的方法称为递推算法。递推算法的首要问题是得到相邻的数据项间的关系即递推关系。递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成了连续的假设干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。例 著名的菲波纳葜()数列，其第一项为，第二项为，从第三项开场，其每一项都是前两项的和。编程求出该数列第项数据。分析：按菲波纳葜数列的原那么，数列为：无疑地，寻找其项数位置及项值的关系即通项公式是非常困难的。而根椐该数列的形成规那么，其有一个的公式即说明了相邻的数据项之间的明显关系。因此，可以其作为递推公式，以项及为起点，逐项产生第项、第项、，直到取得需要的第项为止。在其递推算法的语言实现上，可取、三个变量，分别表示前二项、前一项及当前项，、分别取初值及。第一次通过递推公式得到第三项，并进展移位，即取值、取值，为下次递推作准备；如此反复，经过次的递推，就是第项的值第次产生的是项的值。源程序如下:;()();();(,);.菲波纳葜数列的递推明确地表达了递推算法程序设计的一般原那么，即递推公式取得。例 数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。、一步可沿左斜线向下或右斜线向下走；、角形行数小于等于；、三角形中的数字为，；测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：分析：此题解法有多种，从递推的思想出发，可以设想，当从顶层沿某条路径走到第层向第层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设，存放从，出发到达层的最大值，那么，即为所求的数字总和的最大值。源程序如下：;();();();.五五递归递归在四中，我们了解了迭代及递推。及迭代、递推相对应的算法为递归，本趣谈数据构造，我们就来谈一谈递归算法。递归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。简单地说，递归就是编写这样的一个特殊的过程，该过程体中有一个语句用于调用过程自身称为递归调用。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程可以用图所示。图递归过程的执行流程从图可以看出，递归过程的执行总是一个过程体未执行完，就带着本次执行的结果又进入另一轮过程体的执行，如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，那么不再深入，而执行本次的过程体余下的局部，然后又返回到上一次调用的过程体中，执行其余下的局部，如此反复，直到回到起始位置上，才最终完毕整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合逐步深入，而后又逐步返回的递归调用模型，以解决实际问题。利用递归调用程序设计技术可以解决很复杂但规律性很强的问题，并且可以使程序变得十分简短。例 利用递归调用手段编程计算!。分析：根椐数学知识，正整数的阶乘为：*()*()*，该阶乘序列可转换为求*()!，而()!以可转换为()*()!，直至转换为*!，而。源程序如下:;();()*;()();();();.在过程中，当时，又调用过程，参数为，这种操作一直持续到为止。例如当时，()的值变为*()，求()又变为*()，当 时递归停顿，逐步返回到第一次调用的初始处，返回结果*，即!。例 利用递归调用技术求菲波纳葜数列的第项。分析：我们已经知道菲波纳葜数列的各数列的产生可用以下公式表示：当时因此当大于时，求第项值可转化为求第项值及第项值的和；而求第项又可转化为求项值及项的和，相应地，求项值可转化为求项值和项值的和；如此反复，直至转化为求第项或第项值，而第 项及第项为值和。源程序:;();();();()();();(,)();.本程序采用了函数递归，函数的执行比拟复杂。函数由于存在着两次的递归调用，使递归调用产生执行流程的二叉树行式，大家可参照图来理解这个执行过程。为方便起见，设定，图中的数码表示递归执行的顺序。图 函数的二叉树执行流程递归调用技术的运用，是在牺牲计算机内存空间和程序执行速度的根底上得到的。因为在递归调用的执行过程中，系统必须花费时间及空间以栈的方式记下每次调用的返回位置地址及每一次过程执行的中间结果，以便当递归调用终止条件成立时，能沿着逐步深入的路线逐步返回，取得这些数据，最终准确地回到初始调用处。比方，同是解决菲波纳葜数列问题的程序，使用递推就比使用递归算法设计的程序执行速度快了许多。当一个问题蕴含着递归关系且构造比拟复杂时，采用一般的算法，不仅给程序的设计带来许多困难，而且也会给设计出的程序带来篇幅大、可读性差的缺点，这时采用递归调用技术来设计程序那么会带来相反的效果。例相传在古印度的布拉玛婆罗门圣庙的僧侣在进展一种被称为汉诺塔的游戏，其装置是一块铜板，上面有三根杆编号、，杆上自下而上、由大到小按顺序串上个金盘如图。游戏的目标是把【演示程序：】杆上的金盘全部移到杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许大盘移到小盘之上。现要求利用递归调用技术给出个盘从杆移到杆的移动过程。图 阶汉诺塔分析：这个移动过程很复杂及烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动杆最底部的大盘，而不是其顶部的小盘。不考虑个盘而考虑个盘的一般情况。要想将杆上的个盘移至杆，我们可以这样设想：.以盘为临时杆，从杆将至号盘移至杆。.将杆中剩下的第号盘移至杆。.以杆为临时杆，从杆将至号盘移至杆。我们看到，步骤只需移动一次就可以完成；步骤及的操作那么完全一样，唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为及原问题一样性质的、规模小一些的新问题图。即：()可转化为()及()其中中的参数分别表示需移动的盘数、起始盘、临时盘及终止盘，这种转换直至转入的盘数为为止，因为这时已无盘可移了。这就是需要找的递归调用模型。图 阶汉诺塔源程序如下:;();();(,);();()();();.如果说例及例题的无法表达递归算法的独特优点，那么，例的解法那么很能说明问题，因为一般的算法是很难解决这个问题的，而过程只用了个语句就解决这个难题。不过要说明的是，按照汉诺塔的移动原那么，将个盘从杆移动到杆需要移动盘的次数是的次幂减，那么个盘移动次数就是，近亿亿次。这是一个天文数字，即使一台功能很强的现代计算机来解汉诺塔问题，恐怕也需要很长的时间，因此要想得到结果，在运行程序时，输入的可不能太大。据说布拉玛婆罗门圣庙的僧侣声称，汉诺塔游戏完毕就标志着世界末日的到来，现在看来确实是有道理的。因为如果每秒移动一次，个盘那么大约需近亿年，而据科学家以能源角度推算，太阳系的寿命只不过 亿年而已。()非波那契()数列.数列的递归公式如下:11F()21F()12nnnFFF(3n)按照上面的递归公式,可写出如下程序;:;(:):;()();递归左子树()();递归右子树;();();();.递归的应用.经典递归例如塔问题：经典的递归，原问题包含子问题。有些问题或者数据构造本来就是递归描述的，用递归做很自然。.递归及递推利用递归的思想建立递推关系，如由兔子生崽而来的数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。.分治不少分治方法是源于递归思想，或是递归分解合并处理。.回溯规模较小的问题用回溯解决比拟自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。.动态规划动态规划的子问题重叠性质及递归有某种相似之处。递归动态修改查表是一种不错的建立动态规划模型的方法。.其他其他么，就是不好归类。例如表达式处理，排列组合等。附带说一下，用递归来处理打印方案的问题还是很方便的。求把一个整数无序划分成份互不一样的正整数之和的方法总数。分析 这是一道动态规划题，动态方程如下：()()()()此题可以用循环来实现递推,也可以考虑用递归求解。主过程如下：方案一：(;);()()()()()()();();()()();();方案二：();()()();可以看出，方案一的程序较为冗长，消耗栈空间较大；而方案二较为简洁明了，所用的栈空间也较小，效率较高。因此，使用递归算法也有一个优化问题。算法的简洁及否直接制约了程序的可行性和效率。总结递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据构造时更能体会到这一点。但是，递归在每一次执行时都要为局部变量、返回地址分配栈空间，这就降低了运行效率，也限制了递归的深度。因此，在必要的时候可以只使用递归的思想来求解，而程序那么转用非递归的方式书写。递归习题:.一一.九连环问题:有()个环,拆装这些环的规那么:第一个环可以随意拆装,第二个环只有在第一环已装上时可以拆装;第个环只有在第环已装上,且第，第第环都拆下时可以装拆.编程序描述拆下个环的过程.的所有路径:键盘输入一个含有括号的四那么运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持及原表达式等价。例：输入表达式应输出表达式()(*)*()()注意输入时不能输出。表达式以字符串输入，长度不超过。输入不要判错。所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式化简。有一个人在一个公共汽车站上，从到观察公共汽车到达本站的情况，该站被多条公共汽车线路所公用，他记下了公共汽车到达本站的时刻。在这个期间内，同一条线路上的公共汽车以一样的时间间隔到站。时间单位用“分表示，从到。每条公共汽车线路上的车至少到达本站两次。在本例的公共汽线路数一定。来自不同线路的公共汽车可能在同一时刻到达本站。不同公共汽车线路的车首次到站时间和或 时间间隔到站的可能一样。如果两条公共汽车线路的车有一样的开场时间和一样的时间间隔，它们必须分开表示出来。请为公共汽车线路编一个调度表，目标是：公共汽车线路数目最少的情况下，使公共汽车到达本站的时刻满足输入数据的要求。对于每一公共汽车线路，输出其起始时刻第一次到达本站和到达本站的时间间隔。输入数据：输入文件首先给出观察者所看到的驶进本站的公共汽车数，下面以递增顺序给出各公共汽车到达本站的时刻。我们的例子是：输出数据：在输出文件中列一个表，每一行表示一条公共汽车线路。行中第一个数字表示该线路上的公共汽车的首次到达本站的时刻；第二个数字表示该线路上的公共汽车两次到达本站的时间间隔。时间的单位是分。各公共汽车线路在表中出现的先后顺序没有重要性次序可任意。假设有多个等价解，仅需输出其中一个。我们例子的输出文件的内容为：六六搜索及回溯搜索及回溯本讲，我们来谈谈搜索及回溯。搜索及回溯是计算机解题中常用的算法，有很多问题无法根据某种确定的计算法那么来求解，此时可以利用搜索及回溯的技术求解。回溯是搜索算法中的一种控制策略。它的根本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进展，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，那么沿该方向再向前试探；如果已无路可走，那么返回一步，再看其它方向是否还有路可走；如果有路可走，那么沿该方向再向前试探。按此原那么不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。皇后问题【演示程序皇后问题【演示程序：，源程序，源程序：】问题描述：求出在一个的棋盘上，放置个不能互相捕捉的“皇后的所有布局。算法分析：这是来源于国际象棋的一个问题。皇后可以前、后、左、右和沿着对角线方向相互捕捉。如下图，一个皇后放在棋盘行列位置上，棋盘打的位置就不能再放置皇后。上图提示我们，一个适宜的解应是在每列、每行确实有一个皇后，且在一条对角线上最多只有一个皇后。在开发程序之前，设定表示棋盘的数据构造是一个数组。每一个位置代表棋盘上的一个方格。然而考虑到一个合理的解中每列、每行只能放置一个皇后，棋盘也可用一个一维数组来表示。数组的每一个元素代表棋盘的一列，该元素的值是皇后在该列上的行位置。设数组名为,对于图有。它表示第列的第行有一个皇后。为找到一个解，必须从空布局开场，每放置一个皇后要检查布局是否合理。在合理的情况下，试探找下一个皇后的位置；如果布局不合理，就改变布局。重复检查、试探或检查、改变位置，直到找到最后一个皇后的合理位置，这时就找到一个合理的布局。重复以上过程直到无法再改变皇后位置为止，就可找到所有合理的布局。通过以上讨论，得到程序的第一层描述如下：,:;为皇后总数目，为当前已放置的皇后数:;布局合理及否:;解();输入皇后数目;空布局是合理的搜索到一个解;打印改变布局，继续找解继续试探下一个皇后位置;检查布局是否合理皇后位置不能再改变.子过程改变布局就是试探当前皇后的下一个位置，即试着放在下一列上()。如果，说明当前皇后无位置可放，必须返回到上一个皇后的状态，改变第个皇后位置。为了防止存取不存在的，给数组增设一个元素，它的初值为。;子过程就是试探下一个皇后的位置，这时要尽可能试探完所有的位置，即从第一列放起：;主要的困难是过程。见图中，在棋盘上对列上的皇后配置是检查四个方向；纵向。由问题的数据构造保证一列只放一个皇后。横向。对所有(,)检查不等式是否成立。左高右低对角线。共有()条这样的对角线。同一条对角线上的不同位置它们的行号值及列号值之差相等。所谓检查列上的皇后配置是否及前面的皇后在同一条左高右低对角线上，就是检查对所有(,)不等式成立：()()。左低右高对角线。类似，检查列上的皇后配置是否及前面的皇后在同一条左低右高对角线上，就是检查对所有的(,)不等式成立：()()。【源程序】皇后问题程序(,);:;:;:;,:;转置输出;(,:(*),);(,*);()()()();():);();()();(.);(,.).七七树及二叉树树及二叉树有了前面的数据构造根底，这一讲开场，我们谈点较深入的数据构造知识。本讲，我们先来谈谈树，建立树的根本概念及根本的处理方式。树是一种重要的非线性数据构造，直观地看，它是数据元素在树中称为结点按分支关系组织起来的构造，很象自然界中的树那样。树构造在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法构造。又如在数据库系统中，树型构造也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。一、树的概述树构造的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据构造表示。一树的定义树是由一个或多个结点组成的有限集合，其中：必有一个特定的称为根()的结点；剩下的结点被分成个互不相交的集合、，而且，这些集合的每一个又都是树。树、被称作根的子树()。例如，一个集团公司，可以描述如下:它很象一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据构造就叫做树构造，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的双亲，结点的后趋结点称为该结点的子女或孩子，同一结点的子女之间互称兄弟。二树的表示树中每个结点的内容分两局部表示：结点的性质；结点的指针域。结点的性质：描述结点的必要数据。结点的指针域：指向结点的每一个孩子。指针域采用多重链表，又分为不定长度结点的多重链表及固定长度结点的多重链表。不定长度结点的多重链表表示树时，每个结点的指针域个数等于该结点的孩子的个数，其形式如下:每个指针域指向一个孩子，这样虽然不浪费空间，但由于结点长度不等，将给存储分配造成困难，给各种运算带来极大不便。固定长度结点的多重链表表示树时，树中每个结点的指针域个数都相等于树中结点的最大度数，也就是说，不管结点的孩子多少，其长度均取最大长度。这样长度划一，处理问题简单方便，但对存储空间浪费很大。为了寻求一种恰当的树的存储表示方法，我们将讨论一种称之为二叉树的树型构造。二、二叉树：二叉树是一种十分重要的树型构造。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。定义：二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。图列出了二叉树的五种根本形态。为空二叉树；()只有一个结点的二叉树；()只有左子树的二叉树；()只有右子树的二叉树；()左右完全的二叉树。二满二叉树：一棵深度为的满二叉树，是有个结点的深度为的二叉树。个结点是二叉树所能具有的最大结点个数。图所示为一棵深度为的满二叉树。图图二叉树的性质：二叉树的的层上最多只有12i个结点(1i)。深度为的二叉树，最多只有21k个结点。三完全二叉树对满二叉树，从第一层的结点(即根)开场，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有个结点，深度为的二叉树，当且仅当所有结点对应于深度为的满二叉树中编号由至的那些结点时，该二叉树便是完全二叉树。图是一棵完全二叉树。四二叉树的存储：二叉树一般采用双重链表作为其存储构造，表中每个结点都有三个域：数据域、左指针域和右指针域。其中指针域和分别指向其左孩子和右孩子。如下图。图二叉树结点的构造形式三、二叉树的遍历遍历是对树的一种最根本的运算，所谓遍历二叉树，就是按一定的规那么和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性构造，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设、分别表示遍历左子树、访问根结点和遍历右子树，那么对一棵二叉树的遍历有三种情况：称为先根次序遍历，称为中根次序遍历，称为后根次序遍历。（一）一先根次序遍历的递归定义假设二叉树为空，那么返回；否那么，依次执行以下操作：访问根结点；按先根次序遍历左子树；按先根次序遍历右子树；返回。例：右图为表示表达式 的二叉树。先序遍历此树时，首先访问根结点，得到字符。继而访问结点的左子树，按递归定义，先访问子树的根结点，得到字符。类推访问结点的左子树，此时只有叶子。得到叶子后，访问叶子父结点的右子树，得到右子树的根结点字符。再访问结点的左子树，得到叶子字符后，访问字符父结点的右子树，得到右子树根结点字符，。先序遍历完整棵树，得到序列为：这就是表达式的前缀表示或称波兰表示。二中根次序遍历的递归定义假设二叉树为空，那么返回；否那么，作如下操作：按中根次序遍历左子树；访问根结点；按中根次序遍历右子树；返回。中序遍历图二叉树时，引入栈，先将根结点字符入栈，按定义访问根结点的左子树，遇到子树的根结点字符入栈，访问结点的左子树，到达叶子字符，那么字符为第一个访问的结点。接着，将栈顶字符出栈，访问子树根结点字符。继而访问其右子树，方法同上，子树根结点入栈，。这样，中序遍历完整棵树后，得到的序列为：这就是表达式的中缀表示。三后根次序遍历的递归定义假设二叉树为空，那么返回；否那么，作如下操作：按后根次序遍历左子树；按后根次序遍历右子树；访问根结点；返回。对上图二叉树，后序遍历后得到的序列为：这就是表达式的后缀表示或称表达式的逆波兰表示。逆波兰表示的表达式的优点在于它得到的是不加括号的表示式，但从表示式中确能确定表达式的运算先后顺序。故在源程序如下编译表达式值的处理等方面的应用中经常用到。习题：下面的图表示的二叉树的前序遍历序列：中序遍历序列：后续遍历序列。例题：在磁盘的目录构造中,我们将及某个子目录有关联的目录数称为度。例如以下图：该图表达了盘的目录构造均表示子目录的名字.在这里,根目录的度为。子目录的度为子目录的度为的度均为。假设不考虑子目录的名字.那么可简单的图示为如下的树构造:假设知道一个磁盘的目录构造中.度为的子目录有个,度为的子目录有个,度为的子目录有个。试问：度为的子目录共有几个。习题：设叉树采用列表法表示,即每棵子树对应一个列表,列表的构造为:子树根结点的值局部(设为一个字符)和用“括起来的各子树的列表(如有子树的话),各子列表问用“，分隔。例如下面的三叉树可用列表()()表示。写出右图的三叉树用列表形式表示的结果：。图的根本知识图的根本知识图是一种数据构造，在图中的数据元素通常称为顶点，两个顶点之间的连线称为弧边。最小生成树：最小生成树：假设要在个城市之间建立通信联络网，那么连通个城市之需要条线路。这时，这时自然需要考虑这样一个问题，如何在最节省经费的前提下建立通信网。我们用图的顶点表示要连通的城市，两个城市之间的连线上标出线路的造价权构成一张加权图。这样我们就建立了一个数学模型，接下来我们介绍解决这个数学问题的方法。方法一：在图中选择任何一个圈，删掉权最大的边，如此反复，直到图中没有圈为止。方法二：从所有的边中选择权最小的一条，重复操作选取的边不能及已经选择的顶点构成圈，直到所有的顶点构成的图是连通的。习题：画出下面图的最小生成树。【一笔画问题】如果图是连通的，并且奇顶点的个数为或者，那么图是一笔画，而且在奇顶点的个数为时，这个一笔画最后回到出发点。例题：下面哪些图能够一笔画出。八八排序算法排序算法【演示程序【演示程序：】一、插入排序().根本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。.排序过程：【例如】：初始关键字()()()()()()()(:);对按递增序进展插入排序,是监视哨依次插入;查找的插入位置;将大于的元素后移;插入;二、选择排序.根本思想：每一趟从待排序的数据元素中选出最小或最大的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。.排序过程：【例如】：初始关键字 第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后第六趟排序后 第七趟排序后 最后排序结果(:);对进展直接选择排序做趟选择排序;在当前无序区中选最小的元素 ;交换和;三、冒泡排序().根本思想：两两比拟待排序数据元素的大小，发现两个数据元素的次序相反时即进展交换，直到没有反序的数据元素为止。.排序过程：设想被排序的数组垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原那么，从下往上扫描数组，凡扫描到违反本原那么的轻气泡，就使其向上漂浮，如此反复进展，直至最后任何两个气泡都是轻者在上，重者在下为止。【例如】：(:)从下往上扫描的起泡排序做趟排序;置未排序的标志从底部往上扫描()交换 和 这两个数说明：该函数的功能是实现在给定数组的前数中将最大的放入中,完成冒泡排序的一趟排序。外部循环函数的实现：(,)冒泡排序伪代码为数组的元素的个数，数组下标从开场,对数组前个数排序说明：当数组的元素个数为个时，就要进展次内部比拟和交换的调用。四、快速排序.根本思想：在当前无序区中任取一个数据元素作为比拟的基准(不妨记为)，用此基准将当前无序区划分为左右两个较小的无序区：和，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准那么位于最终排序的位置上，即()，当和均非空时，分别对它们进展上述的划分过程，直至所有无序子区中的数据元素均已排序为止。.排序过程：【例如】：初始关键字 第一次交换后 第二次交换后 向左扫描，位置不变，第三次交换后 向右扫描，位置不变，第四次交换后 向左扫描 一次划分过程初始关键字 一趟排序之后 二趟排序之后 三趟排序之后最后的排序结果各趟排序之后的状态(:;,:;:);对无序区做划分，给以出本次划分后已被定位的基准元素的位置;初始化，为基准()()从右向左扫描，查找第个小于 的元素已找到;相当于交换和;()()从左向右扫描，查找第个大于 的元素;相当于交换和;基准已被最终定位;(;:);对快速排序当为空或只有一个元素是无需排序(,);对做划分(,)递归处理左区间(,)递归处理右区间;五、堆排序().根本思想：堆排序是一树形选择排序，在排序过程中，将看成是一颗完全二叉树的顺序存储构造，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。.堆的定义:个元素的序列.称为堆，当且仅当该序列满足特性：()堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点称为堆顶的关键字最小，我们把它称为小根堆。反之，假设完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，那么称之为大根堆。.排序过程：堆排序正是利用小根堆或大根堆来选取当前无序区中关键字小或最大的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的根本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。【例如】：对关键字序列，建堆(;,:);在数组中调用，使得以它为完全二叉树构成堆。事先其左、右子树(时)均是堆;*;假设,是的左孩子假设当前被调整结点有左孩子()令指向关键字较大的右孩子指向的左、右孩子中关键字较大者 孩子结点关键字较大;将换到双亲位置上;*继续以为当前被调整结点往下层调整;调整完毕，退出循环将最初被调整的结点放入正确位置(:);对进展堆排序建立初始堆(,)进展趟排序;将当前堆顶记录和堆中最后一个记录交换(,)将重成堆;六、几种排序算法的比拟和选择.选取排序方法需要考虑的因素：()待排序的元素数目；()元素本身信息量的大小；()关键字的构造及其分布情况；()语言工具的条件，辅助空间的大小等。.小结：()假设较小();();(:);(:);();(:);();();.十十图论根底知识图论根底知识广度优先搜索广度优先搜索一、队、队的定义：队是特殊的线性表之一，它只允许在队的一端插入，在队的另一端删除。插入一端叫队尾，删除一端叫队首，没有任何元素的队叫做空队。队列遵循先进先出原那么，排队购物、买票等，就是最常见的队。队的根本操作：队的描述：;定义数组;队首、队尾指针初始化图：；：；：；入队操作图：；();读入数据；队尾加一：；出队操作图：；队首加一：；二、广度优先搜索广度优先搜索类似于树的按层次遍历的过程。它和队有很多相似之处，运用了队的许多思想，其实就是对队的深入一步研究，它的根本操作和队列几乎一样。三、队和广度优先搜索的运用右图表示的是从城市到城市的交通图。从图中可以看出，从城市到城市要经过假设干个城市。现要找出一条经过城市最少的一条路线。图分析：看到这图很容易想到用邻接距阵来表示，表示能走，表示不能走。如图。图首先想到的是用队的思想。我们可以记录搜索过程，记录经过的城市记录前趋元素，这样就可以倒推出最短线路。具体过程如下将城市入队，队首、队尾都为。将队首所指的城市所有可直通的城市入队如果这个城市在队中出现过就不入队，可用一个集合来判断，将入队城市的指向队首的位置。然后将队首加，得到新的队首城市。重复以上步骤，直到城市入队为止。当搜到城市时，搜索完毕。利用可倒推出最少城市线路。以下为参考程序：(),(),(),(),(),(),(),();记录定义;.;输出过程();();步骤();队首加一，出队搜索可直通的城市()判断城市是否走过();队尾加一，入队();主程序;.输出：例题：求三角形最大面积例题：求三角形最大面积题目描述圣诞节快到了。你承受了一件荣耀的任务，就是制作圣诞树顶上的那颗大星星。不过当你拿到不过当你拿到制作用的三角形银纸的时