数据结构课设.docx

数据结构课设.docx

ID:58578179

大小:41.78 KB

页数:11页

时间:2020-10-19

数据结构课设.docx_第1页
数据结构课设.docx_第2页
数据结构课设.docx_第3页
数据结构课设.docx_第4页
数据结构课设.docx_第5页
资源描述:

《数据结构课设.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、数据结构课程设计实验报告专业信息管理与信息系统班级学号姓名郭鑫指导教师杨美荣求迷宫最短路径---试从一个迷宫(maze)的入口到出口找出一条最短路经1.问题描述:迷宫问题是实验心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子(迷宫)的入口处赶进迷宫,迷宫中设置了很多墙壁,对前进方向形成了多处障碍。心里学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。如果从迷宫的入口到达出口,途中不出现行进方向错误,则将得到一条最佳线路。求解此迷宫问题固然可以使用递归算法,但是,这里要求不使用递归算法,而是应用顺序堆栈实现迷宫问题的非递归解法。设

2、迷宫用一个二维整数数组maze[m][p]表示(m行,p列),并且各个元素只取0值或1值。若某个元素的值为1,则表示此处无通路;若某个元素的值为0,则表示此处为通路。同时,还设定迷宫的入口为第一个元素maze[0][0]处,出口为最后一个元maze[m-1][p-1]处。另外,若存在最短路经,则输出由出口到入口这一条路径;若不存在最短路经,则输出提示信息:THEREISNOPATHINMAZE.⒉设计:⑴概要设计:求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走;否则沿原路退回,换

3、一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的堆栈来保存从入口到当前位置的路径。Maze()求解迷宫问题即输出从(11)到(MN)的全部路径和最短路径,包含最短路径长度。当找到一条路径时,不使用return语句退出,而是出栈一次回溯走另一条路径,并用minlen记录最短路径长度,Path数组记录最短路径。为了在程序中判断方便,把迷宫扩展成为maze[m+2][p+2],即在迷宫的四周增加一圈围墙,扩展部分(即第0行和第m-1行、第0列和第p-1列)的元素设置为1,借次实现在迷宫周

4、围布上一圈不准通过的墙,这样,在迷宫的任一位置maze[i][j]上都有8个可以移动的方向即:北:maze[i-1][j]-------用0表示此方向(d=0)东北:maze[i-1][j+1]-------用1表示此方向(d=1)东:maze[i][j+1]-------用2表示此方向(d=2)东南:maze[i+1][j+1]-------用3表示此方向(d=3)南:maze[i+1][j]-------用4表示此方向(d=4)西南:maze[i+1][j-1]-------用5表示此方向(d=5)西:maze[i][j-1]-------用6表示此方向(d=6

5、)西北:maze[i-1][j-1]-------用7表示此方向(d=7)b)用结构数组move[8]存放八个方向上的位置偏移量,如表-1所示:表-1前进方向表下标(方向d)ab0:北-101:东北-112:东013:东南114:南105:西南1-16:西0-17:西北-1-1数组move[8]的数据类型为:classoffsets{inta;//相对于点[i][j]的i的某个方向位置偏移量intb;//相对于点[i][j]的j的某个方向位置偏移量}这样,如果当前位置在[i][j]时,若向西南方向(d=5)行走,那么下一相邻位置[g][h]则为g=i+move[5]

6、.a=i+1;h=j+move[5].b=j-1;②位置标记为了标志已经通过的位置,并防止重走原路,则另设一个标志数组mark[m+2][p+2],其初值为0,在寻找路径的过程中,若通过了位置[i][j],则将mark[i][j]置为为1,以防再次通过此位置。③算法基本思想将入口maze[1][1]作为第一个出发点,直至达到出口maze[m][p],或者迷宫所有位置都搜索完毕为止。用栈来保存在试探性的前进过程中所走过的路径。栈中需保存一系列三元组以记录所走过的路径信息,这些三元组的数据类型为:classPath{intx;//行坐标inty;//列坐标intdir;

7、//方向}当在迷宫中向前搜索时,可能同时存在几个允许的前进方向。可以利用三元组记下当前位置和上一步前进方向,然后根据表-1选择某一个允许的前进方向前进一步,并将有关信息入栈,以记下前进路径。如果该前进方向走不通,则将位于栈顶的元素退栈,即在前进路径上回退一步,再尝试其它的允许方向。如果栈空,则表示已经回退到开始位置。⑴详细设计:Math():packagechapter10;publicclassMaze{int[][]maze;intnumOfDir=8;intcount=1;//路径数计数器,记录共有多少条路径intMaxSize;intminlen;//记

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。