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

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

1、21数据结构课程设计湖北工业大学数据结构及应用课程设计题目：求解迷宫问题学院：理学院专业班级：电子信息科学与技术11电科1姓名：姚思琪学号：1111121133指导教师：杨晓艳成绩：第21页共21页21数据结构课程设计目录课程设计目的3迷宫问题的提出与分析4正文5一、采用c++语言定义相关的数据类型5二、各模块的算法分析6三、程序流程图9四、程序调试结果1、程序的初始欢迎界面调试结果102、迷宫的创建.......................................................................................

2、............103、迷宫路径的输出..........................................................................................114、无路径时的输出..........................................................................................12程序设计心得13参考文献14附录15源程序（带注释）15第21页共21页21数据结构课程设计一、课程设计的目的本程序主要是对任意给定的迷宫，求出一

3、条从入口到出口的通路，或得出没有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1、生成迷宫：根据提示输入数据，然后生成一个m行n列的迷宫。2、探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通道块”，朝着“来向”之外的其它方向继续探索。3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后弹出路径坐标，输出在屏幕上。关键字：栈，栈的存储结构，出栈与入栈，递归第21

4、页共21页21数据结构课程设计二、迷宫问题的提出与分析迷宫问题最早出现在古希腊神话中。据说，半人半神的英雄西修斯在克里特的迷宫中勇敢地杀死半人半牛的怪物，并循着绳索掏出迷宫。希腊史学家希罗多德曾探访过那里。他描述说，整个迷宫由12座带顶院落构成，所有院落都由通道连接，形成3000个独立的室。后来的参观者也说，一旦进入迷宫，如果没有向导，根本无望走出。尽管人们并不清楚迷宫的具体情况，人类的聪明之处，就在于可以对走过的地方进行标记，遇到死胡同则返回到上一个标记的位置选择另一个方向进行搜索，这种方法被称为回溯法。回溯法的思想是：对一个包含多个分支打节点，按照一定的顺序向分支节点

5、搜索；当发现某个支点没有分支时，就回溯退回到该节点的上一个节点，继续搜索这个节点的其他尚未搜索过的分支。这样的搜索过程一直继续到搜索到有解或搜索完所有可能的分支而没有解为止。下面对迷宫问题进行分析求解：在迷宫中用1和0分别表示迷宫中的通路和障碍。首先，输入迷宫数据，在计算机的屏幕上显示一个m行n列的矩阵表示迷宫。矩阵中的每个数据或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳入当前

6、路径”，并继续朝“下一个位置”探索，即切换“下一位置”为“当前位置”，如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置”指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径图

7、。第21页共21页21数据结构课程设计正文一、采用c++语言定义相关的数据类型1、定义一个maze类和Point类的结构。#include#include#include#definemaxsize100#defineNULL0typedefstruct//定义迷宫{intMaze[maxsize][maxsize];//二维数组存放迷宫信息intmaze_x,maze_y;//迷宫的行数和列数}maze;mazea;typedefstructpoint//栈链的每