1、 数据结构课程设计报告 题题 目：目： 迷宫问题迷宫问题 院系名称：院系名称： 计算机学院计算机学院 专业名称：专业名称： 软件工程软件工程 一一. . 设计目的设计目的 1.熟悉 C 语言程序的编辑、编译链接和运行的过程，能够熟练地编辑、编译及调试程序。 2.掌握文件和文件指针的概念以及文件的定义方法，学会熟练使用文件打开、关闭、读、写 等基本操作。 3.熟练掌握结构体、链表、指针的使用，及函数间的调用。 4.能够熟练运用所学栈的相关知识及操作，顺利完成题目的要求。 二二. . 设计内容设计内容 迷宫是实验心理学中一个古典问题。用计算机解迷宫路径的程序，就是仿照人走迷宫。 计算机解迷宫时，通
2、常用的是“穷举求解“的方法，即从入口出发，顺某一方向向前探索，若 能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都 探索到为止。 1.1.功能与数据需求功能与数据需求 迷宫求解问题描述： 以一个 MN 的矩阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 1.1 1.1 题目要求的功能题目要求的功能 （1）基本要求： 首先实现一个以链表作存储结构的栈类型， 然后编写一个求解迷宫的非递归程序。 求得 的通路以二元组（i,j）的形式输出，其中： （i,j）指迷宫中对应的坐标。 （
3、2）测试数据： 左上角（1,1）为入口，右下角（9,8）为出口。 左上角（1,1）为入口，右上角（1,8）为出口。 （3）如下图所示： 1 1.2 .2 扩展功能扩展功能 （1）编写非递归形式的算法，求得迷宫中所有可能的通路； （2）以方阵形式输出迷宫及其通路 2.2.界面需求界面需求 （1）在菜单中选择要执行的操作 （2）输出方阵迷宫 （3）用户自己输入迷宫起始位置 （4）输出所走的迷宫路径 （5）输出方阵路径，并保存到文件中 3.3.开发环境与运行需求开发环境与运行需求 Microsoft Visual C+6.0 Ubuntu 三概要设计三概要设计 1 1功能模块图；功能模块图； 本程序
4、包含三个模块 （1）主程序模块： void main（） 初始化； do 接受命令； 处理命令； while（命令！=“退出” ） ； （2）栈模块实现栈抽象数据类型 （3）迷宫模块实现迷宫抽象数据类型 2 2各个模块详细的功能描述。各个模块详细的功能描述。 （1）菜单：从菜单中选择要执行的操作 （2）文件模块：实现文件的各项基本操作 a）打开文件 b）关闭文件 c）从文件读信息 d）向文件中写入内容 （3）栈模块：实现栈的各项基本操作 a）初始化栈 b）入栈 c）出栈 d）取栈顶元素 (4）迷宫模块：求解迷宫问题 a）显示迷宫 b)获取迷宫路径 c）判断当前路径是否走过 d）获得下一个可走的
5、位置 e）获得东面，南面，西面，北面相邻的位置 四四详细设计详细设计 主模块 文件模块 迷宫模块 栈模块 1 1功能函数的调用关系图功能函数的调用关系图 2.2.各功能函数的数据流程图各功能函数的数据流程图 （1）获得迷宫路径函数 do while (cur.x != chukou0 | cur.y != chukou1) 是 否 else if if 主 函 数 打 开 源 文 件 菜 单 显 示 迷 宫 显示 迷宫 路线 获得 迷宫 路径 保存 迷宫 路线 初始 化栈 判 断 当 前 路 径 是 否 走 过 入栈 出栈 获得下 一个可 走的位 置 取栈顶 元素 输出 迷宫 路径 开始 MStackElem start,cur; cur= start; 当前位置是否走过 cur=GetNext(cur Push( cur = GetNext(cur); cur.val=-1 Pop( cur=GetTop( return 1; (2)获得下一个可通行的位置 if if else ifelse if else if else ifelse if else if 3.3.重点设计及编码重点设计及编码 获得迷宫路径的函数： int GetMazePath() MStackElem start,cur; start.x =
