单元点最短路径算法的实现 课程设计

《单元点最短路径算法的实现 课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计设计说明书单元点最短路径算法的实现学生姓名学号班级成绩指导教师余冬梅数学与计算机科学学院2014年3月7日课程设计任务书2013—2014学年第2学期专业：学号：姓名：课程设计名称：数据结构课程设计设计题目：单源点最短路径算法的实现完成期限：自2014年2月24日至2014年3月7日共2周设计依据、要求及主要内容（可另加附页）：最短路径问题是数据结构中数组部分的重点和难点知识。它属于图结构问题，其解决方法也有不少（如Dijkstra、A-star），可自行选择算法。本课程设计按以下的要求运用C/C++结构体、指针、数据结构等基知识编程实现。任务要求：1）阐述设计思想,画

2、出流程图;2）任意建立存储m个顶点n条边的图；3）按照用户要求的源点和目标点，求出它们间的最短路径，并打印出路径，若无路径需给出说明；4）说明测试方法,写出完整的运行结果,较好的界面设计；5）按照格式要求完成课程设计说明书。设计要求:1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说

3、明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和

4、风格良好的源程序清单和结果；6）结果分析：程序运行结果包括合法的输入及其输出结果和含有非法的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；以上要求中前三个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订。指导教师（签字）：教研室主任（签字）：批准日期：2014年2月23日课程设计评阅评语：指导教师签名：年月日指导教师：余冬梅教研室负责人：申静摘要本系统以VC++作为软件开发环境，C语言作为程序开发语言，邻接矩阵作为存储结构，设计与实现了最短路径运算。该系统实现了有向图的

5、存储、最短路径的运算等主要功能。依照该系统可以解决生活中许多问题，比如交通路线的选择，工程时间的预算等等，让人们可以做出合理的选择。本系统通过分析课题的背景、意义、要求，分别从课题描述、逻辑设计、算法设计、调试与测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。界面清晰，操作简单，易于用户接受。关键词：VC++;邻接矩阵;最短路径目录1课题描述12问题分析与任务定义22.1问题分析22.2任务定义23算法设计33.1图的邻接矩阵的存储结构33.2Dijkstra算法思想44系统逻辑设计54.1主函数流程图如图4.1所示54.2Create函数流程图如图4.2

6、所示64.3Dijkstra函数流程图如图4.3所示84源代码115调试与测试146总结16参考文献171课题描述乘车旅行的人大多数都希望找出到目的地尽可能短，花费少的行程，那么如何找出从出发点到目的地的最短路径？由于路径比较多，所以用手工计算起来比较复杂，抽象，因此人们用计算机语言代替手工计算来求得最短路径。而在计算机语言中迪杰斯拉算法比较常用，简捷，故人们经常借助计算机程序用迪杰斯拉算法求得单源点的最短路径，这样可以广泛的提高效率，而且条理清晰，通俗易懂。162问题分析与任务定义2.1问题分析本系统是要解决的是单源点最短路径问题，设计程序，实现最短路径的求法，系统需要达到的主要功能

7、如下：(1)编写算法能够建立带权图，并能够用Dijkstra算法求该图的最短路径。(2)能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图形方式，可顶点序列方式输出。(3)根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块。2.2任务定义根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：