迷宫问题数据结构课程设计任务书

《迷宫问题数据结构课程设计任务书》由会员分享，可在线阅读，更多相关《迷宫问题数据结构课程设计任务书（27页珍藏版）》请在金锄头文库上搜索。

1、长长 春春 大大 学学 课课 程程 设设 计计 任任 务务 书书 题目名称题目名称 走迷宫游戏走迷宫游戏 院院 （系）（系） 计算机科学技术学院计算机科学技术学院 课程名称课程名称 数据结构课程设计数据结构课程设计 班班 级级 网络网络 1040610406 学生姓名学生姓名 指导教师指导教师 起止日期起止日期 2012.7.162012.7.202012.7.162012.7.20 课程设计任务书课程设计任务书 技术参数）及要求 题目名称（包括主要 题目名称：题目名称：走迷宫游戏 设计目的设计目的 1了解并掌握数据结构与算法的设计方法，具备初步 的独立分析和设计能力； 2.初步掌握软件开发过

2、程的问题分析、系统设计、程 序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解 决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开 发，培养软件工作者所应具备的科学的工作方法和作风。 设计要求设计要求 1.问题分析和任务定义：根据设计题目的要求，充分 地分析和理解问题，明确问题要求做什么？（而不是怎么 做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应 的数据类型，并按照以数据结构为中心的原则划分模块， 定义主程序模块和各抽象数据类型。逻辑设计的结果应写 出每个抽象数据类型的定义(包括数据结构的描述和每个 基本操作的功能说明)，

3、各个主要模块的算法，并画出模 块之间的调用关系图。 3.详细设计：定义相应的存储结构并写出各函数的伪 码算法。在这个过程中，要综合考虑系统功能，使得系统 结构清晰、合理、简单和易于调试，抽象数据类型的实现 尽可能做到数据封装，基本操作的规格说明尽可能明确具 体。详细设计的结果是对数据结构和基本操作作出进一步 的求精，写出数据存储结构的类型定义，写出函数形式的 算法框架。 4.程序编码：把详细设计的结果进一步求精为程序设 计语言程序。同时加入一些注解和断言，使程序中逻辑概 念清楚。 5.程序调试：采用自底向上，分模块进行，即先调试 低层函数。能够熟练掌握调试工具的各种功能，设计测试 数据确定疑点

4、，通过修改程序来证实它或绕过它。调试正 确后，认真整理源程序及其注释，形成格式和风格良好的 源程序清单和结果。 6.结果分析：程序运行结果包括正确的输入及其输出 结果和含有错误的输入及其输出结果。算法的时间、空间 复杂性分析。 7.编写课程设计说明书，封面和说明书纸到教务处网 站下载，装订格式如下： 一、封面； 二、目录； 三、说明书正文，主要内容包括： 1设计题目； 2设计目的； 3算法思想分析； 4算法描述与实现； 5结论 设计内容及工作量 【问题描述】 以一个 mn 的长方阵表示迷宫，0 和 1 分别表示迷宫 中的通路和障碍。设计一个程序，对任意设定的迷宫，求 出一条从入口到出口的通路，

5、或得出没有通路的结论。 【基本要求】 1首先用二维数组存储迷宫数据，迷宫数据由用户 输入。 2一个以链表作存储结构的栈类型，然后编写一个 求解迷宫的递归或非递归程序。求得的通路以三元组 （i，j，d）形式输出，其中：（i，j）指示迷宫中的一 个坐标，d 表示走到下一坐标的方向（东、南、西、北四 个方向所用代表数字，自行定义） 。 3可以用多种方法实现，但至少用两种方法，用三 种以上可加分。 【实现提示】 1计算机解迷宫问题通常用的是“穷举求解”方法， 即从入口出发，顺着某一个方向进行探索，若能走通，则 继续往前进；否则沿着原路退回，换一个方向继续探索， 直至出口位置，求得一条通路。假如所有可能

6、的通路都探 索到而未能到达出口，则所设定的迷宫没有通路。 迷宫的入口点的下标为（1，1） ，出口点的下标为 （m，n） 。为处理方便起见，可在迷宫的四周加一圈障碍。 对于迷宫的任一位置，均可约定有东、南、西、北四个方 向可通。 2有一种简单走出迷宫的方法，把手放在右边的墙 上开始前进，始终不要把手从墙上移开。如果迷宫向右拐， 你也顺着墙向右拐。只要不把手从墙上移开，最终就会到 达迷宫的出口。当然这样得到的路径可能不是一个最短的 路径，但它可以最终得到结果，换句话说，这种方法走不 出迷宫的风险是最小的。 主要参考资料 数据结构程序设计题典 李春葆等编 清华大学出版社 数据结构(C 语言版) 黄国

7、瑜 叶乃菁编 清华大学出版社 数据结构课程设计 苏仕华 等编 机械工业出版社 进进 度度 计计 划划 表表 阶段 日期 计划完成工作量指导教师检查意见备注 7.16 分析题目，查阅资料； 7.177.18 算法设计，编码，调 试； 7.19 编码、调试运行； 撰写设计说明书； 7.20 答辩 设计总结： 考核成绩及评语 指导教师签字 年 月 日 教研室意见 教研室主任签字 年 月 日 长长 春春 大大 学学 课课 程程 设设 计计 说说 明明 书书 题目名称题目名称 走迷宫游戏走迷宫游戏 院（系）院（系）计算机科学技术学院计算机科学技术学院 专业（班级）专业（班级） 网络网络 10406104

8、06 学生姓名学生姓名 指导教师指导教师 起止日期起止日期 2012.7.162012.7.162012.7.202012.7.20 目录目录 一、设计题 目2 二、设计目 的2 三、算法思想 析3 1、类的分析与计3 2、程序设计流 图3 四、算法描述与 现 5 1、概要计5 2、调试析5 3、测试果7 五、总结与会10 六、程序码11 七、参考献16 一、设计题目一、设计题目 1、题目：走迷宫游戏 2、问题描述 以一个 mn 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。 设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没 有通路的结论。 3、基本要求 （1）

9、 、首先用二维数组存储迷宫数据，迷宫数据由用户输入。 （2） 、一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或 非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指 示迷宫中的一个坐标，d 表示走到下一坐标的方向（东、南、西、北四个方向 所用代表数字，自行定义） 。 （3） 、可以用多种方法实现，但至少用两种方法，用三种以上可加分。 二、设计目的二、设计目的 1、需求分析与设计要求 随着社会经济和人们物质生活的不断提高，人们对精神生活的需求也越来 越高，在现今社会里，人们对诸如智商、情商等的重视无疑反映了对精神生活 的态度。当然具体到我们每个人来说，想必大多数人

10、小时候都曾玩过魔方、迷 宫吧。作为这种智力游戏，人们是百玩不厌的。正是鉴于这种需求，本设计应 用计算机语言及其算法，将人的意志赋予机器实现，使人们不必再陷于枯燥的 重复劳动，从而将更多的精力投入到对未知领域的探索上。 这次课程设计要求我们在了解并掌握数据结构与算法的设计方法的基础上， 具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设 计、程序编码、测试等基本方法和技能。 同时要求在提高综合运用所学的理论知识和方法独立分析和解决问题的能 力 的同时，训练用系统的观点和软件开发一般规范进行软件开发的方法，培 养一个软件工作者所应具备的科学的工作方法和作风。 三、三、算法思想分析

11、算法思想分析 1、类的分析与设计 由于计算机解谜宫时，通常用的是“穷举求解”的方法，即从入口出发， 顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方 向再继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到 而未能到达出口，则所设定的迷宫没有通路。为了保证在任何位置上都能沿原 路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因 此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 首先，迷宫图用方块表示，每个方块或为通道，或为墙。迷宫的入口点的 下标为（1，1） ，出口点的下标为（m，n） 。为处理方便起见，可在迷宫的四周 加一圈障碍。对于

12、迷宫的任一位置，均可约定有东、南、西、北四个方向可通。 有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把 手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开， 最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但 它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置” ，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通” ，则纳入 “当前路径” ，并继续朝“下一位置”探索，即切换“下一位置”为“当前位 置” ，如此重复直至到达出口；若当前位置“不可通” ，则应顺

13、着“来向”退回 到“前一通道块” ，然后朝着除“来向”之外的其他方向继续探索；若该通道 块的四周 4 个方块均 “不可通” ，则应从“当前路径”上删除该通道块。所谓“下一位置”指 的是“当前位置”四周 4 个方向（东、南、西、北）上相邻的方块。假设以栈 S 记录“当前路径” ，则栈顶中存放的是“当前路径”上最后一个通道块。由 此， “纳入路径”的操作即为“当前位置入栈” ；“从当前路径上删除前一通道 块”的操作即为“出栈” 。 2、程序设计流程图程序设计流程图 （1）程序主要项目 主函数 数 据 存 储 栈的 初始 化及 入栈 出栈 函 数 走过 通道 留下 的痕 迹 探索 从出 口到 入口

14、的路 径 切 换 当 前 探 索 位 置 输 出 迷 宫 信 息 （2）程序运行主流程 开始 建立迷宫并 确定当前位置 当前位置 是否可通 四、四、算法描述与实现算法描述与实现 1、概要设计 以二维数组 mazemapMN表示迷宫，数组中 0 表示通路，1 表示障碍， 3 表示求解之后的迷宫路径。M 为迷宫的宽，N 为迷宫的长。 程序设置一个演示迷宫，另外可由用户自己输入迷宫数据建立迷宫。用户 根据提示输入迷宫的长和宽，入口和出口，以及迷宫每一行的数据，同样用 1 表示障碍，0 表示通路，迷宫周边用 1 表示。 以图形显示出迷宫，用“墙”表示障碍， “口”表示路径。若存在路径， 则显示出路径，

15、否则提示没有路径。 2、调试分析 （1）设定栈的抽象数据类型定义 ADT Stack 数据对象：D=ai|ai 属于 ElemSet,i=1,2,3,4,n,n=0 数据关系：R1=|ai-1,ai 属于 D,i=1,2,3.n 基本操作： InitStack( int signMAXSIZEMAXSIZE;/标记矩阵，当相应块走过后，值变为 1 typedef struct int x; int y; PosType; typedef struct int ord; PosType seat; int di; SElemType; typedef struct int m; int n; i

16、nt mapMAXSIZEMAXSIZE; MazeType; class Stack public: SElemType dataMAXSIZE; int top; Stack(void) top=-1; void push(SElemType e) top+; datatop.ord=e.ord; datatop.di=e.di; datatop.seat=e.seat; void pop(SElemType e.ord=datatop.ord; e.seat=datatop.seat; top-; int empty() if(top=-1) return 1; else return 0; ; void FootPrint(PosType