数据结构课程设计-Floyd算法求解最短路径..doc

数据结构课程设计报告撰写要求 （一）纸张与页面要求 1．采用国际标准A4型打印纸或复印纸，纵向打印。 2．封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。 3．图表及图表标题按照模板中的表示书写。 （二） 课设报告书的内容应包括以下各个部分：（按照以下顺序装订） 1.封页(见课设模版) 2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。 2.任务书(学生教师均要签字,信息填写完整) 3.目录 4.正文一般应包括以下内容: （1)题目介绍和功能要求（或描述） 课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述； （2) 系统功能模块结构图 绘制系统功能结构框图及主要模块的功能说明； （3) 使用的数据结构的描述: 数据结构设计及用法说明; （4) 涉及到的函数的描述 ; （5) 主要算法描述( 程序流程图) （6) 给出程序测试/运行的结果 设计多组数据加以描述（包括输入数据和输出结果） （7) 课程设计的总结及体会 （8) 参考文献 格式要求：[1]作者，等. 书名.出版地：出版社，出版年 5.附录：程序清单 (应带有必要的注释) 沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：利用弗洛伊德（Floyd)算法求解最短路径 院（系）：计算机学院 专 业：计算机科学与技术(物联网方向) 班 级学 号： 姓 名： 指导教师： 说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。 学术诚信声明 本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。 本人签名: 日期： 2015 年 1 月 5 日 沈阳航空航天大学 课程设计任务书 课程设计名称 数据结构课程设计 专业 计算机科学与技术（物联网方向） 学生姓名 孙思 班级学号 2013040101204 题目名称 起止日期 2015 年 1 月 5 日起至 2015 年 1 月 16 日止 课设内容和要求： 给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。 参考资料： 《算法与数据结构》 《C语言程序设计》 教研室审核意见： 教研室主任签字： 指导教师（签名） 年 月 日 学 生（签名） 年 月 日 目 录 第一章 需求设计 1.1 题目介绍 1 1.2 功能要求 2 第二章 程序设计 3 2.1 详细设计 3 2.1.1 总体模块图 3 2.1.2 函数描述 4 2.2 主要算法描述 5 第三章 使用说明 6 3.1 用法说明 9 第四章 程序测试 11 4.1 运行结果 11 4.2 存在的缺陷 12 参考文献 13 附 录（关键部分程序清单） 14  第一章 需求设计 1.1 题目介绍 给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。 将问题分解为三个方面，第一个方面是对于无向图的存储问题，第二个方面是实现弗洛伊德（Floyd）算法求解最短路径，第三个方面是将最短路径输出。首先对于图的建立选择合适的存储结构，考虑到之后要用的弗洛伊德算法所以选择采用邻接矩阵存储无向图。然后采用弗洛伊德算法，该算法又叫插点法。是利用三重循环产生一个存储每个结点最短距离的矩阵，基本思想是设置一个n阶矩阵D(k)，D(k)[i][j]表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若