5.交通实验报告.doc

实验课程名称 数据结构课程设计 专 业 班 级 计算机科学与技术10级1班 学 生 姓 名 罗泽丽 学 号 10410901019 指 导 教 师 冯 韵 2012至201学年第 一 学期第 一 至 九 周目 录1概述31.1现状分析31.2存在的问题31.3实现意义32系统分析31.编写要求32.结构设计33概要设计43.1交通咨询系统模块43.2狄克思拉算法图43.3整体流程图54详细设计64.1建立有向图的存储结构64.2 地杰斯特拉算法64.3费洛伊徳算法74.4 主函数75运行与测试95.1有向图的存储结构建立95.2单源路径的迪杰斯特拉算法95.3调用费洛伊德算法96总结和心得107参考文献108附录101概述1.1现状分析在交通网络非常发达，交通工具盒交通方式不断更新的今天，人们在出差，旅游或做其他行动时，往往由于不知道要去目的地的路线，从而给人们的出行带来了很大的不便。不仅浪费时间，还有大量的交通费用。 1.2存在的问题在人们出行时，有急事的那些人就想很快到达目的地，有些人又想使到达目的地的费用越少越好，而老年人就想周转次数最少，但是由于不知道路线，从而导致了一系列的困难，给人们的出行带来很大的不便。1.3实现意义对于这样一个人们关心的问题可用一个人图结构来表示交通网络系统，利用计算机建立一个交通咨询系统这样极大地方便了人们的出行，使得交通不那么的拥挤，从而让出行者更快，更好的到达想要去的地方。2系统分析1.编写要求（1） 提供对城市信息进行编辑的功能.（2） 图形界面尽可能的人性化。（3） 能够对城市建立交通网络图。（4） 提供路径最优决策。2.结构设计1.建立交通网络图的存储结构2.解决单源最短路径3.实现两个城市顶点之间的最短路径。3概要设计3.1交通咨询系统模块交通咨询管理系统管理员用户咨询一个城市到任意城市距离咨询任意两个城市间最短距离增加城 市设置距 离建立交通网3.2狄克思拉算法图开 始初始化距离和路径i=1j=1;j+;jn 修改最短路径和距离输出结果3.3整体流程图开 始输入选择功能用户管理员运 行 否输入退出 是结束4详细设计4.1建立有向图的存储结构 void CreateMGraph(MGraph * G,int n,int e)int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;printf(输入%d条边的i,j及w:n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕！n);4.2 地杰斯特拉算法（void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; if(D2vMaxint) p2v=v1;else p2v=0;D2v1=0; Sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw & D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;p2w=v;printf(路径长度 路径n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v;printf(n);4.3费洛伊徳算法void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)pij=j;elsepij=0;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij) Dij=Dik+Dkj;pij=pik;4.4 主函数 （void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf(*求城市之间最短路径*n);printf(=n);printf(1.求一个城市到所有城市的最短路径n);printf(2.求任意的两个城市之间的最短路径n);printf(=n);printf(请选择 :1或2，选择0退出:n);scanf(%d,&xz);if (xz=2)Floyd(G,n);printf(输入源点（或起点）和终点:v,w:);scanf(%d,%d,&v,&w);k=pvw;if (k=0)printf(顶点%d 到 %d 无路径!n,v,w);elseprintf(从顶点%d 到 %d 最短路径路径是:%d,v,w,v);while (k!=w)printf(%d,k);k=pkw;printf(%d,w);printf(径路长度:%dn,Dvw);else if(xz=1)printf(求单源路径，输入源点v:);scanf(%d,&v);Dijkstra(G,v,n);printf(结束求最短路径，再见!n); 5运行与测试5.1有向图的存储结构建立5.2单源路径的迪杰斯特拉算法5.3调用费洛伊德算法6总结和心得在这次的试验中，让我更深的了解数据结构，在做实验的时候，自己亲自动手，一点一点慢慢做，突然发现好困难，也由于平时的基本功不够，所以导致了问题的难度性加大了。在这次的试验中，难易程度对我而言较大，程序代码不算长，但由于输入时不细心，导致许多的小错误，但还存在着不少的问题，在同学的帮助下，慢慢解决了这个问题，但许多概念还是模棱两可的，可是这次绝对是我的一个进步。我以后一定认真学习，好好把握问题的关键，掌握知识的要领。7参考文献1 .严蔚敏、吴伟民主编 数据结构（C语言版） 清华大学出版社2 苏仕华主编 数据结构课程设计 机械工业出版社3 严蔚敏、吴伟民 数据结构习题集（C语言版）清华大学出版社8附录#include#include#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G,int n,int e)int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;printf(输入%d条边的i,j及w:n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕！n);void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; if(D2vMaxint) p2v=v1;else p2v=0;D2v1=0; Sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw & D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;p2w=v;printf(路径长度 路径n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v;printf(n);void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)pij=j;elsepij=0;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij) Dij=Dik+Dkj;pij=pik;void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf(*求城市之间最短路径*n);printf(=n);printf(1.求一个城市到所有城市的最短路径n);printf(2.求任意的两个城市之间的最短路径n);printf(=n);printf(请选择 :1或2，选择0退出:n);scanf(%d,&xz);if (xz=2)Floyd(G,n);printf(输入源点（或起点）和终点:v,w:);scanf(%d,%d,&v,&w);k=pvw;if (k=0)printf(顶