1、 数据结构课程设计 设计说明书 迷宫问题求解 学 生 姓 名 学号 班级 成绩 指 导 教 师 计算机科学与技术系 2011 年 9 月 9 日 数据结构 课程设计评阅书 题 目 迷宫问题求解 学生姓名 学号 指导教师评语及成绩 成绩： 教师签名： 年 月 日 答辩教师评语及成绩 成绩： 教师签名： 年 月 日 教研室意见 总成绩： 室主任签名： 年 月 日 注：指导教师成绩 60%，答辩成绩 40%，总成绩合成后按五级制记入。 课程设计任务书 2011 2012 学年第 一 学期 专业： 学号： 姓名： 课程设计名称： 数据结构课程设计 设计题目： 迷宫问题求解 完成期限：自 2011 年
2、8 月 29 日至 2011 年 9 月 9 日共 2 周 设计依据、要求及主要内容（可另加附页）： 输入一个任意大小的迷宫数据，设置入口、出口及障碍，借助栈结构求解走出迷宫的路径并输出。 1.遵循结构化程序设计思想，采用 C/C+实现。 2.界面友好，操作简便，容错性。 基本要求如下： 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类
3、型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图； 3）详细设计 ：定义相应的存储结构。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； 5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格
4、式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果； 7）编写课程设计报告； 以上要求中前三个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。 指导教师（签字）： 教研室主任（签字）： 批准日期： 2011 年 8 月 29 日 摘 要 设计了一个寻找迷宫出口路径的程序，该程序具有设置任 意大小的迷宫数据，通过设置的迷宫入口出口及障碍，探索出一条简单路径并输出的功能。该程序采用 VC 作为软件开发环境，借助栈先入后出的特点
5、，先将入口作为检索的起点，顺着某个方向向前探索，若能走通，则继续往前走；否则沿原路返回，换个方向在继续探索，直到所有可能的通路都探索到为止，最后把探索到的路径输出。 关键词： 迷宫路径；探索；输出 目 录 1.课题描述 . 1 2.问题分析和任务定义 . 2 3.逻辑设计 . 3 4.详细设计 . 4 4.1 迷宫数据的存储 . 4 4.2 当前位置可通性的判断及探索方向的改变 . 5 4.3 无通路时沿原路返回 . 6 4.4 路径信息入栈和出栈 . 7 4.5 当前探索位置的切换 . 8 4.6 最终探索路径的输出及标记 . 9 4.7 打印迷宫信息 . 10 5.程序代码 . 11 5.
6、1 文件包含和结构体的定义 . 11 5.2 栈的初始化及入栈出栈函数 . 11 5.3 申请迷宫大小及障碍的设置 . 12 5.4 通道可通性测试 . 13 5.5 为走过的通道留下足迹 . 13 5.6 探索位置的切换 . 13 5.7 入口到出口的路径探索 . 14 5.8 打印迷宫信息 . 15 5.9 主函数 . 16 6.程序测试 . 18 总结 . 21 参考文献 . 22 _x0001_ 1 百手起驾 整理为您 1.课题描述 本次课题是实现迷宫问题的求解，利用 C语言设计一个能实现输入一个任意大小的迷宫数据，利用二维数组来储存设置的入口、出口及障碍，借助栈先入后出的结构特性保存
7、迷宫探索过程中留下的路径信息，以便在遇到障碍时 沿原路返回，在探索结束后输出栈中保存的最终路径。 _x0001_ 2 百手起驾 整理为您 2.问题分析和任务定义 迷宫求解的实现依赖于路径探索的算法，路径探索的算法采用的是“穷举求解”的方法。因此有以下问题： (1)数据存储结构的选择。 (2)当前位置的可通性判断及探索方向的改变。 (3)道路不通时沿原路返回的算法。 (4)路径信息的入栈和出栈。 (5)最终路径的输出。 _x0001_ 3 百手起驾 整理为您 3.逻辑设计 程序要实现路径探索及输出即要实现当前位置可通性的判断；路径可通时朝默认方向继续向前探索，路径不可通时沿原路返回改变探索方向，
8、输出最终探索结果。其关系如图 3.1 所示。 开始当前位置是否可通给定当前位置朝默认方向继续向前探索Y后退一步改变方向继续探索N结束图 3.1 迷宫路径探索功能结构 _x0001_ 4 百手起驾 整理为您 4.详细设计 4.1 迷宫数据的存储 Maze 是指向指针的指针，用行 h和列 l来存储迷宫的大小，使用 malloc 申请一个二维数组，根据用户输入的障碍坐标在 maze 数组的相应位置存入 1 作为障碍标记，直到用户输入 0 0 结束障碍的设置。该模块的执行过程如图 4.1 所示。 int i =0,j=0;int h ,l,n,mihmaze =( int *) malloc(sizeof (int )* h)maze i=( int *) malloc(sizeof (int )* l)i+Yscanf (“% d%d“,curpos = startcurpos = endNback ( maze , curpos )Ne . di +Yc urpos = nextpos ( curpos , e . di )结束Ye . di 4N开始图 4.2 可通性的判断及探索方向的改变
