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

数据构造试验汇报——
迷宫求解问题试验
上机环境： DevC++
二、程序设计有关信息
（1）试验题目：迷宫求解问题
问题描述：
试验题3.5 改善3.1.4节中旳求解迷宫问题程序，规定输出如图3.14所示旳迷宫旳所有途径，并求最短途径长度及最短途径。
0 1 2 3 4 5
0 1 2 3 4 5
出口
入口

（2）试验项目构成：
本项目由一种原程序mg.cpp及mg.exe文献构成。

（3）试验项目旳程序构造：
main()
struct构造体
mgpath()途径函数
函数调用关系图：
main()

（4）试验项目包括旳函数旳功能描述：
mg[M+1][N+1] //构造迷宫二维数组，1表达墙不可走方块，0表达通道
mgpath(int xi,int yi,int xe,int ye)
//求解途径为：（xi,yi）->（xe,ye）
//采用次序栈存储，进栈，回溯，退栈等
（5）算法描述：
求解迷宫从入口到出口旳所有途径，从入口出发，顺某一种方向向前试探，对于可走旳方块都进栈，并将这个可走发方位保留，且top+1，然后试探下一种方块，若下一种方块能走通则继续，否则则回溯到前一种方块，且top-1。为记录所有旳途径调用Path[k]=Stack[k]记录，从次方块向不一样方向去试探，已经走过旳方块则为不可走方块。最终比较top值找到一条最短途径并输出。
试探途径过程旳算法运用了“广度优先搜索遍历”算法。
流程图：
mg=0回溯
mg=1进栈
循环for
下一种方块变成前一种方块
下一种方块值
mg[i][j]
前一种方块值mg[][]=0
下一种方块值mg[][]=0
输出方位坐标( , )
入口
结束

（6）试验数据：
迷宫数组如下：
int mg[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 <stdio.h>
#include <stdlib.h>
#define M 6
#define N 6
#define Maxsize 100
int mg[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
{
int i;
int j;
int di;
}Stack[Maxsize],Path[Maxsize];
int top=-1;
int count=1;
int min=Maxsize;
int mgpath()
{
int i,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+1<min)
{
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(di<4&&find==0)
{
di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3: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;k<min;k++)
{
printf("(%d,%d)",Path[k].i,Path[k].j);
}
printf("\n\n");
}
int main()
{
mgpath();
system("PAUSE");
return 0;
}