迷宫实验报告.doc

1.实验题目 迷宫问题 （**） [问题描述] 以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 需求分析 输入的形式和输入值的范围：输入迷宫的行数和列数 输出的形式：输出加了围墙的迷宫和迷宫的出口路径 程序所能达到的功能：寻找迷宫的出口路径 测试数据： 迷宫的测试数据如下：左上角（1，l）为入口，右下角（9，8）为出口。 1 2 3 4 5 6 7 8 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 概要设计(1)struct mark {横坐标，纵坐标}定义迷宫内点的坐标类型 struct Element{横坐标，纵坐标，下一步行走的方向} typedef struct LStack {}定义链栈 int CreateStack(PLStack S) 操作结果：构造空栈 int StackEmpty(PLStack S) 初始条件：栈已存在 操作结果：判断栈是否为空，空返回1，非空返回0 int Push(PLStack S, ElemNode e) 初始条件：栈已存在，e已知 操作结果：将e压入栈中，成功返回1 int Pop(PLStack S,ElemNodet e) 初始条件：栈非空，栈顶元素等于e 操作结果：栈顶元素出栈，成功返回1，否则返回0 void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) 初始条件：迷宫出入口已知，迷宫已建 操作结果：输出迷宫路径序列 void Createmaze(int maze[M][N]) 初始条件：迷宫数组已存在 操作结果：建迷宫 void main() 操作结果：在屏幕上显示操作菜单 函数关系 void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) { CreateStack() StackEmpty() Pop() Push()} void main() { Createmaze() MazePath()} 4．详细设计 struct mark //定义迷宫内点的坐标类型 { int x; //横坐标 int y; //纵坐标 }; struct ElemNode //链栈元素结点 { int x,y; //x行,y列 int d; //d下一步的方向 }; typedef struct LStack //链栈 { ElemNode elem; struct LStack *next; //指针变量 }*PLStack; int CreateStack(PLStack S){ 构造空栈，成功返回1} int StackEmpty(PLStack S){ 判断栈是否为空 是空返回1，否则返回0 } int Push(PLStack S, ElemNode e){ 定义参数p分配空间,将e赋值给p p-next指向S 将p压栈 成功返回1 } int Pop(PLStack S,ElemNode e){ 判断栈是否为空 非空提取栈顶元素值 S指针下移 是空返回1，否则返回0 } void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) { 建立两个空栈S1，S2 标记入口点 入口点入栈S1 while(栈S1不为空）{ 栈顶元素出栈 下一个方向 while(d4) //试探东南西北各个方向，用diradd[4][2]标记是哪个方向 { a=i+diradd[d][0]; b=j+diradd[d][1]; if(a==end.x b==end.y maze[a][b]==0) //如果到了出口 将S1逆置存入S2中，S2再出栈 } 如果找到的是可以前进的非出口的点 则点入栈，并作标记 更新数据行坐标，纵坐标的值，d重置为-1 } } void Createmaze(int maze[M][N]){ 先输入迷宫的行数和列数 再输入迷宫数组 用两个for 循环在迷宫的外围加围墙 输出加围墙后的迷宫 } void main() { 输入