《数据结构课设(共11页).docx》由会员分享，可在线阅读，更多相关《数据结构课设(共11页).docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 数据结构课程设计实 验 报 告专 业 信息管理与信息系统班 级 学 号 姓 名 郭 鑫 指导教师 杨美荣 求迷宫最短路径-试从一个迷宫（maze）的入口到出口找出一条最短路经1. 问题描述： 迷宫问题是实验心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫，迷宫中设置了很多墙壁，对前进方向形成了多处障碍。心里学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则将得到一条最佳线路。求解此迷宫问题固然可以使用递归算法，但是，这里要求不使用递归算法，而是应用顺序堆
2、栈实现迷宫问题的非递归解法。设迷宫用一个二维整数数组mazemp表示（m行，p列），并且各个元素只取0值或1值。若某个元素的值为1，则表示此处无通路；若某个元素的值为0，则表示此处为通路。同时，还设定迷宫的入口为第一个元素maze00处，出口为最后一个元mazem-1p-1处。另外，若存在最短路经，则输出由出口到入口这一条路径； 若不存在最短路经，则输出提示信息：THERE IS NO PATH IN MAZE. 设计： 概要设计：求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前试探，若能走通，则继续往前走；否则沿原路退回，换一个方向再
3、继续试探，直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯)，需要用一个后进先出的堆栈来保存从入口到当前位置的路径。Maze()求解迷宫问题即输出从（11）到（MN）的全部路径和最短路径，包含最短路径长度。当找到一条路径时，不使用return语句退出，而是出栈一次回溯走另一条路径，并用minlen记录最短路径长度，Path数组记录最短路径。为了在程序中判断方便，把迷宫扩展成为mazem+2p+2，即在迷宫的四周增加一圈围墙，扩展部分（即第0行和第m-1行、第0列和第p-1列）的元素设置为1，借次实现在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置mazeij上
4、都有8个可以移动的方向即：北： mazei-1j -用0表示此方向(d=0)东北： mazei-1j+1 -用1表示此方向(d=1) 东： mazeij+1 -用2表示此方向(d=2)东南： mazei+1j+1 -用3表示此方向(d=3)南： mazei+1j -用4表示此方向(d=4)西南： mazei+1j-1 -用5表示此方向(d=5)西： mazeij-1 -用6表示此方向(d=6)西北： mazei-1j-1 -用7表示此方向(d=7)b）用结构数组move8存放八个方向上的位置偏移量，如表-1所示： 表-1 前进方向表下标(方向d) a b 0:北 -1 0 1:东北 -1 1
5、2:东 0 1 3:东南 1 1 4:南 10 5:西南1-1 6:西0-1 7:西北 -1-1 数组move8的数据类型为： class offsets int a; /相对于点ij的i的某个方向位置偏移量int b; /相对于点ij的j的某个方向位置偏移量这样，如果当前位置在ij时，若向西南方向（d=5）行走，那么下一相邻位置gh则为 g=i+move5.a=i+1; h=j+move5.b=j-1; 位置标记为了标志已经通过的位置，并防止重走原路，则另设一个标志数组markm+2p+2，其初值为0，在寻找路径的过程中，若通过了位置ij，则将markij置为为1,以防再次通过此位置。 算法
6、基本思想将入口maze11作为第一个出发点，直至达到出口mazemp,或者迷宫所有位置都搜索完毕为止。用栈来保存在试探性的前进过程中所走过的路径。栈中需保存一系列三元组以记录所走过的路径信息，这些三元组的数据类型为： class Pathint x; /行坐标int y; /列坐标int dir; /方向 当在迷宫中向前搜索时，可能同时存在几个允许的前进方向。可以利用三元组记下当前位置和上一步前进方向，然后根据表-1选择某一个允许的前进方向前进一步，并将有关信息入栈，以记下前进路径。如果该前进方向走不通，则将位于栈顶的元素退栈，即在前进路径上回退一步，再尝试其它的允许方向。如果栈空，则表示已经
7、回退到开始位置。 详细设计：Math():package chapter10;public class Maze int maze;int numOfDir = 8 ;int count = 1; /路径数计数器，记录共有多少条路径int MaxSize;int minlen; /记录最短路径长度（即经历的方块个数）int a,b;int i,j,di,find,k;Path path; /记录路径数组Path temp1 = new Path(i,j,di); Path temp2 = new Path(i,j,di);Path temp3 = new Path();SeqStack mys
8、tack ;Offsets move = new OffsetsnumOfDir;public void getOut(int myMaze,Coordinate begin,Coordinate end)/* * 表-1 前进方向表下标(方向d) a b 0:北 -1 0 1:东北 -1 1 2:东 0 1 3:东南 1 1 4:南 1 0 5:西南 1-1 6:西 0-1 7:西北 -1-1 */move0 = new Offsets(-1,0);move1 = new Offsets(-1,1);move2 = new Offsets(0,1);move3 = new Offsets(1
9、,1);move4 = new Offsets(1,0);move5 = new Offsets(1,-1);move6 = new Offsets(0,-1);move7 = new Offsets(-1,-1);maze = myMaze ; int m = maze.length ;int n = maze0.length; a = end.x;b = end.y;MaxSize = (m)*(n);minlen = MaxSize;mystack = new SeqStack(MaxSize);path = new PathMaxSize;for(int h = 0;hMaxSize;
10、h+)pathh = new Path();temp1.x=begin.x; temp1.y=begin.y;temp1.dir=-1;mystack.Push(temp1);/初始化方块进栈mazebegin.xbegin.y=-1;while(mystack.NotEmpty()/栈不空时循环temp2.x = mystack.GetTop().x;temp2.y = mystack.GetTop().y;temp2.dir = mystack.GetTop().dir;i= temp2.x; j= temp2.y; di= temp2.dir;if(i=a&j=b) /找到了出口路径Sy
11、stem.out.println(第+ count+ +条路径是：);for(k=0;kmystack.top;k+)temp1=mystack.GetElement(k);System.out.print( + temp1.x +,+ temp1.y + );System.out.println();if(mystack.topminlen)/比较最短路径for(k=0;kmystack.top;k+)pathk.x=mystack.GetElement(k).x;pathk.y=mystack.GetElement(k).y;pathk.dir=mystack.GetElement(k).
12、dir;minlen=mystack.top;temp1=mystack.Pop();/栈顶元素出栈 mazetemp1.xtemp1.y=0; /让该方块变为其它路径可走方块temp2.x=mystack.GetTop().x;temp2.y=mystack.GetTop().y;temp2.dir=mystack.GetTop().dir;i=temp2.x;j=temp2.y;di=temp2.dir;find=0;while (di8 & find=0)/找下一个可走方块di+;switch(di)/* * 表-1 前进方向表下标(方向d) a b 0:北 -1 0 1:东北 -1 1
13、 2:东 0 1 3:东南 1 1 4:南 1 0 5:西南 1-1 6:西 0-1 7:西北 -1-1 */case 0:i=temp2.x+move0.x; j= temp2.y+move0.y; break;case 1:i=temp2.x+move1.x; j= temp2.y+move1.y; break;case 2:i=temp2.x+move2.x; j= temp2.y+move2.y; break;case 3:i=temp2.x+move3.x; j= temp2.y+move3.y; break;case 4:i=temp2.x+move4.x; j= temp2.y+
14、move4.y; break;case 5:i=temp2.x+move5.x; j= temp2.y+move5.y; break;case 6:i=temp2.x+move6.x; j= temp2.y+move6.y; break;case 7:i=temp2.x+move7.x; j= temp2.y+move7.y; break;if (mazeij=0) find=1;if (find=1) /找到了下一个可走方案mystack.GetTop().dir = di;/+temp3.x = i; temp3.y = j; temp3.dir =-1;mystack.Push(temp
15、3); /下一个可走方块进栈mazeij=-1; /避免重复走到该方块else /没有路径可走,则退栈temp1=mystack.Pop();mazetemp1.x temp1.y=0; /让该位置变为其他路径可走方块if(minlen = MaxSize) System.out.println(THERE IS NO PATH IN MAZE);elseSystem.out.println(最短路径如下：);System.out.println(长度 + minlen);System.out.println(路径： );for(k=0;kminlen;k+)System.out.print(
16、 + pathk.x + , + pathk.y + );System.out.println();SeqStackpackage chapter10;public class SeqStack protected int top;protected Path Data;protected int MaxSize; public SeqStack(int _maxsize) MaxSize = _maxsize; Data= new PathMaxSize; for(int h = 0;hMaxSize;h+) Datah = new Path(); public void Push(Path
17、 item) if(top=MaxSize) System.out.println(堆栈已满); return ; Datatop.x=item.x; Datatop.y = item.y; Datatop.dir = item.dir; top+; public Path Pop() if(top=0) System.out.println(堆栈已空); return null; top-; return Datatop; public Path GetTop() if(top=0) System.out.println(堆栈已空); return null; return Datatop-
18、1; public Path GetElement(int p) if(top=0) System.out.println(堆栈已空); return null; return Datap; public boolean NotEmpty() if(top!=0) return true; return false; Path()package chapter10;public class Path int x; /行坐标int y; /列坐标int dir; /方向Path(int a,int b, int di)x = a ;y = b ;dir = di;Path(int a,int b
19、)x = a ;y = b ;dir = -1;Path()x = -1;y = -1;dir = -1; 测试： Test() package chapter10;import java.util.Scanner;public class Test public static void main(String args) throws Exception System.out.println( ); int maze1= 1,1,1,1,1,1,1,0,1,0,1,1,1,0,0,1,0,1,1,0,1,0,0,1,1,1,0,0,0,1,1,1,1,1,1,1; System.out.pr
20、intln(所要走的迷宫1为：);/开始打印初始的迷宫for(int i=0;imaze1.length;i+)for(int j=0;jmaze10.length;j+)if(maze1ij=1)System.out.print();elseSystem.out.print( );System.out.println();int maze2= 1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1;System.out.println(所要走的迷宫2为：);/开始打印初始的迷宫for(int i=0;im
21、aze2.length;i+)for(int j=0;jmaze20.length;j+)if(maze2ij=1)System.out.print();elseSystem.out.print( );System.out.println(); Maze myMaze = new Maze(); Scanner reader=new Scanner(System.in); System.out.println(start point); int a=reader.nextInt(); int b=reader.nextInt(); System.out.println(over point);
22、 int c=reader.nextInt(); int d=reader.nextInt(); Coordinate begin = new Coordinate(a,b);Coordinate end = new Coordinate(c,d);System.out.println(Maze 1:);myMaze.getOut(maze1, begin, end);System.out.println();System.out.println(Maze 2:);myMaze.getOut(maze2, begin, end); 使用说明和设计小结： 使用时点击运行Test()，会出现提示：
23、请输入起始位置，分别输入起始位置的两个坐标。输入完毕后会出现提示：请输入结束位置，在此分别输入迷宫的终点坐标，点击ENTER键。之后程序就会运行并输出结果。 程序的可视化不够，没有设计图形显示，并且主要思想还是参照老师所给的实现提示。这次的课程设计加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解提高综合运用本课程所学知识的能力。培养了我选用参考书查阅手册及文献资料的能力。培养独立思考深入研究分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试掌握应用软件的分析方法和工程设计方法。通过课程设计培养了我严肃认真的工作作风逐步建立正确的生产观念、经济观念和全局观念。而且做
24、课程设计同时也是对课本知识的巩固和加强平时看课本时有些问题就不是很能理解做完课程设计那些问题就迎刃而解了。而且还可以记住很多东西。认识来源于实践实践是认识的动力和最终目的实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。这次的课程设计使我懂得了理论与实际相结合是很非常重要的只有理论知识是远远不够的只有把所学的理论知识与实践相结合起来从理论中得出结论才能真正为社会服务从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中构思是很花费时间的。调试时经常会遇到这样那样的错误有的是因为粗心造成的语法错误。当然很多也时用错了方法总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。 打印一份程序清单及运行示例的结果。 程序清单如上详细设计。 运行示例结果： 专心-专注-专业