数据结构库VC实践实例：迷宫求解参考答案

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define NULL 0
//墙或通路及前进方向符号定义
#define WALL 0 //代表当前格子是墙
#define PATH 1 //代表是通路且未走过
#define RIGHT -1 //代表是通路且从其向右走
#define DOWN -2 //代表是通路且从其向下走
#define LEFT -3 //代表是通路且从其向左走
#define UP -4 //代表是通路且从其向上走
#define BACK -5 //代表是通路且从其后退一步
#define DESTINATION -6 //代表当前格子是通路且是目标位置
typedef int MazeType[10][10]; //最外凿初始化成墙，实际含*8个格子
typedef int Status;
typedef int ElemType; //迷宫数组中的元素类型
//－－－－－－－－－－栈的定义和实现，采用顺序存储结构－－－－－－－－－－－－//
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
int x;
int y;
}PosType;//迷宫中坐标的位置
typedef struct{
int ord;
PosType seat;
int di;
}SElemType;//栈中元素类型
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}Stack;//栈类型
Status InitStack(Stack &S){
//构造空栈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;
}//InitStack
Status Push(Stack &S,SElemType e){
//插入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.top重新指向原栈顶,因realloc
S.stacksize+=STACK_INIT_SIZE;
}
*S.top++=e; //top指向待插入位置
return OK;
}//Push
Status Pop(Stack &S,SElemType &e){
//若栈不空则栈顶元素出栈并用e带回其值
if(S.top==S.base)return ERROR;
else
e=*(--S.top); //栈顶元素为*(S.top-1)
return OK;
}
Status GetTop(Stack S,SElemType &e){
if(S.top==S.base)return ERROR;
e=*(S.top-1); //注意top指向待插入位置
return OK;
}
Status StackEmpty(Stack S){//判空
if(S.top==S.base)return TRUE;
else return FALSE;
}//StackEmpty
Status StackTraverse(Stack S,Status (*visit)(SElemType)){
//从栈底元素到栈顶元素依次执行visit函数，通常用于输出栈中元素
SElemType *p=S.base;
if(S.base==S.top)printf("空栈\n");
else
while(p<S.top){(*visit)(*p);++p;}
return OK;
}
Status PrintSElem(SElemType e){
printf("step:%d to (%d,%d)\n",e.ord,e.seat.x,e.seat.y);
return OK;
}
//－－－－－－迷宫求解的具体算法---------------------------------------//
Status MakeMaze(MazeType &maze){//生成迷宫,"0"表示通PATH，"1"表示不通WALL
PosType m;
srand(time(NULL));
for(m.y=0;m.y<=9;m.y++) {maze[0][m.y]=WALL;maze[9][m.y]=WALL;}
for(m.x=1;m.x<=8;m.x++) {maze[m.x][0]=WALL;maze[m.x][9]=WALL;}
for(m.x=1;m.x<=8;m.x++)
for(m.y=1;m.y<=8;m.y++)
maze[m.x][m.y]=rand()%2;
return OK;
}//MakeMaze
void PrintMaze(MazeType maze){
int x,y;
for(x=0;x<=9;x++){
for(y=0;y<=9;y++){
switch(maze[x][y]){
case WALL:printf("■");break;
case PATH:printf(" ");break;
case RIGHT:printf("→");break;
case DOWN,printf("↓");break;
case LEFT,printf("←");break;
case UP,printf("↑");break;
case BACK,printf("@ ");break;
case DESTINATION:printf("◎");break;
default:printf("error\n");exit(-1);
}
}
printf("\n");
}
}
PosType Nextpos(PosType position,ElemType direction){
PosType result;
result=position;
switch (direction)
{
case 1:result.y++;break;
case 2:result.x++;break;
case 3:result.y--;break;
case 4:result.x--;break;
}
return result;
}
Status PassMaze(MazeType &maze,PosType start,PosType end,Stack &S){//找出迷宫的一条通路
PosType curpos;
SElemType e;
int curstep=1;
curpos=start;
if(maze[curpos.x][curpos.y]!=PATH) { printf("当前迷宫没有入口\n"); return FALSE;}
do{
if(maze[curpos.x][curpos.y]==PATH){//当前位置可通
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e);
if(curpos.x==end.x&&curpos.y==end.y){maze[curpos.x][curpos.y]=DESTINATION;return OK;}
else{
maze[curpos.x][curpos.y]=RIGHT;//从其向右走
curpos=Nextpos(curpos,1);
curstep++;
}
}
else{//当前位置不通
GetTop(S,e);
while(!StackEmpty(S)&&e.di==4){
maze[e.seat.x][e.seat.y]=BACK;
Pop(S,e);
curstep--;
if(StackEmpty(S))break;
GetTop(S,e);
}
if(e.di<4){ //栈顶位置有其他方向可以选择
Pop(S,e); e.di++; Push(S,e);
maze[e.seat.x][e.seat.y]=-e.di; //注意前进方向踪迹与e.di互为相反数
curpos=Nextpos(e.seat,e.di);
}
}
}while(!StackEmpty(S));
return FALSE;
}
void main(){
MazeType maze;
PosType start,end;
Stack S;
InitStack(S);
MakeMaze(maze);
printf("初始迷宫为：\n");
PrintMaze(maze);
printf("输入迷宫的入口位置坐标从(0,0)到(9,9),");
scanf("%d,%d",&start.x,&start.y);
printf("输入迷宫的出口位置坐标从(0,0)到(9,9),");
scanf("%d,%d",&end.x,&end.y);
if(PassMaze(maze,start,end,S)){
printf("迷宫可通,路径踪迹如下:\n");
PrintMaze(maze);
printf("具体路径为：\n");
StackTraverse(S,PrintSElem);
}
else{
printf("迷宫不可通,路径踪迹如下:\n");
PrintMaze(maze);
}
printf("---------------输入任意数字键结束------------------");
int pause;scanf("%d",&pause);
}