栈和队列(余云)解读.ppt

数 据 结 构 院(系): 信息工程学院 教 师: 余 云 表达式求值 取链栈栈顶元素 SElemType GetTop(LinkStack S) { if (S==NULL) exit(1)； else return S–data; } 3.2 栈的应用 例1：数制转换（十转N） 用栈暂存低位值 例2：括号匹配的检验 用栈暂存左括号 例3：表达式求值 用栈暂存运算符 例4：迷宫求解 用栈实现递归调用 简化了程序设计的问题 算术四则运算规则 (1) 先乘除,后加减 (2) 从左算到右 (3) 先括号内,后括号外 表达式 常数 标识符 操作数(operand) 运算符(operator) 界限符(delimiter) 算术 逻辑 关系 括号 结束符 【算法思想】 表达式求值—— （1）初始化OPTR栈和OPND栈，将 “#”压入OPTR （2）依次读入字符ch，循环执行（3）至（5） （3）取出OPTR的栈顶元素，当OPTR的栈顶元素和ch均为“#”时，表达式求值完毕，OPND栈顶元素为表达式的值 设定两栈 ：OPND-----操作数或运算结果　OPTR------运算符 （4） if (ch是操作数) 则ch进OPND，读入下一字符ch （5） else 比较OPTR栈顶元素和ch的优先级 case ‘’: 运算符ch 进OPTR，读入下一字符ch case‘=’: 脱括号（弹出左括号），读入下一字符ch case ‘’: 栈顶运算符退栈、计算，结果进OPND OperandType EvaluateExpression( ) { InitStack (OPND); ch = getchar( ); while (ch!= # || GetTop(OPTR)! = #) { if (! In(ch,OP)){Push(OPND,ch); ch = getchar(); } // ch不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch)) { //比较优先权 case : //当前字符ch压入OPTR栈，读入下一字符ch Push(OPTR, ch); ch = getchar(); break; case : //弹出OPTR栈顶的运算符运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; case = : //脱括号并接收下一字符 Pop(OPTR,x); ch = getchar(); break; } // switch } // while return GetTop(OPND);} // EvaluateExpression OPTR OPND INPUT OPERATE 3*(7-2)# Push(opnd,’3’) # *(7-2)# 3 # Push(optr,’*’) #,* 3 (7-2)# Push(optr,’(’) #,*,( 3 7-2)# Push(opnd,’7’) #,*,( 3,7 -2)# Push(optr,’-’) #,*,(,－ 3,7 2)# Push(opnd,’2’) #,*,(,－ 3,7,2 )# Operate(7-2) #,*,( 3,5 )# Pop(optr) #,* 3,5 # Operate(3*5) # 15 # GetTop(opnd) 3.3栈与递归 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法 递归定义的数学函数 具有递归特性的数据结构 可递归求解的问题 1. 递归定义的数学函数: 阶乘函数: 2阶Fibonaci数列: 树 2. 具有递归特性的数据结构: Root Lchild Rchild 广义表 A=(a,A) 3. 可递归求解的问题: 　迷宫问题　Hanoi塔问题 分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解