1、 数据结构课程设计报告数据结构课程设计报告 题目题目: 迷宫求解 班级班级: 姓名姓名: 学号学号: 完成日期完成日期: 1 目录目录 一、课程设计概述一、课程设计概述2 二、问题描述二、问题描述. 2 三、需求分析三、需求分析. 2 四、概要设计四、概要设计. 2 五、存储结构五、存储结构. 4 六、流程图六、流程图 . 4 七、七、详细设计详细设计. 4 八、八、调试分析调试分析8 九、九、运运行结果及分析行结果及分析. 8 十、十、参考文献参考文献. 10 十一、十一、主程序主程序10 2 一、课程设计概述一、课程设计概述 本次数据结构课程设计主要完成用栈来实现迷宫求解问题。 使用语言：
2、C 编译环境：VC6.0 二、问题描述二、问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无 顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子 仅有一个出口， 在出口处放置一块奶酪， 吸引老鼠在迷宫中寻找道路以到达出口。 对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。 老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的 矩形迷宫如下图 A 所示，求出一条从入口到出口的通路，或得出没有通路的结 论。 图 1-1. 三、需求分析三、需求分析 要求设计程序输出如下： (1) 建立一个大小为 mn 的任意迷宫（
3、迷宫数据可由用户输入或由程序自动生 成），并在屏幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字 8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 四、四、概要设计概要设计 3 设定栈的抽象数据类型定义为： ADT stack 数据对象数据对象：D=ai|aicharset,i=1,2,n,n0 数据关系数据关系：R1=|ai-1,aiD,i=2,n 基本操作基本操作： InitStack( /迷宫的“出口” I nt predecessor; /该通道的“前趋” queue512
4、; 六、六、流程图流程图 图1-2 5 七、详细设计详细设计 实现概要设计中定义的所有数据类型及操作的伪代码算法 1. 节点类型和指针类型 迷宫矩阵类型：int mazeM+2N+2;为方便操作使其为全局变量 迷宫中节点类型及队列类型：struct pointint row,col,predecessor que512 2. 迷宫的操作 (1)手动生成迷宫 void shoudong_maze(int m,int n) 定义 i,j 为循环变量 for(i0 且 mazep.row-1p.col=0,说明未到迷宫上边界， 且其上方 有通路,则 visit(p.row,p.col+1,maze)
5、,将上方节点入队标记已访问 访问到出口(找到路径)即 p.row=m-1 且 p.col=n-1,则逆序将路径标记为 3 即 mazep.rowp.col=3; while(p.predecessor!=-1) p=queuep.predecessor; mazep.rowp.col=3; 最后将路径图形打印出来。 3.菜单选择 while(cycle!=(-1) 手动生成迷宫 请按：1 自动生成迷宫 请按：2 退出 请按：3 scanf(“%d“, switch(i) case 1：请输入行列数(如果超出预设范围则提示重新输入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 2 ：请输入行列数(如果超
