数据结构之迷宫求解实验报告武汉大学

数据结构实验报告——迷宫求解问题实验上机环境：DevC++二、程序设计相关信息（1）实验题目：迷宫求解问题问题描述：实验题3.5改进3.1.4节中的求解迷宫问题程序，要求输出如图3.14所示的迷宫的所有路径，并求最短路径长度及最短路径。（2）实验项目组成：本项目由一个原程序mg.cpp及mg.exe文件组成。（3）实验项目的程序结构：函数调用关系图：（4）实验项目包含的函数的功能描述：mg[M+1][N+1]//构造迷宫二维数组，1表示墙不可走方块，0表示通道mgpath(intxi,intyi,intxe,intye)//求解路径为：（xi,yi）-（xe,ye）//采用顺序栈存储，进栈，回溯，退栈等012345012345出口入口main()main()struct结构体mgpath()路径函数（5）算法描述：求解迷宫从入口到出口的所有路径，从入口出发，顺某一个方向向前试探，对于可走的方块都进栈，并将这个可走发方位保存，且top+1，然后试探下一个方块，若下一个方块能走通则继续，否则则回溯到前一个方块，且top-1。为记录所有的路径调用Path[k]=Stack[k]记录，从次方块向不同方向去试探，已经走过的方块则为不可走方块。最后比较top值找到一条最短路径并输出。试探路径过程的算法利用了“广度优先搜索遍历”算法。流程图：（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}};实验结果：mg=0回溯mg=1进栈循环for下一个方块变成前一个方块下一个方块值mg[i][j]前一个方块值mg[][]=0下一个方块值mg[][]=0输出方位坐标(,)入口结束三、程序代码：#includestdio.h#includestdlib.h#defineM6#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].j=1;Stack[top].di=-1;mg[1][1]=-1;printf(迷宫所有路径如下:\n);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(\n);}printf(\n);if(top+1min){for(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(di4&&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[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(\n);printf(最短路径如下：\n);printf(路径最短长度：%d\n,min);printf(最短路径路径：\n);for(k=0;kmin;k++){printf((%d,%d),Path[k].i,Path[k].j);}printf(\n\n);}intmain(){mgpath();system(PAUSE);return0;}