数据结构课设

数据结构课程设计实验报告专业信息管理与信息系统班级1203601学号120360114姓名郭鑫指导教师杨美荣求迷宫最短路径---试从一个迷宫（maze）的入口到出口找出一条最短路经1.问题描述：迷宫问题是实验心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫，迷宫中设置了很多墙壁，对前进方向形成了多处障碍。心里学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则将得到一条最佳线路。求解此迷宫问题固然可以使用递归算法，但是，这里要求不使用递归算法，而是应用顺序堆栈实现迷宫问题的非递归解法。设迷宫用一个二维整数数组maze[m][p]表示（m行，p列），并且各个元素只取0值或1值。若某个元素的值为1，则表示此处无通路；若某个元素的值为0，则表示此处为通路。同时，还设定迷宫的入口为第一个元素maze[0][0]处，出口为最后一个元maze[m-1][p-1]处。另外，若存在最短路经，则输出由出口到入口这一条路径；若不存在最短路经，则输出提示信息：THEREISNOPATHINMAZE.⒉设计：⑴概要设计：求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前试探，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯)，需要用一个后进先出的堆栈来保存从入口到当前位置的路径。Maze()11）（MN）路径，包不使用return语句退出，而是出栈一次回溯走另一条路径，并用minlen记录最短路径长度，Path数组记录最短路径。为了在程序中判断方便，把迷宫扩展成为maze[m+2][p+2]，即在迷宫的四周增加一圈围墙，扩展部分（即第0行和第m-1行、第0列和第p-1列）的元素设置为1，借次实现在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置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)西北：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].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;//方向}当在迷宫中向前搜索时，可能同时存在几个允许的前进方向。可以利用三元组记下当前位置和上一步前进方向，然后根据表-1选择某一个允许的前进方向前进一步，并将有关信息入栈，以记下前进路径。如果该前进方向走不通，则将位于栈顶的元素退栈，即在前进路径上回退一步，再尝试其它的允许方向。如果栈空，则表示已经回退到开始位置。⑵详细设计：Math():packagechapter10;publicclassMaze{int[][]maze;intnumOfDir=8;intcount=1;//路径数计数器，记录共有多少条路径intMaxSize;intminlen;//记录最短路径长度（即经历的方块个数）inta,b;inti,j,di,find,k;Path[]path;//记录路径数组Pathtemp1=newPath(i,j,di);Pathtemp2=newPath(i,j,di);Pathtemp3=newPath();SeqStackmystack;Offsets[]move=newOffsets[numOfDir];publicvoidgetOut(int[][]myMaze,Coordinatebegin,Coordinateend){/**表-1前进方向表下标(方向d)ab0:北-101:东北-112:东013:东南114:南105:西南1-16:西0-17:西北-1-1*/move[0]=newOffsets(-1,0);move[1]=newOffsets(-1,1);move[2]=newOffsets(0,1);move[3]=newOffsets(1,1);move[4]=newOffsets(1,0);move[5]=newOffsets(1,-1);move[6]=newOffsets(0,-1);move[7]=newOffsets(-1,-1);maze=myMaze;intm=maze.length;intn=maze[0].length;a=end.x;b=end.y;MaxSize=(m)*(n);minlen=MaxSize;mystack=newSeqStack(MaxSize);path=newPath[MaxSize];for(inth=0;hMaxSize;h++)path[h]=newPath();temp1.x=begin.x;temp1.y=begin.y;temp1.dir=-1;mystack.Push(temp1);//初始化方块进栈maze[begin.x][begin.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){//找到了出口路径System.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++){path[k].x=mystack.GetElement(k).x;path[k].y=mystack.GetElement(k).y;path[k].dir=mystack.GetElement(k).dir;}minlen=mystack.top;}temp1=mystack.Pop();//栈顶元素出栈maze[temp1.x][temp1.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)ab0:北-101:东北-112:东013:东南114:南105:西南1-16:西0-17:西北-1-1*/case0:i=temp2.x+move[0].x;j=temp2.y+move[0].y;break;case1:i=temp2.x+move[1].x;j=temp2.y+move[1].y;break;case2:i=temp2.x+move[2].x;j=temp2.y+move[2].y;break;case3:i=temp2.x+move[3].x;j=temp2.y+move[3].y;break;case4:i=temp2.x+move[4].x;j=temp2.y+move[4].y;break;case5:i=temp2.x+move[5].x;j=temp2.y+move[5].y;break;case6:i=temp2.x+move[6].x;j=temp2.y+move[6].y;break;case7:i=temp2.x+move[7].x;j=temp2.y+move[7].y;break;}if(maze[i][j]==0)find=1;}if(find==1){//找到了下一个可走方案mystack.GetTop().dir=di;//+++++++++++++++++++++++++++++++++temp3.x=i;temp3.y=j;temp3.dir=-1;mystack.Push(temp3);//下一个可走方块进栈maze[i][j]=-1;//避免重复走到该方块}else{//没有路径可走,则退栈temp1=mystack.Pop();maze[temp1.x][temp1.y]=0;//让该位置变为其他路径可走方块}}if(minlen==MaxSize){System.out.println(THEREISNOPATHINMAZE);}else{System.out.println(最短路径如下：);System.out.println(长度+minlen);System.out.println(路径：);for(k=0;kminlen;k++)System.out.print((+path[k].x+,+path[k].y+));}System.out.println();}}SeqStackpackagechapter10;publicclassSeqStack{protectedinttop;protectedPath[]Data;protectedintMaxSize;publicSeqStack(int_maxsize){MaxSize=_maxsize;Data=newPath[MaxSize];for(inth=0;hMaxSize;h++){Data[h]=newPath();}}publicvoidPush(Pathitem){if(top==MaxSize){System.out.println(堆栈已满);return;}Data[top].x=item.x;Data[top].y=item.y;Data[top].dir=item.dir;top++;}publicPathPop(){if(top==0){System.out.println(堆栈已空);returnnull;}top--;returnData[top];}publicPathGetTop(){