资源描述：
《基于c语言的迷宫问题课程设计》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、.*******************实践教学*******************兰州理工大学软件学院2012年春季学期算法与数据结构课程设计题目：迷宫问题专业班级：姓名：学号：指导教师：成绩：_______________..摘要在现实生活中，会遇到很多很多关于迷宫这样很复杂、很难解决的问题的问题。如果人工去解决这些问题，会很麻烦，花很长的时间，甚至无法解决。假如用计算机去解决，可以通过手动生成迷宫，也可以通过计算机随机的产生迷宫，最终退出。而且可以很快的求解迷宫，找到从入口到出口的通路，或者当没有通路时，得出没有通路的结论。找出通路之后，会显示出通路路经，而且以图示的方式
2、显示出通路，这样会使人一目了然的看清此迷宫的通路。迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。关键词：迷宫；通路；二维数组；路径..序言随着社会经济的发展，信息化程度的不断深入，传统的人工求解迷宫问题已不能满足生活的需要。近几年，随着迷宫问题越来越复杂、科技也越来越发达，人们逐渐的开始用计算机求解迷宫问题。
3、迷宫问题很复杂，但是人们又不得不去研究这个问题，因为人们的生活中需要它，离不开它。在迷宫路径的搜索过程中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的
4、算法，如果找到路径，则为最短路径。..目录一、需求分析51.1功能与数据需求51.1.1题目要求的功能51.1.2扩展功能51.2界面需求61.3开发环境与运行需求6二、概要设计72.1主要数据结构72.2各模块函数说明8三、详细设计9四、测试10五、使用说明135.1应用程序功能的详细说明135.2应用程序运行环境要求135.3输入数据类型、格式和内容限制13六、总结提高146.1课程设计总结146.2开发中遇到的问题和解决方法146.3对自己完成课设完成情况的评价14参考文献15致谢16..一、需求分析1.1功能与数据需求问题描述：以一个m×n的长方形表示迷宫，0和1分别表示
5、迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1.1.1题目要求的功能基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）,（1,2,2）,（2,2,2）（3,2,3）,（3,1,2）,…。测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。0010001000100010000011010111001000
6、01000001000101011110011100010111000000123456781.1.2扩展功能（1）编写递归形式的算法，求得迷宫中所有可能的通路；..（2）以方阵形式输出迷宫及其通路1.2界面需求请求输入进入程序请求输入起始位置请求输入终点位置输出方阵迷宫输出路径输出方阵路径1.3开发环境与运行需求VisualC++6.0..二、概要设计2.1主要数据结构输入起始位置，终点位置判断首节点是否为通路判断路径能否走通对坐标标记是否到达迷宫出口处左边是否存在通路下边是否存在通路右边是否存在通路上边是否存在通路存储路径，将路径入栈有解迷宫无解迷宫YNYNY输出迷宫选择路径
7、图一.主流程图..2.2各模块函数说明typedefstruct{intpos_x[length];//进栈坐标intpos_y[length];inttop;intbase;}Stack;//新建结构体voidinitStack(Stack*p)//初始化栈Push(Stack*p,intx,inty,intd)//入栈具体操作Pop(Stack*p,intread[2],intd)//出栈并读出前一步的坐标initMaze(intMaze[10][9])//建立迷宫Ways(
