迷宫问题实验报告用栈解决迷宫问题

迷宫问题实验报告用栈解决迷宫问题迷宫问题实验报告用栈解决迷宫问题数据结构实验报告题目:用栈解决迷宫问题一(需求分析 1( 以结构体Maze表示迷宫，其中pos表示该位置是否有障碍; freq记录该位置被经过的次数;数组move表示下一步的方向。 2( 本程序自动随机生成一个12×12大小的迷宫，字符“H”表示有障碍，空符表示通路。 3( 迷宫的入口为左上角，出口为右下角。 4( 本程序只求出一条成功的通路。二(概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块: (1) 主程序模块:实现人机交互。 ...

迷宫问题实验报告用栈解决迷宫问题数据结构实验报告题目:用栈解决迷宫问题一(需求分析 1( 以结构体Maze 表示迷宫，其中pos表示该位置是否有障碍; freq记录该位置被经过的次数;数组move表示下一步的方向。 2( 本程序自动随机生成一个12×12大小的迷宫，字符“H”表示有障碍，空符表示通路。 3( 迷宫的入口为左上角，出口为右下角。 4( 本程序只求出一条成功的通路。二(概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块: (1) 主程序模块:实现人机交互。 (2) 迷宫生产模块:随机产生一个12×12的迷宫。 (3) 路径查找模块:实现通路的查找。 (4) 求解迷宫中一条通路的伪代码: do{ 若当前位置可同，则{ 将当前位置插入栈顶; 若该位置是出口位置，则结束; 否则切换当前位置的东临方块为新的当前位置; } 否则{ 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则{ 删去栈顶位置; 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。 } } } while(栈不空) 三( 详细设计栈的设计: typedef struct { Node *base,*top; int length; }Stack; Stack *initstack(); //初始化栈 void printstack(Stack *s); //打印栈 Status destroy(Stack *); //销毁整个栈 Status deltop(Stack *s); //出栈 Status pushelem(Stack *,ElemType ,ElemType); //进栈 1. 主程序模块: int main() { printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路:\n"); Maze a[N][N]; makemaze(a); printf("输入回车键显示路径,*字符表示路径。\n"); getchar(); findpath(a); while(1); return 0; } 2. 迷宫生产模块; void makemaze(Maze (*p)[N]) { int i,j,conter; for(i=0;ipos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move[0]=0; (*(p+i)+j)->move[1]=0; (*(p+i)+j)->move[2]=0; (*(p+i)+j)->move[3]=0; } for(j=0;jpos='X'; (*(p+N-1)+j)->pos='X'; } for(i=1;ipos='X'; (*(p+i)+N-1)->pos='X'; } srand((int)time(NULL)); for(conter=0;conter<20;++conter) { i=rand()%(N-2); j=rand()%(N-2); (*(p+i)+j)->pos='X'; if(i==1&&j==1||i==N-1&&j==N-1) { (*(p+i)+j)->pos=0; } } printmaze(p); } 3.路径查找模块。 Maze *testnewpos(Maze (*p)[N],Stack *s,int *i,int *j) { Maze *q=NULL; int select=0; *i=*j=0; for(;q==NULL&&select<4;++select)//在可行的方向上只选一个 { switch(select) { case 0: if( (*(p+s->top->x)+s->top->y)->move[0]!=1 ) { (*(p+s->top->x)+s->top->y)->move[0]=1; q=*(p+s->top->x)+s->top->y+1; *i=s->top->x+0; *j=s->top->y+1; }// 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move[1]!=1 ) { (*(p+s->top->x)+s->top->y)->move[1]=1; q=*(p+s->top->x+1)+s->top->y; *i=s->top->x+1; *j=s->top->y+0; }// 退回前一步检查南方向是否可通 break; case 2: if( (*(p+s->top->x)+s->top->y)->move[2]!=1 ) { (*(p+s->top->x)+s->top->y)->move[2]=1; q=*(p+s->top->x)+s->top->y-1; *i=s->top->x+0; *j=s->top->y-1; }// 退回前一步检查西方向是否可通 break; case 3: if( (*(p+s->top->x)+s->top->y)->move[3]!=1 ) { (*(p+s->top->x)+s->top->y)->move[3]=1; q=*(p+s->top->x-1)+s->top->y; *i=s->top->x-1; *j=s->top->y+0; }// 退回前一步检查北方向是否可通 } } return q; } void printpath(Stack *s,Maze (*p)[N]) { Node *n; int i,j,conter; conter=0; n=s->base; for(;n;n=n->next) { (*(p+n->x)+n->y)->pos='*'; } for(i=0;ipos); if(conter%12==0) TURNLINE; } TURNLINE; } 完整的程序: maze.h #ifndef MAZE_H #define MAZE_H #include "mazepath.h" #include #define N 12//10+2 #define FORMAT "%2c" #define TURNLINE printf("\n") typedef struct { char pos; int freq; int move[4]; }Maze; void makemaze(Maze (*p)[N]); void printmaze(Maze (*p)[N]); void findpath(Maze (*p)[N]); Maze *testnewpos(Maze (*p)[N],Stack *,int *,int *); void printpath(Stack *s,Maze (*p)[N]); void makemaze(Maze (*p)[N]) { int i,j,conter; for(i=0;ipos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move[0]=0; (*(p+i)+j)->move[1]=0; (*(p+i)+j)->move[2]=0; (*(p+i)+j)->move[3]=0; } for(j=0;jpos='X'; (*(p+N-1)+j)->pos='X'; } for(i=1;ipos='X'; (*(p+i)+N-1)->pos='X'; } srand((int)time(NULL)); for(conter=0;conter<20;++conter) { i=rand()%(N-2); j=rand()%(N-2); (*(p+i)+j)->pos='X'; if(i==1&&j==1||i==N-1&&j==N-1) { (*(p+i)+j)->pos=0; } } printmaze(p); } void printmaze(Maze (*p)[N]) { int i,j,conter; conter=0; for(i=0;ipos); if(conter%12==0) TURNLINE; } TURNLINE; } void findpath(Maze (*p)[N]) { Maze *q=NULL; int i=1,j=1,*pi=&i,*pj=&j,success=0; Stack *s; s=initstack();//初始化用来存储路径的栈 q=*(p+1)+1;//初始化当前位置为入口位置 do { if(q->pos!='X'&&!(q->freq))//当前位置通且在当前路径中未被访问过，则入栈 { if(i==N-2&&j==N-2) { pushelem(s,N-2,N-2); success=1; } else if(i==1&&j==1) { pushelem(s,i,j); q->freq=1;//当前位置已经进栈，作标记，不能再入栈，不然就只能兜死胡同了 q->move[0]=1;//切换下一位置为东邻位置,并做标记，东邻位置已经使用 i=s->top->x+0; j=s->top->y+1; q=*(p+i)+j; } else { pushelem(s,i,j); q->freq=1; q=*(p+i)+j; } } else//当前位置不通，则在前一步(栈顶)检查是否有其他方向可行 { //printf("step here..."); if(s->base!=s->top) { do//查找新的通路直到新通路出现或者回到初始位置 { q=testnewpos(p,s,&i,&j);//返回其它三个方向的其中一个和新的当前位置的坐标 if(q==NULL) deltop(s);//栈顶没有可继续往下走的通路，删除栈顶，在新的栈顶找 }while(q==NULL&&s->base!=s->top); } } }while(success!=1); printpath(s,p); } Maze *testnewpos(Maze (*p)[N],Stack *s,int *i,int *j) { Maze *q=NULL; int select=0; *i=*j=0; for(;q==NULL&&select<4;++select)//在可行的方向上只选一个 { switch(select) { case 0: if( (*(p+s->top->x)+s->top->y)->move[0]!=1 ) { (*(p+s->top->x)+s->top->y)->move[0]=1; q=*(p+s->top->x)+s->top->y+1; *i=s->top->x+0; *j=s->top->y+1; }// 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move[1]!=1 ) { (*(p+s->top->x)+s->top->y)->move[1]=1; q=*(p+s->top->x+1)+s->top->y; *i=s->top->x+1; *j=s->top->y+0; }// 退回前一步检查南方向是否可通 break; case 2: if( (*(p+s->top->x)+s->top->y)->move[2]!=1 ) { (*(p+s->top->x)+s->top->y)->move[2]=1; q=*(p+s->top->x)+s->top->y-1; *i=s->top->x+0; *j=s->top->y-1; }// 退回前一步检查西方向是否可通 break; case 3: if( (*(p+s->top->x)+s->top->y)->move[3]!=1 ) { (*(p+s->top->x)+s->top->y)->move[3]=1; q=*(p+s->top->x-1)+s->top->y; *i=s->top->x-1; *j=s->top->y+0; }// 退回前一步检查北方向是否可通 } } return q; } void printpath(Stack *s,Maze (*p)[N]) { Node *n; int i,j,conter; conter=0; n=s->base; for(;n;n=n->next) { (*(p+n->x)+n->y)->pos='*'; } for(i=0;ipos); if(conter%12==0) TURNLINE; } TURNLINE; } #endif mazepath.h #ifndef MAZEPATH_H #define MAZEPATH_H #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct node { ElemType x; ElemType y; struct node *next; struct node *prior; }Node,*Postion; typedef struct { Node *base,*top; int length; }Stack; Stack *initstack(); //初始化栈 void printstack(Stack *s); //打印栈 Status destroy(Stack *); //销毁整个栈 Status deltop(Stack *s); //出栈 Status pushelem(Stack *,ElemType ,ElemType); //进栈 Stack *initstack() { Stack *s; s=(Stack *)malloc(sizeof(Stack)); if(!s) return ERROR; s->base=s->top=NULL; //栈空 s->length=0; return s; } void printstack(Stack *s) { Node *N; N=s->base; for(;N;N=N->next) { printf("%2d %2d ",N->x,N->y); } printf("\n\n"); } Status destroy(Stack *s) { Node *p; p=s->base; while(s->base->next) { s->base=s->base->next; //N=N->next和free(P)不能倒换位置，当释放p时， free(p); //如果不将N移向下一个位置，将导致N指向的内存释放，N->next 不再有效 p=s->base; } s->base=s->top=NULL; s->length=0; return OK; } Status deltop(Stack *s) { Node *p; if(!s->length) printf("Underflow\n"); //已经是空栈 else { p=s->top; s->top=p->prior; free(p); --s->length; s->top->next=NULL; } return OK; } Status pushelem(Stack *s,ElemType i,ElemType j) { Node *n; n=(Node *)malloc(sizeof(Node)); if(!n) return ERROR; n->x=i; n->y=j; if(s->length==0) { s->base=s->top=n; n->prior=NULL; } else { n->prior=s->top; s->top->next=n; s->top=n; } n->next=NULL; ++s->length; return OK; } #endif MyMain.cpp #include "maze.h" int main() { printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路:\n"); Maze a[N][N]; makemaze(a); printf("输入回车键显示路径,*字符表示路径。\n"); getchar(); findpath(a); while(1); return 0; } 四(调试结果及说明 1( 说明:本程序的运行环境为VC++6.0，执行文件为MgProblem.exe。 2( 测试结果实际程序执行过程如下图所示:

                    本文档为【迷宫问题实验报告用栈解决迷宫问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

迷宫问题实验报告用栈解决迷宫问题

你可能还喜欢