栈与迷宫问题课程设计

『壹』 【迷宫问题】用堆栈解迷宫

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>


#defineMAXM40
#defineMAXN60
intmaze[MAXM][MAXN];//01-障碍物
intm=40,n=60;//40行60列
intused[MAXM][MAXN];//记录是否到过


intline[MAXM*MAXN];//记录迷宫路线
intline_len;
intline_r[MAXM*MAXN];

intd[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//4个方向

voiddfs(intu,intv,intstep)
{
intx,y,i;
if(line_len!=0)
return;
if(u==m-1&&v==n-1)
{
line_len=step;
memcpy(line_r,line,line_len*sizeof(int));
return;
}

for(i=0;i<4;i++)
{
x=u+d[i][0];
y=v+d[i][1];
if(x>=0&&x<m&&y>=0&&y<n&&!used[x][y]&&maze[x][y]==0)
{
used[x][y]=1;
line[step]=x<<16|y;
dfs(x,y,step+1);
//used[x][y]=0;//不用退回来了，因为只需要一条路径
}
}
}

intmain()
{
inti,j;
//随机生成迷宫
srand(time(NULL));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
maze[i][j]=rand()%8==0?1:0;//是1的概率约1/8,通路的概率大些
maze[0][0]=maze[m-1][n-1]=0;//起始点和终端必须为0

line_len=0;
line[0]=0<<16|0;
memset(used,0,sizeof(used));
dfs(0,0,0);//(0,0)->(m-1,n-1)

if(line_len==0)
printf("没有通路
");
else
{
for(i=0;i<line_len;i++)
printf("(%d,%d)
",(line_r[i]>>16)+1,(line_r[i]&0xffff)+1);
}

return0;
}

你给的那库实在是没什么用的欲望，要最短路径一般用广度搜索，上面的代码应该属于深度搜索

『贰』 用栈做的迷宫问题，要代码，急急急

1． 设计栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai|ai∈CharSet,i=1,2..,n}
数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
基本操作:(这里仅列举本题中使用的操作)
Creat()
操作结果:构建一个空栈。
Push()
操作结果:在栈顶插入新的元素。
Pop（）
操作结果：将栈顶元素弹出。
Empty（）
判断栈是否为空
}ADT stack
2． 本程序包含了三个模块
1） 主程序模块：
void main()
{
输入起点，终点；
处理命令；
输出结果；
}
2） 栈模块-----实现栈抽象数据类型
3） 迷宫模块-----找出迷宫中的通路
3.求解迷宫中一条通路的伪码
设定当前位置的初值为入口位置:
do{
若当前位置可通,
则{ 将当前位置插入栈顶; //纳入路径
若该位置是出口,则输出迷宫图,结束; //求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置;
}
否则{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置四周均不可通，
则{删去栈顶位置； //后退一步，从路径中删去该通道
若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}
}while（栈不空）
（栈空说明没有路径存在）
二. 详细设计
迷宫坐标位置类型
typedef struct maze{
int a;
int b;
int dir;
struct maze *next;
}mazestack;
栈的基本操作实现
1） 栈的初始化
mazestack *creat(){
mazestack * p;
p=(mazestack *)malloc(sizeof(mazestack)); //开辟坐标空间
if(!p)
return NULL; //开辟失败，返回空值
p->next=NULL;
return p; //返回栈顶指针
}
2） 压栈操作
mazestack * push(mazestack * p,int i,int j,int k) //p为栈顶指针
i , j为坐标参数，k为通路下一步方向代码
{
mazestack * p1;
p1=(mazestack *)malloc(sizeof(mazestack)); //开辟坐标空间
if(!p1)
return NULL;
p1->a=i;
p1->b=j;
p1->dir=k; //将参数导入坐标空间
p1->next=p; //将新开辟空间压入栈
p=p1; //移动栈顶指针到新栈顶
return p; //返回栈顶指针
}
3） 弹栈操作
mazestack * pop(mazestack *p, int *i,int *j,int *k) // p为栈顶指针，i，j为坐标参数，k为通路下一步方向代码
{
mazestack *p1;
p1=p;
*i=p1->a;
*j=p1->b;
*k=p1->dir; //将空间中坐标和方向代码导出
p=p->next; //将栈顶指针移动到新栈顶位置
free(p1); //释放旧栈顶空间
return p;
}
4） 判断栈空
int empty(mazestack *p) //p为所要判断的指针
{
if(p->next==NULL){
return 1; //栈空，返回1
}
else return 0; /栈不空，返回0
}
改变路径前进方向
int nextpos(int *i,int *j,int di) //i，j为迷宫坐标，di为下一步路径的方向
{
switch(di){
case 1: *i=*i;*j=*j+1;break; //di=1 ，下一步向东
case 2: *i=*i+1;*j=*j;break; //di=2 ，下一步向南
case 3: *i=*i;*j=*j-1;break; //di=3 ， 下一步向西
case 4: *i=*i-1;*j=*j;break; //di=4 ， 下一步向北
}
return 1;
}
求迷宫路径的算法
mazestack * maze(int i1,int j1,int i2,int j2) //i1，j1为入口坐标，i2，j2为出口坐标
{
int a[10][10]={ 0,0,0,0,0,0,0,0,0,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,1,1,0,0,1,1,0,
0,1,0,0,0,1,1,1,1,0,
0,1,1,1,0,1,1,1,1,0,
0,1,0,1,1,1,0,1,1,0,
0,1,0,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0}; //具体迷宫形式
int i=i1,j=j1;
int k;
mazestack * p;
p=creat(); //建立栈
do{
if(a[i][j]==1){ //判断路径是否已经经过
a[i][j]=5; //没有经过，则将该坐标进行标记
p=push(p,i,j,a[i][j]); //将该坐标点压入栈中
if(i==i2&&j==j2){ //判断压入坐标是否为终点
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(a[i][j]>1){
a[i][j]=5;
printf(" %d ",a[i][j]);
}
else printf(" %d ",a[i][j]);
}
printf("\n\n");
} //压入坐标是终点，将走迷宫图输出，其中路径值为5

return p; //返回栈顶指针
}
nextpos(&i,&j,1); //压入坐标不是终点，将坐标点向东移动一步
}
else{ //路径已经经过
if(!empty(p)){
p=pop(p,&i,&j,&k); //退回一步
a[i][j]=k;
while(a[i][j]==4&&!empty(p)) //判断该坐标周围是否还有通路
{
a[i][j]=1;
p=pop(p,&i,&j,&k);
a[i][j]=k; //没有通路，将其坐标置回成没有经过的路，退回到上一步
}
if(a[i][j]<4){
a[i][j]++;
p=push(p,i,j,a[i][j]);
nextpos(&i,&j,a[i][j]);
} //存在通路，则向下一步方向前进
else if(a[i][j]>4){
a[i][j]=2;
p=push(p,i,j,a[i][j]);
nextpos(&i,&j,a[i][j]);
} //只经过一次的通路，下一步向南走
}
}
}while(!empty(p)) ;
return NULL;
}
主函数算法
main()
{
int i1,i2,j1,j2;
int m,n,l;
int num=0;
mazestack * ma;
printf("input start point\n");
scanf("%d,%d",&i1,&j1); //输入起点
printf("input end point\n");
scanf("%d,%d",&i2,&j2); //输入终点
ma=maze(i1,j1,i2,j2); //求解迷宫
if(ma==NULL){
printf("There is no way");
} //空栈，说明没有路经
else{
while(!empty(ma)){
ma=pop(ma,&m,&n,&l);
printf("(%d,%d) ",m,n);
num++;
} //输出路径结果和步长
printf("the step is %d",num);
}
}

这个应该自己能看懂吧~~根据你自己的需要,改动某些部分即可~~

『叁』 C语言中用栈实现迷宫问题

#include
#define MAXSIZE 100
using namespace std;
struct stack{
int iway;
int jway;
int dire;
};
stack maze[MAXSIZE];
int top;
int map[14][28]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1},
{1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};

void findway(int xS,int yS,int xE,int yE)
{
top=0;
maze[top].iway=xS;
maze[top].jway=yS;
map[xS][yS]=-1;
int i,j,di,find;
while(top>-1)
{
i=maze[top].iway;
j=maze[top].jway;
di=maze[top].dire;
if(i==xE&&j==yE)
{
cout<<"***********************************\n";
cout<<"path"<<":"<<endl;
cout<<"("<<maze[0].iway<<","<<maze[0].jway<<")";
for(int val=1;val<top+1;val++)
{
cout<("<<maze[val].iway<<","<<maze[val].jway<<")";
if((val+1)%5==0)
cout<<endl;
}
cout<<endl;
cout<<"***********************************\n";
return;
}
find=0;
while(find==0&&di<4)
{
di++;
switch(di)
{
case(0):i=maze[top].iway;
j=maze[top].jway+1;
break;
case(1):i=maze[top].iway;
j=maze[top].jway-1;
break;
case(2):i=maze[top].iway+1;
j=maze[top].jway;
break;
case(3):i=maze[top].iway-1;
j=maze[top].jway;
break;
}
if(map[i][j]==0)
{
find=1;
}
}
if(find==1)
{
maze[top].dire=di;
top++;
maze[top].iway=i;
maze[top].jway=j;
maze[top].dire=-1;
map[i][j]=-1;
}
else
{
map[maze[top].iway][maze[top].jway]=0;
top--;
}
}
}
int main()
{
for(int i=0;i<14;i++) //迷宫图形化输出
{
for(int j=0;j<28;j++)
{
if(map[i][j]==1)
cout<<"■";
else cout<<"□";
}
cout<<endl;
}
int xStart,yStart,xEnd,yEnd;
cout<<"请输入迷宫起点坐标，用空格隔开(左上角坐标为(0,0)):";
cin>>xStart>>yStart;
cout<<"请输入迷宫终点坐标，用空格隔开(右上角坐标为(13,27)):";
cin>>xEnd>>yEnd;
findway(xStart,yStart,xEnd,yEnd);
return 0;
}
满意请采纳！

『肆』 1、 迷宫寻路（递归程序设计和栈的应用） 【问题描述】 将一只老鼠从一个矩形无顶大盒子（

这里有篇博文基于栈和队列的迷宫问题求解基于栈和队列提供迷宫问题的解决方案，也属有提供源码下载~也可以在这个网站上面搜索看看，刚才还搜到很多课设和毕设，都有源码和文档，一个干货满满的博客，有用的话记得采纳哦^_^

『伍』 迷宫问题（栈实现）

问题补充：这个迷宫是八个方向走的，不只是上下左右四个方向。而且迷宫数据肯定没问题。 #include

『陆』 C++课程设计：迷宫问题演示程序

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define M 15
#define N 15
int z=0;
struct Point
{
int m_1;
int n_1;
Point_cout();
Point_cout1();
};
Point::Point_cout()
{
return(m_1);
}
Point::Point_cout1()
{
return(n_1);
}
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(p);
return 1;
}
else
return 0;
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[2][4][2],int z,int &a,int &b)
{
int m=a;
int n=b;
int i,j,d;
int a_1,b_1;
Element elem;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
if(z<2)
{
for(int w_1=0;w_1<9;w_1++)
for(int w_2=0;w_2<8;w_2++)
if(maze[w_1][w_2]==2)
maze[w_1][w_2]=0;
maze[start.x][start.y]=2;
//入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1;
Push(S1,elem); //开始为-1
//cout<<elem.x<<" "<<elem.y<<" "<<elem.d<<" "; while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
//cout<<elem.x<<elem.y<<elem.d;
i=elem.x;
j=elem.y;
d=elem.d+1;while(d<4) //试探东南西北各个方向
{
a_1=i+diradd[z][d][0];
b_1=j+diradd[z][d][1];
if(a_1==end.x && b_1==end.y && maze[a_1][b_1]==0) //如果到了出口
{
cout<<"可以到达出口的路径有："<<endl;
//maze[a][b]=2
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a_1;
elem.y=b_1;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
//cout<<"\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)";
cout<<endl;
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,elem);
//cout<<"("<<e.x<<","<<e.y<<","<<e.d<<")"<<"-->";
Push(S2,elem);
}
while(S2)
{
Pop(S2,elem);
printf("-->(%d,%d,%d)",elem.x,elem.y,elem.d);
}
cout<<endl;
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
++z;
MazePath(start,end,maze,diradd,z,a,b);
}
if(maze[a_1][b_1]==0) //找到可以前进的非出口的点
{
maze[a_1][b_1]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a_1; //下一点转化为当前点
j=b_1;
d=-1;
}
d++;
}
}
//cout<<"("<<elem.x<<","<<elem.y<<","<<elem.d<<")"<<"-->"<<"||";
}
//cout<<"没有找到可以走出此迷宫的路径\n";
}
/*************建立迷宫*******************/
int initmaze(int maze[M][N],int &a,int &b)
{
int i,j;
int m,n; //迷宫行,列
cout<<"请输入迷宫的行数 m=";
cin>>m;
cout<<"请输入迷宫的列数 n=";
cin>>n;
a=m;
b=n;
cout<<"请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙:";
cout<<endl;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>maze[i][j];
cout<<"你建立的迷宫为:";
cout<<endl;
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=8;
maze[i][n+1]=8;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=8;
maze[m+1][j]=8;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
return 0;
} void main()
{
int a=0;
int b=0;
int sto[M][N]; struct mark start,end; //start,end入口和出口的坐标
int add[2][4][2]={{{0,1},{1,0},{0,-1},{-1,0}},{{1,0},{0,1},{0,-1},{-1,0}}};//行增量和列增量 方向依次为东西南北
cout<<"注:上面的式子一维为2，根据东西南北，共有16种排列，因数量太多，故省略只写顺序依次为东南西北和南东西北";
cout<<endl;
initmaze(sto,a,b);//建立迷宫
cout<<"输入入口的横坐标,纵坐标";
cin>>start.x>>start.y;
cout<<"输入出口的横坐标,纵坐标";
cin>>end.x>>end.y;
MazePath(start,end,sto,add,z,a,b); //find path
//system("PAUSE");
}
// 下面是以9行8列的输入（你可以复制，黏贴就ok 了）0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1

『柒』 迷宫问题的课程设计报告

http://download.csdn.net/source/298953
这里有下载呼呼
还有个要交钱的也给你吧
http://cn.happycampus.com/docs/983345939101@hc04/56958/

『捌』 数据结构课程设计的迷宫问题~~~~急！！！

看下我的程序,,要不是你要的.

#include <iostream>
#include <iomanip>
using namespace std;
#define M 20
#define N 20
struct move{int dx,dy;};
move mazemove[8];
char ma[M][N];
int False=0;

void maze()
{int i,j,num;
for(i=1;i<M-1;i++)
{for(j=1;j<N-1;j++)
{num=(800*(i+j)+1500)%327;
if((num<156)&&(i!=M||j!=N))
ma[i][j]='1';
else
ma[i][j]='0';
}
}
ma[1][1]='0';
ma[M-2][N-2]='0';
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
cout<<setw(3)<<ma[i][j];
cout<<endl;
}
}

void inimove()
{mazemove[0].dx=0;mazemove[0].dy=1;
mazemove[1].dx=1;mazemove[1].dy=1;
mazemove[2].dx=1;mazemove[2].dy=0;
mazemove[3].dx=1;mazemove[3].dy=-1;
mazemove[4].dx=0;mazemove[4].dy=-1;
mazemove[5].dx=-1;mazemove[5].dy=-1;
mazemove[6].dx=-1;mazemove[6].dy=0;
mazemove[7].dx=-1;mazemove[7].dy=1;
}

void outpath()
{int i,j,x,y,k;
i=1;j=1;k=0;
while((i!=(M-2))||(j!=(N-2)))
{for(k=0;k<8;k++)
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if(ma[x][y]=='0'){k=0;break;}
}
if(k!=8)
{if(ma[i][j]=='8')ma[i][j]='2';
if(ma[i][j]=='0')ma[i][j]='>';
i=x;j=y;
}
else
{for(k=0;k<8;k++)
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if(ma[x][y]=='8')break;
}
ma[i][j]='2';
i=x;j=y;
}
if((i==1)&&(j==1))
{False=0;
break;
}
else False=1;
}

}

int main()
{int i,j;
maze();
inimove();
outpath();
cout<<endl;
if(False==0)
cout<<"无法走出该迷宫!"<<endl;
else
{cout<<"走出迷宫的路径(用‘>’符号表示)为:"<<endl;
ma[M-2][N-2]='>';
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
{ {if(ma[i][j]=='2')ma[i][j]='>';
if(ma[i][j]=='0')ma[i][j]=' ';
if(ma[i][j]=='1')ma[i][j]='*';
}
cout<<setw(3)<<ma[i][j];
}
cout<<endl;
}
}
return 0;
}

『玖』 迷宫问题（栈的应用）

太难了......

『拾』 请帮我做一道数据结构程序题，题目为用栈解决迷宫问题

注：下面分别是三个文件：栈的定义与声明（头文件）、栈的实现、迷宫问题。

/* 顺序栈表示：类型和界面函数声明 */

enum { MAXNUM = 20 /* 栈中最大元素个数，应根据需要定义 */
};

typedef int DataType; /* 栈中元素类型，应根据需要定义 */

struct SeqStack { /* 顺序栈类型定义 */
int t; /* 栈顶位置指示 */
DataType s[MAXNUM];
};

typedef struct SeqStack SeqSack, *PSeqStack; /* 顺序栈类型和指针类型 */

/*创建一个空栈;为栈结构申请空间，并将栈顶变量赋值为-1*/
PSeqStack createEmptyStack_seq( void );

/*判断pastack所指的栈是否为空栈，当pastack所指的栈为空栈时，则返回1，否则返回0*/
int isEmptyStack_seq( PSeqStack pastack );

/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x );

/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack );

/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack );

/* 顺序栈表示：函数定义 */

#include <stdio.h>
#include <stdlib.h>

#include "sstack.h"

/*创建一个空栈;为栈结构申请空间，并将栈顶变量赋值为-1*/
PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
printf("Out of space!! \n");
else
pastack->t = -1;
return pastack;
}

/*判断pastack所指的栈是否为空栈，当pastack所指的栈为空栈时，则返回1，否则返回0*/
int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}

/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Stack Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}

/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}

/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack ) {
return pastack->s[pastack->t];
}

/* 迷宫问题的非递归算法(栈实现)*/

#define MAXNUM 100/* 栈中最大元素个数 */
#define N 11 /*地图的第一维长度*/
#include <stdio.h>
#include <stdlib.h>

typedef struct {
int x;/* 行下标 */
int y;/* 列下标 */
int d;/* 运动方向 */
} DataType;

struct SeqStack { /* 顺序栈类型定义 */
int t; /* 指示栈顶位置 */
DataType s[MAXNUM];
};

typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */
PSeqStack pastack; /* pastack是指向顺序栈的一个指针变量 */

PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack == NULL)
printf("Out of space!! \n");
else
pastack->t = -1;
return pastack;
}

int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}

/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}

/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}

/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack ) {
return (pastack->s[pastack->t]);
}

void pushtostack(PSeqStack st, int x, int y, int d) {
DataType element;
element.x = x;
element.y = y;
element.d = d;
push_seq(st, element);
}

void printpath(PSeqStack st) {
DataType element;
printf("The revers path is:\n"); /* 打印路径上的每一点 */
while(!isEmptyStack_seq(st)) {
element = top_seq(st);
pop_seq(st);
printf("the node is: %d %d \n", element.x, element.y);
}
}

/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2) {
int i, j, k, g, h;
PSeqStack st;
DataType element;
st = createEmptyStack_seq( );
maze[x1][y1] = 2; /* 从入口开始进入,作标记 */
pushtostack(st, x1, y1, -1); /* 入口点进栈 */

while ( !isEmptyStack_seq(st)) { /* 走不通时,一步步回退 */
element = top_seq(st);
pop_seq(st);
i = element.x; j = element.y;
for (k = element.d + 1; k <= 3; k++) { /* 依次试探每个方向 */
g = i + direction[k][0];h = j + direction[k][1];
if (g == x2 && h == y2 && maze[g][h] == 0) { /* 走到出口点 */
printpath(st); /* 打印路径 */
return;
}
if (maze[g][h] == 0) { /* 走到没走过的点 */
maze[g][h] = 2; /* 作标记 */
pushtostack(st, i, j, k); /* 进栈 */
i = g; j = h; k = -1; /* 下一点转换成当前点 */
}
}
}
printf("The path has not been found.\n");/* 栈退完未找到路径 */
}

int main(){
int direction[][2]={0,1,1,0,0,-1,-1,0};
int maze[][N] = {
1,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,0,0,1,
1,0,0,0,0,0,1,0,0,1,1,
1,0,1,1,1,0,0,0,1,1,1,
1,0,0,0,1,0,1,1,0,1,1,
1,1,0,0,1,0,1,1,0,0,1,
1,1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1
};
mazePath(maze,direction,1,1,6,9);
getchar();
return 0;
}