第六讲栈和队列（一）增加 1/13

栈 教学目标 掌握栈的应用：数制转换、括号匹配检验和行编辑程序； 理解栈在递归函数调用中的应用。 2/13

数制转换-1 N = (N div d)×d + N mod d 举例说明 10进制数转换为d进制数的原理 N         N div 8           N mod 8 1348      168                   4 （个位）   168         21                   0 （十位）      21          2                      5 （百位）      2        0                     2 （千位） 2504 3/13

数制转换-2 提出问题：输入任意一个非负十进制整数，要求输出与其等值的八进制数。 分析问题：转换过程是从低位到高位顺序产生八进制数的各个数位，然而打印输出需要从高位到低位进行。 分析结果：如果将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。 4/13

数制转换函数代码 void conversion (int N) { InitStack(S); // 构造空栈 do { Push(S, N % 8); N = N/8; } while (N!=0) while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } } // conversion （1348)10 = (2504)8 如果用递归，则应该如何实现？ 5/13

括号匹配的检验 扫描该表达式的每个字符，为左括号便入栈；为右括号便检验栈顶是否为与其匹配的左括号，如果是则出栈，否则说明括号不匹配。 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，则正确的嵌套格式: [([][])], 不正确的嵌套格式: [(](]]。 算法设计思想 扫描该表达式的每个字符，为左括号便入栈；为右括号便检验栈顶是否为与其匹配的左括号，如果是则出栈，否则说明括号不匹配。 当扫描结束时，栈为空则说明括号匹配，否则不匹配。 6/13

括号匹配函数代码 status matching(string exp) { InitStack(S); int state = 1; //匹配时state为1，否则state为0 while (i<=length(exp) && state){ swith (exp[i]) { case 左括号: { Push(S,exp[i]); i++; break; } case 右括号: { if (!StackEmpty(S) && GetTop(S) == 对应左括号) { Pop(S,e); i++; } else { state = 0; } break; } default: break; } //switch } //while if ( state && StackEmpty(S) ) return OK ; else return ERROR; } // matching 7/13

行编辑程序 行编辑程序的功能 举例说明 算法设计思想 whli##ilr#e（s#*s） while (*s) 接受用户从终端输入的程序或数据，并存入用户的数据区。 允许用户输入出差错，并在发现有误时可以及时更正。 举例说明 设退格符“#”表示前一个字符无效；退行符“@”表示当前行中的字符均无效。 算法设计思想 如果它既不是退格符也不是退行符，则将该字符压入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清为空栈。 whli##ilr#e（s#*s） outcha@putchar(*s=#++); while (*s) putchar(*s++); 8/13

行编辑程序代码 void LineEdit(){ InitStack(S); ch = getchar(); while (ch != EOF){ while (ch != EOF && ch != '\n'){ switch (ch){ case '#' : Pop(S, c); break; // 仅当栈非空时退栈 case '@': ClearStack(S); break; // 重置S为空栈 default : Push(S, ch); break; // 有效字符进栈 } //switch ch = getchar(); // 从终端接收下一个字符 } //while 将从栈底到栈顶的字符传送至调用过程的数据区； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); DestroyStack(S); }// LineEdit 9/13

栈与函数调用之间的关系 将所有的返回地址和实在参数等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 主调函数调用被调函数 将所有的返回地址和实在参数等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 被调用函数返回调用函数 保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。 10/13

栈与递归函数调用之间的关系 long f(int n){ if(n==0)return 1; return (n*f(n-1)); } 思考题：分析栈的变化情况。 11/13

Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

Hanoi塔问题 当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。 在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。 public static void hanoi(int n, int a, int b, int c) { if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); }

小结 本讲主要介绍了栈的应用，重点介绍了数据转换、括号匹配、行编辑程序以及栈在函数调用中的作用。 14/13

作业与实验 作业 简述栈在函数调用中的作用。 利用栈将链表中的数据逆序打印出来。 实验 无 15/13