迷宫最短路径数据结构源码实验报告.docx
《迷宫最短路径数据结构源码实验报告.docx》由会员分享，可在线阅读，更多相关《迷宫最短路径数据结构源码实验报告.docx（14页珍藏版）》请在冰点文库上搜索。
迷宫最短路径数据结构源码实验报告
本页仅作为文档页封面，使用时可以删除Thisdocumentisforreferenceonly-rar21year.March
迷宫最短路径-数据结构-源码-实验报告
实验报告
课程名称数据结构
实验名称迷宫最短路径
实验类型综合型
实验地点计405机房
实验日期2017.5.13
指导教师魏海平
专业软件工程
班级软件1601
学号1611030102
姓名寇春雷
辽宁石油化工大学计算机与通信工程学院
数据结构实验报告评分表
项目
要求
分数
有无项目（√）
得分
预习报告
（30分）
实验目的明确
5
实验内容理解透彻
5
实验方案设计完整合理
程序总体框架设计完整
10
完成相关辅助代码
5
测试方案合理
5
实验过程
（30分）
发现问题
5
问题的分析
15
问题的解决方法
10
实验报告
（20分）
内容翔实无缺漏
5
如实记录实验过程
10
撰写规整
5
实验总结
（10分）
实验结果的分析
5
按照结果对原实验方案的改进意见
5
实验体会
（10分）
实验的收获
5
实验内容的发散考虑
5
总分
实验二迷宫最短路径
题目：
迷宫最短路径
⒈问题描述
从一个迷宫的入口到出口找出一条最短路经。
用一个二维数组MAZE（1..m，1..n）模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。
MAZE（1，1）和MAZE（m，n）分别为迷宫的入口和出口。
⒉基本要求
（1）输入数据
a.输入迷宫的大小m行和n列，两者为整数
b.由随机数产生0或1，建立迷宫。
（2）输出数据
首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：
（m，n），……，（i，j），……，（1，1）
如无通道，则打印：
THEREISNOPATH.
⒊实现提示
（1）数据结构
①为了在程序中判断方便，把迷宫扩展成为MAZE（0..m+1，0..n+1），扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置（I，j）上都有八个可以移动的方向。
②用二维数组MOVE（1..8，1..2）存放八个方向上的位置量，如图所示：
（i+MOVE[1，1]，j+MOVE[1，2]）
（i+MOVE[8，1]，j+MOVE[8，2]）（i+MOVE[2，1]，j+MOVE[2，2]）
（i+MOVE[7，1]，j+MOVE[7，2]）（i+MOVE[3，1]，j+MOVE[3，2]）
（i+MOVE[6，1]，j+MOVE[6，2]）（i+MOVE[4，1]，j+MOVE[4，2]）
（i+MOVE[5，1]，j+MOVE[5，2]）
MOVE的设置情况
ij
1
2
1
-1
0
2
-1
1
3
0
1
4
1
1
5
1
0
6
1
-1
7
0
-1
8
-1
-1
③为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻找路径的过程中，若通过了位置（i，j），则将MARK（i，j）置为为1。
④为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1，0..2）数组，对于某一个数组元素Q（P），其中，Q（P，0）和Q（P，1）记下到达位置i和j，Q（P，2）记下其出发点在Q数组中的下标。
（2）算法基本思想
将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口（m，n）或者迷宫所有位置都搜索完毕为止。
具体实施：
从（m，n）开始，将其记入Q数组，比如记入Q
（1），以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置（I，j）可通行并且尚未经过（即MAZE（i，j）=0且MARK（i，j）=0），则记入Q数组，如记在Q（P），则在Q（P，2）中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置（m，n），表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。
4.需求分析
（1）以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1]（0=数组中元素0表示障碍1表示可通过，迷宫的大小可不限；
（2）迷宫中的数据均由用户自由输入；
（3）迷宫的出口和入口可由用户自由设定；
（4）本程序只求出一条成功的通路；
（5）程序执行的命令为：
①创建迷宫②求解迷宫③输出迷宫的解
5.概要设计
5.1抽象数据类型定义
（1）设定栈的抽象数据类型定义：
ADTStack{
数据对象：
D={ai|ai∈CharSet，i=1,2，…,n，n>=0}
数据关系：
R1{|a（i-1）,ai∈D,i=2,3…n}
基本操作：
InitStack（&S）
操作结果：
构造一个空栈S。
DestroyStack（&S）
初始结果：
栈S已存在。
操作结果：
销毁栈S。
ClearStack（&S）
初始结果：
栈S已存在。
操作结果：
将S清为空栈。
StackLength（S）
初始结果：
栈S已存在。
操作结果：
返回栈S的长度
StackEmpty（S）
初始条件：
栈S已存在。
操作结果：
若S为空栈，则返回TRUE，否则返回FALSE
GetTop（S,&e）
初始条件：
栈S已存在。
操作结果：
若栈S不空，则以e返回栈顶元素e。
Push（&S,e）
初始条件：
栈S已存在。
操作结果：
在栈S的栈顶插入新的栈顶元素。
Pop（&S,&e）
初始条件：
栈S已存在。
操作结果：
删除S的栈顶元素，并以e返回其值。
StackTraverse（S,visit（））
初始条件：
栈S已存在。
操作结果：
从栈底到栈顶依次对S中的每个元素调用visit（）
}ADTStack
（2）设定迷宫的抽象数据类型为：
ADTmaze{
数据对象：
D={a（i,j）|a（i,j）∈{0,1}，0=数据关系：
R={M，N}
M={|a（i-1,j），a（i,j）∈D,i=1,2,…,m+1,j=0,1,…n+1}
N={|a（i,j-1）,a（i,j）∈D,I=0,1,…m+1,j=1,2,…n+1}
基本操作：
InitMaze（&M,maze,m,n）
初始条件：
二维数组maze[m+1][n+1]已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障碍。
操作结果：
构成迷宫的字符型数组，以字符0表示通路，以字符1障碍，并在迷宫四周加上一圈障碍。
MazePath（&M）
初始条件：
迷宫M已被赋值。
操作结果：
若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：
以数字0代表可通过，数字1代表不可通过.
6.模块划分
（1）主程序模块：
voidmain（）
{
intsto[M][N];
structmarkstart,end;//start,end入口和出口的坐标
intadd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量
initmaze（sto）;//建立迷宫
printf（"输入入口的横坐标,纵坐标[逗号隔开]\n"）;
scanf（"%d,%d",&start.x,&start.y）;
printf（"输入出口的横坐标,纵坐标[逗号隔开]\n"）;
scanf（"%d,%d",&end.x,&end.y）;
MazePath（start,end,sto,add）;//findpath
system（"PAUSE"）;
}
（2）栈模块——实现栈抽象数据类型；
（3）迷宫模块——实现迷宫抽象数据类型，建立迷宫，求解迷宫的一条路径。
7.源程序代码:
#include"stdafx.h"
#include
#include
#include
int**CreateArr（intm,intn）{//创建动态全局二维数组
inti;
int**p;
p=（int**）malloc（sizeof（int*）*m）;
for（i=0;ip[i]=（int*）malloc（sizeof（int）*n）;
}
return（p）;
}
int**MAZE;
int**MARK;
int**Q;
intflag=0;
voidprint（intstep）{
inti,j;
for（i=step;i>=1;i--）{
j=0;
printf（"（%d,%d）,",Q[i][j],Q[i][j+1]）;
}
printf（"\n"）;
}
voidbacktrack（intx,inty,intstep,intm,intn）{
MARK[x][y]=1;
intw,v;
if（x==m&&y==n）{
flag=1;
Q[step][0]=x;
Q[step][1]=y;
print（step）;
return;
}else{
for（w=1;w>=-1;w--）{
for（v=1;v>=-1;v--）{
if（w!
=0||v!
=0）{
x+=w;y+=v;step++;//第w，v个值可选
Q[step][0]=x;Q[step][1]=y;
if（MARK[x][y]==0&&MAZE[x][y]==0）backtrack（x,y,step,m,n）;
step--;x-=w;y-=v;
}
}
}
}
return;
}
intmain（）{
intm,n;
printf（"请输入迷宫的行数:
\nm="）;
scanf_s（"%d",&m）;
printf（"请输入迷宫的列数:
\nn="）;
scanf_s（"%d",&n）;
MAZE=CreateArr（m+2,n+2）;
MARK=CreateArr（m+2,n+2）;
Q=CreateArr（m*n,2）;
srand（（unsigned）time（NULL））;
inti,j,p;
for（i=0;i<=n+1;i++）{//第0行用
MAZE[0][i]=-5;
MAZE[m+1][i]=-5;
}
for（i=0;i<=m+1;i++）{//第0列不用
MAZE[i][0]=-5;
MAZE[i][n+1]=-5;
}
for（i=1;ifor（j=1;jp=rand（）%10%2;//x的值为0或1
MAZE[i][j]=p;
}
}
MAZE[1][1]=0;//入口为0
MAZE[m][n]=0;//出口为0
for（i=1;ifor（j=1;jprintf（"%d",MAZE[i][j]）;
}
printf（"\n"）;
}
//递归中超界，对MARK[][]特殊处理
for（i=1;ifor（j=1;jMARK[i][j]=0;
}
}
for（i=0;i<=m+1;i++）{
MARK[i][n+1]=1;
MARK[i][0]=1;
}
for（i=0;i<=n+1;i++）{
MARK[m+1][i]=1;
MARK[0][i]=1;
}
MARK[1][1]=1;
Q[1][0]=1;
Q[1][1]=1;
backtrack（1,1,1,m,n）;
printf（"\n"）;
if（flag==0）
printf（"THEREISNOPATH.\n"）;
return0;
}
8．程序截图：
9.实验总结
1、开始没有将M[n][m].start.end设置为MAZE型数据的下属单元，使得各个迷宫操作的函数参数十分散杂，调试时各参数关系不易把握。
2、另行设置Print函数，使得终端输出更加友好，并巧妙地将迷宫以特殊、明朗的字符输出，效果更好。
3、开始的条件没有控制好，导致输出时不是完整路径，甚至出错。
4、选择方向时有一定策略，开始选择时按照顺时针依次读取方向，发现太耗时且效果不好，容易出现不必要的弯折走法，后来通过控制方向顺序，即第一方向为东南方，然后再东方、南方...，选取越靠近出口的方向为优先方向，因为这样的话搜索路径时自然会本着路径最短的原则向出口处行进，那么找到的路径自然是最短路径（之一）。
5、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况，比如先往东再往西南，其实是可以直接往南的，因此为了避免这种情况，在入栈时还要先进行这种情况的判断，如是这种情况则出栈将前一位置方向改变再入栈。
6、为了便于找到最短路径，起初只使用了靠近出口处的五个方向，但是发现有特殊情况存在时由于不能想远离出口的方向行进而找不到路径，因此在搜索路径时进行了两次搜索，第一次使用五个靠进出口的方向搜索，找到路径时则返回，若未搜索到则再进行一次八个方向的搜索，即为了防止漏掉特殊情况，找到时则返回，由于第一搜索无结果若第二次搜索到路径也只能是特殊情况，故也应该是最短路径（之一）。
7、最大的问题是并没有按照题目要求来做，因为题目中要求用队列来存储路径。
10.实验心得体会
根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业实验课，多在实践中锻炼自己。
2、写程序的过程中要考虑周到，严密。
3、在做设计的时候要有信心，有耐心，切勿浮躁。
4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
每个实验通常都要花费很久的时间才能理清一个程序的思路，而且要不断的调试程序才能把程序调试正确，同时还要做到界面的输出也是需要美化的。
这次课程设计终于顺利完成了，在设计中遇到了很多专业知识问题，最后在老师的辛勤指导下，也完成了课程设计。
通过这次的课程设计，让我更加了解到数据结构的重要性。
以及它对我们专业的发展发挥的作用。
对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。
让我知道了学无止境的道理。
我们每一个人永远不能满足于现有的成就。
这次课程设计必将成为我人生旅途上一个非常美好的回忆！
同时在做课程设计时要能够从多方面去考虑，去研究，用多种算法去实现要求。
此次课程设计，学到了很多课内学不到的东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅，今后的制作应该能够更轻松，自己也都能够解决并高质量的完成项目。
升级会员 