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

《基于栈的走迷宫最短路径实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、成绩课程设计说明书(论文)题目课程名称数据结构课程设计院（系、部、中心）计算机工程学院专业班级学生姓名学号设计地点设计起止时间：2016年12月25日至2016年12月31日数据结构课程设计题目（例如表达式求值问题求解）一、课程设计目的和要求目的：深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。要求：熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问

2、题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二、题意说明及分析一个迷宫如图所示，它有一个入口和出口，其中白色单元表示通路，黑色单元表示路不通。寻找一条从入口到出口的路径，每步只能从一个白色单元走到相邻的白色单元，直至出口。使用栈实现走迷宫的功能，演示走迷宫的过程。可走的白色单元用0表示，不可走的黑色单元用1表示，使用栈，栈顶元素temp标记位置，走出迷宫。输出迷宫和走出路径。入口↓→↓↓↓←↓→→→→→→↑三、算法设计与分析用ArrayLi

3、st作为栈的数据结。ArrayList是java中Collection集合中线性表，可以通过add.remove操作添加删除元素，coordition是定义的内部类，用来存放一个节点的横纵坐标。这样，栈中的每个元素就是迷宫中一个位置的坐标。寻路算法(若存在路径，返回true；若不存在，返回false)：while栈非空获取栈顶元素temp=stack.getTopiftemp是出口位置跳出循环else继续向下执行iftemp上边可走andtemp上边未遍历把temp所在位置标记为已遍历，将temp上边的位置加入栈顶进入下一次循环iftem

4、p右边可走andtemp右边未遍历把temp所在位置标记为已遍历，将temp右边的位置加入栈顶进入下一次循环iftemp下边可走andtemp下边未遍历把temp所在位置标记为已遍历，将temp下边的位置加入栈顶进入下一次循环iftemp左边可走andtemp左边未遍历把temp所在位置标记为已遍历，将temp左边的位置加入栈顶进入下一次循环上下左右都不可走，标记temp为已读，并从栈中移出，进入下次循环最后退出while循环有两种情况：1）找到出口位置，那栈中保留的就是从入口到出口的路径2）栈为空，说明没有路径能从入口到出口四、源程序packagecom.te

5、st;importjava.util.ArrayList;importjava.util.List;publicclassMaprinth{privateint[][]map;//存放迷宫矩阵，0表示可走，1表示不可走privatecoordinatestart;//记录起点坐标privatecoordinateend;//记录终点坐标privateListstack;//栈/**坐标**/classcoordinate{publicintx;publicinty;publiccoordinate(intx,inty){this.x=x;

6、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;}/**出栈操作**/publiccoordinatepop(){if(!stac

7、k.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

8、]=0;map[2][2