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

《迷宫问题实验报告用栈解决迷宫问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、的查找。（4）求解迷宫中一条通路的伪代码：do{若当前位置可同，则{将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；}否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。}}}while(栈不空)三．详细设计栈的设计：typedefstruct{Node*base,*top;in

3、tlength;}Stack;Stack*initstack();//初始化栈voidprintstack(Stack*s);//打印栈Statusdestroy(Stack*);//销毁整个栈Statusdeltop(Stack*s);//出栈Statuspushelem(Stack*,ElemType,ElemType);//进栈1.主程序模块：intmain(){printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路：");Mazea[N][N];makemaze(a)

4、;printf("输入回车键显示路径,*字符表示路径。");getchar();findpath(a);while(1);return0;}2.迷宫生产模块；voidmakemaze(Maze(*p)[N]){inti,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[

5、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

6、(i==1&&j==1

7、

8、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;intselect=0;*i=*j=0;for(;q==NULL&&select<4;++select)//在可行的方向上只选一个{switch(select){case0:if((*(p+s->top->x)+s->top->y)->m

9、ove[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;case1: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-

10、>top->x+1;*j=s->top->y+0;}//退回前一步检查南方向是否可通break;case2: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;case3:if((*(p+s->to