资源描述：
《数据结构上机作业迷宫求解.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构集中上机》报告第一题：迷宫求解（参见教材描述）任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；源程序： #include#include#defineM15#defineN15structmark//定义迷宫内点的坐标类型{intx;inty;};structElement{intx,y;//x行,y列intd;//d下一步的方向};typedefstructLStack//链栈{Elementelem;structLStack*next;}*PLSta
2、ck;intInitStack(PLStack&S)//构造空栈{S=NULL;return1;}intStackEmpty(PLStackS)//判断栈是否为空{if(S==NULL)return1;elsereturn0;}intPush(PLStack&S,Elemente)//压入新数据元素{PLStackp;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return1;}intPop(PLStack&S,Element&e)//栈顶元素出栈{PLStackp;if(
3、!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return1;}elsereturn0;}voidMazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2]){inti,j,d;inta,b;Elementelem,e;PLStackS1,S2;InitStack(S1);InitStack(S2);maze[start.x][start.y]=2;//入口点作上标记elem.x=start.x;elem.y=star
4、t.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
5、.y=b;elem.d=886;//方向输出为-1判断是否到了出口Push(S1,elem);printf("0=东1=南2=西3=北886为则走出迷宫通路为:(行坐标,列坐标,方向)");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;//标记走过此
6、点elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);//当前位置入栈i=a;//下一点转化为当前点j=b;d=-1;}d++;}}printf("没有找到可以走出此迷宫的路径");}/*************建立迷宫*******************/voidinitmaze(intmaze[M][N]){inti,j;intm,n;//迷宫行,列printf("请输入迷宫的行数m=");scanf("%d",&m);printf("请输入迷宫的列数n=");scanf("%d",&n);printf(
7、"请输入迷宫的各行各列:用空格隔开,0代表路,1代表墙",m,n);for(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&maze[i][j]);printf("你建立的迷宫为:");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"
8、,maze[i][j]);printf("");}}voidmain(){intsto[M][N];structmarkstart,end;//s
