3第3章栈和队列.ppt

case @: ClearStack(S); break; // 重置S为空栈 default : Push(S, ch); break; // 有效字符进栈，未考虑栈满情形 } ch = getchar(); // 从终端接收下一个字符 } 将从栈底到栈顶的字符传送至调用过程的数据区； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); } DestroyStack(S); }// LineEdit 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 入口 出口 例4： 迷宫求解 $ $ $ $ $ $ $ $ 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 假设迷宫如上页图所示: 假设“当前位置”指的是“在有哪些信誉好的足球投注网站过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。 求迷宫中一条从入口到出口的路径的算法可简单描述如下： 设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； // 纳入路径 若该位置是出口位置，则结束； // 求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置；｝ 否则 { 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻 块； 若栈不空但栈顶位置的四周均不可通， 则｛ 删去栈顶位置； // 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝ ｝while (栈不空）； 在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。 typedef struct { int ord; // 通道块在路径上的“序号” PosType seat; // 通道块在迷宫中的“坐标位置” int di; // 从此通道块走向下一通道块的“方向” } SElemType; // 栈的元素类型 Status MazePath ( MazeType maze, PosType start, PosType end ) { // 若迷宫maze中从入口 start到出口 end的通道， // 则求得一条存放在栈中（从栈底到栈顶），并返回 // TRUE；否则返回FALSE InitStack(S); curpos = start; // 设定“当前位置”为“入口位置” curstep = 1; // 探索第一步 do { if (Pass (curpos)) { // 当前位置可以通过，即是未曾走到过的通道块 FootPrint (curpos); // 留下足迹 e = ( curstep, curpos, 1 ); Push (S,e); // 加入路径 if ( curpos == end ) {输出从栈底到栈顶的元素; return (TRUE);} // 到达终点（出口） curpos = NextPos ( curpos, 1 ); // 下一位置是当前位置的东邻 curstep++; // 探索下一步 }//if else { // 当前位置不能通过 if (!StackEmpty(S)) { Pop (S,e); while (e.di==4 !StackEmpty