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