《单元点最短路径算法的实现课程设计》由会员分享，可在线阅读，更多相关《单元点最短路径算法的实现课程设计（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计设 计 说 明 书单元点最短路径算法的实现 学 生 姓 名 学 号 班 级 成 绩 指 导 教 师 余 冬 梅 数学与计算机科学学院2014 年 3 月 7 日 课程设计任务书20132014 学年第 2 学期专业： 学号： 姓名： 课程设计名称：数据结构课程设计 设计题目： 单源点最短路径算法的实现 完成期限：自 2014 年 2 月 24 日至 2014 年 3 月 7 日共 2 周设计依据、要求及主要内容（可另加附页）：最短路径问题是数据结构中数组部分的重点和难点知识。它属于图结构问题，其解决方法也有不少（如 Dijkstra、 A-star），可自行选择算法。本课程设计
2、按以下的要求运用 C/ C+结构体、指针、数据结构等基知识编程实现。任务要求：1）阐述设计思想,画出流程图;2 ）任意建立存储 m 个顶点 n 条边的图；3）按照用户要求的源点和目标点，求出它们间的最短路径，并打印出路径，若无路径需给出说明；4）说明测试方法,写出完整的运行结果,较好的界面设计；5）按照格式要求完成课程设计说明书。设计要求:1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和
3、各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明） ，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：能够熟练掌
4、握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括合法的输入及其输出结果和含有非法的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；以上要求中前三个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订。指导教师（签字）： 教研室主任（签字）： 批准日期：2014 年 2 月 23 日课程设计评阅评语：指导教师签名：年 月 日指导教师：余冬梅 教研室负责人：申静摘 要本系统以 VC+作
5、为软件开发环境，C 语言作为程序开发语言，邻接矩阵作为存储结构，设计与实现了最短路径运算。该系统实现了有向图的存储、最短路径的运算等主要功能。依照该系统可以解决生活中许多问题，比如交通路线的选择，工程时间的预算等等，让人们可以做出合理的选择。本系统通过分析课题的背景、意义、要求，分别从课题描述、逻辑设计、算法设计、调试与测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。界面清晰，操作简单，易于用户接受。关键词：VC+;邻接矩阵; 最短路径目录1 课题描述 .12 问题分析与任务定义 .22.1 问题分析 .22.2 任务定义 .23 算法设计 .33.1 图的邻接矩
6、阵的存储结构 .33.2 DIJKSTRA算法思想 .44 系统逻辑设计 .54.1 主函数流程图如图 4.1 所示 .54.2 CREATE函数流程图如图 4.2 所示 .64.3 DIJKSTRA 函数流程图如图 4.3 所示 .84 源代码 .115 调试与测试 .146 总结 .16参考文献 .1701 课题描述乘车旅行的人大多数都希望找出到目的地尽可能短，花费少的行程，那么如何找出从出发点到目的地的最短路径？由于路径比较多，所以用手工计算起来比较复杂，抽象，因此人们用计算机语言代替手工计算来求得最短路径。而在计算机语言中迪杰斯拉算法比较常用，简捷，故人们经常借助计算机程序用迪杰斯拉算
7、法求得单源点的最短路径，这样可以广泛的提高效率，而且条理清晰，通俗易懂。12 问题分析与任务定义2.1 问题分析本系统是要解决的是单源点最短路径问题，设计程序，实现最短路径的求法，系统需要达到的主要功能如下：(1) 编写算法能够建立带权图，并能够用 Dijkstra 算法求该图的最短路径。(2) 能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图形方式，可顶点序列方式输出。(3) 根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块。2.2 任务定义根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调用
8、的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：(1) 建立有向图的存储结构。(2) 应用 Dijkstra 算法求出该有向图的最短路径。(3) 在主函数中调用两个子函数，完成最短路径的程序设。23 算法设计3.1 图的邻接矩阵的存储结构一个图的邻接矩阵表示唯一的。故在图的邻接矩阵表示中，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有 n 个元素的一维数组存储顶点信息，其中下标为 i 的元素存储顶点 vi 的信息。本设计是基于类 C 语言的算法描述，因此，图的邻接矩阵的存储结构定义如下:#define MVNum 50typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum；Mgraph;在本系统中，
