mazelinkstack.cpp

数据结构 迷宫问题 链栈实现 代码中包含多种的基本操作和迷宫算法

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2


#define STACK_INIT_SIZE 10
#define STACKINCREMENT 10

#define ROW 9
#define COL 8

typedef int Status;

typedef struct
{
	int r,c;     //迷宫中r行c列的位置

}PosType;

typedef struct
{
	char arr[ROW][COL];

}MazeType;

typedef struct
{
	int step;     //当前位置在路径上的"序号"
	PosType seat; //当前的坐标位置
	int di;       //往下一坐标位置的方向

}SElemType;       //栈元素类型

typedef struct NodeType
{
	SElemType data;
	struct NodeType *next;

}NodeType,*LinkType; //节点类型

typedef struct
{
	LinkType top;
	int size;

}LinkStack;            //栈类型


LinkStack *S; //全局变量，指向栈类型的指针


void main()
{

	//函数声明
    //初始化迷宫
	void InitMaze(MazeType &maze);
	void PrintMaze(MazeType maze);
	//栈操作
    void InitStack(LinkStack *p);
    Status StackEmpty(LinkStack *p);
	void Push(LinkStack *p,SElemType e);  
    Status Pop(LinkStack *p,SElemType &e);
	//寻找路径操作
	Status Pass(MazeType MyMaze, PosType CurPos);
	void FootPrint(MazeType &MyMaze, PosType CurPos);
	void MarkPrint(MazeType &MyMaze, PosType CurPos);
	PosType NextPos(PosType CurPos, int Dir);
	Status MazePath(MazeType &maze, PosType start, PosType end);
	//初始化变量
	MazeType Initmaze;
	PosType start_coordinates,end_coordinates; //要和二维数组下标匹配
	start_coordinates.r=0;     //起点坐标
	start_coordinates.c=0;   
	end_coordinates.r=8;       //终点坐标
	end_coordinates.c=7;
	//调用函数
	InitMaze(Initmaze);
	fflush(stdin);
	PrintMaze(Initmaze);
	MazePath(Initmaze,start_coordinates,end_coordinates);
	PrintMaze(Initmaze);


}

void InitMaze(MazeType &maze)
{
	//按照用户输入的row行和col列的二维数组(元素值为0或1)
	int i,j;
	printf("Please input the Intialize maze:\n");
	for(i=0;i<ROW;i++)
	{
		for(j=0;j<=COL;j++)  //注意等号
		{
			scanf("%c",&(maze.arr[i][j]));

		}

	}

}

void PrintMaze(MazeType maze)
{
	int i,j;
	printf("The maze is as fllowing:\n");
	for(i=0;i<ROW;i++)
	{
		for(j=0;j<COL;j++)
		{
			printf("%c ",maze.arr[i][j]);
		}
		printf("\n");
	}
	

}

void InitStack(LinkStack *&p)//LinkStack *表示指针类型,&的含义：引用调用，传变量的地址，p的值会改变.
{
	p=(LinkStack *)malloc(sizeof(LinkStack)); //**********分配一个LinkStack的空间让p指向*********(重点啊~~)
	p->top=NULL;
	p->size=0;
}

Status StackEmpty(LinkStack *p)
{
	if(p->top==NULL)
		return TRUE;
	else
		return FALSE;
         
}

void Push(LinkStack *p,SElemType e)
{
    LinkType q;        
	q=(NodeType*)malloc(sizeof(NodeType));
    q->data=e;
    q->next=p->top;
    p->top=q;
	p->size++;

}


Status Pop(LinkStack *p,SElemType &e)
{
	LinkType q=p->top;
	if(StackEmpty(p))
	{
		return FALSE;

	}
	else 
	{
		p->top=q->next;
		e=q->data;
		free(q);
		p->size--;
		return TRUE;

	}

	return OK;
}


Status Pass(MazeType MyMaze,PosType CurPos) {
  if (MyMaze.arr[CurPos.r][CurPos.c]=='0')
    return 1;     // 如果当前位置是可以通过，返回1
  else return 0;  // 其它情况返回0
}

void FootPrint(MazeType &MyMaze,PosType CurPos) 
{
  MyMaze.arr[CurPos.r][CurPos.c]='*';   //留下走过的标记
}


void MarkPrint(MazeType &MyMaze,PosType CurPos)
{
  MyMaze.arr[CurPos.r][CurPos.c]='!';  //留下不能通过的标记
}


PosType NextPos(PosType CurPos, int Dir)  //Dir是下一个方向(1.表示东,2.表示南,3.表示西,4.表示北)
{
  PosType ReturnPos; 
  switch (Dir)                  //逆时针查找路径
  {
    case 1:
        ReturnPos.r=CurPos.r;
        ReturnPos.c=CurPos.c+1; //东方向
        break;
    case 2:
        ReturnPos.r=CurPos.r+1; //南方向
        ReturnPos.c=CurPos.c;
        break;
    case 3:
        ReturnPos.r=CurPos.r;
        ReturnPos.c=CurPos.c-1; //西方向
        break;
    case 4:
        ReturnPos.r=CurPos.r-1; //北方向
        ReturnPos.c=CurPos.c;
        break;
  }
  return ReturnPos;
}




Status MazePath(MazeType &maze, PosType start, PosType end) 
{  
  // 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中，即输入入口和出口的位置，找出一条路径
  // （从栈底到栈顶），并返回TRUE；否则返回FALSE
  PosType curpos;
  int curstep,i;
  SElemType e,e1,print_coordinates[21];
  //LinkType p;
  InitStack(S);
  curpos=start;  // 设定"当前位置"为"入口位置"
  curstep=1;     // 探索第一步
  do {
    if (Pass(maze,curpos))  //检测函数，后面加上的记号也能够检测到
	{  
	  // 当前位置可通过，即是未曾走到过的通道块
      FootPrint(maze,curpos); // 留下足迹
      e.di =1;
      e.step=curstep;
      e.seat=curpos;
      Push(S,e);             // 加入路径

      if (curpos.r==end.r && curpos.c==end.c)  
	  {
		  printf("\n");
		  while (!StackEmpty(S))
		  { 
			  
			  for(i=19;i>=0;i--)
			  {
				  Pop(S,e1);
				  print_coordinates[i].seat.r=e1.seat.r;
			      print_coordinates[i].seat.c=e1.seat.c;
				  print_coordinates[i].di=e1.di;

			  }
			  printf("The Paths is as fllowing:\n");
			  for(i=0;i<20;i++)
			  {
				  printf("NO.%d step:Row:%d,Col:%d,NextDir:%d.",i+1,print_coordinates[i].seat.r,print_coordinates[i].seat.c,print_coordinates[i].di);
				  printf("\n");
			  }
			 
		  }
		  printf("\n");
		  return (TRUE); 
		  
	  }                                   // 到达终点（出口）
      curpos=NextPos(curpos,1);           // 下一位置是当前位置的东邻
      curstep++;                          // 探索下一步
    
	} 
	else 
	{  
	  // 当前位置不能通过
      if (!StackEmpty(S)) 
	  {
        Pop(S,e);
        while (e.di==4 && !StackEmpty(S)) 
		{
          MarkPrint(maze,e.seat);  
          Pop(S,e);    // 留下不能通过的标记，并退回一步
        } // while
        if (e.di<4) 
		{
          e.di++;
          Push(S,e);  // 换下一个方向探索
          curpos=NextPos(e.seat,e.di); // 当前位置设为新方向的相邻块
        } // if
      } // if
    } // else
  } while (!StackEmpty(S));
  return FALSE;
} // MazePath

/*
测试迷宫数据：

00100010
00100010
00001101
01110010
00010000
01000101
01111001
11000101
11000000

*/