数据结构课程设计-迷宫问题

《数据结构课程设计-迷宫问题》由会员分享，可在线阅读，更多相关《数据结构课程设计-迷宫问题（17页珍藏版）》请在毕设资料网上搜索。

1、 目录 第一部分 需求分析 第二部分 详细设计 第三部分 调试分析 第四部分 用户手册 第五部分 测试结果 第六部分 附录 第七部分 参考文献 一、一、 需求分析需求分析 1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出 口的通路，并把这条通路显示出来； 如果没有找到这样的通路给出没 有这样通路的信息。 2、可以用一个 mn 的长方阵表示迷宫，0 和 1 分别表示迷宫中的 通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到 出口的通路，或得出没有通路的结论。 3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j， d)的形式输出，其中：(i，j)指示迷宫中的一个坐

2、标，d表示走到下 一坐标的方向。 4、由于迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应 的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的 个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。 二、详细设计二、详细设计 1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发， 顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路 退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所 有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口 点的下标为(n，n)。为处理方便起见，可在迷宫的

3、四周加一圈障碍。 对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 2、如果在某个位置上四个方向都走不通的话，就退回到前一个位 置， 换一个方向再试， 如果这个位置已经没有方向可试了就再退一步， 如果所有已经走过的位置的四个方向都试探过了， 一直退到起始点都 没有走通，那就说明这个迷宫根本不通。 3、所谓“走不通“不单是指遇到“墙挡路“，还有“已经走过的路不能 重复走第二次“，它包括“曾经走过而没有走通的路“。 显然为了保证在任何位置上都能沿原路退回，需要用一个“后进 先出“的结构即栈来保存从入口到当前位置的路径。并且在走出出口 之后，栈中保存的正是一条从入口到出口的路径。 4、若当

4、前位置“可通” ，则纳入“当前路径” ，并继续朝“下一位 置”探索；若当前位置“不可通” ，则应顺着“来的方向”退回到“前 一通道块” ，然后朝着除“来向”之外的其他方向继续探索；若该通 道块的四周四个方块均“不可通” ，则应从“当前路径”上删除该通 道块。 所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、 北）上相邻的方块。假设以栈 S 记录“当前路径” ，则栈顶中存放的 是 “当前路径上最后一个通道块” 。 由此， “纳入路径” 的操作即为 “当 前位置入栈” ； “从当前路径上删除前一通道块”的操作即为“出栈” 。 5、找通路的程序的关键部分可以表示如下： do 若当前位置可

5、通， 则 将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； / 此时栈中存放的是一条从入口位置到出口位置的路径 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的 下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)； 6、程序中用的数据结构解析： 程序中用了顺序栈保存当前找到的路径， 当前位置不可通时， 可以出栈，退回到前一个位置再继续

6、探索通路，栈的定义如下： struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base 的值 为 NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 ; / 顺序栈 栈中元素的类型结构 程序中先定义了一个表示坐标的类型结构： struct PosType / 迷宫坐标位置类型 int x; / 行值 int y; / 列值 ; 栈中元素的类型结构如下： struct SElemType / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03 表 示东北) ; 7、主函数的流程图 三、三、 调试分析调试分析 1、对于程序的设计由简单到复杂，先设计一个整体的轮廓然后再慢 慢的增加程序的功能，这样