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

《数据结构课程设计-Floyd算法求解最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.....数据结构课程设计报告撰写要求（一）纸与页面要求1．采用国际标准A4型打印纸或复印纸，纵向打印。2．封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。3．图表及图表标题按照模板中的表示书写。（二）课设报告书的容应包括以下各个部分：（按照以下顺序装订）1.封页(见课设模版)2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。2.任务书(学生教师均要签字,信息填写完整)3.目录4.正文一般应包括以下容:（1)题目介绍和功能要求（或描述）课程设计任务的详细描述(注意不能直接抄任务书),将容做更详细

2、的具体的分析与描述；（2)系统功能模块结构图绘制系统功能结构框图及主要模块的功能说明；（3)使用的数据结构的描述:数据结构设计及用法说明;（4)涉及到的函数的描述;（5)主要算法描述(程序流程图)（6)给出程序测试/运行的结果设计多组数据加以描述（包括输入数据和输出结果）（7)课程设计的总结及体会（8)参考文献格式要求：[1]作者，等.书名.出版地：，出版年5.附录：程序清单(应带有必要的注释).资料........航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：利用弗洛伊德（Floyd)算法求解最

3、短路径院（系）：计算机学院专业：计算机科学与技术(物联网方向)班级：34010105学号：姓名：指导教师：说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。.资料........学术诚信声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致中所罗列的容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。

4、与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。本人签名:日期：2015年1月5日航空航天大学.资料........课程设计任务书课程设计名称数据结构课程设计专业计算机科学与技术（物联网方向）学生思班级34010105学号2013040101204题目名称起止日期2015年1月5日起至2015年1月16日止课设容和要求：给出一无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市

5、之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。参考资料：《算法与数据结构》《C语言程序设计》教研室审核意见：教研室主任签字：指导教师（签名）年月日学生（签名）年月日.资料........目录第一章需求设计1.1题目介绍11.2功能要求2第二章程序设计32.1详细设计32.1.1总体模块图32.1.2函数描述42.2主要算法描述5第三章使用说明63.1用法说明9第四章程序测试114.1运行结果114.2存在的缺陷12参考文献13附录（关键部分程

6、序清单）14.资料........第一章需求设计1.1题目介绍给出一无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。将问题分解为三个方面，第一个方面是对于无向图的存储问题，第二个方面是实现弗洛伊德（Floyd）算法求解最短路径，第三个方面是将最短路径输出。首先对于图的建立选择合适的存储结构，考虑到之后要用的弗洛伊德算法所以选择采用邻接矩阵存储无向图。然后采用弗洛伊德算法，该算法又叫插点法。

7、是利用三重循环产生一个存储每个结点最短距离的矩阵，基本思想是设置一个n阶矩阵D(k)，D(k)[i][j]表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，p[v][w][u]存储的是由i到j路径经过的所有顶点。三重循环执行完毕最短路径的信息存储在两个数组中。最后将最短路径的信息输出。.资料........1.2功能要求一个无向图用每个顶点代表城市，顶点

8、之间边的权重表示城市之间的路径，将顶点信息和边的信息输入程序，即可得到每两个城市之间的最短路径长度值以及这条路径经过的城市。可以为建址问题提供参考。设计环境：（1）WINDOWS7系统（2）VisualC++开发环境开发语言：C语言.资料........第二章程序设计2.1详细设计2.1.1功能模块图用弗洛伊德算法求解最短路径主函