数据结构课程设计--迷宫问题

《数据结构课程设计--迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、长沙学院课程设计说明书题目迷宫问题系(部)计算机科学与技术系专业(班级)2012软件工程（服务外包）9班姓名高锐学号2012022907指导教师付细楚起止日期2013.12.09—2013.12.21课程设计任务书课程名称：数据结构与算法设计题目：迷宫问题已知技术参数和设计要求：问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）

2、指示迷宫中的一个坐标，d表示走到下一坐标的方向。测试数据：迷宫用伪随机数产生程序产生。左上角（1，1）为入口，右下角（m,n）为出口。选作内容：1编写递归形式的算法，求得迷宫中的所有可能的通路2以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路设计工作量：40课时工作计划：见课表指导教师签名：　　　　　　　　　日期：　2013.12.12　　教研室主任签名：　　　　　　　日期：　　　　　　　　系主任签名：　　　　　　　　　日期：　　　　　　　　长沙学院课程设计鉴定表姓名高锐学号2012022907专业软件工程班级12软9班设计题目迷宫问题指导教师付细楚指导教师意见：评定等级

3、：教师签名：日期：答辩小组意见：评定等级：　　　　　答辩小组长签名：　　　　　日期：　　　　教研室意见：教研室主任签名：日期：　系（部）意见：系主任签名：　　　　　　　　日期：　　　　　说明课程设计成绩分“优秀”、“良好”、“中等”、“及格”、“不及格”五类；摘要计算机系的课程设计，我设计了一个迷宫系统，利用了链表栈结构来保存所走的宫路径，可以实现寻找迷宫通路的功能，当无法找到出口时，可提示用户不存在。当输入行数和列数（包括外墙）、迷宫内墙单元数、迷宫内墙每个单元的行数和列数就可以自动生成一个迷宫。关键词：课程设计，数据结构，迷宫，链表栈；目录第1章设计内容与要求21.1设

4、计内容21.2设计要求2第2章需求分析32.1功能需求分析32.2软件功能32.3需求分析用例42.4求迷宫路径的基本思想42.5输入的形式和输入值的范围42.6输出的形式42.7程序所能达到的功能42.8迷宫求解流程图5第3章系统设计63.1界面设计63.2函数设计63.3结构设计73.4算法设计8第4章系统实现154.1输出迷宫的结构154.2迷宫的实现17第5章总结21参考文献22附录2328第1章设计内容与要求1.1设计内容设计一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结

5、论。1.2设计要求创建一个以链表作存储结构的栈类型，编写一个求迷宫问题的非递归程序，求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。28第2章需求分析2.1功能需求分析求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向在继续探索，直至搜有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法

6、中应用“栈”也就是自热而然的事了2.2软件功能迷宫问题以一个m*n的长方阵表示迷宫0和1分别表示迷宫中的通路和障碍通路以三元组（i，j，d）的形式输出图1.1系统功能结构图1、迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。2、迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表

7、示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。3、迷宫路径的搜索：28首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到