栈和队列2.pptVIP

函数的递归调用 1. 定义： 在调用一个函数的过程中直接或间接地调用该函数本身。 直接调用 int f(x) int x; { int y,z; ….. z=f(x); …… return (2*z); } 间接调用 int f1(x) int x; { int y,z; ….. z=f2( y); …… return (2*z); } int f2(t) int t; { int a,c; ….. c=f1(a); …… return (3+c); } 特点 是无终止的递归调用，因此，应该给定一个限制递归次数的条件。 3、栈的应用举例 栈的应用举例 栈的应用举例 问题 判断是运算符还是数据？ 算符比较算法 Char Precede( char c1, char c2) {int c_temp1, c_temp2; switch(c1) {case ‘ * ‘ : case ‘ / ‘ : c_temp1=4; break; case ‘ +‘ : case ‘ -‘ : c_temp1=2; break; . . . . . . } switch(c2) {case ‘ * ‘ : case ‘ / ‘ : c_temp2=3; break; case ‘ +‘ : case ‘ -‘ : c_temp2=1; break; . . . . . . } 续 if (c_temp1c_temp2) return( ‘ ‘ ); if (c_temp1=c_temp2) return( ‘ =‘ ); if (c_temp1c_temp2) return( ‘ ‘ ); } 栈的应用举例 3.2 栈的应用举例 3.1 栈 例 表达式求值 1）问题的提出 设计一个小计算器: 对键入的表达式进行求值。 如何对表达式求值呢？ 高级语言中的赋值语句：变量=表达式； Y=2; Z=3; X=y+z*2; 2） 表达式的构成 操作数+运算符+界符（如括号） 3） 表达式的求值： 例 5+6? (1+2)- 4 按照四则运算法则，上述表达式的计算过程为： 5+6? (1+2)- 4=5+6? 3- 4 = 5+18-4= 23-4=19 1 2 3 4 如何确定运算符的运算顺序？ 4） 算符优先关系表 表达式中任何相邻运算符c1、c2的优先关系有： c1c2：c1的优先级低于c2 c1=c2：c1的优先级等于c2 c1c2：c1的优先级高于c2 + c2 c1 - * / ( ) # + - * / ( ) # = = 算符间的优先关系表 注： c1 c2是相邻算符， c1在左， c2在右 算符的优先级设置 算符 栈内优先级 栈外优先级 * / + - ( ) # 4 3 1 5 0 -1 -1 5 0 2 5 算符优先算法 从左向右扫描表达式： 遇操作数——保存； 遇运算符号cj——与前面的刚扫描过的运算符ci比较 若cicj 则保存cj，（ 因此已保存的运算符的优先关系为 c1c2c3c4。。 ） 若cicj 则说明ci是已扫描的运算符中优先级最高者，可进行运算；? 若ci = cj 则ci为（，cj 为 ），说明括号内的式子已计算完，需要消去括号； 5 + 4 ? (1 + 2