数据结构C语言版迷宫问题

数据结构C语言版的迷宫问题如何解决？~

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define M 10
#define N 10
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[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(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=4; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("0=东 1=南 2=西 3=北 4为则走出迷宫
通路为:(行坐标,列坐标,方向)
");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
printf("成功 !
");
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("没有找到可以走出此迷宫的路径,等着憋死吧!
");
}

void initmaze(int maze[M][N])
{//建立迷宫
int i,j;
int m,n; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("请输入迷宫的各行各列:(用空格隔开,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 ",maze[i][j]);
printf("
");
}
}

void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]
");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]
");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //寻找路径
}

这个迷宫的路径不是唯一的，因此从不同方向开始试探执行结果也可能会不唯一。我写的是参考书上的，共有八个方向可以试探。
栈解决迷宫主要的几个问题：
1.迷宫的存储
2.栈的设计
3.试探方向
4.不重复到达某点，即不陷入死循环
如果对算法有什么疑问，或是我的回答有错误的地方，可以Hi我。
#define LINES 9 // 定义行数
#define COLS 8 // 定义列数

#include
#include
#include

typedef struct{
int line;
int col;
}MOVE; // 定义试探方向的结构体
MOVE to[8] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; // 定义数组，存放8个试探方向
typedef struct{ // 行、列、方向构成的三元组
int x;
int y;
int d;
}DataType;
typedef struct node{
DataType element;
struct node * next;
}StackNode,*LinkStack;

LinkStack InitStack(LinkStack s); // 栈初始化
LinkStack PushStack(LinkStack,DataType *); // 入栈函数
LinkStack PopStack(LinkStack,DataType *); // 出栈函数
int EmptyStack(LinkStack s); // 判定栈空
int path(int maze[][COLS+2]); // 打印路径
void printpath(LinkStack s,DataType * t);

int main( void )
{
int i,j;
int maze[LINES+2][COLS+2] = // 定义存放迷宫的数组并初始化
{1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,1,1,
1,0,1,1,1,0,0,1,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,1,1,
1,0,1,1,1,1,0,0,1,1,
1,1,1,0,0,0,1,0,1,1,
1,1,1,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1
};
for(i=1;i<LINES+1;i++)
{
for(j=1;j<COLS+1;j++){
if( 0 == maze[i][j] ){
printf("□");
}
else{
printf("■");
}
}
printf("
");
}
if( path(maze) ){
printf("找到一条路径
");
for(i=1;i<LINES+1;i++)
{
for(j=1;j<COLS+1;j++)
{
if( 0 == maze[i][j] ){
printf("□");
}
else if( 1 == maze[i][j]){
printf("■");
}
else{
printf("☆");
}
}
printf("
");
}
}
else{
printf("迷宫无路径
");
}
return 0;
}
LinkStack InitStack(LinkStack s)
{
return NULL;
}
LinkStack PushStack(LinkStack s,DataType * t)
{
StackNode * p;
p = NULL;
p = (StackNode *)malloc(sizeof(StackNode));
if(!p){
printf("申请结点失败
");
exit(1);
}
p->element = *t;
p->next = s;
s = p;
return s;
}
LinkStack PopStack(LinkStack s,DataType *t)
{
StackNode * p = NULL;
if( EmptyStack(s) ){
printf("栈空
");
return NULL;
}
p = s;
*t = p->element;
s = s->next;
free(p);
p = NULL;
return s;
}
int EmptyStack(LinkStack s)
{
if( NULL == s ){
return 1;
}
return 0;
}
int path(int maze[][COLS+2])
{
int i,j,x1,y1,v;
DataType temp;
LinkStack top;
temp.x = 1;
temp.y = 1;
temp.d = -1;
top = InitStack(top);
top = PushStack(top,&temp);
while( !EmptyStack(top) )
{
top = PopStack(top,&temp);
// 入口为(1,1)，从0方向开始试探
x1 = temp.x;
y1 = temp.y;
v = temp.d + 1;
while( v < 8 )
{
i = x1 + to[v].line;
j = y1 + to[v].col;
if( 0 == maze[i][j] ){ // 到达新点
temp.x = x1;
temp.y = y1;
temp.d = v;
top = PushStack(top,&temp); // 坐标及方向入栈
x1 = i;
y1 = j;
maze[x1][y1] = -1; // 对已经到过的点做标记
if( x1 == LINES && y1 == COLS ){ // 到达出口
printpath(top,&temp); // 打印路径
return 1;
}
else{
v = 0;
}
}
else{
v++;
}
}
}
return 0;
}
void printpath(LinkStack s,DataType * t)
{
while( !EmptyStack(s) )
{
printf("(%d, %d, %d)
",s->element.x,s->element.y,s->element.d);
s = PopStack(s,t);
}
}

刚学都这样，想当初我学习的时候连一个单链表的逆置，都要理解半天。编程就是把实际问题给抽象成数学或非数学模型，结合数据的表示，再找到解决的方法。别忘了，学习数据结构是为了更好的操作数据。
思路：
首先，迷宫如何用计算机语言表示？一般用二维数组。0表示墙，1表示路。
其次，其次就是如何从迷宫中走出来了。结合堆栈，进行搜索。
你可以尝试着对问题进行分层，然后逐步细化来解决。

如果你要解决一个别人给的走迷宫的问题，同样还是要这样，首先把别人给的迷宫在计算机中表示出来，其次结合数据结构所学的知识，找到通路，（关于结合数据结构的知识就看你自己的了，关键是对堆栈的了解）。

关于你说的，先看别人的程序，找到思路后自己才能编程问题。我看你是操之过急了，你得明白，知识的学习，首先就是会模仿，等你对整个课程有了系统的认识，你才会有自己的解题思路。创新是在有基础的前提下进行的。别人的东西，试着理解，毕竟许多东西单凭我们自己是不太可能想出来的，就像kmp算法一样（你应该马上就会学到）。
第一章说过，研究数据间的关系的目的是为了更好的操作数据，迷宫问题，可以说是一类“搜索”问题，更强调的是算法，即在精通堆栈的基础上想出一个利用堆栈对迷宫进行搜索的办法。而堆栈，则是基础，堆栈的操作就那么几个，学完马上就会用。关键是如何运用三种程序设计方法再结合某些数据结构设计出一个算法。一步一步来吧。
对了，给你一个问题考虑考虑，“不用任何辅助变量”编写一个程序，逆置一个字符串试试。只给你一个参数：该参数就是指向字符串的指针。

你的最后问题问的就有点没头绪了，学习的过程并不是你想的那样的，不见得数据结构学完之后就能编写高质量程序，写程序和看程序是相辅相成的，写而不学则怠，学而不写则罔。可以尝试的写写，自己找不到思路可以看看别人是怎么想的，自己多做做总结。

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define M 10
#define N 10
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[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(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=4; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("0=东 1=南 2=西 3=北 4为则走出迷宫\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);
}
printf("成功 !\n");
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; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("请输入迷宫的各行各列:(用空格隔开,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}};//行增量和列增量 方向依次为东西南北
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); //寻找路径
}

这是个经典的数学问题，说的是：在一个随机的迷宫里，小白鼠如何能最快地从起点走到终点。

-# --------### # ## # # ###
----# # #-## # # # #### #### #
## ## #-# ## # # # #---# ## #
## # # # # -# ### ## #### ##
# # ----# # # ## # # # ## ### ##
-# --# ---### -* # ## # # ###
----# # #-## # # -----### #### #
## ## #-# ## # # # #---# ## #
## # # # # -# ### ## #### ##
# # ----# # # ## # # # ## ### ##

按上图，老鼠用“*”来表示，要求从迷宫的左上脚选择一条路径，跑道右下脚的出口。也许用神经网络、用遗传算法之类能找到一个最佳的做法，但我这个程序是基于对迷宫完全无知，而且没有试验的这个前提，所以我只能采用最机械的办法：每条路都试探。具体是这样的：向左看看，能否过去。只要左面不是墙，就走到出一步。若左面不能过去，看下面，再看右面...若三个方向都不能过去，只能回到上一步，重复干...
程序并不长，但它在四年前费了我一个星期的所有时间（包括上课 :-)）。一直在我磁盘里放着，不拿出来分享，怪可惜的。你看看能不能找到更好的办法？望交流。

注释一：你能看见迷宫几乎完全是随机的，但为了保证一定有一条通道，我在起点和终点附近各放了九个可以通行的点。不算作弊吧。
注释二：循环里面的延时对于PENTIUM几乎一点作用都没有。所以运行时你或者选用 STEP，或者把延时提高一点，才能看清小白鼠是如何迈向前途未卜的新一步，又是如何迷途知返，重新审视自己的步伐。
注释三：这个程序的技巧很好，但完全没有注释，风格也不太好，但这正是几年前我的标准的程序，所以现在我也不改，直接拿出来，仅供一娱。
注释四：程序用TC才能编译。VC，标准C中没有“gotoxy”等函数。当然，这只影响界面显示，不影响我们老鼠行走的算法。

您还可以直接下载已编译好的程序maze.exe
--------------------------------------------------------------------------------
源程序如下：

#include < stdlib.h>
#include < time.h>
#include < stdio.h>
#include < conio.h>
main()
{int x,y,a[72][22];
char o;
int c,d,four,k=0,i,end,step;
randomize();
/* printf("Do you want it run or step?(0/1)");
scanf("%d",&step);*/
clrscr();
for(x=0;x < 72;x++){
for (y=0;y < 22;y++){
if ((y==0)||(x==0)||(x==71)||(y==21)) {
a[x][y]=11;
continue;}
if (random(3)==0) {
a[x][y]=11;
gotoxy(x,y);
printf("#");
}
else
a[x][y]=1;
}
}

for(y=1;y < 10;y++)
{ a[1][y]=1;
gotoxy(1,y);
printf(" ");
a[70][21-y]=1;
gotoxy(70,21-y);
printf(" ");
}
x=1;
y=1;
end=0;
gotoxy(1, 23);
printf("Step?(1/0) ");scanf("%d", &step);
//Above is to prepare the Maze. Now, our little mouse is comming.

while((x < 70)||(y < 20)) {

c=x;d=y;four=0;
do{
k++;
if ((a[x+1][y]==1)||((a[x+1][y]%7==0)&&(a[x][y]%2!=0)&&(four==1)))
{
a[x][y]=a[x][y]*2;
x=x+1;
break;
}
if ((a[x][y+1]==1)||((a[x][y+1]%5==0)&&(a[x][y]%3!=0)&&(four==1)))
{
a[x][y]=a[x][y]*3;
y=y+1;
break;
}
if ((a[x][y-1]==1)||((a[x][y-1]%3==0)&&(a[x][y]%5!=0)&&(four==1)))
{
a[x][y]=a[x][y]*5;
y=y-1;
break;}
if ((a[x-1][y]==1)||((a[x-1][y]%2==0)&&(a[x][y]%7!=0)&&(four==1)))
{a[x][y]=a[x][y]*7;
x=x-1;
break;
}
four++;
if (four == 2){
gotoxy(25, 23); printf("Cannot go out!");
end=1;
break;}

if (k>3000) {
gotoxy(30, 23); printf("Too long!");
end=1;
break;}
}while(1);
if (end==1) break;
/* gotoxy(x,y);printf("*");*/
gotoxy(c,d);printf("-");
gotoxy(16, 23); printf("step:%d ", k);
gotoxy(x,y); printf("*");
if (step==1) getch();
}/* no end point*/
if (end==1) printf("Error.");
else printf("ok!");
getch();
}/*end main()*/

即要知道在该点是否已经向右走过？是否向左走过？用了4天脑袋里跳出“素数”这样一个悠久的名词，于是一切就水到渠成了！
在Do-While中的第一个if的意思是：如果右边的方格是如果从未走过的空地（值为1），走过去。但是，如果上下左右都没有值为1的空地，就必须考虑退路了。这时four==1，查看一下我是否已经走过这个地方 (a[x][y]%2!=0)？我是否从那里过来的(a[x+1][y]%7==0)？也就是说当four==4时我只走回头路。

你的程序会采取这种策略吗？

迷宫么，自然该有入口和出口，结合数据结构，每一个小方格是一个结构，小方格有入口和出口，随即生成N*N个小方格，然后从（0,0）开始遍历整个数组，进入每一个小方格，由入口开始对其他的三个方向搜索是否有出口，有，则从出口（即下一个小方格的入口）进入下一个方格，并要保存此位置用于后面出现死路返回，如此类推
讲的不是很清楚，大概这样思考吧~~

void
creatstack(StackNode
*s)
/*创建链式栈*/
{
s=NULL;
}
这里错了，如果你用的是C++开发工具，就改为void
creatstack(StackNode
*&s) ，如果用的是TC2.0的话，就要用指向指针的指针，或者返回类型是StackNode
*也可以，例如
StackNode
*creatstack（）
｛

StackNode
*s=(StackNode
*)malloc(sizeof(StackNode
));

s->next=NULL;

return
s;
}

---

数据结构C语言版迷宫问题视频