85问答库 > 数据结构迷宫问题，程序有错，请问下面的程序应该怎么修改，急！！！

数据结构迷宫问题，程序有错，请问下面的程序应该怎么修改，急！！！

2025-02-23 01:31:56

推荐回答（1个）

回答1：

#include 
#include 
#include 

typedef struct pos   /*描述迷宫当前位置和方向*/
{
 int x;
 int y;
 int way;    /*0:无效,1:左,2:下,3:右,4:上*/
}P;

typedef struct LinkNode  /*链表结构,用于栈的元素类型*/
{
 P pos;
 struct LinkNode *next;
}LinkNode;

typedef struct stack  /*链式栈,用于存储迷宫路径信息*/
{
 LinkNode *head;   /*头指针*/
}Stack;

int row=0;     /*迷宫的行数*/
int line=0;     /*迷宫的列数*/

void InitStack(Stack *s) /*栈置空*/
{
 s->head=NULL;
}

void Push(Stack *s,P p)  /*数据入栈*/
{
 LinkNode *LN=(LinkNode *)malloc(sizeof(LinkNode));
 LN->pos=p;
 LN->next=s->head;
 s->head=LN;
}
  
P Pop(Stack *s)    /*栈顶元素出栈*/
{
 P pos;
 LinkNode *LN;
 LN=s->head;
 s->head=s->head->next;
 pos=LN->pos;
 delete LN;
 return pos;
}

P GetPop(Stack s)   /*读取栈顶元素*/
{
 return s.head->pos;
}

int Empty(Stack s)   /*判空*/
{
 if(s.head==NULL)
  return 1;
 else 
  return 0;
}

int **InitMaze()   /*返回迷宫的二维指针*/
{
 int **maze=NULL;
 int i;
 int j;
 printf("请输入迷宫的行跟列(x,y):"); 
 scanf("%d,%d",&row,&line);   /*输入迷宫的行和列*/
 maze=(int **)malloc((row+2)*sizeof(int *)); 
 for(i=0;i {
  maze[i]=(int *)malloc(sizeof(int)*(line+2));  
 }
 printf("请输入迷宫\n");    /*输入迷宫,1代表路障,0代表通行*/
 for(i=1;i<=row;i++)
  for(j=1;j<=line;j++)
   scanf("%d",&maze[i][j]);
 for(i=0;i  maze[0][i]=1;
 for(i=0;i  maze[row+1][i]=1;
 for(i=0;i  maze[i][0]=1;
 for(i=0;i  maze[i][line+1]=1;
 for(i=0;i {
  for(j=0;j   printf("%3d",maze[i][j]);
  printf("\n");
 }
 return maze;
}

void PrintWay(Stack p)     /*输出路径*/
{
 P pos;
 Stack t;       /*临时栈,用于存储从入口到出口的路径*/
 LinkNode *temp;
 int a,b;
 InitStack(&t);
 temp=(LinkNode *)malloc(sizeof(LinkNode));
 temp->pos=Pop(&p);     /*取栈顶元素,即出口*/
 Push(&t,temp->pos);     /*入栈*/
 free(temp);
 while(!Empty(p))
 {
  temp=(LinkNode *)malloc(sizeof(LinkNode));
  temp->pos=Pop(&p);    /*获取下一个元素*/
  a=GetPop(t).x-temp->pos.x;  /*左:a=0,b=1;   下:a=1,b=0*/
  b=GetPop(t).y-temp->pos.y;  /*右:a=0,b=-1   上:a=-1,b=0;*/
  if(b==1)
   temp->pos.way=1;
  else if(a==1)
   temp->pos.way=2;
  else if(b==-1)
   temp->pos.way=3;
  else if(a==-1)
   temp->pos.way=4;
  Push(&t,temp->pos);    /*新位置入栈*/
  free(temp);
 }
 printf("迷宫的路径为:\n");
 printf("前两个数字表示位置,最后一个数字表示方向\n");
 printf("1表示向左,2表示向下,3表示向右,4表示向上,0表示无方向\n");
 while(!Empty(t))     /*输出路径*/
 {
  pos=Pop(&t);
  printf("%3d,%3d,%3d\n",pos.x,pos.y,pos.way);
 }
}

int FindMaze(int **maze,int r,int l) /*寻找路径,找到返回1,没找到返回0*/
{
 Stack p,q;       /*栈p,q分别表示探索迷宫的路径和过程*/
 P temp1,temp2;
 int a,b;
 InitStack(&p);
 InitStack(&q);
 temp1.x=1;
 temp1.y=1;       //
 maze[1][1]=-1;      /*标记已经走过*/
 Push(&p,temp1);
 Push(&q,temp1);
 while(!Empty(q))
 {
  temp2=GetPop(q);
  if(!(GetPop(p).x==GetPop(q).x
    &&GetPop(p).y==GetPop(q).y))  
   Push(&p,temp2);    /*若有新元素入栈,就把q的栈顶元素存入p中*/ 
  a=temp2.x;
  b=temp2.y+1;     /*当前位置左方向相邻的方块*/
  if(maze[a][b]==0)
  {
   temp1.x=a;
   temp1.y=b;
   maze[a][b]=-1;    /*标记已走过*/
   Push(&q,temp1);
  }
  if(a==r&&b==l)     /*到达出口*/
  { 
   temp1.way=0;
   Push(&p,temp1);
   PrintWay(p);
   return 1;
  }
  a=temp2.x+1;
  b=temp2.y;     /*当前位置下方向相邻的方块*/
  if(maze[a][b]==0)
  {
   temp1.x=a;
   temp1.y=b;
   maze[a][b]=-1;    /*标记已走过*/
   Push(&q,temp1);
  }
  if(a==r&&b==l)     /*到达出口*/
  {
   temp1.way=0;
   Push(&p,temp1);
   PrintWay(p);
   return 1;
  }
  a=temp2.x;
  b=temp2.y-1;     /*当前位置右方向相邻的方块*/
  if(maze[a][b]==0)
  {
   temp1.x=a;
   temp1.y=b;
   maze[a][b]=-1;    /*标记已走过*/
   Push(&q,temp1);
  }
  if(a==r&&b==l)     /*到达出口*/
  {
   temp1.way=0;
   Push(&p,temp1);
   PrintWay(p);
   return 1;
  }
  a=temp2.x-1;
  b=temp2.y;     /*当前位置上方向相邻的方块*/
  if(maze[a][b]==0)
  {
   temp1.x=a;
   temp1.y=b;
   maze[a][b]=-1;    /*标记已走过*/
   Push(&q,temp1);
  }
  if(a==r&&b==l)     /*到达出口*/
  {
   temp1.way=0;
   Push(&p,temp1);
   PrintWay(p);
   return 1;
  }
  if(GetPop(p).x==GetPop(q).x
     &&GetPop(p).y==GetPop(q).y)   /*若四个方向都走不通,则数据出栈,退回一格*/
  { 
   Pop(&p);
   Pop(&q);
  }
 }
 return 0;       /*探索迷宫失败*/
}

void main()
{
 int **maze=InitMaze();    /*初始化迷宫*/
 if(FindMaze(maze,row,line))   /*探索路径*/
  printf("路径探索成功!\n");
 else
  printf("路径探索失败!\n");
 getch();
}

最新问答

有源低音炮怎么配音箱

穿越小说。男主是王爷，女主魂穿到古代。结局是男女主相爱。一夜洞

WOW夜色镇旅店二楼左手边第一间房靠墻的那个NPC叫什么名字

华为和荣耀是一个代工厂生产的吗？

3平方-1=8=8x1,5平方-3平方=16=8x2,7平方-5平方=24=8x3......你发现了什么规律？根据规律，计算

2020年下半年全国计算机等级考试报名时间

奔驰glb天窗能打开吗

请问一下医生写的什么字？我看不懂，来求求大神帮帮忙和我说一下

梦见自己喜欢的男孩说喜欢我，这代表什么

没有出现酸啊，都是盐。和它解释都有什么关系？