课程设计迷宫求解

《课程设计迷宫求解》由会员分享，可在线阅读，更多相关《课程设计迷宫求解（20页珍藏版）》请在毕设资料网上搜索。

1、 目 录 1 前言 . 1 2 需求分析 . 1 2.1 课程设计目的 1 2.2 课程设计任务 1 2.3 设计环境 .1 3 概要设计 . 1 3.1 数据结构设计 1 3.2 模块设计 .3 4 详细设计 . 3 5 测试分析 . 8 6 课程设计总结 10 参考文献 10 致 谢 11 附 录 12 程序代码实现 12 1 1 前言 设计一个简单迷宫程序，从入口出发，按某一方向向前探索，若能走通（未 走过的） ，即某处可以到达，则到达新点，否则试探下一方向；若所有方向均没 有通路，则沿原点返回前一点，换下一个方向在继续试探，直到所有可能的通路 都探索到，或找到一条通路，或无路可走又返回

2、到入口点。并利用两种方法实现： 一种用栈实现，另一种用队列实现。 2 需求分析 2.1 课程设计目的 学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问 题的专业课题。通过课程设计（论文） ，提高学生综合运用所学知识来解决实际 问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论 文）打基础。 2.2 课程设计任务 给出一个任意大小的迷宫数据，求出一条走出迷宫的路径，输出迷宫并将所 求路径输出。 要求用两种方法实现：一种用栈实现，另一种用队列实现。 2.3 设计环境 （1）WINDOWS 2000/2003/XP/7/Vista 系统 （2）Visual C+

3、或TC集成开发环境 3 概要设计 3.1 数据结构设计 （1）迷宫类型 设迷宫为 M 行 N 列，利用 mazeMN来表示一个迷宫，maze=0 或 1，其中 0 表示通路，1 表示不通。当从某点试探是，中间点有 8 个不同点可以试探，而四个角 有 3 个方向，其他边缘点有 5 个方向，为使问题更容易分析我们用 mazeM+2N+2 来表示迷宫，而迷宫四周的值全部为 1。定义如下： 2 #define M 6 /*迷宫的实际行*/ #define N 8 /*迷宫的实际列*/ int mazeM+2N+2; （2）栈的类型定义 入口坐标从（1,1） ，每个点有 8 个方向可以试探，若当前点的坐

4、标为（x,y）,则 与其相邻的 8 个点坐标都可根据与该点的相邻方位而得到。因为出口在MN,因此 规定试探顺序为 从正东沿顺时针方向进行。为简化问题，方便地求出新点的坐标， 将从正东方开始沿顺时针进行的这 8 个方向的坐标增量放一个结构体数组 move8 中，在 move 数组中，每个元素有横坐标增量：x，纵坐标增量：y组成。定义如下： Typedef struct int x,y; item; Item move8; 当到达了某点五路可走时需返回前一点，再从前一点开始向下一方向继续试探， 因此，压入栈中的不仅是顺序到达的个点坐标，而且还要有从当前点到下一个点的方 向序号。因此定义栈栈中元素类

5、型有行、列、方向组成的三元组。定义如下： typedef struct int x,y,d; /d 下一步方向 elemtype; Typedef struct elemtype dataMAXSIZE; int top; Sqstack; （3）队列的类型定义 队列的有关数据结构、试探方向等和栈的求解方法处理基本相同。不同的是：如 何存储搜索路径。在搜索过程中必须几下每一个可到达的坐标点，以便从这些点出发 继续向四周搜索。到达迷宫的出口点（m,n）后，为能够从出口沿搜索路径回溯直至 入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此用一个结 3 构体数组 eleMAX作为队列

6、的存储空间，因为每一点至少被访问一次，所以 MAX 至多等于 m*n。该结构体有三个域：x、y和 pre。其中 x、y分别为所到达点的坐标， pre 为前驱点在 elem 中的下标。除此之外，还需设定头、尾指针，分别指向队头，队 尾。类型定义如下： typedef struct /队的相关类型定义 int x,y; int pre; Elemtype; typedef struct /队列的类型定义 Elemtype elemMAXSIZE; int front,rear; int len; SqQueue; 3.2 模块设计 定义函数Zprintpath( ) 利用栈实现迷宫求解，用二维数组MazeM+2N+2 表示迷宫，move8表示坐标增量数组。 定义函数DLmazepath( )，利用队列实现迷宫求。 定义函数Zprintpath( )实现栈的迷宫路径输出，栈中保存的就是一条迷宫的通 路。 定义函数DLmaze