迷宫系统课程设计报告

《迷宫系统课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、设计题目：迷宫系统专业班级：计科一班小组成员:赵大江（）　　　　　赵春鹏（）　　　　　沙　娇（）　　　　　李　静（）2012-5-28　　　　　　　　　　　一、问题描述：把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫。迷宫中设置了很多墙壁，对前进方向形成了多处障碍。在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则得到一条最佳路线。我们利用非递归方法获得迷宫从入口到出口的最佳路线。二、需求分析：Ø【基本需求】（１）设置可选择的入口及出口，具有良好的界面以便用户操作。　（２）自动生成

2、迷宫，迷宫中用不同的符号标志代表墙壁和通路。（３）利用非递归算法实现，并输出有无通路两种情况下的迷宫路径，便于用户查看。Ø【简单分析】（1）本程序中定义了三个二维数组。一个迷宫数组，两个标记数组。对它们进行相同的初始化。introwintcolstructPoint*nextstructPoint（2）程序使用create()函数，系统自动创建一个大小确定的迷宫，该迷宫有A、B、C、D四个门。任何两个门之间是否存在路径不能确定，系统自动分配。²入口截图:（3）输出的形式：在有无通路时使用两种不同的标记路径方式，有通路时采用图形输出，无通路时则采用标记数组maz

3、e[][]表示。²有通路的路径截图：²无通路的路径截图：三、概要设计：1、数据结构的设计首先，在寻找迷宫路径的时候,当走到某一位置而不能再前进时,就需要后退。因此，我们需要用“栈”的思想来满足这一要求。其次，当成功找到路径时，我们需要用图形输出迷宫。在输出路径时每个点之间必须要有联系，所以我们又用了“链表”的思想。最后,结合以上两点,在本程序中,我们应用了“链式栈”的思想，用以解决存放迷宫路径以及输出路径的问题。2、算法的设计（１）创建迷宫：用二维数组Maze[m+2][n+2]来表示迷宫矩阵，当数组元素Maze[i][j]=1时，表示该位置是墙壁,不能通行；

4、当数组元素Maze[i][j]=0时，表示该位置是通路。（1im）(1jn)数组的第０行、第m+1行、第０列、第n+1列是迷宫的围墙。建立过程中调用库函数rand()，产生随机数，从而自动生成迷宫。（２）路径查找：使用链式栈来存储在试探的过程中所走过的路径。一旦需要回退，可以从栈中取得刚才走过位置的坐标和前进方向。如果某个前进方向走不通，则将位于栈顶的活动记录退栈，使得在前进路径上回退一步，再尝试其他的允许方向，直至找到出口为止（有通路）。如果栈空则表示已经退回到开始位置（无通路）。（３）路径输出：①有路径时，用标记数组mark[][]输出。mark[][]数

5、组中各元素的值与迷宫数组Maze[][]完全相同,此时我们采用图形输出。具体算法如下所示：假定p、q为指向Point的指针，p指向当前位置，q指向下一位置。当p->row>q->row时，输出↓；当p->rowrow时，输出↑；当p->col>q->col时，输出→；当p->colcol时，输出←；②没有路径时，用标记数组maze[][]输出。由于当没有找到通路时，栈内元素退栈并删除内存空间。因此，我们用maze[][]数组来存放所有走过的点用以输出。（4）主函数：在该函数中，我们用了一个while循环贯穿整个函数。用于能够多次进行寻找迷宫路径

6、。v迷宫系统功能模块图迷宫系统出栈，释放空间无通路有通路无通路有通路调用库函数：rand()函数产生随机数输出模块：print函数主函数：while函数创建模块：create函数路径查找：Mazepath函数调用create()Mazepath()print()函数您是否还要再试一次系统自动创建生成四个门入栈K++，标记已访问再闯请输0否则请输1输出，图形表示输出，标记数组maze[][]四、详细设计：（1）定义三元组结构：TypedefstructPoint{introw;intcol;structPoint*next;}Point;intmark[M+2]

7、[N+2];intmaze[M+2][N+2];（2）成员函数流程图：①　创建迷宫：create()②　路径查找：Mazepath()③　路径输出：print2()是创建迷宫：create()其中有四个for嵌套循环，此处以第一个for循环为例exit是否i++;j++;Maze[i][j]=1;（迷宫数组）mark[i][j]=1;（标记数组1）maze[i][j]=1;（标记数组2）（对它们进行相同的初始化）j<=N+1？j=0;（Maze[][]的列）i<=M+1?i=0;（Maze[][]的行）开始否开始查找路径：Mazepath()此流程图以A为入口

8、，D为出口为例。里的内容表示的是注释说