迷宫问题的求解数据结构课程设计.doc

数据结构课程设计
设计说明书
迷宫问题求解
学生姓名
马东
学号
班级
信管103
成绩
指导教师
李婧
数学与计算机科学学院
2012年3月2日
数据结构课程设计评阅书
题目
迷宫问题求解
学生姓名
马东
学号
指导教师评语及成绩
成绩: 教师签名: 年月日
答辩教师评语及成绩
成绩: 教师签名: 年月日
教研室意见
总成绩: 室主任签名: 年月日
注:指导教师成绩60%,答辩成绩40%,总成绩合成后按五级制记入。
课程设计任务书
2011—2012学年第二学期
专业: 信息管理与信息系统学号: 姓名: 马东
课程设计名称: 数据结构课程设计
设计题目: 迷宫问题求解
完成期限:自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周
设计依据、要求及主要内容(可另加附页):
设计要求:
设计内容:输入一个任意大小的迷宫数据,设置入口、出口及障碍,借助栈结构求解走出迷宫的路径并输出。
逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的原则划分模块,定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明),各个主要模块的算法,并画出模块之间的调用关系图;
详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中,要综合考虑系统功能,使得系统结构清晰、合理、简单和易于调试,抽象数据类型的实现尽可能做到数据封装,基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精,写出数据存储结构的类型定义,写出函数形式的算法框架;
程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言,使程序中逻辑概念清楚;
程序调试与测试:采用自底向上,分模块进行,即先调试低层函数。能够熟练掌握调试工具的各种功能,设计测试数据确定疑点,通过修改程序来证实它或绕过它。调试正确后,认真整理源程序及其注释,形成格式和风格良好的源程序清单和结果;
结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析;
编写课程设计报告;
以上要求中前三个阶段的任务完成后,先将设计说明数的草稿交指导老师面审,审查合格后方可进入后续阶段的工作。设计工作结束后,经指导老师验收合格后将设计说明书打印装订,并进行答辩。
指导教师(签字): 教研室主任(签字):
批准日期: 年月日
摘要
由计算机解迷宫时,通常用的是穷举求解的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路反回,换一个方向继续探索,直至所有可行的通路都探索到为止。为了保证在任何位置上都能沿原路返回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。显然要用到栈。
关键词:迷宫;穷举;栈;
目录
1 课题描述··········································································1
2 问题分析和任务定义······························································2
3 数据结构分析···································································· 3
········································································3
········································································3
4 流程图·································································6
5 程序编码·········································································10
6 程序测试与运行过程·····························································19
······································································19

·····················