(迷宮问题)数据结构课程设计任务书.doc

长 春 大 学 课 程 设 计 任 务 书 题目名称 走迷宫游戏 院 （系） 计算机科学技术学院 课程名称 数据结构课程设计 班 级 网络10406 学生姓名 指导教师 起止日期 2012.7.16~2012.7.20 课程设计任务书 技术参数）及要求 题目名称（包括主要 题目名称：走迷宫游戏 设计目的 1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 设计要求 1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。 3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。 4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。 5.程序调试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 7.编写课程设计说明书，封面和说明书纸到教务处网站下载，装订格式如下： 一、封面； 二、目录； 三、说明书正文，主要内容包括： 1．设计题目； 2．设计目的； 3．算法思想分析； 4．算法描述与实现； 5．结论 设计内容及工作量 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 1．首先用二维数组存储迷宫数据，迷宫数据由用户输入。 2．一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。 3．可以用多种方法实现，但至少用两种方法，用三种以上可加分。 【实现提示】 1．计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。 2．有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。 主要参考资料 《数据结构程序设计题典》 李春葆等编 清华大学出版社 《数据结构(C语言版)》 黄国瑜 叶乃菁编 清华大学出版社 《数据结构课程设计》 苏仕华 等编 机械工业出版社 进 度 计 划 表 阶段 日期 计划完成工作量 指导教师检查意见 备注 7.16 分析题目，查阅资料； 7.17~7.18 算法设计，编码，调试； 7.19 编码、调试运行； 撰写设计说明书； 7.20 答辩 设计总结： 考核成绩及评语 指导教师签字 年 月 日 教研室意见 教研室主任签字