XX大学信息与计算科学专业2008级《数据结构》集中上机设计题目：迷宫求解（非递归求解）设计时间：2010-2011学年第一学期目录一、实验内容 (2)二、需求分析 (2)三、总体设计 (2)（一）存储结构 (2)（二）流程图 (3)四、详细设计 (3)（一）基本算法解析 (3)（二）为实现算法，需要的象的数据类型 (4)(三)函数的调用关系 (5)（四）算法时间、空间复杂度 (5)五、代码 (5)六、运行结果分析 (10)（一）迷宫路径探索成功 (10)（二）迷宫路径未找到的情况 (13)（三）程序的优缺点与改进 (13)七、参考文献 (14)八、心得体会 (14)一、实验内容任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。
二、需求分析1、可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求使用非递归算法。
2、用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立迷宫。
3、可以自行输入迷宫的入口和出口坐标。
4、程序执行的命令包括：（1）构造栈函数。
其中包括了构造空栈InitStack；压入新数据元素Push；栈顶元素出栈Pop。
（2）构造求迷宫路径函数。
其中定义了二维数组maze[M][N]存取迷宫数据；输出找到的通路MazePath。
（3）建立一个迷宫initmaze。
其中包括输入迷宫行数列数以及各行各列；加一圈围墙并输出迷宫。
三、总体设计（一）存储结构：首先用二维数组存储迷宫数据，迷宫数据由用户输入。
一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。
1．从入口出发，顺着某一个方向进行探索，若能走通，继续往前走，否则沿原路退回，换一个方向继续探索，直至出口位置，求得一条通路。
假如所有可能的通路都探索到但没能到达出口，则所设置的迷宫没有通路。
迷宫的入口点的下标（a,b），出口点的下标（m,n）。
为方便，可在迷宫周围加一周障碍。
对于迷宫的任意位置，均可约定有东西南北4个方向可以走通。
经过的位置把0变成-1，输出迷宫路径。
2本程序有三个模块;（1）主程序模块（2）三个模块即其对象，实现栈链表抽象数据类型（3）迷宫存储迷宫，寻路径，输出迷宫。
（二）流程图四、详细设计（一）基本算法解析：首先用二维数组存储迷宫数据，迷宫数据由用户输入。
一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。
迷宫的过程可以模拟成一个搜索的过程。
每到一处，总让它按东西南北四个方向顺序试探下一个位置，如果某方向可以通过，并且不曾到达，则前进一步，在新的位置上继续进行探索。
如果4个方向都走不通或者曾经到达过，则退回一步，在原来的位置上继续试探下一位置。
每前进一步或后退一步，都要进行判断，若前进到了出口处，则说明找到了一条通路，若退回到了入口处，则说明不存在通路。
用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。
迷宫的入口点在位置（a,b）处，出口点在位置（m,n）处。
设计一个模拟走迷宫的算法，为期寻找一条从入口点到出口点的通路。
二维数组的0行m+1列元素全置成“1”，表示迷宫的外墙，第一行第一列元素和第m行m列元素置成“0”，表示迷宫的入口和出口。
假设当前所在位置是（x,y）。
延某个方向前进一步，它可能到达的位置最多有4。
如果用结构体Element elem记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用结构体Element elem确定while(!StackEmpty(S1)) //栈不为空有路径可走{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1;从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。
定义一个栈，按从入口到出口存取路径，在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中，当前位置“-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。
如果没有新位置入栈，则返回到上一个位置。
一直到达出口。
总之，入口出发，顺着某一个方向进行探索，若能走通，则继续往前进，否则沿着原路返回，换一个方向继续探索，直至出口位置，求得一条通路。
假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
迷宫的入口点在位置（1,1），出口点在位置（m,n）。
为处理方便，可在迷宫的四周加一周障碍。
对于迷宫的任一位置，均可定为东南西北四个方向可通。
（二）为实现算法，需要的象的数据类型InitStack() 构造空栈StackEmpty() 判断栈是否为空Push() 压入新数据元素Pop() 栈顶元素出栈m 迷宫的行数n 迷宫的列数d 0=东1=南2=西3=北typedef struct Lstack{Element elem; 链栈struct LStack *next;}*PLStack;(三)函数的调用关系mainInitStack Push Pop（四）算法时间、空间复杂度1）本算法在空间上主要开辟了一个二维数组，规模都是迷宫（m+2）*（n+2）。
一个是栈，一个是迷宫路径记录，输入时候调用栈。
2)在时间上为简单的链表栈的存储结构，二维指针initmaze函数算法时间复杂度为O（（m+2）*（n+2）），Mazepath为O（1），（m为行数n为列数）。
五、代码/*以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
首先实现一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
*/#include<stdio.h>#include<stdlib.h>#define M 15#define N 15struct mark //定义迷宫内点的坐标类型{int x;int y;};struct Element //栈元素{int x,y; //x行,y列int d; //d下一步的方向};typedef struct LStack //链栈{Element elem;struct LStack *next;}*PLStack;/*************栈函数****************/int InitStack(PLStack &S)//构造空栈{S=NULL;return 1;}int StackEmpty(PLStack S)//判断栈是否为空{if(S==NULL)return 1;elsereturn 0;}int Push(PLStack &S, Element e)//压入新数据元素{PLStack p;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return 1;}int Pop(PLStack &S,Element &e) //栈顶元素出栈{PLStack p;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return 1;}elsereturn 0;}/***************求迷宫路径函数***********************/void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) {int i,j,d;int a,b;Element elem,e;PLStack S1, S2;InitStack(S1);InitStack(S2);maze[start.x][start.y]=2; //入口点作上标记elem.x=start.x;elem.y=start.y;elem.d=-1; //开始为-1Push(S1,elem);while(!StackEmpty(S1)) //栈不为空有路径可走{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1; //下一个方向while(d<4) //试探东南西北各个方向{a=i+diradd[d][0];b=j+diradd[d][1];if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口{elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);elem.x=a;elem.y=b;elem.d=886; //方向输出为-1 判断是否到了出口Push(S1,elem);printf("\n0=东1=南2=西3=北886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");while(S1) //逆置序列并输出迷宫路径序列{Pop(S1,e);Push(S2,e);}while(S2){Pop(S2,e);printf("-->(%d,%d,%d)",e.x,e.y,e.d);}return; //跳出循环}if(maze[a][b]==0) //找到可以前进的非出口的点{maze[a][b]=2; //标记走过此点elem.x=i;elem.y=j;elem.d=d;Push(S1,elem); //当前位置入栈i=a; //下一点转化为当前点j=b;d=-1;}d++;}}printf("没有找到可以走出此迷宫的路径\n");}/*************建立迷宫*******************/void initmaze(int maze[M][N]){int i,j;int m,n; //迷宫行,列[/M]printf("请输入迷宫的行数m=");scanf("%d",&m);printf("请输入迷宫的列数n=");scanf("%d",&n);printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);for(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&maze[i][j]);printf("你建立的迷宫为(最外圈为墙)...\n");for(i=0;i<=m+1;i++) //加一圈围墙{maze[i][0]=1;maze[i][n+1]=1;}for(j=0;j<=n+1;j++){maze[0][j]=1;maze[m+1][j]=1;}for(i=0;i<=m+1;i++) //输出迷宫{for(j=0;j<=n+1;j++)printf("%d ",maze[i][j]);printf("\n");}}void main(){int sto[M][N];struct mark start,end; //start,end入口和出口的坐标int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量方向依次为东西南北[/M]initmaze(sto);//建立迷宫printf("输入入口的横坐标,纵坐标[逗号隔开]\n");scanf("%d,%d",&start.x,&start.y);printf("输入出口的横坐标,纵坐标[逗号隔开]\n");scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add); //find pathsystem("PAUSE");}六、运行结果分析（一）迷宫路径探索成功初始界面测试数据迷宫6行（输入“6”点击Enter得到下一界面）测试数据迷宫8列（输入“8”点击Enter得到下一界面）测试数据6行8列迷宫0 1 0 1 1 0 1 10 0 1 1 1 0 1 01 0 1 1 0 1 0 01 0 0 0 1 0 1 10 0 0 1 1 1 1 01 1 0 0 1 0 1 1（输入上述迷宫，点击Enter得到下一界面）测试数据迷宫入口（1,1）（输入“1，1”点击Enter得到下一界面）测试数据迷宫出口（6,3）（输入“6，3”点击Enter得到下一界面）如上图，我们可以得到：当迷宫为0 1 0 1 1 0 1 10 0 1 1 1 0 1 01 0 1 1 0 1 0 01 0 0 0 1 0 1 10 0 0 1 1 1 1 01 1 0 0 1 0 1 1迷宫入口为（1,1）出口为（6,3）时迷宫路径为，（括号内的内容分别表示为（行坐标，列坐标，数字化方向（0=东1=南2=西3=北））<1,1,1> <2,1,0> <2,2,1> <3,2,1> <4,2,0> <4,3,1> <5,3,1> <6,3,886>迷宫路径探索成功！（二）迷宫路径未找到的情况在上述测试的数据当中，我们把迷宫出口改为（6,5）得到的运行结果如下图：（三）程序的优缺点与改进1、该程序在输出上显得有些繁琐。