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

(√)得分预****报告(30分)实验目的明确5实验内容理解透彻5实验方案设计完整合理程序总体框架设计完整10完成相关辅助代码5测试方案合理5实验过程(30分)发现问题5问题的分析15问题的解决方法10实验报告(20分)内容翔实无缺漏5如实记录实验过程10撰写规整5实验总结(10分)实验结果的分析5按照结果对原实验方案的改进意见5实验体会实验的收获5(10分)实验内容的发散考虑5总分实验二迷宫最短路径题目:迷宫最短路径⒈问题描述从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1..m,1..n)模拟迷宫,数组元素为0表示该位置可以通过,数组元素为1表示该位置不可以通行。MAZE(1,1)和MAZE(m,n)分别为迷宫的入口和出口。⒉基本要求(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数组中已经没有位置可以作为新的出发点了,则表示迷宫没有通路。(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)程序执行的命令为:①创建迷宫②求解迷宫③(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)初