第四章　栈和队列VIP免费

第四章栈和队列栈和队列是两种重要的线性结构。从数据结构角度看，栈和队也是线性表，其特殊性存于栈和队的基本操作是线性表操作的子集，它们是受限制的线性表。一、栈（stack）栈顶（top）栈底（bottom）空栈栈又称为后进先出（lastinfirstout）线性表。关于栈的操作有：1）inistack(s)初始化操作，设定一个空栈要S。2）empty(s)关栈空函数。空返回“true”。3）push(s,x)入栈操作。4）pop(s)出栈函数。5）gettop(s)取栈顶元素函数。6）clear(s)栈置空操作。7）current_size(s)求当前栈中元素个数函数。栈的一个重要应用是在程序设计语言中实现递归过程。递归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。简单地说，递归就是编写这样的一个特殊的过程，该过程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程可以用图1所示。图1递归过程的执行流程从图1可以看出，递归过程的执行总是一个过程体未执行完，就带着本次执行的结果又进入另一轮过程体的执行，……，如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分，……，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合"逐步深入，而后又逐步返回"的递归调用模型，以解决实际问题。利用递归调用程序设计技术可以解决很复杂但规律性很强的问题，并且可以使程序变得十分简短。它经常出现在以下几个方面：1）有很多数学函数是递归定义的。如（1）阶乘函数1n=0fact(n)=n*fact(n-1)n>0（2）菲波拉契数列（Fibonacci）0n=0fib(n)=1n=1fib(n-1)+bib(n-2)其它情形（3）阿克曼函数（Ackerman）n+1m=0ack(m,n)=ack(m-1,1)n=0ack(m-1,ack(m,n-1))其它情形2）有的数据结构本身固有的递归特性。如：二叉树广义表等3）还有一类问题，虽则问题本身没有明显的递归结构，但用递归求解比迭代求解更简单。如：八皇后问题，汉诺塔（Hanoi）问题等。例4_1利用递归调用手段编程计算N!。分析：根椐数学知识，1!=1，正整数N的阶乘为：N*(N-1)*(N-2)*…*2*1，该阶乘序列可转换为求N*(N-1)!，而(N-1)!以可转换为(N-1)*(N-2)!，……，直至转换为2*1!，而1!=1。源程序如下:(例程见exm_4_1.pas)programexm4_1;varn:integer;y:real;functionfac(n:integer):real;beginifn=0thenfac:=1elsefac:=n*fac(n-1)end;beginwrite('N=');readln(n);y:=fac(n);writeln(n,'!=',y:1:0);readln;end.在函数fac中，当N>1时，又调用函数fac，参数为N-1，…，这种操作一直持续到N=1为止。例如当N=5时，fac(5)的值变为5*fac(4)，求fac(4)又变为4*fac(3)，…，当N=1时递归停止，逐步返回到第一次调用的初始处，返回结果5*4*3*2*1，即5!。练习一：利用递归调用技术求菲波拉契数列的第N项。例4_2、相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏，其装置是一块铜板，上面有三根杆（编号A、B、C），A杆上自下而上、由大到小按顺序串上64个金盘（如图3）。游戏的目标是把A杆上的金盘全部移到C杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许大盘移到小盘之上。现要求利用递归调用技术给出N个盘从A杆移到C杆的移动过程。图3N阶汉诺塔分析：这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：1.以C盘为临时杆，从A杆将1至N-1号盘移至B杆。2.将A杆中剩下的第N号盘移至C杆。3.以A杆为临时杆，从B杆将1至N-1号盘移至C杆。我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同，唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模...