Stack.h：定义了栈的基础操作和数据类型

#include <iostream>

const int Stack_Size=9;
const int Stack_Incricement=2;

enum {OK=0,WRONG=-1};
typedef int Status;

typedef struct
{
 int x;
 int y;
}Pos;

typedef struct
{
 Pos CurPos;
 int ord;
 int di;
}Elem;

typedef struct
{
 Elem *base;
 Elem *top;
 int StackSize;
}Stack;

 

 

Status InitStack(Stack &S)
{
 if((S.base=new Elem[Stack_Size])==NULL)
  return WRONG;
 S.top=S.base;
 S.StackSize=Stack_Size;
 return OK;
}

void DstoryStack(Stack &S)
{
 delete S.base;
 S.top=S.base=NULL;
 S.StackSize=0;
}

void ClearStack(Stack &S)
{
 S.top=S.base;
}

bool IsEmpty(Stack &S)
{
 return S.base==S.top;
}

int GetLen(Stack &S)
{
 return S.top-S.base;
}

Status GetTop(Stack S,Elem &e)
{
 if(IsEmpty(S)==true)
  return WRONG;
 e=*(S.top-1);
 return OK;
}

Status Push(Stack &S,Elem e)
{
 if(S.StackSize<=S.top-S.base)
 {
  Elem *newbase=new Elem[S.StackSize+Stack_Incricement];
  if(newbase==NULL)
   return WRONG;
  memcpy(newbase,S.base,S.StackSize*sizeof(Elem));
  //delete S.base;
  S.base=newbase;
  S.top=S.base+S.StackSize;
  S.StackSize+=Stack_Incricement;
 }
 *(S.top)++=e;
 return OK;
}

Status Pop(Stack &S,Elem &e)
{
 if(IsEmpty(S)==true)
  return WRONG;
 e=*--S.top;
 return OK;
}

void StackTraverse(Stack S,void(*visit)(Elem e))
{
 Elem *p=S.base;
 while(p<S.top)
 {
  visit(*p);
  p++;
 }
}

main.cpp：主程序

#include "Stack.h"

int map[7][7]={{0,0,0,0,0,0,0},{0,1,0,1,1,1,0},{0,1,1,0,0,1,0},{0,1,0,1,1,1,0},{0,1,1,1,0,1,0},{0,1,0,0,1,1,0},{0,0,0,0,0,0,0}};
Pos d[4]={{1,0},{-1,0},{0,1},{0,-1}};

Stack S;
int curstep=1;
bool Pass(Pos p)
{
 if(map[p.x][p.y]==1)
  return true;
 else
  return false;
}

void PrintFoot(Pos p)
{
 map[p.x][p.y]=curstep;
}

void GetNext(Pos &p,int di)
{
 p.x+=d[di].x;
 p.y+=d[di].y;
}

void Mark(Pos p)
{
 map[p.x][p.y]=-1;
}

bool Maze(Pos Start,Pos End)
{
 InitStack(S);
 Elem e;
 Pos curpos=Start;
 do
 {
  if(Pass(curpos))
  {
   PrintFoot(curpos);
   e.CurPos=curpos;
   e.di=0;
   e.ord=curstep;
   Push(S,e);
   curstep++;
   if(curpos.x==End.x&&curpos.y==End.y)
    return true;
   GetNext(curpos,e.di);
  }
  else
  {
   if(!IsEmpty(S))
   {
    Pop(S,e);
    curstep--;
    while(e.di==3&&!IsEmpty(S))
    {
     Mark(e.CurPos);
     curstep--;
     Pop(S,e);
    }
    if(e.di<3)
    {
     e.di++;
     Push(S,e);
     curstep++;
     curpos=e.CurPos;
     GetNext(curpos,e.di);
    }
   }
  }
 }while(!IsEmpty(S));
 return false;
}

int main()
{
 Pos Start={1,1},End={5,5};
 if(Maze(Start,End)==true)
  std::cout<<"OK";
 else
  std::cout<<"WRONG";
 std::cout<<std::endl;
 int i,j;
 for(i=0;i<7;i++)
 {
  for(j=0;j<7;j++)
  {
   std::cout.width(2);
   std::cout<<map[i][j]<<" ";
  }
  std::cout<<std::endl;
 }
 return 0;
}