我当时写的实验报告，里面有代码流程图发不上来，还有都过这么久了你都不发奖励，估计你是混答案不给分数。答案留在这里，如果别人需要的话可以看。maxwell1013，记住你了，以后不回答你的问题了。一、 需求分析1．问题描述：给一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意给定的迷宫，求出一条从入口到出口的通路，或者得出没有通路的结论。本题题目较为简单，用一个简单队列就可以实现，初始状态是把出发点入队，每次从队首元素点开始寻找一个可达的未到过的点 ，标记他并入队，一直重复次过程，直到寻到终点，此时所找到的路即最短路。2．界面：采用文件读入模式，标准输出，读入数值为迷宫规模，迷宫具体够着以及出发点和终点（出发点和终点任给），输出为迷宫中行走通路。3．程序执行的命令：由于本程序功能较为单一，故将所有的内容归到main函数中。4.实现方式：采用队列这一数据结构，对于可达节点进行处理。5.优化：另外开辟了一个二维（与迷宫同规模），记录从起始点到本点最短路，在找到是否有可行路后可从本数组直接往回寻找到路径。 6.测试数据：9 80 0 1 0 0 0 1 00 0 1 0 0 0 1 00 0 0 0 1 1 0 10 1 1 1 0 0 1 00 0 0 1 0 0 0 00 1 0 0 0 1 0 10 1 1 1 1 0 0 11 1 0 0 0 1 0 11 1 0 0 0 0 0 02 2 9 8二、概要设计为了实现上述程序功能，应以队列来实现链表抽象数据类型的定义为：ADTQueue{数据元素：可以是任意类型的数据，但必须属于同一个数据对象。关系：队列中数据元素之间是线性关系。基本操作：（1）InitQueue(&Q)：初始化操作。设置一个空队列。（2） IsEmpty(Q)：判空操作。若队列为空，则返回TRUE，否则返回FALSE。（3）EnterQueue(&Q，x)：进队操作。在队列Q的队尾插入x。操作成功，返回值为TRUE，否则返回值为FALSE。（4）DeleteQueue(&Q,&x)：出队操作。使队列Q的队头元素出队，并用x带回其值。操作成功，返回值为TRUE，否则返回值为FALSE。（5）GetHead（Q,&x）：取队头元素操作。用x取得队头元素的值。操作成功，返回TRUE，否则返回值为FALSE。（6）ClearQueue(&Q)：队列置空操作。将队列Q置为空队列。（7）DestroyQueue(&Q)：队列销毁操作。释放队列的空间。} ADTQueue三、详细设计#include#includeconst int ROWMAXN=1000;//最大行数const int COLMAXN=1000;//最大列数struct node{ int x; int y;}b[ROWMAXN*COLMAXN];//队列node start,end;//两个node类型的值，分别表示起始节点与终止节点int a[ROWMAXN+2][COLMAXN+2];//输入的迷宫状态存放数组int road[ROWMAXN+2][COLMAXN+2];//标记当前状态的数组int state[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//四个方向int i,j,head,tail,row,col;int main(){ memset(road,0,sizeof(road));//标记所有的迷宫格状态为未到达 memset(a,1,sizeof(a));//迷宫初始化 freopen("in.txt","r",stdin);//文件读入方式,文件名为"in.txt" scanf("%d%d",&row,&col);//读入迷宫的规格 for (i=1;i<=row;i++)for (j=1;j<=col;j++) scanf("%d",&a[j]);//读入迷宫状态 scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);//读入起始点与终点 if (a[start.x][start.y]!=0||a[end.x][end.y]!=0)//特殊情况判定:迷宫起始位置不可达 {printf("Failed to find the road!\n");return 0; } head=0;tail=0; b[0].x=start.x; b[0].y=start.y; road[start.x][start.y]=1; while (head<=tail)//队列操作,每次把可达格入队 {if (b[head].x==end.x&&b[head].y==end.y) break;//已经找到最小通路for (i=0;i<4;i++) if (!road[b[head].x+state[0]][b[head].y+state[1]]&&!a[b[head].x+state[0]][b[head].y+state[1]]) {
tail++;
road[b[head].x+state[0]][b[head].y+state[1]]=road[b[head].x][b[head].y]+1;
b[tail].x=b[head].x+state[0];
b[tail].y=b[head].y+state[1]; }head++; } if (road[end.x][end.y]==0) printf("Failed to find the road!\n");else//寻找通路并输出{ head=0; b[head].x=end.x; b[head].y=end.y; while (!(b[head].x==start.x&&b[head].y==start.y)) {
for (i=0;i<4;i++)
if (road[b[head].x+state[0]][b[head].y+state[1]]==road[b[head].x][b[head].y]-1)
{
head++;
b[head].x=b[head-1].x+state[0];
b[head].y=b[head-1].y+state[1];
a[b[head].x][b[head].y]=i+2;
break;
} } for (i=1;i<=row;i++) {
for (j=1;j<=col;j++)
{
if (i==end.x&&j==end.y) printf(" e");
else if (i==start.x&&j==start.y) printf(" s");
else if (a[j]<=1) printf("%2d",a[j]);
else if (a[j]==4) printf("↓");
else if (a[j]==5) printf("→");
else if (a[j]==2) printf("↑");
else printf("←");
}
printf("\n"); }} return 0;}四、调试分析1．为了方便起见，本程序的输入采用了文件读入的方式，使用者可以在原迷宫结构上进行修改。2．输出方面采用的路线输出，更加直观。 3．本程序的模块划分较为合理，进行了一些的简单操作，在寻找是否有可行路上采用了一次队列，并以一个二维数组记录状态，在输出上利用状态数组倒着寻找路径。 4．算法时空分析1）本算法在空间上主要开辟了三个数组，规模都是迷宫点个数，一个是队列，一个是迷宫记录，还有一个是状态记录，输出时候未另开数组，而是直接采用了先前的队列数组。2）在时间上为简单的广度优先队列实现，其算法时间复杂度为O（row*col）（row为行数，col为列数）。五、用户手册1．本程序是在控制台上运行的，执行文件为“迷宫.exe”。2．操作界面较为简单，在文件读入迷宫数据后输出路线。 1）有可行路的情况：（s表示起点，e表示终点，可行路按照箭头方向）2）找不到可行路的情况： 七、附录源程序文件名清单：迷宫.cpp//主程序 |
