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

C:C: Windows\system32\end. exe Include 初始迷 #include #include #include ■■■■■■■■■ //函数状态码定义 位置坐标从 Define WALl 0 /代表当前格子是墙 tep: 2 to (2.5) step:3 to (3,5> Define path 1 /代表是通路且未走过 tep:4 to #define right ∥代表是通路且从其向右走Ftep:5to33 step:6to(4,3) #define down /代表是通路且从其向下走tep:?to<53 #define left -3 /代表是通路且从其向左走 step:8 to (5,2) 输入任意数字键结 #define UP-4 /代表是通路且从其向上走 /代表是通路且从其后退一步 # define destinati0N-6/代表当前格子是通路且是目标位置 ypedef int MazeType[l0][10]://最外凿初始化成墙,实际含*8个格子 typedef int Status typedef int ElemType;//迷宫数组中的元素类型 一栈的定义和实现,采用顺序存储结构一 #define sTACK INIT size 100 Define sTacKIncrement 10 ypedef struct Int y: } Pos Type;//迷宫中坐标的位置 typedef struct( int ord PosType seat

#include #include #include #include #include //函数状态码定义 #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 d } SElemType;//栈中元素类型 ypedef struct I * base int stacksize } Stack;//栈类型 Status InitStack(Stack &S)i /构造空栈S S base=(SElemType*)malloc(STACK_ INIT SIZE*sizeof(SElemType)); if(!S.base)exit( VERFLOW);//存储分配失败 S.top= S base;/空栈 S. stacksize=STACK INIT SIZE: return 1/InitStack Status Push(Stack &S, SElemType e)i //插入e为栈顶元素 f(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指向待插入位置 1//Push Status Pop (Stack &S, SElemType &e)f //若栈不空则栈顶元素出栈并用e带回其值 if(S top==S base)return ERROR //栈顶元素为*(S.top-1) return OK. Status GetTop(Stack S, SElemType &e)I if(S top==S base)return ERROR *(S.top-1);//注意top指向待插入位置 return OK Status StackEmpty( Stack s){/判空

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. 1//StackEmpty Status StackTraverse(Stack S, Status (*visit)(SElemType))I /从栈底元素到栈顶元素依次执行 vIsIt函数,通常用于输出栈中元素 SElemType *p=S base if(S.base=S.top) printf("空栈\n") while(p<S top)f(*visit)(*p): ++p: I 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"表示不通WAL srand(time(NULL)) for(m. y=0; m. y<=9; m. y++)Maze [O] [m, y]=WALL; maze [9][m y]=WALL; for(m x=l: m x=8: m x++)maze [m x][O]=WALL; maze [m x][9]=WALL; K for(m for(m y=l; m. y<=8: m. y++) maze [m x][m y]=rand(%2 1//MakeMaze void PrintMaze(Maze Type maze)I int x,y for(x=0;x<=9;x++){ switch(maze [x]ly])t case WALL: printf(a"): break case PATH: printf("): break case RIGHT: printf("-"): break: case LEFT: printf("+): break case BACK: printf(e"): break case DESTINATION: printf(@"): break

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 (Pos Type position, ElemType direction) PosType result result=position; switch(direction) case l: 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, Pos Type end, Stack&S){/找出迷宫的一条通路 Pos Type curpos SElemType e if(maze[ curpos.x][ curpos.y]!=PATH){ printf("当前迷宫没有入口n"); return false;} f(maze[ curpos.x][ curpos.y]==PAT){/当前位置可通 Push(S, e) f(curpos x==end. x&&curpos y=end. y)(maze [curpos. x][curpos y]=DESTINATION; return OK: I el maze[ curpos.x][ curpos.y]= RIGHT://从其向右走 curpos=Nextpos(curpos, 1) else{/当前位置不通 while(!StackEmpty(S)&&e di==4)t maze[e seat. x]Le. seat. y]=BACK Pop(s, e)

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--;

f(StackEmpty(S))break GetTop(s, e) if(e.di<4){//栈顶位置有其他方向可以选择 maze[e,seat.x][e.seat.y]=e.di;/注意前进方向踪迹与e.di互为相反数 curpos=Nextpos(e seat, e di) Iwhile(! StackEmpty(S)) MazeType maze PosType start, end; Stack s InitStack(S) MakeMaze(maze) printf("初始迷宫为:n") 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, Print SElem) printf("迷宫不可通,路径踪迹如下:n PrintMaze(maze) 输入任意数字键结束 int pause: scanf(%d",&pause)

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