资源描述：
《数据结构之迷宫求解实验报告武汉大学.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构实验报告——迷宫求解问题实验上机环境：DevC++二、程序设计相关信息（1）实验题目：迷宫求解问题问题描述：实验题3.5改进3.1.4节中的求解迷宫问题程序，要求输出如图3.14所示的迷宫的所有路径，并求最短路径长度及最短路径。012345012345出口入口（2）实验项目组成：本项目由一个原程序mg.cpp及mg.exe文件组成。（3）实验项目的程序结构：main()struct结构体mgpath()路径函数函数调用关系图：main()（4）实验项目包含的函数的功能描述：mg[M+1][N+1]//构造迷宫二维数组，1表示墙不可走方块，0
2、表示通道mgpath(intxi,intyi,intxe,intye)//求解路径为：（xi,yi）->（xe,ye）//采用顺序栈存储，进栈，回溯，退栈等（5）算法描述：求解迷宫从入口到出口的所有路径，从入口出发，顺某一个方向向前试探，对于可走的方块都进栈，并将这个可走发方位保存，且top+1，然后试探下一个方块，若下一个方块能走通则继续，否则则回溯到前一个方块，且top-1。为记录所有的路径调用Path[k]=Stack[k]记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。最后比较top值找到一条最短路径并输出。试探路径过程的算法
3、利用了“广度优先搜索遍历”算法。流程图：mg=0回溯mg=1进栈循环for下一个方块变成前一个方块下一个方块值mg[i][j]前一个方块值mg[][]=0下一个方块值mg[][]=0输出方位坐标(,)入口结束（6）实验数据：迷宫数组如下：intmg[M+1][N+1]={{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};实验结果：三、程序代码：#include#include#defineM6
4、#defineN6#defineMaxsize100intmg[M+1][N+1]={{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};struct{inti;intj;intdi;}Stack[Maxsize],Path[Maxsize];inttop=-1;intcount=1;intmin=Maxsize;intmgpath(){inti,j,di,find,k;top++;Stack[top].i=1;Stack[top]
5、.j=1;Stack[top].di=-1;mg[1][1]=-1;printf("迷宫所有路径如下:");while(top>-1){i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;if(i==M-2&&j==N-2){printf("%4d:",count++);for(k=0;k<=top;k++){printf("(%d,%d)",Stack[k].i,Stack[k].j);if((k+1)%5==0)printf("");}printf("");if(top+16、(k=0;k<=top;k++)Path[k]=Stack[k];min=top+1;}mg[Stack[top].i][Stack[top].j]=0;top--;i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;}find=0;while(di<4&&find==0){di++;switch(di){case0:i=Stack[top].i-1;j=Stack[top].j;break;case1:i=Stack[top].i;j=Stack[top].j+1;break;case2:i=Stack[
7、top].i+1;j=Stack[top].j;break;case3:i=Stack[top].i;j=Stack[top].j-1;break;}if(mg[i][j]==0)find=1;}if(find==1){Stack[top].di=di;top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;mg[i][j]=-1;}else{mg[Stack[top].i][Stack[top].j]=0;top--;}}printf("");printf("最短路径如下：");print
8、f("路径最短长度：%d",min);printf("最短路径路径：");for(k=0;k
