搜索
实验报告课程名称数据结构实验名称迷宫最短路径实验类型综合型实验地点计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的设置情况ij121-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)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0=i=N+1)以及maze[0][j]和maze[M+1][j](0=j=M+1)为外加的一圈围墙。数组中元素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)|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，否则返回FALSEGetTop(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=i=m+1,0=j=n+1,m,n=10}数据关系：R={M，N}M={a(i-1,j)，a(i,j)|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)|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);//findpathsystem(PAUSE);}(2)栈模块——实现栈抽象数据类型；(3)迷宫模块——实现迷宫抽象数据类型，建立迷宫，求解迷宫的一条路径。7.源程序代码:#includestdafx.h#includestdio.h#includecstdlib#includectimeint**CreateArr(intm,intn){//创建动态全局二维数组inti;int**p;p=(int**)malloc(sizeof(int*)*m);for(i=0;im;i++){p[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;im+1;i++){//其余的随机生成0或1for(j=1;jn+1;j++){p=rand()%10%2;//x的值为0或1MAZE[i][j]=p;}}MAZE[1][1]=0;//入口为0MAZE[m][n]=0;//出口为0for(i=1;im+1;i++){//0行0列不显示for(j=1;jn+1;j++){printf(%d,MAZE[i][j]);}printf(\n);}//递归中超界，对MARK[][]特殊处理for(i=1;im+1;i++){//MARK全体置为零for(j=1;jn+1;j++){MARK[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、由于八个方向的特殊性，根据方向的顺序，搜索路径时仍会出现多走的情况，比如先往东再往西南，其实是可以直接往南的，因此为了避免这种情况，在