数据结构课程设计—城市道路交通咨询系统

1、榆林学数据结构课程设计报告目城市交通咨询系统杨朝业信息管理与信息系统号 1514210121指导老师张慧答辩时间2016.12.18目录1.系统需求分析.1.1用户需求分析1.2功能需求分析1.3数据需求分析1.4小结.2.系统设计2.1系统设计功能2.2每个模块的具体功能。2.2.1采用 C 语言定义相关数据类型42.2.2建立邻接矩阵交通网络：2.2.3查询指定城市到其他城市自己建的最短路程：2.2.4查询任意两个城市之间的一条最短路径：2.3 主函数的调用关系图3. 系统测试3.1 操作说明3.2 测试数据104. 总结5. 致谢6. 附录3.2.1 用户进入界面：3.2.2 、具体功能

2、的实现3.2.3 、结束程序1011121313141 . 系统需求分析现如今网络非常发达， 无论人们出差， 旅游或者做其他的出行之时， 都会想 到道路问题， 切不仅仅关心的是交通费用， 而且对于里程和所需要的时间等的问 题也是同样的关心， 在此系统中， 完全面向用户， 可以用一个图结构来表示交通 网络系统，利用计算机建立一个交通咨询系统。且在图中，顶点表示城市，边表 示城市之间的交通关系。 设计一个交通咨询系统， 能够让旅客咨询从任一城市顶 点到达另外一个城市之间顶点的最短路径问题（最短里程问题） 。对系统分析，主要从以下几个方面进行分析。1. 用户需求分析2. 功能需求分析3. 数据需求分

3、析1.1 用户需求分析现如今网络非常发达， 无论人们出差， 旅游或者做其他的出行之时， 都会想 到道路问题， 切不仅仅关心的是交通费用， 而且对于里程和所需要的时间等的问 题也是同样的关心， 在此系统中， 完全面向用户， 可以用一个图结构来表示交通 网络系统，利用计算机建立一个交通咨询系统。且在图中，顶点表示城市，边表 示城市之间的交通关系。 设计一个交通咨询系统， 能够让旅客咨询从任一城市顶 点到达另外一个城市之间顶点的最短路径问题（最短里程问题） 。当要查询某两个城市之间的最短交通路线或者其中一个城市到达其余城市 的最短路线时，是一个很繁琐的过程。根据用户自己的需求， 可以自定义地图， 此

4、程序就是主要以满足用户自己的 环境与实际情况， 在难以计算路程时， 可将地图输入进行计算， 系统将会为用户 提供所用路径最短的出现路线， 更好的满足用户需求。 以下是针对咨询用户说明 其最基本的模块功能。1） 进入程序后， 用户可自己设置城市的个数， 以及所有城市之间总共的路径，且分别用顶点和边表示城市与路径（2） 用户根据自己设置的城市个数和路径数， 具体输入每个路径的起始点 以及每条路径的长度。3）进入菜单选择界面（4）选择 2，系统为用户进行提供任意城市的交通查询 , 即查询任意两个城 市之间的一条最短路径。（5）选择 1，系统为用户提供指定城市的交通查询，即查询指定城市到其 他城市之间

5、的最短路径。 如若输入顶点超出范围显示错误， 系统回到菜单重新选 择6）选择 0，系统推出程序。1.2 功能需求分析城市交通咨询系统总体的设计目标： 用数据结构 中的邻接矩阵作数据结 构，并结合数据结构有向图的最短路径计算方法，结合相应的数据算法以及 c 语言的相关知识，编写一个良好的，具有可操作性的，以及能方便用户的使用， 包括自定义地图， 路径与城市个数可结合实际情况而言， 相对操作， 简便易懂并 无难度。系统在菜单可根据命令进行相应的操作，已满足用户的需求。城市交通系统基本功能根据以上分析，此系统具备以下功能：1）2）用户进入后的地图创建界面（明确地图中城市的个数以及路径的个数）地图完善

6、界面（用户自己输入地图中相关路径的起始点以及路径长度）3）菜单界面包含两条命令命令 1 求一个城市到所有城市的最短距离(5)命令2求任意的两个城市之间的最短距离(6) 回复命令0可推出程序。1.3数据需求分析用邻接矩阵建立交通网络模块VertexType vexsMVNum;/ 顶点数组，类型假定为 charAdjmatrix arcsMVNumMVNum;/ 邻接矩阵，类型假定为 int 型 建立邻接矩阵，用函数 void CreateMGraph(MGraph* G,int n,int e) /采用邻接矩阵表示法构造有向图 G n、e表示图的当前顶点数和边数用迪杰斯特拉算法计算某顶点到其余

7、顶点的最短路径来定义此函数用函数 void Dijkstra (MGraph * G,int n,int e)采用邻接矩阵表示法构造有向图 G, n、e表示图的当前顶点数和边数用弗洛伊德算法求任意一对顶点的最短路径用函数void Floyd(MGra ph *G,i nt n)来定义。利用费洛伊德算法,求出最短路径。1.4小结从各种需求方面下手改编代码，并不断调试，让界面更加友好。不断地尝试 在各种问题上不断突破，慢慢的完善代码，等最大限度的满足用户需求。这上,几天短时间的课程设计也让我认识到了自己在这门课程上还面临着许许多多的 问题，为以后的具体实践明确了努力方向。同时，城市交通咨询系统的实

8、现，为 用户更好的解决了再实际出行时遇到的路径问题，最初的设计也为代码敲定了编 写方向。再三考虑后确定了系统的功能， 确定什么功能有实现必要，什么功能可 有可无。在这样的基础之下使得思路更加清晰。2.系统设计本程序首先是用户编辑界面，用户根据自己的需求编写地图，从而加入顶点 的数组之中，创建的地图用邻接矩阵存储，在从主函数之中进行调用，实现对两 个算法的调用。用户在输入顶点以及边的信息都会存储，在存储成功之后会提示用户存储成 功，之后进入到菜单界面，菜单界面提供两种选择口令，分别可以调运Dijkstra 和Floyd算法，调用之后输入相应的口令以及要查询的城市编号，算法会根据邻接矩阵存储的地图

9、进行计算，求出最短路径。在以后使用完系统后，可输入口令 0,系统会结束一切运算，退出程序。2.1系统设计功能菜单界面的主要功能有两个：(1)、求一个城市到所有城市的最短距离(2)、求任意的两个城市之间的最短距离城市交通咨询系统主要有三个模块分别为:邻接矩阵的输入与存储构建交通网络(2)、任意两个城市的最短距离查询(3)、两个指定城市的最短距离查询主界面的模块概念图如图2-1 :用户进入系统 交通网络构建图2.12.2每个模块的具体功能。2.2.1采用C语言定义相关数据类型1.定义一个，用来存储顶点信息。typ edef structVertexTy pe vexsMAX;Adjmatrix a

10、rcsMAXMAX;MGra ph;.定义一个 Dijkstra 函数void Dijkstra(MGra ph *G,i nt v,i nt n);3. 定义一个Floyd函数 void Floyd(MGra ph *G,i nt n);2.2.2建立邻接矩阵交通网络:结束图2-2邻接矩阵构造图结构函数 数据类型定义:typ edef structVertexTy pe vexsMAX;Adjmatrix arcsMAXMAX;MGra ph;邻接矩阵构成有向图void CreateMGra ph(MGra ph *G,i nt n,i nt e)/for(i=1;i<=n ;i+)G

11、->vexsi=(char)i;for(i=1;i<=n ;i+)for(j=1;j<=n;j+)printf("输入 d条边的 i,j 及 w: n",e);for(k=1;kv=e;k+)scan f("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向图的存储结构建立完毕!n"）;其中vexsMAX保存顶点信息，arcsMAXMAX用于保存边与边之间的信息。在构建时通过输入的边数i , j作为矩阵的行、列确定顶点的出度和入度。用邻接矩阵方法存储图。

12、V分成两组,基本思想：设G（V,E）是一个带权有向图，把图中的顶点集合第一组为已经求出的最短路径的顶点集合（用S表示，初始时S中只有一个原点， 以后每求得一条最短路径就加入的集合 S中，知道全部顶点都加入到集合中）， 第二组，为其余未确定最短路径的顶点集合（用 U表示），按最短路径长度的递 增次序依次把第二组的顶点就如 S中。如果两个顶点之间有权值，并且各个路径 的权值不同，就把最小的作为顶点与顶点的最短距离。y图2-4v=>k=>u。同理若x+yvz，则最短的如图所示 若x+y<z，则最短的路径就是路径就是v=>u,D v1=0;Sv1=1; /原点编号放入s中for

13、(i=2;iv n;i+)mi n=IDF;for(w=1;w<=n; w+)if(!Sw &&D wvmi n)v=w;mi n=D w;Sv=1;/ 修改顶点u放入s中for(w=1;w<=n; w+)if(!Sw &&(D v+G->arcsvwvD w)D w=D v+G->arcsvw;P w=v;2.2.4查询任意两个城市之间的一条最短路径:其具体的流程图如图2-5所示:结用邻接矩阵保存图存储后，另外需要存一个二维数组A存放当前顶点之间的 最短路径长度。分量Aij 表示当前顶点i至叮的最短路径长度。弗洛伊德算 法的基本思维是递

14、推产生一个矩阵序列A0, A1, A2,.Ak,An,其中Akij表示从顶点到vi到顶点vj的路径上所经过的顶点编号不大于 k的最短路径长度。Aij=costijA(k+1)ij=mi nAkij,Aki+1k+1+Akk+1j弗洛伊德主要算法，若Akij 已求出，顶点i到顶点k+1的路径长度为Akik+1，顶点路径长度为Akij，顶点k+1到顶点j的路径长度为Akk+1j，如果此时 Akik+1+Akk+1j< Akij,则将原来的顶点 i到顶点j的路径改为顶点，否则不需要修改顶点i至叮的路径。Aki,k+1Akk+1,jAki,j图2-6修改路径修改长度若 Akik+1+Akk+1

15、j< Akij,过程:for(k=1;kv=n ;k+)for(i=1;i<=n ;i+)for(j=1;j<=n;j+) if(Dik+Dkj<Dij)Dij=Dik+Dkj; /Pij=P ik；2.3主函数的调用关系图程序是通过进入程序之后，用户开始根据自己的实际情况来输入具体的地图 参数，构建自己所需要的地图大小以及城市个数和路径长短。 当输入完毕参数之 后，用户进入主菜单查询界面。可根据不同的选口令，用户可以选择不同的系统 功能。查询1可以进入狄克斯特函数，来求取得到一个城市到所有城市自己还能的 具体的最短路径以及走法。当用户输入口令2之后，可以进入弗洛伊德函

16、数的调用，更加提示用户输入想要查询的两个城市， 系统会根据地图自动计算出所需要 的最短距离以及最短路径，完美的满足用户自己的需求。当输入口令0之后，用 户可以选择退出程序，结束城市查询。同时由于地图的邻接矩阵建立是由 malloc 函数申请的空间，在结束运行之后，系统自动释放空间，从而减少系统空间的占 有率。输出结退出输出结图2-73. 系统测试双击“城市交通咨询系统.exe ”根据屏幕菜单提示信息，选择任意可选项3.1操作说明进行相关操作。根据提示开始输入城市个数以及路径总个数。 之后开始建立地图, 建立成功后根据菜单界面选择功能。3.2测试数据输入测试数据可以对程序进行如下的图的数据进行数

17、据测试。图3-1F面运行程序检查输入，输出结果。321用户进入界面:(1)、输入城市个数与路径个数图3-2杓R 料护卄孜迎咗用城市玄通咨询吞玮甘神*KW=12=巳3, 疔 !j虫=3, 3,4, 3,输人峨加牛纹和路径牛鬣e； 4,fi稀入6条这人L (起点)、j (裂点Ry 樂込氏嗖)：有向3人存诵绪崗建立笼年！一*曲:京*林岀曲*精#:求堀市之闾的最fe距离*曲杯柄=!.求一个城帀對所有最厉更离K"； -"2.求仟意由J商/”城芾之间話最田疤問=：=请选择；1或Z进拜0退出:(2)输入具体的顶点以及边的个数:图3-3地图输入完成，有向图存储结构建立完成。322、具体功能

18、的实现1、求一个城市到所有城市之间的最短距离。查询一个顶点到其他顶点的最短路径。如下图。经过手工计算:1=>1 长度=0, 1=>2 长度=8, 1=>3 长度=8+6=14, 1=>4 长度=8+5=13;和下图完全一致=1,NE-2, 3, 6-2j 4h 5二=二32t 6-3. K 1-13 7 '"育问国人疗陆结柯穿立垃申！曲* *求诚帀:?.间的晶帝髙祗*N*"*W*；*二減诞飜蕊辛鹦龍鷲芸:1或匕 滋毎0逵出上1 亠求单邀毙往，输人源点1粘毘:路径反瞠.0S141321】4<-2<-1 _亠求 城市之 间的最蛊意複#

19、«<*#*#*：#*图3-4为保证结果正确换一个顶点进行：如顶点 2到其他的距离经过手工计算：2=>1长度=6+4=10, 2=>2长度=0, 2=>3长度=6，2=>4长=-请送择；1或沢 选择n君出I 1 =一求苹源路径*输入源点¥- ?路牡K-3<-23<-24< 2_10065林林杯和<：M（林林 求域市Z间的距 离林窝杠 林林和林二二二二L求一个诚市到別有城市的最短壯厲- =2求仕意的两个城市Z间的最矩距离=度=5;和下图完全一致图3-52、求任意的两个城市之间的最短距离例1到3之间的最短距离，经过计算可得最短

20、距离为仁>2=>3,且路径请选择；1或2,选择0退a： 2=输入源点和终点：V, W： 1, 3二=从顶点1到3最短路径是1->2-3=路径长度：14,_材* *# *4 #拓益衬水求城市之 间的最短距离京:沖左:*衬* *：*掾任錨課蠶鸚朧蠶请选择；1或选择0退&为14,与下图结果相同。图3-6为保证结果正确换一个顶点进行：如顶点 2到4之间的最短路径以及 距离经过计算可得2到4的最短路径是2=>4,且最短路径为5图3-7323、结束程序当用户输入命令0时，结束程序图3-84. 总结通过这次数据结构课程设计， 我对数据结构 这门课程有了更深一步的了 解，使我对

21、数据结构这门课程掌握以及运用更加灵活。同时也让我发现了自 己在这门课上的不足与缺陷， 同时也明确了自己在以后的类似课程中的具体学习 方法。这次在应用中， 我发现了自己的很多不足， 在编写城市交通咨询系统的过程 中，自己C语言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一 次的更改， 一次又一次的失败， 也终于是在最后也完成了自己的要求， 同时我也 知道了平时用功学习的重要性。 尤其是在日常学习之中， 对于单一的只是点也许 掌握的还不错，但是自己动手太少，实践经验严重不足，且面临课程设计之时， 要求多方面的只是结和编码， 对于我而言还是有很大的难度的。 如此次对于邻接 矩阵的存储于读取

22、， 以及最短路径算法的实现， 两个及其重要的算法， 狄克斯特 拉算法和佛洛依德算法，在具体的应用上还是有很多不足。通过此次课程设计， 我也明白了对于一个完成的程序而言， 想要完成它最重 要的代码， 最初，也是最为重要的一个部分就是算法思想， 以及具体程序功能规 划，只有最重要的地基部分完美实现， 才可以进行接下来的具体代码编程， 以及 更多细节上的完美。通过这次的课程设计我有懂得了好多数据结构的知识，以前上课没有听的， 不知道的，这次都有所了解了，像有向图的构建，弗洛伊德算法，迪克斯特拉算 法。这些知识从曾经的听说到现在的了解，进了一大步。不但如此，这次的课设 也是我感觉到了数据结构的强大与神

23、奇。 渐渐的爱上他了。 不仅让我了解了数据 结构更加深了对它与 C 语言的联系的理解。因为自己的不学习， 导致这次的课设变得如此的艰难。 且因为自己生病住院 也更是浪费了很大的时间， 对于我自己做课程设计的时间就少的可怜， 这也无疑 是对我更大的挑战。 在临近答辩， 我的代码才基本完成， 夜以继日的努力也终于 是让我完成5. 致谢本次课程设计我遇到了极大的问题， 不管是时间方面还是内容方面， 自己都显得慌乱过， 我能够完成本次课程设计也完全感谢舍友的支持与帮助， 在难点上 能够对我进行帮助。 尤其感谢我的知道老师张老师。 感谢她在百忙之中抽出时间 来为我解答疑惑， 解决问题， 她对我此次的课程

24、设计有极大的帮助。 再次感谢张 老师。课程设计马上结束， 同时也谢谢所有的负责老师， 谢谢她们这几天对我们 的付出，老师辛苦了。6. 附录#include<stdio.h> #include<stdlib.h> #define MVNum 100/ 最大顶点数#define Maxint 32767 enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;/ 顶点数组，类型假定为 charAdjmatrix arcsMV

25、NumMVNum;/ 邻接矩阵，类型假定为 int 型MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;/* 建立有向图的储存结构 */ void CreateMGraph(MGraph * G,int n,int e)/ 采用邻接矩阵表示法构造有向图G，n、 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;/初始化邻接矩阵p

26、rintf("=径长度)：n",e);输入c条边人i （起点）、j （终点）及W （路for(k=1;k<=e;k+)/读入 e 条边，建立邻接矩阵="); printf(" scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向图人存储结构建立完毕！ =n"）;/* 迪杰斯特拉算法 */ void Dijkstra(MGraph *G,int v1,int n)/利用迪杰斯特拉算法，求出有向图G的v1顶点到其他顶点V的最短路径Pv 及

27、权 Dv int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;vv=n;v+)/初始化 S 和 DSv=FALSE;/ 置空最短路径终点集D2v=G->arcsv1v;/ 置初始的最短路径值if(D2v<Maxint)P2v=v1;/v1 是 v 的前趋（双亲）elseP2v=0;/v 无前趋（双亲）D2v1=0;Sv1=TRUE;/S 集初始时只有源点，距离为 0 for(i=2;i<n;i+)/ 其余 n-1 个顶点min=Maxint;for(w=1;w<=n;w+) if(!Sw &

28、& D2w<min) v=w;min=D2w; /w 顶点离 v1 顶点更近Sv=TRUE;for(w=1;w<=n;w+)/ 更新当前最短路径及距离if(!Sw&&(D2v+G->arcsvw<D2w) D2w=D2v+G->arcsvw;P2w=v;printf("路径长度，路径 =n");for(i=1;i<=n;i+) printf("%5d",D2i);printf("%5d",i); v=P2i;while(v!=0) printf("<-%d&q

29、uot;,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;void main()printf("*欢迎使用城市交通咨询系统*n");printf("n");