005堆栈 - 2.ppt

* * //在迷宫周围增加一圈障碍物 for (int i = 0; i = m+l; i++) { maze[0][i]= maze[m+l][i]= 1; //底和顶 maze[i][0]= maze[i][m+l]= 1; // 左和右 } Position here; here.row = 1; here here.col = 1; maze[1][1]= 1; // 阻止返回入口 int option = 0; int LastOption = 3; 搜索迷宫路径的代码 * * //寻找一条路径 while (here.row!=m||here.col!=m){ // 不是出口 //寻找并移动到一个相邻位置 int r, c; while (option = LastOption) { r = here.row + offset[option].row; c = here.col + offset[option].col; if (maze[r][c]== 0) break; option++; //下一个选择 } 搜索迷宫路径的代码 * * // 找到一个相邻位置了吗? if (option = LastOption){//移动到maze[r][c] path-Add( here ) ; here.row = r; here.col = c; //设置障碍物以阻止再次访问 maze[r][c]= 1; option = 0; } 搜索迷宫路径的代码 * * else {//没有可用的相邻位置，回溯 if (path-IsEmpty()) return false; Position next; path-Delete(next) ; if (next.row == here.row) //here为next邻居 option = 2 + next.col -here.col; else option = 3 + next.row -here.row; here = next; } } return true;//到达迷宫出口 } 搜索迷宫路径的代码 老鼠游走过程 * * 1，1 Path堆栈 … 1，1 2，1 2，2 1，1 2，1 * * 在最坏情况下，可能要遍历每一个空闲的位置 每个位置进入堆栈的机会最多有四次 每个位置从堆栈中被删除的机会也最多有四次 对于每个位置，需花费 Q( 1 )的时间来检查它的相邻位置 程序的时间复杂性应为O (unblocked) O(unblocked) =O( m2 ) 搜索迷宫路径复杂性分析 * * 堆栈的实现方式 括号匹配 汉诺塔 火车车厢重排 开关盒布线 离线等价类 迷宫老鼠 第五章 总结 作业 假设一数列的输入顺序为1234,若采用堆栈结构调整数列输出顺序，设计算法求出所有可能的输出序列(合法序列)。 * * * 第 5 章 堆栈 (STACKS) * * 5.1 抽象数据类型 5.2 派生类和继承 5.3 栈的公式化描述 5.4 栈的链表描述 5.5 应用 本章内容 * * 堆栈的实现 堆栈的应用 本章重点 * 5.5.3 火车车厢重排 5 8 1 6 3 ……. 货运列车共有n节车厢，每节车厢将停放在不同的车站 n个车站的编号分别为1到n 货运列车按照第n站至第1站的次序经过这些车站 车厢的编号与它们的目的地相同。 重新排列车厢，使各车厢从前至后按编号1到n的次序排列。 n n-1 n-2 2 1 ……. * * 在一个转轨站里完成车厢的重排工作 在转轨站中有一个入轨、一个出轨和k个缓冲铁轨(位于入轨和出轨之间)。 缓冲铁轨是按照LIFO的方式使用的 车厢可以从入轨的前部（即右端）移动到一个缓冲铁轨的顶部或出轨的左端。 车厢可以从一个缓冲铁轨的顶部移动到出轨的左端。 火车车厢重排问题 * * 从前至后依次检查入轨上的所有车厢。 如果正在检查的车厢就是下一个满足排列要求的车厢 可以直接把它放到出轨上去 循环输出缓冲铁轨中满足排列要求的车厢 如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。 火车车厢重排方案 * 3个缓冲铁轨中间状态 选择缓冲铁轨的分配规则 新的车厢u应送入这样的缓冲铁轨：其顶部的车厢编号v 满足v u，且v 是所有满足这种条件的缓冲铁轨顶部车厢编号中最小的一个编号。 k 个链表形式的堆栈来描述k 个缓冲铁轨。 * * bool Railroad(int p[], int n, int k) {// k 个缓冲铁轨，车厢初始排序为p [ 1 : n ] // 如果重排成功，