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

《迷宫最短路径 数据结构 源码 实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.实验报告课程名称数据结构实验名称迷宫最短路径实验类型综合型实验地点计405机房实验日期2017.5.13指导教师海平专业软件工程班级软件1601学号1611030102寇春雷石油化工大学计算机与通信工程学院word范文.数据结构实验报告评分表项目要求分数有无项目（√）得分预习报告（30分）实验目的明确5实验容理解透彻5实验方案设计完整合理程序总体框架设计完整10完成相关辅助代码5测试方案合理5实验过程（30分）发现问题5问题的分析15问题的解决方法10实验报告（20分）容翔实无缺漏5如实记录实验过程10撰写规整5实验总结（10分）实验结果的分析5按照结果对原实验方案的改进意见5实验体会（10

2、分）实验的收获5实验容的发散考虑5总分word范文.实验二迷宫最短路径题目：迷宫最短路径⒈问题描述从一个迷宫的入口到出口找出一条最短路经。用一个二维数组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)如无通道，则打印：THEREISN

3、OPATH.⒊实现提示(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[

4、6，2])(i+MOVE[4，1]，j+MOVE[4，2])(i+MOVE[5，1]，j+MOVE[5，2])MOVE的设置情况ij12word范文.1-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）算法基本思想将入

5、口（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从数组中重新取出一个位置作为

6、新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。4.需求分析(1)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0=

7、建迷宫②求解迷宫③输出迷宫的解5.概要设计5.1抽象数据类型定义word范文.(1)设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai

8、ai∈CharSet，i=1,2，…,n，n>=0}数据关系：R1{

9、a(i-1),ai∈D,i=2,3…n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始结果：栈S已存在。操作结果