数据结构课程实践报告城市道路交通.doc
哈尔滨理工大学管理学院 数据结构课程设计实验题目：交通咨询系统设计 学 院： 专 业： 信息管理与信息系统 班 级： 11-2班 姓 名： 学 号： 11060402 完成时间：2013年6月28日 指导老师： 数据结构实验项目任务书实验题目交通咨询系统设计学院管理学院专业信管专业年级11-2班任务描述： 综合运用C+编程技术和Dijkstra算法和Floyd算法，用VS2010或QT等设计建立一个交通咨询系统，实现解决一个简单的城市之间最短路径问题，求一个城市到所有城市的最短路径，及任意的两个城市之间的最短路径。最后提交完整的设计报告和软件程序拷贝。设计要求：1.编写系统帮助旅客咨询从一个城市顶点到另一个城市顶点之间的最短路径（里程）。2.用户可以根据需要指定一个源点，软件需计算出该源点到其他剩余节点之间的最短距离和详细路径。3.用户可以直接查看所有城市之间的最短距离。参考资料：p 课程设计实验教材 p 数据结构（ C 语言版），严蔚敏，吴伟民编著，清华大学出版社，2007年第1版 任务下达日期 2013 年6 月 24 日完成日期2013年 6 月 28日 目 录第一章：问题描述4第二章：算法设计42.1算法设计分析42.2模块图42.2.2迪杰斯特拉算法52.2.3费洛伊德算法5三 关键代码描述63.1完整的程序代码63.2代码改写9四、运行结果截图展示14五、实验心得15 第一章：问题描述 在交通网络发达，交通工具和交通方式不断更新的今天，人们在出差，旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题更感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，并利用计算机建立一个交通咨询系统。 设计实现一个简单的城市之间最短路径管理咨询系统，能够模拟实现以下功能：1.帮助旅行者了解从一个城市到另一个城市之间的最短路径。2.用户可以根据需要指定一个源点，软件需计算出该源点到其他剩余节点之间的最短距离和详细路径。3.用户可以直接查看所有城市之间的最短距离。 第二章：算法设计2.1算法设计分析该设计共分三个部分：一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现两个城市顶点之间的最短路径问题。 其中，单源最短路径，需要用到迪杰斯特拉（Dijkstra）算法（即迪杰斯特拉提出按路径长度递增产生各定点的最短路径算法）。 任意一对顶点间的最短路径，可以依次把有向网络图中的每个顶点作为源点，重复执行前面讨论过的迪杰斯特拉算法n次，即可求得每对之间的最短路径。这里用另一种算法，费洛依德（Floyd）算法求得。 交通咨询系统 用户查询（建立有向的存储结构）单源最短路任意一对顶点最短路径2.2模块图2.2.1功能的实现 2.2.2迪杰斯特拉算法2.2.3费洛伊德算法三 关键代码描述3.1完整的程序代码/主控程序 #include<stdio.h>#include<stdlib.h>#define MVNum 100 /最大顶点数#define Maxint 32767typedef char VertexType;typedef int Adjmatrix;typedef enum FALSE,TRUE boolean; /定义布尔型typedef structVertexType vexsMVNum; /顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph;int DlMVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;#include"save.c"#include"dijkstra.c"#include"floyd.c"void main( ) MGraph G; int n,e,v,w,k; int xz=1; 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(" 0.退出程序 n"); printf("=n"); printf(" 请选择： 1或2，或 0 :"); scanf("%d",&xz); if(xz=2) Floyd(G,n); /调用洛伊德算法 printf("输入源点（或称起点）和终点: v,w: "); scanf("%d,%d",&v,&w); k=Pvw; /k为起点v的后继顶点 if(k=0) printf("从顶点%d 到 %d 无路径！n",v,w); else printf("从顶点 %d 到 %d 的最短路径是:%d",v,w,v); while(k!=w) printf("->%d",k); /输出后继顶点 k=Pkw; /继续找下一个后继顶点 printf("->%dn",w); /输出终点w printf(" 路径长度: %dn",Dvw); else if(xz=1) printf("求单源路径，输入源点v:"); scanf("%d",&v); Dijkstra(G,v,n); /调用迪杰斯特拉算法 printf("结束求最短路径，再见！n");/建立有向图的存储结构void CreateMGraph(MGraph *G,int n,int e)int i,j,k,w;for (i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->arcsij=Maxint;printf("输入%d 条边i,j及 w:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向图的存储结构建立完毕！n");/迪杰斯特拉算法void Dijkstra(MGraph G,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;boolean SMVNum;for(v=1;v<=n;v+)Sv=FALSE;D2v=G.arcsv1v;if(D2v<Maxint)P2v=v1;elseP2v=0;/end_forD2v=0;Sv=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+) /更新当前最短路径及距离if(!Sw&&D2w<min)v=w;min=D2w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw&&(D2v+G.arcsvw<D2w)D2w=D2v+G.arcsvw;P2w=v;/End_if/End_forprintf("路径长度 路径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;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(G.arcsij!=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+Dkj<Dij) Dij=Dik+Dkj;Pij=Pik; 四、运行结果截图展示 五、实验心得 本实验是对图结构的应用，本章的课程设计是数据结构这门课程的重点，也是应用非常广泛的一种技术，针对图的存储结构以及最短路径等概念进行了综合练习。求最短路径部分是以邻接矩阵作为存储结构，而求关键路径则是以邻接表形式存储。其中运用到两个重要算法，一个是迪杰斯特拉算法，另一个是费洛伊徳算法。 图是一种较线性表和树更为复杂的数据结构，在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继，在图的结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 实验同时说明，图的应用极为广泛，特别是近年来的迅速发展，已经渗入到各个学科中去，例如：在这学期管理运筹学中离散数学中关于图与网络的章节学习。本实验仅仅是图的应用中一个小实例，如果结合可结合MFC书写界面则可以制作一个简单的城市之间最短路径管理软件。实现路径维护功能，程序接受用户输入城市列表(包含城市名称信息)和连接用户城市的路径列表(包含距离信息)，在软件运行过程中这些信息均可修改这些功能。所以，图这一章节是值得我们深入探究的，同时可以多做类似的实例进一步理解图的结构和算法思维。
