3_数据结构与算法_北京大学2008_张铭_栈和队列.ppt

6.标号为t+1的语句 switch ((x=S.top ()).rd) { case 0 : goto label 0; break; case 1 : goto label 1; break; ………. case t+1 : item = S.pop() // 返回处理 break; default : break; } 7. 改写循环和嵌套中的递归 对于循环中的递归，改写成等价的goto型循环 对于嵌套递归调用 譬如，recf (… recf()) 改为： exmp1 = recf ( ); exmp2 = recf (exmp1); … exmpk = recf (exmpk-1) 然后应用规则 4 解决 8. 优化处理 经过上述变换所得到的是一个带goto语句的非递归程序。可以进一步优化 去掉冗余进栈/出栈 根据流程图找出相应的循环结构，从而消去goto语句 递归的非递归实现 请大家思考，用机械的转换方法 阶乘函数 2阶斐波那契函数 f0=0, f1=1, fn = fn-1+ fn-2 Hanoi塔 后缀表达式的计算 23 34 45 * 5 6 + 7 + / + =？ 计算特点？ 中缀和后缀表达式的主要异同？ 23+34*45/(5+6+7) = ? 23 34 45 * 5 6 + 7 + / + =？ 从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号： (1) 当输入的是操作数时，直接输出到后缀表达式序列； (2) 当遇到开括号时，把它压入栈； (3) 当输入遇到闭括号时，先判断栈是否为空，若为空（括号不匹配），应该作为错误异常处理，清栈退出。 若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中（弹出的开括号不放到序列中），若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。 中缀表达式?后缀表达式 中缀表达式?后缀表达式 从左到右扫描中缀表达式。用栈存放表达式中的操作数、开括号以及在此开括号后暂不确定计算次序的其他符号： （4）当输入为运算符op（ 四则运算 + - * / 之一）时 （a）循环 当（栈非空 and 栈顶不是开括号 and 栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中； （b）将输入的运算符压入栈内； （5）最后，当中缀表达式的符号全部读入时，若栈内仍有元素，把它们全部依次弹出，放在后缀表达式序列的尾部。若弹出的元素遇到开括号，则说明括号不匹配，做异常处理，清栈退出。 中缀表达式?后缀表达式 待处理中缀表达式： 输出后缀表达式： 栈的状态 23 / 45 5 6 7 * ＋ ＋ ＋ ( ) ( ) 34 后缀表达式求值 循环：依次顺序读入表达式的符号序列（假设以＝作为输入序列的结束），并根据读入的元素符号逐一分析： 1.当遇到的是一个操作数，则压入栈顶； 2.当遇到的是一个运算符, 就从栈中两次取出栈顶，按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶 如此继续，直到遇到符号＝, 这时栈顶的值就是输入表达式的值 后缀表达式求值 待处理后缀表达式： 23 / 45 5 6 7 * ＋ ＋ ＋ 34 栈状态的变化 1530 11 18 85 108 后缀表达式求值 中缀表达式： 运算符在中间 需要括号改变优先级 4* x * (2 * x + a) – c 后缀表达式 运算符在后面 完全不需要括号 4 x * 2 x * a + * c – 后缀计算器的类定义 // Class Declaration 类的说明 (参见算法3.5) class Calculator { private: Stackdouble s; // 这个栈用于压入保存操作数 // 从栈顶弹出两个操作数opd1和opd2 bool GetTwoOperands(double opd1,double opd2); // 取两个操作数，并按op对两个操作数进行计算 void Compute(char op); public: Calculator(void){} ; // 创建计算器实例，开辟一个空栈 void Run(void); // 读入后缀表达式，遇到符号=时，求值计算结束 void Clear(void); //清除计算器，为下一次计算做准备 }; 3.1.5 栈与递归 函数的递归定义 主程序和子程序的参数传递 栈在实现函数递归调