资源描述：
《第3章 队列与堆栈ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.2栈的应用举例 3.2.5表达式求值算符优先法:（4+2*3）-10/5=（4+6）-10/5=10-10/5=10-2=8操作数(operand):进OPND栈操作符(operator):进OPTR栈界限符(delimiter):#、（）等#是我们设定的表达式开始和结束标识符。算符间的优先关系:θ1θ2+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<≒)>>>>>>#<<<<<=Precede:判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间的优先关系的函数。Operate:进
2、行二元运算aθb的函数。假定出现的表达式没有语法错误。算法基本思想:1、设置操作数栈OPND为空，表达式起始符#为运算符栈OPTR的栈底元素；2、依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后做相应操作，直到整个表达式求值完毕。算术表达式求值过程(算法3.4)OperandTypeEvaluateExpression(){InitStack(OPTR);Push(OPTR,‘#’);InitStack(OPND);c=getchar();while(c!=’#’
3、
4、Ge
5、tTop(OPTR)!=’#’){if(!In(c,OP)){Push(OPND,c);c=getchar();}//不是运算符则进栈elseswitch(Precede(GetTop(OPTR),c)){case‘<’://栈顶元素优先权低Push(OPTR,c);c=getchar();break;case‘=’://脱括号并接受下一个字符Pop(OPTR,x);c=getchar();break;case‘>’://退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Pus
6、h(OPND,Operate(a,theta,b));break;default:printf(“Expressionerror!”);return(ERROR);}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression对算术表达式3*(7-2)求值.步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#Push(OPND,’3’)2#3*(7-2)#Push(OPTR,’*’)3#*3(7-2)#Push(OPTR,’(’)4#*(37-2)#Push(OPND
7、,’7’)5#*(37-2)#Push(OPTR,’-’)6#*(-372)#Push(OPND,’2’)7#*(-372)#Operate(‘7’,’-‘,’2’)8#*(35)#POP(OPTR)9#*35#Operate(‘3’,’*’,’5’)10#15#Return(GetTop(OPND))**3.3栈与递归的实现将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：保存
8、被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈
9、顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n==1)2move(1,x,z);//将编号为１的圆盘从x移到z3else{4hanoi(n-1,x,z,y);//将x上编号为１至n-1的//圆盘移到y,z作辅助塔5move(n,x,z);//将编号为n的圆盘从x移到z6hanoi(n-1,y,x,z);//将y上编号为１至n-1的//圆
10、盘移到z,x作辅助塔7}8}83abc返址nxyz52acb51abc71cabvoidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(1,x,z);4else{5hanoi(n-1,x,z,y);6move(n,x,z);7han
