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

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

2、能说明； （3) 使用的数据结构的描述: 数据结构设计及用法说明;（4) 涉及到的函数的描述 ; （5) 主要算法描述( 程序流程图)（6) 给出程序测试/运行的结果设计多组数据加以描述（包括输入数据和输出结果） （7) 课程设计的总结及体会（8) 参考文献 格式要求：1作者，等. 书名.出版地：出版社，出版年 5.附录：程序清单 (应带有必要的注释) 沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：利用弗洛伊德（Floyd)算法求解最短路径院（系）：计算机学院专 业：计算机科学与技术(物联网方向)班 级：34010105学 号：姓 名： 指导教师： 说明：结

3、论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。学术诚信声明 本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。 本人签名: 日

4、期： 2015 年 1 月 5 日沈阳航空航天大学课程设计任务书课程设计名称 数据结构课程设计专业计算机科学与技术（物联网方向）学生姓名孙思班级34010105学号题目名称起止日期2015年1月5日起至2015年1月16日止课设内容和要求：给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。参考资料： 算法与数据结构C语言程序设计教研室审核意见： 教研室主任签字：指导教师（签名）年月日学 生（签名）年月日目 录 TOC o 1-3 h z u 第一章 需求设计

5、 HYPERLINK l _Toc201982612 1.1 题目介绍 PAGEREF _Toc201982612 h 1 HYPERLINK l _Toc201982613 1.2 功能要求 PAGEREF _Toc201982613 h 2第二章 HYPERLINK l _Toc201982614 程序设计 PAGEREF _Toc201982614 h 3 HYPERLINK l _Toc201982615 2.1 详细设计 PAGEREF _Toc201982615 h 3 HYPERLINK l _Toc201982616 总体模块图 PAGEREF _Toc201982616 h

6、3 HYPERLINK l _Toc201982617 2.1.2 函数描述 PAGEREF _Toc201982617 h 4 HYPERLINK l _Toc201982618 2.2 主要算法描述 PAGEREF _Toc201982618 h 5 HYPERLINK l _Toc201982619 第三章 使用说明6 HYPERLINK l _Toc201982621 3.1 用法说明 PAGEREF _Toc201982621 h 9 HYPERLINK l _Toc201982622 第四章 程序测试 PAGEREF _Toc201982622 h 11 HYPERLINK l _

7、Toc201982623 运行结果 PAGEREF _Toc201982623 h 11 HYPERLINK l _Toc201982624 4.2 存在的缺陷 PAGEREF _Toc201982624 h 12 HYPERLINK l _Toc201982625 参考文献 PAGEREF _Toc201982625 h 13 HYPERLINK l _Toc201982626 附 录（关键部分程序清单） PAGEREF _Toc201982626 h 14 第一章 需求设计1.1 题目介绍给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路

8、经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。将问题分解为三个方面，第一个方面是对于无向图的存储问题，第二个方面是实现弗洛伊德（Floyd）算法求解最短路径，第三个方面是将最短路径输出。首先对于图的建立选择合适的存储结构，考虑到之后要用的弗洛伊德算法所以选择采用邻接矩阵存储无向图。然后采用弗洛伊德算法，该算法又叫插点法。是利用三重循环产生一个存储每个结点最短距离的矩阵，基本思想是设置一个n阶矩阵D(k)，D(k)ij表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使

9、得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，pvwu存储的是由i到j路径经过的所有顶点。三重循环执行完毕最短路径的信息存储在两个数组中。最后将最短路径的信息输出。1.2 功能要求一个无向图用每个顶点代表城市，顶点之间边的权重表示城市之间的路径，将顶点信息和边的信息输入程序，即可得到每两个城市之间的最短路径长度值以及这条路径经过的城市。可以为建址问题提供参考。设计环境：（1）WINDOWS 7系统（2）VisualC+开发环境开发语言：C语言第二章 程序设计2.1 详细设计 2.1.1功能模块图用弗洛伊德算法求解最短路径用弗洛伊德算法求解最短路径主函数主函数输出

10、最短路径信息调用弗洛伊德算法输入无向图顶点及权值2.1.2 函数描述Find：根据名称得到指定顶点在顶点集合中的下标，利用此函数找到顶点所在位置，进而对无向图赋权值。Create：创建无向图的邻接矩阵，因为每条边都有权值，创建的是无向网的邻接矩阵，用权值代替1，没有边连接则为无穷。FLOYD：设置一个n阶矩阵D(k)，D(k)ij表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，pvwu存储的是由i到j路径经过的所有顶点。三重循

11、环执行完毕最短路径的信息存储在两个数组中。主函数：在主函数里定义一个无向图，一个三维矩阵p，二维矩阵D，对各个函数进行调用，实现无向网的建立，运用弗洛伊德算法求解出最短路径，将路径长度以及经过的顶点信息输出。2.2 主要算法描述 图2.2.1 FLOYD函数 图2.2.2 Find函数 图2.2.3 Main函数 图2.2.4 Create函数第三章 使用说明3.1 用法说明将顶点数和边数输出，中间用空格隔开。输入顶点信息。依次输入每条边连接的两个顶点用空格间隔，边的权值。得到每两个顶点城市间的最短距离以及经过的城市。.4第四章 程序测试 运行结果4.2 存在的缺陷 无向图的顶点信息只能用一个

12、字符表示。将存储顶点信息的字符型改为字符数组就可以完善该缺陷。将两点的最短路径输出时只能显示经过的顶点有哪些，无法显示真实的路径顺序。输入无向图信息只能用手动输入，无法用文件直接写入。输入不符合要求的数据会使程序自动停止。参考文献1 张长海.C语言程序设计M.北京：高等教育出版社，20062 吴启武.HYPERLINK :/59.73.148.12:8080/opac/openlink.php?title=C语言课程设计案例精编C语言课程设计案例精编.北京:清华大学出版社,2011.3 郭翠英.HYPERLINK :/59.73.148.12:8080/opac/openlink.php?ti

13、tle=C语言课程设计案例精编C语言课程设计案例精编.北京:中国水利水电出版社,2004.4 姜灵芝, 余键.HYPERLINK :/59.73.148.12:8080/opac/openlink.php?title=C语言课程设计案例精编C语言课程设计案例精编.北京:清华大学出版社,2008.5 黄明, 梁旭, 万洪莉.HYPERLINK :/59.73.148.12:8080/opac/openlink.php?title=C语言课程设计C语言课程设计.北京:电子工业出版社,2006附 录（关键部分程序清单）#include stdio.h#include stdlib.h#define

14、MAX 20#define INFINITY 9999typedef bool PathMatrixMAXMAXMAX;typedef int DistanceMatrixMAXMAX;typedef structint vexnum,arcnum; char vexsMAX; int arcsMAXMAX;MGraph;int Find(char vex, MGraph MG)/根据名称得到指定顶点在顶点集合中的下标 vex表示顶点 / return 如果找到则返回下标，否则返回 int i; for (i=0;iMG.vexnum;i+) if (MG.vexsi = vex) retur

15、n i; return 0;void Create(MGraph &G) int i,j,k,v1,v2,w; printf(请输入顶点数和边数:); scanf(%d %d,&G.vexnum,&G.arcnum); getchar(); for(i=0;iG.vexnum;i+) printf(请输入第%d个结点：,i+1); scanf(%c,&G.vexsi); getchar(); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; for(k=0;kG.arcnum;k+) char c1,c2; print

16、f(请输入与第%d条边相连的两条边v1 v2:,k+1); scanf(%c,&c1); getchar(); scanf(%c,&c2); printf(请输入该边的权重：); scanf(%d,&w); getchar(); v1=Find(c1,G); v2=Find(c2,G); G.arcsv1v2=w; G.arcsv2v1=w; void FLOYD(MGraph G,PathMatrix &P,DistanceMatrix &D) int v,w,u,i; for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w) Dvw=G.arcsvw; for(

17、u=0;uG.vexnum;+u)Pvwu=false; if (DvwINFINITY) Pvwv=true; Pvww=true; for(u=0;uG.vexnum;+u)for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w)if (Dvu+DuwDvw)Dvw=Dvu+Duw;for(i=0;iG.vexnum;+i)Pvwi=Pvui|Puwi;int main() MGraph G; int i,j,k; Create(G); PathMatrix p; DistanceMatrix D; FLOYD(G,p,D); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+)if(i=j)continue;elseprintf(%c 到%c 经过的顶点有:,G.vexsi,G.vexsj);for(k=0;kG.vexnum;k+)if(pijk=0)continue;elseprintf(%c ,G.vexsk);printf(最短路径长度为: %dnn,Dij); return 0;课程设计总结：此次课程设计中，我了解到了许多以前不太会的知识，也在对程序的不断的调试中认识到调试时的细心是很重要的，这些都让我受益匪浅。譬如，getchar()的使用，用在输入字符型数据的时候，g