迷宫系统课程设计报告.docVIP

问题描述： 把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫。迷宫中设置了很多墙壁，对前进方向形成了多处障碍。在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则得到一条最佳路线。我们利用非递归方法获得迷宫从入口到出口的最佳路线。 二、需求分析： 【基本需求】 设置可选择的入口及出口，具有良好的界面以便用户操作。　 自动生成迷宫，迷宫中用不同的符号标志代表墙壁和通路。 利用非递归算法实现，并输出有无通路两种情况下的迷宫路径，便于用户查看。 【简单分析】 （1）本程序中定义了三个二维数组。一个迷宫数组，两个标记数组。对它们进行相同的初始化。 int row int col struct Point *next （2）程序使用create()函数，系统自动创建一个大小确定的迷宫，该迷宫有A、B、C、D四个门。任何两个门之间是否存在路径不能确定，系统自动分配。 入口截图: 输出的形式： 在有无通路时使用两种不同的标记路径方式，有通路时采用图形输出，无通路时则采用标记数组maze[][]表示。 有通路的路径截图： 无通路的路径截图： 三、概要设计： 1、数据结构的设计 “栈”的思想来满足这一要求。 其次，当成功找到路径时，我们需要用图形输出迷宫。在输出路径时每个点之间必须要有联系，所以我们又用了“链表”的思想。 最后, 结合以上两点,在本程序中,我们应用了“链式栈”的思想，用以解决存放迷宫路径以及输出路径的问题。 2、算法的设计 创建迷宫： 用二维数组Maze[m+2][n+2]来表示迷宫矩阵，当数组元素Maze[i][j]=1时，表示该位置是墙壁, 不能通行；当数组元素Maze[i][j]=0时，表示该位置是通路。（1im）(1jn) 数组的第０行、第m+1行、第０列、第n+1列是迷宫的围墙。 建立过程中调用库函数 rand()，产生随机数，从而自动生成迷宫。 路径查找： 使用链式栈来存储在试探的过程中所走过的路径。一旦需要回退，可以从栈中取得刚才走过位置的坐标和前进方向。如果某个前进方向走不通，则将位于栈顶的活动记录退栈，使得在前进路径上回退一步，再尝试其他的允许方向，直至找到出口为止（有通路）。如果栈空则表示已经退回到开始位置（无通路）。 路径输出： ①有路径时，用标记数组mark[][]输出。mark[][]数组中各元素的值与迷宫数组Maze[][]完全相同,此时我们采用图形输出。 具体算法如下所示： 假定p、q为指向Point的指针，p指向当前位置，q指向下一位置。 当 p-row q-row 时，输出↓； 当 p-row q-row 时，输出↑； 当 p-col q-col 时， 输出→； 当 p-col q-col 时， 输出←； ②没有路径时，用标记数组maze[][]输出。由于当没有找到通路时，栈内元素退栈并删除内存空间。因此，我们用maze[][]数组来存放所有走过的点用以输出。 主函数： 在该函数中，我们用了一个while循环贯穿整个函数。用于能够多次进行寻找迷宫路径。 迷宫系统功能模块图 详细设计： 定义三元组结构： Typedef struct Point { int row ; int col; struct Point *next; }Point; int mark[M+2][N+2]; int maze[M+2][N+2]; 成员函数流程图： 创建迷宫：create() 路径查找：Mazepath() 路径输出：print2() （3）主函数流程图： 五、实现与测试 1.调试过程中遇到的问题 (1)输出问题 问题解决前： 如上图所示，有图可发现迷宫中的通路不易查找；走过的路径标记不明显，而且也没有标记清楚走的过程。因此，在迷宫及路径输出时，我们通过图形输出，以达到标记走路径的过程。如下图所示： 问题解决后： (2)查找路径问题 问题解决前： 如上图所示，选定入口为A，出口为D。由图可以发现，在走的过程中，走法太过死板。因此，当选定入口和出口后，我们规定了判断上下左右四个方向的先后判断顺序。以减少走的步骤。如下图所示： 问题解决后： 2.测试数据及输出结果 (1) 输入正确数据及输出的结果 ★ 有路径的情况 选择入口为A，出口为D。则结果如下图所示： ★ 没有路径的情况 选择入口为C，出口为B。则结果如下图如所示： (2) 输入错误数据及输出的结果 3.