第三章栈和队列 - 数据结构.ppt

《数据结构》第三章 栈和队列;栈和队列概述;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;3.1栈;float evaluate(char exp[]) {/*实现开辟操作数栈s1和运算符栈s2，并将(入到s2中；exp是输入表达式串*/ while(1) {从exp中取出一个单词x switch(x) { case x是操作数:push(s1,x);break; case x是): 反复出栈处理,直到遇到(为止.break; case x是;:反复出栈处理，直到栈只剩下(为止；return 操作数栈顶值; case x是其它运算符: while(ielp(x)=isp(s2.elem[s2.top--])){出栈处理} push(s2,x);break; }//switch }//while };3.1栈(学生自已看;;3.1栈(学生自已看);基本思想： 1)如果(n,x,y)是递归终点,则直接返回具体值; 2)如果(n,x,y)不是递归终点,那么形成新的参数(n-1,A(n,x,y-1),x)。但必须先求A(n,x,y-1),的值，因此需要将[n,x]入栈。这个过程称为一次递归。 3)整个算法就是无限循环，反复执行递归和返回操作，直到栈空时，结束算法。 ;3.1栈(学生自已看);算法思想： 1)递归:只要n!=0y!=0, 则反复执行： y--;准备计算下一个A(n,x,y) 将返回信息(n-1,x)入栈 2)返回：如果(n,x,y)是递归终点，得到一个终点值v。如果栈空，算法结束。否则弹出栈顶，构成新的参数(n-1,v,x)再次进入递归。;3.1栈(学生自已看);typedef struct { int n, x, y; }elemtype; int Ackerman(int n,int x, int y) {SQSTACK s; elemtype e; int v; initstack(s); e.n=n; e.x=x; e.y=y;push(s,e);/*初始参数入栈*/ while(!stackempty(s)) {gettop(s,e);n=e.n;x=e.x;y=e.y;/*获取栈顶参数*/ while(n!=0y!=0)/*一直递归到终点*/ {y--;e.n=n;e.x=x;e.y=y; push(s,e);/*继续入栈下一组参数*/ } v=Akmvalue(n,x,y);pop(s,e);/*终点参数出栈*/ if(stackempty(s)) return v; else {pop(s,e);e.n--;e.y=e.x;e.x=v; push(s,e);/*替换成新的栈顶参数*/ } }//while };3.1栈(学生自已看);迷宫行走的8个方向;算法思想： 1)用二维数组maze表示迷宫，数组单元是0表示可走，是1表示不通。 2)将方向按顺时针编成号：1－8，1表示正北 3)利用两个一维数组表示位置的变化两： int movex[]={0,-1,-1,0,1,1, 1, 0,-1};//行变化 int movey[]={0, 0, 1,1,1,0,-1,-1,-1}; //列变化 注意：movex[0]、movey[0]为无效方向;1、确定入栈的返回信息，这些返回信息在出栈时可以帮助计算函数值或者新的返回信息 2、确定入栈的条件，即非递归终点的条件 3、确定出栈时对栈顶的操作，是替换成新的返回信息还是直接出栈 4、确定算法终止的条件;递归问题的非递归算法编写技巧;3.2队列;3.2队列;;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;3.2队列;栈空间分配 ;O V E R