迷宫最短路径

《迷宫最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖南工业大学课程设计计算机与通信学院（系、部）2012~2013学年第2学期课程名称数据结构课程设计指导教师xxxx职称副教授学生姓名xxx专业班级计算机科学与技术学号xxxxxx题目迷宫最短路径求法成绩起止日期2013年6月26日～2013年6月27日目录清单序号材料名称资料数量备注1课程设计任务书12课程设计说明书13张456湖南工业大学课程设计任务书2012—2013学年第2学期3计算机与通信学院（系、部）计算机科学与技术专业1203班级课程名称：数据结构课程设计设计题目：求迷宫问题的最短路径完成期限：自2013年6月25日至2013年6月27日共周内容及

2、任务一：设计的主要技术参数1、函数的调用2、公用体、结构体3、循环语句和选择语句4、队列5、指针与数组的应用6、结构体的应用7：遍历三、设计工作量1、函数编码设计2、函数的调试及运行3、系统的调试一、设计内容：迷宫问题是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。我们要解决的是如何找到一条迷宫的最短路径。二、任务：掌握结构化程序设计的主体思想，以自顶向下逐步求精的方法编制程序解决一些实际的问题，为将来

3、编写软件积累一些典型的案例处理经验。1.设计正确，方案合理。2.界面友好，使用方便。3.程序精炼，结构清晰。4.设计报告，含程序设计说明，用户使用说明，源程序清单及程序框图。5.上机演示。6.按学号顺序选课题号，并在规定的时间内独自完成相关课题的C源程序编写、调整和运行。源程序及编译生成各文件均保存在软盘中；7.按本任务书的要求，按附录的要求编写《课程设计报告》（Word文档格式）。并用A4的复印纸打印并装订。进度起止日期工作内容3安排2013.06.25~2013.06.27选题及组内成员分任务，开始熟悉课题并进行构思2013.06.25编写源程序、运行、修改

4、2013.06.26编写文档并打印文稿主要参考资料[1]谭浩强.C语言程序设计（第三版）［Ｍ］.北京：清华大学出版社，2005[2]数据结构实验教程［Ｍ］.北京：高等教育出版社，2005[3]刘振鹏罗文劼石强.数据结构（第三版）中国铁道出版社指导教师（签字）：年月日系（教研室）主任（签字）：年月日3数据结构课程设计设计说明书求迷宫的最短路径起止日期：2013年6月25日至2013年6月27日学生姓名xxx班级计算机科学与技术1203学号xxxx成绩指导教师(签字)计算机与通信学院（部）2013年6月26日.41.目录1课程设计简介11.1课程设计的目的11.2课

5、程设计内容12数据结构的设计23功能模块（或算法）描述34程序运行结果45心得体会5参考文献6.41.1课程设计简介1.1课程设计的目的通过实验，掌握如下内容：1：进一步掌握指针、模板类、异常处理的使用；2：掌握队列的操作和实现方法；3：学习使用队列解决实际问题的能力；4：学习使用图的广度优先搜索解决实际问题的能力。1.2课程设计内容2利用数据结构的队列遍历求出迷宫问题的最短路径。迷宫求解问题如下：迷宫问题是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处

6、放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。我们要解决的是如何找到一条迷宫的最短路径。测试算法的迷宫由使用者设置，例如设置的迷宫如下图所示1.3程序功能打印老鼠走出迷宫的最短路径.41.2.程序算法及功能分析2.1存储结构：队列顺序存储示意图如下：1.2关键算法分析核心算法思想：1：如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径，为了改变算法，达到输出最短路径的目的，采用队列的实现方式。2：为查找最短路径，使用了图中的广度搜索。算法的基本思路为：从迷宫入口点（1,1）出发，向四周搜索，几下所有一步能到达的坐标点；然后依次再

7、从这些点出发，再几下所有一步能到达的坐标点；依此类推，直到到达迷宫的出口点（m,n）为止，然后从出口点沿着搜索路径回溯到入口。typedefstruct{intx,y;//行、列坐标intpre;//链域}sqtype;sqtypesq[r];//作为队列的存储空间，记录被访问过的点关键算法思想的描述和实现：为寻求最短路径，采用广度优先搜索方法，使用队列实现路径存储，队列中每个元素用结构存储体系，包含迷宫坐标，队列中的序号，队首指针front,队尾指针rear,最后采用回溯的方法将路径打印出来。算法1：intSHORTPATH(intmaze[m2][n2])/

8、/找迷宫maze的最短路