1、 数据结构数据结构 -课程设计报告课程设计报告 题目：题目： 班级：班级： 学号：学号： 姓名：姓名： 同组成员：同组成员： 指导教师：指导教师： 数据结构课程设计之迷宫问题 1 目录 一、一、 设计题目设计题目2 二、二、 需求分析需求分析2 三、三、 概要设计概要设计2 四、四、 详细设计详细设计2 五、五、 运行数据及结果运行数据及结果5 数据结构课程设计之迷宫问题 2 一、设计题目一、设计题目 迷宫问题 二、需求分析二、需求分析 迷宫实验是取自心理学的一个古典的实验。在该实验中，把一只老鼠从一个无顶大盒 子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻拦。盒子仅有一个出口，在出
2、口处放置一块奶酪， 吸引老鼠在迷宫中寻找道路以到达出口。 对同一只老鼠重复进行上述实 验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走通迷宫的 路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有 通路的结论。 要求程序输出： （1）一条通路的二元组（i，j）数据序列， （i，j）表示通路上某一点的坐标。 （2）用一种标志（如数字 8）在二维数组中标出该条通路，并在屏幕上输出二维数组。 三、概要设计三、概要设计 1.功能模块设计 该程序的主要模块有：初始化栈模块、迷宫建立模块、迷宫求解模块 （1） 初始化栈模块，由 InitStack(Sta
3、ck 由 InitMaze1(maze,a,row,col)，InitMaze2(maze,a,row,col)函数构成，此 模块用于产生迷宫 （3） 迷宫求解模块，由 MazePath(maze,start,end)，NextPos(e.seat,e.di)函数构成，此模块 是基于栈的特点与迷宫实际结合来实现的。 2.算法设计 走迷宫的过程可以模拟为一个搜索的过程：每到一处总让它按东、东南、南、西南、 西、 西北、 北、 东北 8 个方向顺序试探下一个位置； 如果可以通过并不曾到达， 则前进一步， 在新的位置上继续进行搜索；如果 8 个方向都走不通或曾经到达过，则退回一步，在原来的 位置继续
4、试探下一个位置。每前进或后退一步，都要进行判断：若前进到出口处，则说明找 到一条通路，并打印路径；若退回到路口处，则说明不存在通路。 用一个字符型的二维数组表示迷宫，数组中的每个元素取值 “0” （表示通路）或“1” （表示墙壁） ，并且将 0 记录为“ ” ，1 记录为 “#” ； 迷宫的产生可由用户决定： 1.自动生成 2.手动输入。 迷宫生产后，入口与出口由用户自己输入。设计一个模拟走迷宫 的算法，为其寻找一条从入口到出口的通入。 从迷宫的入口位置开始沿图示方向顺序依次进行搜索。搜索 过程中，每前进一步，在当前位置处做标记“*” （表示这个位置 在通路上） ，并将该位置的压入栈中。每后退
5、的时候，将该位置标 记为“” ，表示该路不通， 并将元素从栈中弹出。 搜索到出口位置时，数组中那些值为“*”的元素形成一条通路。 图 1 位置方向图 四四、详细设计、详细设计 1、迷宫建立模块设计 此模块主要由 InitMaze1(maze,a,row,col)，InitMaze2(maze,a,row,col)函数构成，其中 InitMaze1(maze,a,row,col)用于用户自己建立迷宫，InitMaze2(maze,a,row,col)是利用库函数中 的随机函数来建立迷宫，迷宫是通过矩阵形式表现的，用 1、0 分别表示墙和通路，并用二 维数组存储，从而将实际问题转化为数学模型，方便程序的设计。 数据结构课程设计之迷宫问题 3 void InitMaze1(MazeType printf(“n 请输入迷宫数据，1 为障碍，0 为通路n“); for(m=1;mdata; printf(“(%d,%d)=“,e.seat.r,e.seat.c); S.size-; printf(“迷宫入口“); if(found) return true; else return false;/没有找到路径 五、运行数据及结
