数据结构实验报告
实验〇：迷宫求解问题
专 业： 信息管理与信息系统 班 级： 信管1403 姓 名： 徐朋姣 学 号： 140750505 指导教师： 应明幼 日 期： 2015-11-07
一、 实验目的
熟练掌握栈的应用，出栈，入栈等知识，以及各种循环语句
二、 实验内容
通过二维数组，建立一个m*n的迷宫，并且用#表示迷宫的外墙以及障碍物，路径测试后，若通，则用*表示，若不通，则用@表示，程序中，分别用1,2,3,4来表示方位上的东南西北，通过循环，进行完探索，最后输出迷宫通路。
三、 需求分析
1. 以二维数组建立一个迷宫，并且设置好外墙和和障碍路段，用#表示
2. 随意设置一个入口，入a【0】【0】，或者其他
3. 通过循环，把能够走过的路用*表示，若当前路径的下一方向不通，则应先转换到另一个方向，若四个方向都不通，则用@标记，表示走过但不通的路
4. 最后通过一系列的试探，输出能够走出的路径，用坐标表示出出口
5. 程序执行的命令为：
1) 创建迷宫； 2)求解迷宫； 3)输出迷宫的解。
四、 概要设计
1. 主要函数
int main()主函数
structLNode定义链式结构
structLStack栈顶指针
Status InitStack(LStack&s)构造空栈
Satus Push(LStack&s,SElemType e)入栈，插入元素
Status Pop(LStack&s,SElemType&e)出栈，删除元素
Status DestroyStack(LStack&s)销毁栈S
Status InitMaze(MazeType&maze)初始化迷宫
Satus Pass(MazeTypemaze,PostTypecurpos)路径测试
PrintMaze(maze)打印路径
五、 详细设计
1. 坐标位置的类型
typedefstruct{//迷宫中r行c列的位置
int r; int c;
}PostType;//坐标位置类型
typedefstruct{
2.
3.
4.
5. intord;// 当前位置在路径上的序号 PostType seat;// 当前坐标 int di;// 从此通块走向下一通块的“方向” }SElemType;// 栈的元素类型 链式栈的存储结构 structLNode { SElemType data;//数据域 structLNode *next;//指针域 }; structLStack { structLNode *top;//栈顶指针 }; 构造一个空栈S Status InitStack(LStack&s)//操作结果：构造一个空栈S { structLNode *p; p=(LNode *)malloc(sizeof(LNode)); if(!p) {printf("分配失败，退出程序"); exit(ERROR); } s.top=p; p->next=NULL; return OK; } 入栈函数 Status Push(LStack&s,SElemType e)//插入元素e成为新的栈顶元素 { structLNode *p; p=(LNode *)malloc(sizeof(LNode)); if(!p) exit(OVERFLOW); s.top->data=e; p->next=s.top; s.top=p; return OK; } 出栈函数
Status Pop(LStack&s,SElemType&e)//删除s的栈顶元素，并且用e返回其值
{ structLNode *p;
if(!(s.top->next))
exit(UNDERFLOW);
p=s.top;
s.top=p->next;
e=s.top->data;
free(p);
return OK;
}
6. 迷宫的路径测试
PostTypeNextPos(PostType&curpos,inti)
{// 指示并返回下一位置的坐标
PostTypecpos;
cpos=curpos;
switch(i){//1.2.3.4 分别表示东南西北方向
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
7. 输出路径信息
voidPrintMaze(MazeType&maze)
{// 将标记路径信息的迷宫输出到终端
inti,j;
printf("\n输出迷宫(*表示通路):\n\n");
printf("");
for(i=0;i<=maze.r+1;i++)// 打印列数名
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.r+1;i++
) { printf("%2d",i);// 打印行名
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);// 输出迷宫当前位置的标记
printf("\n\n");
}
六、 调试分析
本次作业难度太大了！真的是花了好久好久，查找资料，看书，最终勉强完成。
七、 使用说明
程序调试之后，会有提示，输入入口坐标，用户可在范围之内输入数据，之后，程序会建立一个迷宫，然后开始进行路径测试，若此迷宫有解，可通，则程序会输出一条路径，若不通，则出错
八、 测试结果
输入入口为（1,1）
结果：
九、 附录：部分代码
#define MAXLEN 10// 迷宫包括外墙最大行列数
typedefstruct
{ int r;
int c;
char adr[MAXLEN][MAXLEN];// 可取' ''*' '@' '#' }MazeType;// 迷宫类型
Status InitMaze(MazeType&maze){
// 初始化迷宫，成功返回TRUE，否则返回FALSE intm,n,i,j; printf("输入迷宫行数和列数（包括了外墙）: ");
scanf("%d%d",&maze.r,&maze.c); // 输入迷宫行数和列数 for(i=0;i<=maze.c+1;i++)
{// 迷宫行外墙
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i<=maze.r+1;i++) {// 迷宫列外墙
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#'; }
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';// 初始化迷宫
printf("输入障碍的坐标((-1 -1)结束): ");
scanf("%d%d",&m,&n);// 接收障碍的坐标
while(m!=-1)
{ if(m>maze.r || n>maze.c)// 越界
exit(ERROR);
maze.adr[m][n]='#';
// 迷宫障碍用#标记printf("输入障碍的坐标((-1,-1)结束): "); scanf("%d%d",&m,&n);
}//while
return OK;
}//InitMaze
Status Pass(MazeTypemaze,PostTypecurpos)
{// 当前位置可同则返回TURE,否则返回FALSE
if(maze.adr[curpos.r] [curpos.c]==' ')// 可通
return TRUE;
else
return FALSE;
}//Pass
Status FootPrint(MazeType&maze,PostTypecurpos)
{// 若走过并且可通，则返回TRUE,否则返回FALSE maze.adr[curpos.r]
[curpos.c]='*';//"*"表示可通
return OK;
}//FootPrint
PostTypeNextPos(PostType&curpos,inti)
{// 指示并返回下一位置的坐标
PostTypecpos;
cpos=curpos;
switch(i){//1.2.3.4 分别表示东南西北方向 case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
returncpos; }//Nextpos
Status MarkPrint(MazeType&maze,PostTypecurpos) {// 曾走过，但不是通路标记，并返回OK
maze.adr[curpos.r][curpos.c]='@';//"@" 表示曾走过但不通
return OK;
}//MarkPrint
Status MazePath(MazeType&maze,PostTypestart,PostType end)
{// 若迷宫maze存在通路，则求出一条同路放在栈中，并返回TRUE，否则返回FALSE
structLStack S;
PostTypecurpos;
intcurstep;// 当前序号，1,2,3,4分别表示东南西北方向
SElemType e;
InitStack(S);
curpos=start; //设置"当前位置"为"入口位置"
curstep=1;// 探索第一位
printf("以三元组形式表示迷宫路径：\n");
do{ if(Pass(maze,curpos)) {// 当前位置可以通过
FootPrint(maze,curpos);// 留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
printf("%d %d %d-->",e.seat.r,e.seat.c,e.di);
Push(S,e);// 加入路径
if(curpos.r==end.r&&curpos.c==end.c)
if(!DestroyStack(S))// 销毁失败
exit(OVERFLOW);
else return TRUE; // 到达出口 else { curpos=NextPos(curpos,1); // 下一位置是当前位置的东邻 curstep++;// 探索下一步
}//else
}//if
else {// 当前位置不通时
if(!StackEmpty(S))
{ Pop(S,e);
while(e.di==4&& !StackEmpty(S)) { MarkPrint(maze,e.seat); Pop(S,e);
// 留下不能通过的标记，并退一步 }//while
if(e.di< 4)
{ e.di++;// 换一个方向探索
Push(S,e);
curpos=NextPos(e.seat,e.di);// 设定当前位置是该方向上的相邻 printf("%d %d %d-->",e.seat.r,e.seat.c,e.di);
}//if
}//if
}//else
}while(!StackEmpty(S));
if(!DestroyStack(S))// 销毁栈
exit(OVERFLOW);
else
return FALSE;
}//MazePath
voidPrintMaze(MazeType&maze)
{// 将标记路径信息的迷宫输出到终端
inti,j;
printf("\n输出迷宫(*表示通路):\n\n");
printf("");
for(i=0;i<=maze.r+1;i++)// 打印列数名
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.r+1;i++
) { printf("%2d",i);// 打印行名
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);// 输出迷宫当前位置的标记 printf("\n\n");
}
}//PrintMaze
第二篇：数据结构之迷宫求解实验报告武汉大学
数据结构实验报告——
迷宫求解问题实验
上机环境： DevC++
二、程序设计相关信息
（1）实验题目：迷宫求解问题
问题描述：
实验题3.5 改进3.1.4节中的求解迷宫问题程序，要求输出如图3.14所示的迷宫的所有路径，并求最短路径长度及最短路径。
（2）实验项目组成：
本项目由一个原程序mg.cpp及mg.exe文件组成。
（3）实验项目的程序结构：
函数调用关系图：
（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值找到一条最短路径并输出。
试探路径过程的算法利用了“广度优先搜索遍历”算法。
流程图：
（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;
}