《数据结构课程设计--迷宫问题》由会员分享，可在线阅读，更多相关《数据结构课程设计--迷宫问题（32页珍藏版）》请在金锄头文库上搜索。
1、长 沙 学 院课程设计说明书题目迷宫问题系(部)计算机科学与技术系专业(班级)2012 软件工程（服务外包）9班姓名高锐学号指导教师付细楚起止日期2013.12.09 2013.12.21课程设计任务书课程名称：数据结构与算法课程名称：数据结构与算法设计题目：设计题目：迷宫问题迷宫问题已知技术参数和设计要求：已知技术参数和设计要求： 问题描述：问题描述： 以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。迷宫问题要求 求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。 基本要求：基本要求： 首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题
2、的非递归程序， 求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 测试数据：测试数据： 迷宫用伪随机数产生程序产生。 左上角（1，1）为入口，右下角（m,n）为出口。 选作内容：选作内容： 1 编写递归形式的算法，求得迷宫中的所有可能的通路 2 以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路设计工作量：设计工作量： 40 课时工作计划：工作计划： 见课表指导教师签名： 日期： 2013.12.12 教研室主任签名： 日期： 系主任签名： 日期： 长沙学院课程设计鉴定表姓名高锐学号专业软件工程班级12 软 9 班设计题目迷宫问题
3、指导教师付细楚指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级： 答辩小组长签名： 日期： 教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名： 日期： 说明课程设计成绩分“优秀” 、 “良好” 、 “中等” 、 “及格” 、 “不及格”五类；摘要摘要计算机系的课程设计，我设计了一个迷宫系统，利用了链表栈结构来保存所走的宫 路径，可以实现寻找迷宫通路的功能，当无法找到出口时，可提示用户不存在。当输入行 数和列数（包括外墙） 、迷宫内墙单元数、迷宫内墙每个单元的行数和列数就可以自动生成 一个迷宫。关键词：关键词：课程设计，数据结构，迷宫，链表栈；1目录目录第 1
4、章 设计内容与要求.2 1.1 设计内容.2 1.2 设计要求.2 第 2 章 需求分析.3 2.1 功能需求分析.3 2.2 软件功能.3 2.3 需求分析用例.4 2.4 求迷宫路径的基本思想.4 2.5 输入的形式和输入值的范围.4 2.6 输出的形式.4 2.7 程序所能达到的功能.4 2.8 迷宫求解流程图.5 第 3 章 系统设计.6 3.1 界面设计.6 3.2 函数设计.6 3.3 结构设计.7 3.4 算法设计.8 第 4 章 系统实现.15 4.1 输出迷宫的结构.15 4.2 迷宫的实现.17 第 5 章 总结.21 参考文献.22 附录.232第第 1 1 章章 设计内
5、容与要求设计内容与要求1.11.1 设计内容设计内容设计一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。迷宫问题要 求求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。1.21.2 设计要求设计要求创建一个以链表作存储结构的栈类型，编写一个求迷宫问题的非递归程序，求得的通 路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标， d 表示走到 下一坐标的方向。3第第 2 2 章章 需求分析需求分析2.12.1 功能需求分析功能需求分析求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的
6、方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向在继续探索，直至搜有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自热而然的事了2.22.2 软件功能软件功能迷宫问题以一个 m*n 的长方阵表示迷宫0 和 1 分别表示迷宫中的通路和障碍通路以三元组（i，j，d）的形式输出图图 1.1 系统功能结构图系统功能结构图 1、迷宫的建立：、迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用 0 表示通路，用 1 表示障碍，这 样迷宫就可以
7、用 0、1 矩阵来描述。 2、迷宫的存储：、迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位 置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可 以考虑先定义一个较大的二维数组 mazeM+2N+2,然后用它的前 m 行 n 列来 存放元素，即可得到一个 mn 的二维数组，这样(0,0)表示迷宫入口位置，(m- 1,n-1)表示迷宫出口位置。 3、迷宫路径的搜索：、迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路 径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍， 就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选
