[普通]数据结构-迷宫问题

一、实验的目的和要求

1、了解栈的特征，以及顺序表在迷宫问题中的应用。

2、掌握顺序栈在迷宫问题如何实现，熟练掌握顺序栈的基本操作。

二、实验的主要内容

问题描述:在迷宫中求从入口到出口的一条简单路径。迷宫可用下图中所示的方块来表示，每个方块或者是通道（用空白方块表示）或者是墙（用带阴影的方块表示）。

三、解题思路

本实验的实验题目是在迷宫中求从入口到出口的一条简单路径。迷宫用一个二维字符数组maze来表示，用x表示纵坐标，y表示横坐标。

（1）定义探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，用Switch语句根据当前的位置坐标来判断下一步要探索的方向求出下一步要走的位置坐标。

（2） 探索迷宫的四个方向的坐标表示：RIGHT（x,y+1）, DOWN(x+1,y), LEFT(x,y-1), UP(x-1,y)。

（3）对每个方向探索时，用0表示可通过，用1表示不能通过是障碍

（4） 对探索过的位置加以标记，若可以通过则用’.’ 表示，若是死胡同则用‘#’表示。

（5）把每一个可以通过的位置坐标放入栈中，最后打印输出路径。

（6）根据二维字符数组和加标记的位置坐标，输出迷宫的图形。

四、源程序清单

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 20

#define ERROR -1

#define OK   1

#define FALSE 0

#define TRUE  1

typedef enum{RIGHT,DOWN,LEFT,UP}Direction;

typedef enum{YES,NO}MarkTag;

typedef struct position   //迷宫中位置的坐标

{  int x;

   int y;

}Position;

typedef struct

{  int order;          //当前位置在路径中的序号

  Position seat;       //当前位置在迷宫中的坐标

  Direction di;       //从当前位置走到下一位置的方向

}SElemType;              //栈元素的类型

typedef struct

{ 

SElemType *elem;

  int top;

}Stack;

char maze[MAXSIZE][MAXSIZE]={

 {'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'}

 };    //用二维字符数组表示迷宫

int InitStack(Stack *S)             //创建一个空栈

{

S->elem=(SElemType*)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType));

 if(!S->elem)  return ERROR;

 S->top=0;    return OK;

}  

int Push(Stack *S,SElemType e)     //元素e入栈

{   if(S->top>=MAXSIZE*MAXSIZE)   return ERROR;

 S->elem[S->top++]=e;　　return OK;

} 

int Pop(Stack *S,SElemType *e) //栈顶元素出栈，由e带回栈顶元素

{   if(S->top<=0)     return ERROR;

  *e=S->elem[--S->top];   return OK;

}

 int Empty(Stack S)    //判断栈是否为空

{  if(S.top==0)    return TRUE;

   else   return FALSE;

} 

int createMaze(Position *startpos,Position *endpos)

{ Position start,end;

 printf("请输入迷宫入口的位置：");

 scanf("%d%d",&start.x,&start.y);

printf("请输入迷宫出口的位置：");

 scanf("%d%d",&end.x,&end.y);

     *startpos=start; *endpos=end;

 return OK;

}  //createMaze

int canPass(Position curpos)

{    if(maze[curpos.x][curpos.y]=='0')   return TRUE;

     return FALSE;

}   //canPass

void markPos(Position curpos,MarkTag tag)     //为已经探索过的位置加标记

{  switch(tag)

 {  case YES: maze[curpos.x][curpos.y]='.'; break;   //路径标记

  case NO:  maze[curpos.x][curpos.y]='#'; break;   //死胡同标记

 }

}  

//根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标

Position nextPos(Position curpos,Direction dir)

{    Position nextpos;

switch(dir)

  {  case RIGHT:nextpos.x=curpos.x ;nextpos.y =curpos.y +1; break;

     case DOWN :nextpos.x=curpos.x+1 ;nextpos.y =curpos.y; break;

     case LEFT :nextpos.x=curpos.x ;nextpos.y =curpos.y -1; break;

     case UP :nextpos.x=curpos.x-1 ;nextpos.y =curpos.y;  break;

  }

  return nextpos;

}

Direction nextDir(Direction dir)

{  switch(dir)

  {   case RIGHT: return DOWN;

      case DOWN : return LEFT;

      case LEFT: return UP;

  }

}

int Solve(Stack *S,Position start,Position end)

{//若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中，并返回TRUE,若迷宫中不存在从入口start到出口end的通道，并返回FALSE

 Position curpos;

 SElemType e;

 int curstep=1;   //共用的步数

if(InitStack(S)==ERROR)  return FALSE;

 curpos=start;

do{

 if(canPass(curpos)){      //当前位置可以通过

     markPos(curpos,YES);   //留下足迹

     e.order=curstep;e.seat=curpos;e.di=RIGHT;

     Push(S,e);             //当前位置加入路径

     if(curpos.x==end.x&&curpos.y==end.y)   //当前位置是出口

      return TRUE;

     curpos=nextPos(curpos,RIGHT);

     curstep++;

  }

  else{              //当前位置不能通过

if(!Empty(*S)){

 if(Pop(S,&e)==ERROR)   return FALSE;

     while(e.di==UP&&!Empty(*S)){

     //四个方向都试探过，没有找到通路也不能继续探索，则回溯

      curpos=e.seat;markPos(curpos,NO);

      if(Pop(S,&e)==ERROR)  return FALSE;

}

    if(e.di!=UP){   //四个方向还没有试探完

      e.di=nextDir(e.di);

      Push(S,e);  //换下一个方向探索

      curpos=nextPos(e.seat,e.di);

}

}

  }

 }while(!Empty(*S));

 return FALSE;

}

void main()

{  Position startPos,endPos;

   Stack path;

 int i,j;

SElemType e;

if(createMaze(&startPos,&endPos)==ERROR) return ;

 Solve(&path,startPos,endPos);

while(!Empty(path)){    //输出出口到入口的路径

  Pop(&path,&e);

  printf("(%d,%d)",e.seat.x,e.seat.y);

 }

//输出迷宫的图形

 printf("\n");

    for(i=0;i<8;i++)

 {for(j=0;j<11;j++)

   printf("%c ",maze[i][j]);

  printf("\n");

 }

}

五、程序调试及输出结果

请输入迷宫入口的位置：1 1

请输入迷宫出口的位置：6 9

（6，9）（6，8）（6，7）（6，6）（6，5）（5，5）（4，5）（3，5）（2，5）（2，4）（2，3）（2，2）（2，1）（1，1）

Press any key to continue

六、调试小结

在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。在迷宫中用‘1’表示墙，用‘0’表示通道；探索过的路径用‘.’表示可通过，用‘#’表示死胡同。定义了一个二维字符数组来表示迷宫，将迷宫的入口位置的坐标，在路径中的序号及该位置走到下一个位置的方向放入栈中。在设计程序的过程中由于没有注意到行列都是从0开始的，导致输出时少了一行和一列，后来行数和列数都加1后就正确了。虽然这个程序运行后可以得到正确的实验结果，但是有时还会显示存在着一个警告（warning C4715: 'nextDir' : not all control paths return a value）就是说不是所有的控制路径都能返回一个真值。我上网查了许多的资料还是不能解决这个问题，是做这个程序设计留下的一个遗憾。通过这次的程序设计我学习到了很多的东西，明白了做一个大的程序题要用到以前学到过的很多知识，就说我的程序用的是栈的知识，还用了Switch语句和for语句这两个循环语句，用了二维字符数组的知识。迷宫问题还有许多其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。

七、主要参考文献

1）王国钧、唐国民、苏哓萍等，《数据结构——C语言描述》，科学出版社

2）严蔚敏、吴伟民编著，C语言版《数据结构》，清华大学出版社

3）谭浩强编著，《Ｃ程序设计（第二版）》，清华大学出版社