数据结构1236new

1、 课程设计说明书（论文） 第 I 页 交通咨询系统的开发摘 要 此次课程设计主要运用图的知识，借助弗洛伊德算法实现最短路径的求解，完成了时间复杂度的计算,并依此实现交通系统的开发。首先对算法进行分析，即弗洛伊德思路算法思想的阐述，然后编写最短路程序。在算法设计是，首先生成邻接矩阵，然后再进行逐点比较，最后算出任意两点之间的最短路径。完成程序设计后，并举例完成交通咨询系统的开发。最后并扩展算法的应用即工程安排、设备更新等实际问题 。关键词：弗洛伊德，最短路径，算法，图，交通咨询系统课程设计说明书（论文） 第 II 页 目 录1 绪 论.12 课题描述 .13 算法时间复杂度 .14 弗洛伊德算法

2、的思路 .25 弗洛伊德算法设计 .26 具体实例 .47 实例分析 .6总 结.9参考文献.10课程设计说明书（论文） 第 1 页 1 绪 论 自 1946 年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至一秒钟就能生产出一台微型计算机，产量猛增，价格低廉，这就使得它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多的用于控制、管理及数据处理等非数值计算的处理工作。于此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写出一个“

3、好”的程序，必须分析待处理的对象的特性以及各种处理对象之间存在的关系。这就是“数据结构”这门学科的形成和发展的背景。2 课题描述最短路问题 short-path problem，若网络中的每条边都有一个数值 (长度、成本、时间等)，则找出两节点 (通常是源节点和阱节点 )之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决交通咨询、管路铺设、线路安装、厂区布局和 设备更新等实际问题 。3 算法时间复杂度算法来决定的。整个算法的执行时间与该基本操作（乘法）重复执行的次数 n3成正比，故时间复杂度为 。3( )()T nO n4 弗洛伊德算法的思路 UYI VEW

4、RWE 次算法是从带权邻接矩阵 cost 出发，其基本思想如下： 假设求从定点到的最短路径，如果从到有弧，则从到存在一条长度为ivjvivjvivjvarcsijd 的路径，该路径不一定是最短路径，尚需进行 n 次试探。首先考虑路径（vi, ,）是否存在(即判断弧（,） ，和（, ）是否存在)。如果存在，则0vjviv0v0vjv比较（，）和（， , ）的路径长度取长度较短者为从到的中间顶点的ivjviv0vjvivjv序号不大于 0 的最短路径。加入在路径上再增加一个顶点，也就是说，如果1v课程设计说明书（论文） 第 2 页 （,v1）和（v1, ）分别是当前找到的中间顶点的序号不大于 0

5、的最短路径，ivjv那么， （vi,v1,., ）就有可能是从到的中间顶点的序号不大于 1 的最短路jvivjv径。将它和已经得到的从到中间顶点序号不大于 0 的最短路径相比较，从中选出ivjv中间顶点不大于 1 的最短路径之后，再增加一个顶点，继续进行试探。依次类推。2v在一般情况下，若（, ）和(, )分别是从到的中间顶点的序号不ivkvkvjvivjv大于的最短路径，则将（, , ）和已经得到的从到且序号不大1k ivkvjvivjv于的最短路径相比较，取长度较短者便是从到的中间顶点的序号不大于的1k ivjvk最短路径。这样在经过 n 次比较后，最后求得的必是从到的最短路径。ivjv5

6、 弗洛伊德算法设计 弗洛伊德算法最短路程序如下：#define n 6#define MaxNum 1000 /*定义一个最大数*/#include/* 定义邻接矩阵类型 */typedef int adjmatrixnn; /* 建立图的邻接矩阵 */void CreatMatrix(adjmatrix G)int i,j,k,e,arcnum; printf(图中有%d 个顶点n,n); for(i=0;in;i+) for(j=0;jn;j+) if(i=j) Gij=0; /*对角线的值置为 0*/ else Gij=MaxNum; /*其它位置的值初始化为一个最大数*/ printf

7、(请输入边的个数(5-30):);课程设计说明书（论文） 第 3 页 scanf(%d,&arcnum); printf(请输入边的信息,按照起点,终点,权值的形式输入:n); for(k=0;karcnum;k+) scanf(%d,%d,%d,&i,&j,&e); Gj-1i-1=Gi-1j-1=e; /*弗洛伊德算法*/void Floyd(int Gnn, int Ann, int Pnn) int i, j, k; for (i=0; in; i+) for(j=0;jn;j+) Aij=Gij;Pij=0; for (k=0; kn; k+) for

8、 (i=0; in; i+) for (j=0; jn; j+) if(Aik +AkjAij) Pij=k+1;Aij=Aik+Akj; void main() int i,j; adjmatrix G,A,P; CreatMatrix(G); Floyd(G, A, P); printf(原图的临界矩阵n); for(i=0;in;i+) for(j=0;jn;j+) printf(t%d,Gij); printf(nn);课程设计说明书（论文） 第 4 页 printf(两点间的距离n); for(i=0;in;i+) for(j=0;jn;j+) printf(t%d,Aij); pr

9、intf(nn); printf(两点间路径的中介点n); for(i=0;in;i+) for(j=0;jn;j+)printf(t%d,Pij); printf(nn);6 具体实例举个简单的例子,假设有六座城市，现在有一个游客要从城市 到城市观光旅游，ij他向交通咨询系统咨询乘座哪一路车划算，即花费最少。现在我们帮旅客解决这个问题。比如这六座城市的地理位置的布局，其中权值代表两座城市之间的距离（） 。kmA111B2C3D4F6654535403016802220课程设计说明书（论文） 第 5 页 运行上面设计的程序，运行结果：图中有 6 个顶点请输入边的个数（5-30） ； 101,2

10、,452,3,653,5,805,6,566,1,404,1,204,2,224,3,354,5,304,6,16原图的临界矩阵 两点间的距离 04510002010004045065221000100010006503580100020223503016100010008030056401000100016560042552050364205722523855570356551202235030165052653004636385116460E556课程设计说明书（论文） 第 6 页 两点间路径的中介点 040444400444440444000000440004440440结果分析：A 城

11、市到 B、C、D、E、F 的最短距离依次为 42、55、20、50、36，中间经过4、0、4、4、4；B 到 C、D、E、F 的最短距离依次为 57、22、52、38，中间经过0、4、4、4；C 到 D、E、F 的最短距离依次为 35、65、51，中间经过 4、4、4；D 到 E、F 的最短距离依次为 30、16，中间不经过任何城市；E 到 F 的最短路径为 46，中经过城市 4。 （其中 0 代表不经过任何城市。 ）由以上分析可知城市 4 是中心城市。现实生活中的交通网是很复杂的，我们只需调整其中的节点 n 即可，即可以完成大型的交通咨询系统的开发。课程设计说明书（论文） 第 7 页 总 结

12、此次数据结构课程设计，历经一周时间，虽然时间紧任务重，但是还是按时完成了课程设计。由于前期没有开设 C 语言，数据结构学习一直都很吃力，在授课期间，叶老师给我们适当的补 C 语言的必要知识，这给我们的学习带来了很大的帮助。这次课程设计我选作的是基于左端路径问题的交通咨询系统的开发，并列举实例，进行此算法的应用。算法实现使用的是弗洛伊德算法，阐述了弗洛伊德的算法的设计思想和程序实现。完成最短路径设计后，并对算法的应用进行扩展比如解决交通咨询、管路铺设、线路安装、厂区布局和设备更新等实际问题 ，并且对工程安排、设备更新等进行了详细的阐述。在做课程设计的过程中，我遇到了很多困难。比如不知道如何定义结构等，知道算法的思想但不知道用语言如何实现，这些困难困惑了我很久，对亏了叶老师的耐心指导，使我的课程设计能够得以顺利的完成。通过这次