migong.rar_数据结构 迷宫

#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); }