C语言数据结构中的迷宫问题（栈的应用）

不念不忘少年蓝@ 2021-11-05 19:12 320阅读 0赞

\#include<stdio.h>  
\#include<stdlib.h>  
\#define M 15  
\#define N 15  
struct 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;  
else  
return 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§;  
return 1;  
\}  
else  
return 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; //开始为-1  
Push(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(aend.x && bend.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; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用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 path  
system(“PAUSE”);  
\}