数据结构课程设计
实习报告
题 目： 学 号：姓 名：年 级：学 院：专 业：完成日期：授课教师：
模拟走迷宫过程
1.题目
模拟走迷宫过程。
2.要求
习题内容：
模拟走迷宫过程。 1 使用二维数组保存迷宫；
2 设计算法，从入口进入迷宫，在有出口的情况下，找到出口； 3 改进算法，找到从入口到出口的最短路径。
要求：
编写递归方法mazeTraverse走迷宫。该方法需要两个参数：表示迷宫的N*N字符数组和迷宫的起始位置。在mazeTraverse试图找到出口的过程中，将字符#放入路径中走过的每一格。每走一步，方法都应显示整个迷宫，以便用户能看清是怎样走出迷宫的。
算法介绍：
有一个简单的走迷宫算法，它保证能找到出口（假定有出口）。如果没有出口，就重新回到出发点。将右手放在身体右边的墙壁上，开始向前走。始终不要将手从墙上移开。如果迷宫向右转，就跟着墙壁向右边走。只要不将手从墙壁上移走，最终都将达到迷宫的出口。也许有其他比刚才所选的更短的路径，但是只要遵循这个算法，保证能走出迷宫。
输入数据格式：
下列由符号“1”和“0”组成的网格是一个表示迷宫的二维数组。其中，“1”号表示迷宫的墙，“0”表示穿越迷宫的可能路径中的方格。只有在数组中含有符号（0）的地方才可以走。
输出数据格式：
111111111111 1XXX1XXXXXX1入口 XX1X1X1111X1111X1XXXX1X11XXXX111X1XX1111X101X1X11
X
X
1
X
1
0
1
X
1
X
1
11X1X101X1X11XXXXXXXX1X1111111111111 1XXX1XXXXXX1入口 XX1X1X1111X1111X1XXXX1X11XXXX111X1XX1111X101X1X11
X
X
1
X
1
0
1
X
1
X
1
11X1X101X1X11XXXXXXXX1X1
出口
出口
3.程序实现
3.1程序运行及编译环境
Windows xp系统，VC++6.0 3.2程序描述
该程序使用递归的方法，完成对一个由数字01构成的矩阵迷宫，0表示通路1表示墙壁，通过程序的调用可以在原矩阵中标记出一条从出口到入口间的最短路径。
3.3实现功能
介绍该程序应具有的功能，可采用IPO图（即输入一处理一输出图）的形式。 说明：如果该程序只有单一功能时可以直接描述其输入项、输出项等等各个部分，否则按照各个子功能模块分别介绍。 3.3.1子功能模块1
该函数为程序的核心，函数通过递归的方法找到一条从起始点（有函数的参数x,y引入）到终点（全局常量x2，y2）的路径，并将路径在原来迷宫数组中标记出来（将经过的位置数字0改为6）。 注意由于递归函数的水用，标记路径的过程实际上与走迷宫的过程相反，即从终点到起始点。 代码如下：
//从迷宫中坐标（x，y）的位置寻找通向终点（m，n）的路径 //若找到则返回true，否则返回falsebool SeekPath(int x,int y){
//i作为循环变量，代表从当前位置移动到下一个位置的方向 int i;
//g和h作为下一个位置的行坐标和列坐标 int g,h;
//达到递归出口，返回true结束程序 if((x==x2)&&(y==y2)) return true;
//依次按每个方向寻找通向终点的路径，i=0,1,2,3分别为东南西北 for(i=0;i<4;i++) {
//求出下一个位置的行坐标和列坐标 g=x+move[i][0];h=y+move[i][1];
//若下一个位置可通行同时没有被访问过，则从该位置寻找 if((maze[g][h]==0)&(mark[g][h]==0)) {
//置mark数组中对应位置为1，表明已访问过 mark[g][h]=1;
//当条件成立时，表明从（g，h）到终点存在通路
//将对应位置中maze数组中的值给为6，对走过的通路进行标记，同时返回true结束递归
}
}
//从当前位置（g，h）没有找到通往终点的路径，应返回false return false;
}
//否则进入下一轮循环，向下一个方向试探 if(SeekPath(g,h)){ }
maze[g][h]=6; return true;
3.3.1.1 输入项
迷宫得起点由函数的参数（x,y）引入，终点由全局常量（x2,y2）引入，数组maze[][]mark[][]为全局变量，以上数据均为int型 3.3.1.2输出项
不直接输出，只返回是否找到路径 3.3.1.3数据结构的定义
3.3.1全局数据结构 3.3.2 局部数据结构
3.3.1.4算法及程序说明
函数为递归函数 递归出口为找到迷宫出口
循环试探每个方向的下一个位置，当maze[h][g]的值为0且mark[h][g]的值为0，即位置可走且没有被走过时，选择该位置，改变mark[h][g]为1，即该位置走过，然后将此位置作为当前位置，递归调用函数，寻找下一个可行位置。当四个方向不可行时，则向他的上一级调用函数返回false，退回前一个节点，换一个方向寻找可行路径。以此类推，直到找到迷宫出口返回true，或者所有可行路径均不可达返回false。
SeekPath(x1,y1) 起始点 路径不通， 返回，换一个 SeekPath(h1,g1) 路径不通， 返回，换一个 SeekPath(h2,g2) 路径不通， 返回，换一个 SeekPath(x2,y2) 终止点
3.4运行结果
图4-1 迷宫的初始形态及找到的最短路径（在下面的矩阵中用数字6标记出来）
图4-2 两种形式输出的路径
从图中可以看出递归函数路径的标记过程与走迷宫的过程是相反的，即从出口到入口
因篇幅问题不能全部显示，请点此查看更多更全内容