[计算机软件及应用]3栈和队列.pptVIP

#define MAX 100 Int stack[MAX],top1=0,top2=MAX-1; 0 MAX-1 top1 top2 栈1 栈2 栈1进栈 top1+1 栈2进栈 top2-1 top1top2时出现“上溢” 练习：写出栈共享的算法 本章小结 熟练掌握： (1)栈、队列的定义、特点和性质； (2)ADT栈、ADT队列的设计和实现以及基本操作及 相关算法。 重点学习： ADT栈和队列在表达式求值、括号匹配、数制转换、迷宫求解中的应用，提高利用栈和队列解决实际问题的应用水平。 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.4 表达式求值 3.2.3 行编辑程序问题 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设 “#”为退格符，“@”为退行符。 在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。 解决办法 问题描述 假设从终端接受了这样两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行： while (*s) putchar(*s++); 例 3.2.3 行编辑程序问题 DestroyStack(S); } void LineEdit(){ //利用字符栈S，从终端接收一行并传送至调 //用过程的数据区 InitStack(S); ch=getchar(); …………. 3.2.3 行编辑程序问题 行编辑问题算法 while (ch != EOF) { //EOF为全文结束符 while (ch != EOF ch != ‘\n’) {……} switch (ch) { case # : Pop(S, c); break; case @: ClearStack(S); break;// 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); 栈中字符传送至调用过程的数据区； 3.2.3 行编辑程序问题 行编辑问题算法 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序问题 3.2.4 表达式求值 3.2.4 表达式求值 一个表达式由操作数(operand)、运算符(operator)、界限符(delimiter)组成。写出“算符优先法”求值的算法。 问题描述 例 求3*(2+3*5)+6的值 设置两个栈，一个存操作数，栈名为OPND，一个存运算符，栈名为OPTR栈。 (1) 首先置操作数栈为空，表达式起始符#为运算符栈的栈底元素； (2)依次读入表达式中每个字符， 若是操作数则进栈； 若是运算符则与运算符栈的栈顶运算符比较： 3.2.4 表达式求值 算法求解过程 若栈顶运算符小于输入运算符则进栈； 若栈顶运算符等于输入运算符（只有栈顶是“（”，输入是“）”，或者栈顶是“#”，输入是“#）”两种情况，分别去除一对括号，或结束。 若栈顶运算符大于输入运算符，弹出栈顶运算符，并从操作数栈中弹出两个操作数与弹出运算符计算后再存入操作数。 3.2.4 表达式求值 算法求解过程 直到整个表达式操作完毕。 OperandType EvaluateExpression(){ initStack(OPTR);Push(OPTR,’#’); initStack(OPND);c=getchar(); while(c!=‘#’)||GetTop(OPTR)!=‘#’){ if(!In(c,OP)) {Push((OPND,c);c=getchar();} else