数据结构迷宫代码

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以 三元组（i，j，d）的形式输出，其中（i，j）指示迷宫中的一个位置（行号和列号），d 表示走到下一 位置的方向（对于迷宫中任一位置，均有下、右、上、左四个方向来走出下一个位置，这四个方向可 分别编号为 1，2，3，4）。例如，对于下面测试数据给出的迷宫，输出的一条通路为： （1,1,1)，(2,1,1)， （3,1,1），(4,1,1） ，（5,l,2)，（5,2,2)， （5,3,1)，…。

#include 
#include 
#define overflow -1 
#define ok 1 
#define error 0  
#define STACK_INIT_SIZE  100 
#define STACKINCREMENT 10 
typedef int  Status; 
typedef struct  
  {  int x;  
     int y;  
  }PosType;//位置类型   
typedef struct 
  {  int rowcol;  
     int a[50][50]; 
  }MazeType;//迷宫类型     
typedef struct 
  {  
    int ord;//通道块在路径上的序号  
    PosType seat;//通道块在迷宫中的“坐标位置“  
    int di;//从此通道块走向下一个通道块的方向   
  }SElemType;//栈的元素类型   
typedef struct
  {  
    SElemType *base; 
    SElemType  *top;  
    int Stacksize;   
  }SqStack;//栈结构    
Status InitStack（SqStack &S）//初始化栈 
 {  
    S.base=（SElemType *）malloc（STACK_INIT_SIZE*sizeof（SElemType））;  
    if（!S.base）  exit （overflow）;  
    S.top=S.base;
    S.Stacksize=STACK_INIT_SIZE;  
	return ok; 
 }   
Status Push（SqStack &SSElemType e）//入栈 
 {
   if（S.top-S.base>=S.Stacksize）  
    { S.base=（SElemType*）realloc（S.base（S.Stacksize+STACKINCREMENT）*sizeof（SElemType））;      
       if（!S.base）  exit （overflow）;   
       S.top=S.base+S.Stacksize;   
       S.Stacksize+=STACKINCREMENT;  
    }  
      *S.top++=e;  
      return ok; 
 }   
Status Pop（SqStack &SSElemType &e）//出栈 
{  if（S.top==S.base） return error;  
   e=*--S.top;  return ok;
}   
bool StackEmpty（SqStack S）//判断栈是否为空 
{  if（S.top==S.base）  
   return ok;  
   else return error; 
}   
Status InitMaze（MazeType &maze）//初始化迷宫 
{      int ij;      
    for（ j=0;j        maze.a[0][j]=1;  
    for（ i=1;i    {   maze.a[i][0]=1;   
        maze.a[i][maze.col+1]=1;         
    for（int j=1;j        scanf（“%d“&maze.a[i][j]）; 
    }      
    for（j=0;j    maze.a[maze.row+1][j]=1;           
    return ok;     
}//为了避免检查边界，把迷宫的外围都设成障碍，迷宫的内核是row行，col列的数组     
bool Pass（MazeType mazePosType curpos）//判断是否可以通过 
  {  return maze.a[curpos.x][curpos.y]==0;  
  }  
Status FootPrint（MazeType &mazePosType curpos）//留下足迹 
  {    
    maze.a[curpos.x][curpos.y]=2;   
    return ok; 
  }   
SElemType CreatElem（int stepPosType posint di）//创造一个SElemType型的数据 
  {  SElemType e;  
     e.ord=step;  
     e.seat=pos;  
     e.di=di;  
     return e; 
  }   
bool IsEnd（PosType pos1PosType pos2）//判断是否结束