第二节栈的应用举例 数制转换:(1348)10=(2504)3-2-1wf void conversion 0 ∥对于输入的任意一个非负十进制整数, 打印输出与其等值的八进制数 nitstack(S);∥构造空栈 cin>>N;∥输入一个十进制数
第二节 栈的应用举例 • 数制转换 ：(1348)10 = (2504)8 3-2-1.swf • void conversion () { // 对于输入的任意一个非负十进制整数， 打印输出与其等值的八进制数 InitStack(S); // 构造空栈 cin >> N; // 输入一个十进制数
while(N) Push(s,N%8);∥“余数”入栈 N=N/8: ∥非零“商”继续运算 while( StackEmpty) {和"求余"所得相逆的顺序输出八进制的 各位数 Pop(s, e); cout≤<e;
• while(N) { Push(S,N % 8); // “余数”入栈 N = N/8; // 非零“商”继续运算 } while (!StackEmpty) {// 和"求余"所得相逆的顺序输出八进制的 各位数 Pop(S,e); cout << e; } }
括弧匹配检验 考虑下列括号序列 12345678
括弧匹配检验 • 考虑下列括号序列 • [ ( [ ] [ ] ) ] • 1 2 3 4 5 6 7 8
迷宫求解问题 通常用的是“穷举求解”的方法,即从入口 出发,顺某一方向向前探索,若能走通,则 继续往前走;否则沿原路退回,换一个方向 再继续探索,直至所有可能的通路都探索到 为止 如果所有可能的通路都试探过,还是不能走 到终点,那就说明该迷宫不存在从起点到终 点的通道
迷宫求解问题 • 通常用的是“穷举求解”的方法，即从入口 出发，顺某一方向向前探索，若能走通，则 继续往前走；否则沿原路退回，换一个方向 再继续探索，直至所有可能的通路都探索到 为止 • 如果所有可能的通路都试探过，还是不能走 到终点，那就说明该迷宫不存在从起点到终 点的通道
所谓“下一位置”指的是“当前位置”四 周四个方向(东、南、西、北)上相邻的 方块。 假设以栈S记录“当前路径”,则栈顶中存 放的是“当前路径上最后一个通道块” 纳入路径”的操作即为“当前位置入 栈 “从当前路径上删除前一通道块”的操作 即为“出栈”。 3-3-1.swf3-3-2.swf
• 所谓“下一位置”指的是“当前位置”四 周四个方向（东、南、西、北）上相邻的 方块。 • 假设以栈S记录“当前路径”，则栈顶中存 放的是“当前路径上最后一个通道块”。 • “纳入路径”的操作即为“当前位置入 栈”； • “从当前路径上删除前一通道块”的操作 即为“出栈”。 • 3-3-1.swf 3-3-2.swf