Chapter_03 栈和队列.ppt

算法与数据结构;前一章复习;第三章 栈与队列（5）;;;;;;;; ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 ;InitStack(S);InitStack(S) 操作结果：构造一个空栈 S。DestroyStack(S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。;StackEmpty(S)初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALSE。;GetTop(S, e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。;Push(S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。;Pop(S, e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。;;;;知识回顾（6）;;;;;;;;;;;;;;;;链栈的表示;;;;;;;;; * ;;;;; N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2;void conversion( ) { Initstack(S); scanf (“%d”,n); while(n){ Push(S,n%8); n=n/8; } while(! Stackempty(S)){ Pop(S,e); printf(“%d”,e); } } ;假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式，;算法的设计思想：;Status matching(string exp) { int state = 1; while (i=Length(exp) state) { switch of exp[i] { case 左括弧:{Push(S,exp[i]); i++; break;} case”)”: { if(NOT StackEmpty(S)GetTop(S)=“(“ {Pop(S,e); i++;} else {state = 0;} break; } … … } if (StackEmpty(S)state) return OK; …...;回文游戏：顺读与逆读字符串一样（不含空格）;表达式求值;一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符组成。 算术表达式有三种表示： 中缀(infix)表示 操作数 操作符 操作数，如 A+B； 前缀(prefix)表示 操作符 操作数 操作数，如 +AB； 后缀(postfix)表示 操作数 操作数 操作符，如 AB+；;表达式的中缀表示;应用后缀表示计算表达式的值;应用后缀表示计算表达式的值;通过后缀表示计算表达式值的过程;后缀表达式的处理过程;void calculate(string str) { Initstack(S); i=0; while (str[i]!=‘\0’) { if str[i] 是操作数 { Push(S,str[i]);} else { pop(S,a1);pop(S,a2); 计算 sum=a2 stri[i] a1; push(S,sum); } i++;} Pop(S,e); printf(“%d”,e); } ;编程几点注意事项;将中缀表示转换为后缀表示;中缀表达式转换为后缀表达式;各个算术操作符的优先级;中缀表达式转换为后缀表达式的算法;若 icp (ch) isp (op)，令ch进栈，读入下一个字符ch。 若 icp (ch) isp (