迷宫最短路径 数据结构 源码 实验报告.doc

实 验 报 告课程名称 数据结构 实验名称 迷宫最短路径 实验类型 综合型 实验地点 计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)如无通道，则打印： THERE IS NO PATH.实现提示(1)数据结构为了在程序中判断方便，把迷宫扩展成为MAZE(0.m+1，0.n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。用二维数组MOVE(1.8，1.2)存放八个方向上的位置量，如图所示： (i+MOVE1，1， j+MOVE1，2) (i+MOVE8，1， j+MOVE8，2) (i+MOVE2，1， j+MOVE2，2) (i+MOVE7，1， j+MOVE7，2) (i+MOVE3，1， j+MOVE3，2) (i+MOVE6，1， j+MOVE6，2) (i+MOVE4，1， j+MOVE4，2) (i+MOVE5，1， j+MOVE5，2) MOVE的设置情况 i j121-102-1130141151061-170-18-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)以二维数组mazeM+2N+2表示迷宫，其中mazei0和mazeiN+1(0=i=N+1)以及maze0j和mazeM+1j(0=j=0数据关系：R1 | a(i-1),aiD,i = 2,3n基本操作： InitStack(&S) 操作结果：构造一个空栈S。DestroyStack(&S) 初始结果：栈S已存在。 操作结果：销毁栈S。ClearStack(&S) 初始结果：栈S已存在。 操作结果：将S清为空栈。StackLength(S) 初始结果：栈S已存在。 操作结果：返回栈S的长度StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSEGetTop(S,&e) 初始条件：栈S已存在。 操作结果：若栈S不空，则以e返回栈顶元素e。Push(&S,e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素。Pop(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit() 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用visit()ADT Stack(2) 设定迷宫的抽象数据类型为：ADT maze 数据对象：D = a(i,j) | a(i,j)0,1，0=i=m+1,0=j=n+1,m,n=10 数据关系：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) 初始条件：二维数组mazem+1n+1 已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障碍。 操作结果：构成迷宫的字符型数组，以字符0表示通路，以字符1障碍，并在迷宫四周加上一圈障碍。 MazePath(&M)初始条件：迷宫M已被赋值。 操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以数字0代表可通过，数字1代表不可通过.6.模块划分(1) 主程序模块： void main() int stoMN; struct mark start,end; /start,end入口和出口的坐标 int add42=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); /find path system(PAUSE); (2) 栈模块实现栈抽象数据类型；(3) 迷宫模块实现迷宫抽象数据类型，建立迷宫，求解迷宫的一条路径。7.源程序代码:#include stdafx.h#include #include#includeint * CreateArr(int m, int n)/创建动态全局二维数组int i;int *p;p = (int*)malloc(sizeof(int*)*m);for (i = 0; i =1;i-)j=0;printf(%d,%d),Qij,Qij+1);printf(n); void backtrack(int x,int y,int step,int m,int n)MARKxy=1;int w,v;if(x=m & y=n)flag=1;Qstep0=x;Qstep1=y;print(step);return;elsefor( w=1;w=-1;w-)for( v=1;v=-1;v-)if(w!=0 | v!=0) x+=w;y+=v;step+;/第w，v个值可选 Qstep0=x;Qstep1=y;if(MARKxy=0 & MAZExy=0) backtrack(x,y,step,m,n);step-;x-=w;y-=v;return;int main()int m,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);int i,j,p;for(i=0;i=n+1;i+)/第0行用 MAZE0i=-5;MAZEm+1i=-5;for(i=0;i=m+1;i+)/第0列不用 MAZEi0=-5;MAZEin+1=-5;for(i=1;im+1;i+)/其余的随机生成0或1 for(j=1;jn+1;j+)p=rand()%10%2;/x的值为0或1 MAZEij=p;MAZE11=0;/入口为0 MAZEmn=0;/出口为0 for(i=1;im+1;i+)/0行0列不显示 for(j=1;jn+1;j+)printf(%d ,MAZEij);printf(n);/递归中超界，对MARK特殊处理 for(i=1;im+1;i+)/MARK全体置为零 for(j=1;jn+1;j+) MARKij=0; for(i=0;i=m+1;i+) MARKin+1=1;MARKi0=1; for(i=0;i=n+1;i+) MARKm+1i=1; MARK0i=1; MARK11=1;Q10=1;Q11=1;backtrack(1,1,1,m,n); printf(n);if(flag=0)printf(THERE IS NO PATH.n);return 0; 8程序截图： 9. 实验总结1、开始没有将Mnm.start.end设置为MAZE 型数据的下属单元，使得各个迷宫操作的函数参数十分散杂，调试时各参数关系不易把握。2、另行设置Print函数，使得终端输出更加友好，并巧妙地将迷宫以特殊、明朗的字符输出，效果更好。3、开始的条件没有控制好，导致输出时不是完整路径，甚至出错。4、选择方向时有一定策略，开始选择时按照顺时针依次读取方向，发现太耗时且效果不好，容易出现不必要的弯折走法，后来通过控制方向顺序，即第一方向为东南方，然后再东方、南方.，选取越靠近出口的方向为优先方向，因为这样的话搜索路径时自然会本着路径最短的原则向出口处行进，那么找到的路径自然是最短路径（之一）。5、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况，比如先往东再往西南，其实是可以直接往南的，因此为了避免这种情况，在入栈时还要先进行这种情况的判断，如是这种情况则出栈将前一位置方向改变再入栈。6、为了便于找到最短路径，起初只使用了靠近出口处的五个方向，但是发现有特殊情况存在时由于不能想远离出口的方向行进而找不到路径，因此在搜索路径时进行了两次搜索，第一次使用五个靠进出口的方向搜索，找到路径时则返回，若未搜索到则再进行一次八个方向的搜索，即为了防止漏掉特殊情况，找到时则返回，由于第一搜索无结果若第二次搜索到路径也只能是特殊情况，故也应该是最短路径（之一）。7、最大的问题是并没有按照题目要求来做，因为题目中要求用队列来存储路径。10. 实验心得体会根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。每个实验通常都要花费很久的时间才能理清一个程序的思路，而且要不断的调试程序才能把程序调试正确，同时还要做到界面的输出也是需要美化的。这次课程设计终于顺利完成了，在设计中遇到了很多专业知识问题，最后在老师