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

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

1、华北科技学院数据结构课程设计说明书班级小组成员:______成绩:_____小组成员:成绩:_____小组成员:_成绩:_____设计题目:_____迷宫问题_______设计时间:2013.7.1至2013.7.5指导教师:________________评语:_________________________________________________________________________________________________________________________________________________

2、__________评阅教师:_____________目录设计总说明II第1章课程设计内容和要求11.1问题描述11.2设计要求11.3需求分析2第2章课程设计总体方案及分析32.1问题分析32.2系统总体设计42.3系统详细设计6第3章程序运行结果与分析113.1调试分析113.2测试结果11第4章心得总结20参考文献21附录22设计总说明：本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用一个保

3、存从入口到当前位置的路径的结构。因此，在求迷宫通路的算法中要应用“队列”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向（上、下、左、右）上相邻的方块

4、。假设以队列记录“当前路径”，则队列中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入队”；“从当前路径上删除前一通道块”的操作即为“出队”。关键词：迷宫；穷举；队列。第1章课程设计内容和要求1.1问题描述迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。

5、设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的论。                                                      图1.1矩形迷宫图1.2设计要求要求设计程序输出如下：(1)建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。（3）用一种标志（如数字8）在迷宫中标出该条通路；第17页共31页（4）在屏幕上输出迷宫和通路；（5）上述功能可用

6、菜单选择。1.3需求分析1、用户进入菜单页面选择迷宫的状态（1表示手动生成迷宫，2表示自动生成迷宫，3表示迷宫游戏，4表示退出）2、运用本迷宫系统，用户可以根据自己的需求输入所需的迷宫，其中0表示通路，1表示障碍。用户可以自己定义迷宫并设置其中的障碍，以矩阵形式输入，也可通过定义迷宫的行列数由系统自动生成迷宫。3、本系统自带一迷宫地图可供用户娱乐，用户的最高成绩可以被保存，下次进入游戏系统可以刷新纪录。第17页共31页第2章课程设计总体方案及分析2.1问题分析1.迷宫的建立要建立迷宫首先就要建立存储结构，这里我们用数组的方式建立的。根据用户输入的迷

7、宫的大小（我们设置的最大值为40可以根据要求调解），迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述；2.迷宫的存储迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。注：其中M，N分别表示迷宫最大行、列数，本程序M、N的缺省值

8、为39、39，当然，用户也可根据需要，调整其大小。3.迷宫路径的搜索首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找