基于栈的走迷宫最短路径实现

课程设计说明书(论文)题目课程名称数据结构课程设计院（系、部、中心）计算机工程学院专业班级学生姓名学号设计地点设计起止时间：2016年12月25日至2016年12月31日成绩－1－数据结构课程设计题目（例如表达式求值问题求解）一、课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。要求：熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二、题意说明及分析一个迷宫如图所示，它有一个入口和出口，其中白色单元表示通路，黑色单元表示路不通。寻找一条从入口到出口的路径，每步只能从一个白色单元走到相邻的白色单元，直至出口。使用栈实现走迷宫的功能，演示走迷宫的过程。可走的白色单元用0表示，不可走的黑色单元用1表示，使用栈，栈顶元素temp标记位置，走出迷宫。输出迷宫和走出路径。入口↓→↓↓↓←↓→→→→→→↑－2－三、算法设计与分析用ArrayListcoordition作为栈的数据结。ArrayList是java中Collection集合中线性表，可以通过add.remove操作添加删除元素，coordition是定义的内部类，用来存放一个节点的横纵坐标。这样，栈中的每个元素就是迷宫中一个位置的坐标。寻路算法(若存在路径，返回true；若不存在，返回false)：while栈非空获取栈顶元素temp=stack.getTopiftemp是出口位置跳出循环else继续向下执行iftemp上边可走andtemp上边未遍历把temp所在位置标记为已遍历，将temp上边的位置加入栈顶进入下一次循环iftemp右边可走andtemp右边未遍历把temp所在位置标记为已遍历，将temp右边的位置加入栈顶进入下一次循环iftemp下边可走andtemp下边未遍历把temp所在位置标记为已遍历，将temp下边的位置加入栈顶进入下一次循环iftemp左边可走andtemp左边未遍历把temp所在位置标记为已遍历，将temp左边的位置加入栈顶进入下一次循环上下左右都不可走，标记temp为已读，并从栈中移出，进入下次循环最后退出while循环有两种情况：1）找到出口位置，那栈中保留的就是从入口到出口的路径2）栈为空，说明没有路径能从入口到出口－3－四、源程序packagecom.test;importjava.util.ArrayList;importjava.util.List;publicclassMaprinth{privateint[][]map;//存放迷宫矩阵，0表示可走，1表示不可走privatecoordinatestart;//记录起点坐标privatecoordinateend;//记录终点坐标privateListcoordinatestack;//栈/**坐标**/classcoordinate{publicintx;publicinty;publiccoordinate(intx,inty){this.x=x;this.y=y;}}/**入栈***/publicvoidpush(coordinateco){if(this.stack!=null){this.stack.add(co);}elsethis.stack=newArrayList();stack.add(co);}/**获取栈顶元素**/publiccoordinategetTop(){if(!stack.isEmpty()){returnstack.get(stack.size()-1);}elsereturnnull;}/*－4－*出栈操作**/publiccoordinatepop(){if(!stack.isEmpty())returnstack.remove(stack.size()-1);elsereturnnull;}/**产生例题的迷宫矩阵**/publicvoidgeneratemap2(){map=newint[6][6];map[0][0]=0;map[0][1]=1;map[0][2]=0;map[0][3]=0;map[0][4]=0;map[0][5]=1;map[1][0]=0;map[1][1]=0;map[1][2]=0;map[1][3]=1;map[1][4]=0;map[1][5]=1;map[2][0]=1;map[2][1]=0;map[2][2]=1;map[2][3]=0;map[2][4]=0;map[2][5]=1;map[3][0]=0;map[3][1]=0;map[3][2]=0;map[3][3]=1;map[3][4]=1;map[3][5]=1;map[4][0]=0;map[4][1]=1;map[4][2]=1;map[4][3]=0;map[4][4]=0;map[4][5]=0;map[5][0]=0;map[5][1]=0;map[5][2]=0;map[5][3]=0;map[5][4]=1;map[5][5]=1;start=newcoordinate(0,0);end=newcoordinate(4,5);//打印迷宫矩阵printmap();}publicvoidprintmap(){if(this.map!=null){for(inti=0;imap.length;i++){for(intj=0;jmap.length;j++)System.out.print(map[i][j]+);System.out.println();}}}/**寻路函数*returntrue:存在路径*returnfalse：不存在路径**/publicbooleansearch(){//记录遍历情况数组0表示未遍历，1表示遍历int[][]flag=newint[map.length][map.length];//栈this.stack=newArrayList();coordinatestart=this.start;coordinateend=this.end;stack.add(start);－5－inti=0;//栈非空while((!stack.isEmpty()&&(i10)){//按照上右下左的顺序遍历//取栈顶coordinatetemp=getTop();//终点则停止if((temp.x==this.end.x)&&(temp.y==this.end.y))break;//向上if(temp.x0){//上可走且未遍历if((map[temp.x-1][temp.y]!=1)&&(flag[temp.x-1][temp.y]==0)){//标记已遍历flag[temp.x][temp.y]=1;//入栈push(newcoordinate(temp.x-1,temp.y));continue;}}//向右if(temp.ymap.length-1){//右可走且未遍历if((map[temp.x][temp.y+1]!=1)&&(flag[temp.x][temp.y+1]==0)){flag[temp.x][temp.y]=1;//stack.add(newcoordinate(temp.x,temp.y+1));//入栈push(newcoordinate(temp.x,temp.y+1));continue;}}//向下if(temp.xmap.length-1){//下可走且未遍历if((map[temp.x+1][temp.y]!=1)&&(flag[temp.x+1][temp.y]==0)){flag[temp.x][temp.y]=1;//stack.add(newcoordinate(temp.x+1,temp.y));//入栈push(newcoordinate(temp.x+1,temp.y));continue;}}//向左if(temp.y0){//左可走且未遍历if((map[temp.x][temp.y-1]!=1)&&(flag[temp.x][temp.y-1]==0)){flag[temp.x][temp.y]=1;//stack.add(newcoordinate(temp.x,temp.y-1));－6－//入栈push(newcoordinate(temp.x,temp.y-1));continue;}}//上下左右都不能走,标记已遍历并移出flag[temp.x][temp.y]=1;//stack.remove(stack.size()-1);//出栈pop();}//出入口没有路径if(stack.size()==0)returnfalse;//找到路径elsereturntrue;}/**打印路径***/publicvoidprintPath(){if(!stack.isEmpty()){for(inti=0;istack.size()-1;i++){System.out.print((+stack.get(i).x+,+stack.get(i).y+)+-);}System.out.println((+stack.get(stack.size()-1).x+,+stack.get(stack.size()-1).y+));}}publicstaticvoidmain(String[]args){MaprinthMaprinth=newMaprinth();Maprinth.generatemap2();if(Maprinth.search())//打印路径Maprinth.printPath();elseSystem.out.println(无可用路径！);}－7－五、结果及分析输出了这个迷宫和所走的最短路径六、总结与思考通过本次课程设计，我对栈的了解更深了一个层次。栈是一种特殊的线性表，特殊之处在于插入和删除操作的位置受到限制，栈的插入和删除操作只允许在线性表的一端进行，特点是先进后出。允许操作的一端为栈顶，栈中插入元素的操作为入栈，删除元素的操作为出栈。没有进行本次课程设计以前，我对栈的理解仅仅于书上的顺序栈和链式栈的程序，不懂应用。通过这次课程设计，我将栈的思想方法应用于了走迷宫这一过程中，成功的走出了迷宫。实践才能出真知，在通过了上机自己动手写程序操作后，才发现了许多平时理论课上我都没有注意到的问题。编写程序的时候经常会出错，但是经过反复调试修改最后通了，我想在以后的学习过程中，我需要时刻注意这些问题，多加练习，才能稳步解决，多加提高。－8－教师评语：