文档介绍：武汉纺织大学数学与计算机学院数据结构课程设计报告迷宫问题求解学生姓名: 学号: 班级: 指导老师: 报告日期: 一、问题描述以一个 mxn的长方矩阵表示迷宫, 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 step; //当前位置在路径上的"序号" PosType seat; //当前的坐标位置 DirectiveType di; //往下一个坐标位置的方向}SElemType; typedef struct //栈类型{SElemType *base; //栈的尾指针 SElemType *top; //栈的头指针 int stacksize; //栈的大小}SqStack; 六、调试结果和分析 a) 测试结果实际程序执行过程如下图所示: 参考文献[1] 严蔚敏、吴伟民:《数据结构(C语言版)》[M] ,清华大学出版社 2007 年版[2] 谭浩强:《C语言设计(第三版)》[M] ,清华大学出版社 2005 年版心得体会通过这段时间的课程设计,本人对计算机的应用,数据结构的作用以及 C 语言的使用都有了更深的了解。尤其是 C语言的进步让我深刻的感受到任何所学的知识都需要实践,没有实践就无法真正理解这些知识以及掌握它们,使其成为自己的财富。在设计此程序时,刚开始感到比较迷茫,然后一步步分析, 试着写出基本的算法,思路渐渐清晰,最后完成程序。当然也遇到不少的问题, 也正是因为这些问题引发的思考给我带了收获。在遇到描写迷宫路径的算法时,我感到有些困难,后来经过一步步分析和借鉴书本上的穷举求解的算法,最后把算法写出来。这次课程设计让我更加深入了解很多方面的知识,如数组的运用等等。在程序的编写中不要一味的模仿,要自己去摸索,只有带着问题反复实践,才能熟练地掌握和运用。附录、源代码#include <> //头文件#include <> #include <