第三章chap003.ppt

第三章 栈和队列 本章重点： 栈的特点及存储结构上操作的实现 栈的应用 队列的特点及存储结构上操作的实现 队列的应用 如何从后缀式求值？ 先找运算符， 再找操作数 从原表达式求得后缀式的规律为： 1) 设立操作数栈； 2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”； 3) 若当前字符是操作数， 则直接发送给后缀式。 4) 若当前运算符的优先数高于栈顶运算符，则进栈； 5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。 从原表达式求得后缀式的规律为： void transform(char suffix[ ], char exp[ ] ) { InitStack(S); Push(S, ?#?); p = exp; i=0; while (Gettop(S,c) c!= ?#?)||*p!= ?#?{ if (!IN(ch, OP)) strcopy((Suffix[i++], *p++); else switch (compare[c,*p]) { case ?? : Push(S ,*p++); break; case ?=? : Pop(S, c);p++;break; case ?? : Pop(S, c); strcopy((Suffix+(i++), c); break; } } // while } // CrtExptree 例四、实现递归 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。 从被调用函数返回调用函数之前，应该完成下列三项任务： 多个函数嵌套调用的规则是： 此时的内存管理实行“栈式管理” 后调用先返回 ！ 例如： void main( ){ void a( ){ void b( ){ … … … a( ); b( ); … … }//main }// a }// b Main的数据区 函数a的数据区 函数b的数据区 递归工作栈：递归过程执行过程中占用的 数据区。 递归工作记录：每一层的递归参数合成 一个记录。 当前活动记录：栈顶记录指示当前层的 执行情况。 当前环境指针：递归工作栈的栈顶指针。 递归函数执行的过程可视为同一函数进行嵌套调用，例如： void hanoi (int n, char x, char y, char z) { // 将塔座x上按直径由小到大且至上而下编号为1至n // 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n==1) 2 move(x, 1, z); // 将编号为１的圆盘从x移到z 3 else { 4 hanoi(n-1, x, z, y); // 将x上编号为１至n-1的 //圆盘移到y, z作辅助塔 5 move(x, n, z); // 将编号为n的圆盘从x移到z 6 hanoi(n-1, y, x, z); // 将y上编号为１至n-1的 //圆盘移到z, x作辅助塔 7 } 8 } 8 3 a b c 返址 n x y z 5 2 a c b 5 1 a b c 7 1 c a b void hanoi (int n