武汉纺织大学数学与计算机学院 数据结构课程设计报告 迷宫问题求解 学生姓名: 学 号: 班 级: 指导老师: 报告日期: 一、 问题描述 以一个m x n 的长方矩阵表示迷宫,1 和0 分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出从入口到出口的通路,或者没有通路的结论。 二、 需求分析 1、 以二维数组maze[10][10]表示迷宫,数组中以元素1 表示通路,0 表示障碍,迷宫的大小理论上可以不限制,但现在只提供10*10 大小迷宫。 2、 迷宫的入口和出口需由用户自行设置。 3、 以长方形矩阵的形式将迷宫及其通路输出,输出中“#”表示迷宫通路,“1”表示障碍。 4、 本程序只求出一条成功的通路。但是只要对函数进行小量的修改,就可以求出其他全部的路径。 5、 程序执行命令为:(1)输入迷宫;(2)、求解迷宫;(3)、输出迷宫。 三、 概要设计 1、 设定栈的抽象数据类型定义: ADT zhan{ 基本操作: InitStack(SqStack &S) 操作结果:构造一个空栈 push(*s,*e) 初始条件:栈已经存在 操作结果:将e 所指向的数据加入到栈 s 中 pop(*s,*e) 初始条件:栈已经存在 操作结果:若栈不为空,用e 返回栈顶元素,并删除栈顶元素 getpop(*s,*e) 初始条件:栈已经存在 操作结果:若栈不为空,用e 返回栈顶元素 stackempty(*s) 初始条件:栈已经存在 操作结果:判断栈是否为空。若栈为空,返回 1,否则返回 0 }ADT zhan 2、 设定迷宫的抽象数据类型定义 ADT migong{ 基本操作: Status print(MazeType maze); //显示迷宫 Status Pass(MazeType maze,PosType curpos); //判断当前位置是否可通 Status FootPrint(MazeType &maze,PosType curpos);//标记当前位置已经走过 Status MarkPrint(MazeType &maze,PosType curpos); //标记当前位置不可通 PosType NextPos(PosType curpos,DirectiveTypedi); // 进入下一位置 }ADT yanshu 3、 本程序包括三个模块 a、 主程序模块 void main() { 初始化; 迷宫求解; 迷宫输出; } b、 栈模块——实现栈的抽象数据类型 c、 迷宫模块——实现迷宫的抽象数据类型 四、流程图 五、 数据结构 typedef struct //位置结构 { int row; //行位置 int col; //列位置 }PosType; typedef struct //迷宫类型 { int arr[10][10]; }MazeType; typedef struct { int st...