迷宫问题 数据结构
这程序段在VC++6.0上运行有错，请大神看一下，怎么改#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//*************参数定义****************
int m,n;
int **maze = NULL; //表示迷宫
struct Element
{ //这里就是定义节点
int i;
int j;
int di;
};
typedef struct LinkStack
{ //这里就是定义链栈...
struct Element element;
struct LinkStack * next;
struct LinkStack * prior;
}LinkStack;
LinkStack *top = NULL; //栈顶指针,因为是链栈，所以栈顶指针要是一个指针变量
LinkStack *head = NULL; //链栈的头指针
int count=0; //路径计数
int mgpath(int xi,int yi,int xe,int ye);
//**************迷宫输出函数****************
void printMaze(int ** maze) //输出迷宫
{
int i,j;
printf("您的迷宫图如下所示:\n");
for(i=0; i<m+2; i++)
{
for(j=0; j<n+2; j++)
{
printf("%4d",maze[i][j]);
}
printf("\n");
}
printf("\n******************************\n");
}
void addWall(int ** maze) //给迷宫加墙
{
int i,j;
for(i=0; i<m+2; i++)
{
for(j=0; j<n+2; j++) {
if(i==0){
maze[i][j] = 1;
}
if(i>0 && i<(m+2-1)) {
maze[i][0]=1;
maze[i][n+2-1]=1;
break;
}
if(i==m+2-1) {
maze[i][j]=1;
}
}
}
}
//********************迷宫初始化函数***********
int ** initMaze()
{ //对迷宫进行初始化的函数
int i,j;
int flag = 0;
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
maze = (int **)malloc(sizeof(int *) * (m+2)); //开辟迷宫的存储空间
printf("\n*****************************************\n");
for(i=0; i<n+2; i++)
{
*(maze+i) = (int *)malloc(sizeof(int)*(n+2));
}
addWall(maze); //给迷宫加墙
printf("\n请输入迷宫的各行各列(注意:最后一个数需要是0):\n用空格隔开,0代表路,1代表墙\n\n"); //保证出口是路，所以最后一个数要是0
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++)
{
scanf("%d",&maze[i][j]);
}
}
printf("\n***************************************\n");
printMaze(maze); //输出迷宫图
return maze;
}
//****************递归寻找所有通路函数************
void mazePath()
{
if(top == head && head != NULL) //终止递归的条件
{
return;
}
int k = 0;
int find = 0;
int i = 0,j=0;
int di = -1;
if(top != NULL)di=top->element.di; //di一开始就保存当前栈顶指针所指的节点的方向
LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack)); //每一次递归都首先开辟节点(因为要查找元素，所以要先开辟节点）
node->element.di = di;
if(top == NULL)
{
head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针
head->element.i = 1;
head->element.j = 0;
head->element.di = 1;
head->prior = NULL;
top = head;
node->element.i = 1;
node->element.j = 1;
node->element.di = -1;
}
top->next = node;
node->next = NULL;
node->prior = top;
top = node; //新开辟节点进栈
di = top->element.di;//取得当前栈顶指针所指的元素的方向
while(di<4 && find == 0)
{
di++;
switch(di)
{
case 0: i = top->prior->element.i - 1;j = top->prior->element.j;break;
case 1: i = top->prior->element.i;j = top->prior->element.j + 1;break;
case 2: i = top->prior->element.i + 1;j = top->prior->element.j;break;
case 3: i = top->prior->element.i;j = top->prior->element.j - 1;break;
}
if(maze[i][j] == 0)find = 1;
}
if(i == m && j == n)
{
top->element.i = m;
top->element.j = n;
top->prior->element.di = di;
printf("%4d:",++count);
LinkStack * n = head->next;
while(n != NULL)
{
printf("(%d,%d,%d ) ",n->element.i,n->element.j,n->element.di);//找到出口，输出路径
printf(" -> ");
if((k + 1)%5 == 0)
{
printf("\n\t");
}
k++;
n = n->next;
}
printf("出口");
printf("\n");
maze[top->element.i][top->element.j] = 0;
top = top->prior; //退栈
free(node);
mazePath();
}
else
{
if(find == 1)
{
top->prior->element.di = di; //退栈时，当找到下一个可走的节点后必须对当前节点的方向进行了更新
top->element.i = i;
top->element.j = j;
top->element.di = -1;
maze[i][j] = -1; //避免重复走到该点
mazePath();
}
else
{
maze[top->prior->element.i][top->prior->element.j] = 0; //让它成为下条路径的可走路径
top = top->prior->prior; //退栈
free(node);
mazePath();
}
}
}
//*******************穷举求解通路函数*********************
int mgpath(int xi,int yi,int xe,int ye)
{ printf("非递归通路：\n");
int i,j;
int find;
int di;
LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack));
head = (LinkStack *) malloc(sizeof(LinkStack)); //链表的头指针
head->element.i = 1;
head->element.j = 0;
head->element.di = 1;
head->prior = NULL;
top = head;
node->element.i = xi; //入口节点进栈
node->element.j = yi;
node->element.di = -1;
maze[1][1]=1; //进栈后标记为不可走节点
top->next = node;
head->next=node;
node->next = NULL;
node->prior = top;
di= node->element.di;
top=node;
LinkStack * n = head->next;
while(top->prior!= NULL)
{
find=0;//find的初始化
di=top->element.di;
while(di<4&&find==0) //寻找下一个可走节点
{
di++;
switch(di)
{
case 0:i=top->element.i-1;j=top->element.j;break;
case 1:i=top->element.i;j=top->element.j+1;break;
case 2:i=top->element.i+1;j=top->element.j;break;
case 3:i=top->element.i,j=top->element.j-1;break;
if(maze[i][j]==0){find=1;top->element.di=di;printf("find找到的点%d,%d,%d",i,j);}
//find为1表示为找到下一个可走节点
}
if(find==1)
{
if(i==xe&&j==ye&&maze[i][j]==0) //如果找到的节点是出口
{
LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack)); //出口节点入栈
top->element.di=di;
node1->element.i=i;
node1->element.j=j;
node1->element.di=-1;
top->next=node1;
node1->next=NULL;
node1->prior=top;
top=node1;
maze[i][j]=1;
printf(" ");
while(n!=NULL) //输出栈
{printf("(%d,%d,%d)",n->element.i,n->element.j,n->element.di);
printf(" -> ");
n=n->next;
}
printf("出口");
printf("\n");
return(0);
}
else //如果找到的点不是出口
{
LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack));
//可走节点入栈
top->element.di=di;
node1->element.i=i;
node1->element.j=j;
node1->element.di=-1;
top->next=node1;
node1->next=NULL;
node1->prior=top;
top=node1;
maze[i][j]=1;
printf("找到的节点有%d,%d,%d",node1->element.i,node1->element.j,node1->element.di);
}
}
else //没有下一个可走节点就将该节点退栈
{
maze[top->element.i][top->element.j]=0;
top = top->prior; //退栈
free(top->next);
}
}
return(0);
}
//******************主函数**************************
void main()
{
int i;
initMaze();
mazePath();
if(count==0)
{printf("************");
printf("\n该迷宫没有通路\n");
return;
}
printf("\n**************************\n");
mgpath(1,1,m,n);
if(head != NULL) //释放内存
{
free(head);
}
return;
}
