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

1、榆林学院数据结构课程设计报告题目城市交通咨询系统作者皿专业信息管理与信息系统学号指导老师张慧答辩时间目录1 .系统需求分析11.1 用户需求分析11.2 功能需求分析21.3 数据需求分析21.4 小结32 .系统设计32.1 系统设计功能32.2 每个模块的具体功能。2.2.1 采用C语言定义相关数据类型42.2.2 建立邻接矩阵交通网络：42.2.3 查询指定城市到其他城市自己建的最短路程：62.2.4 查询任意两个城市之间的一条最短路径：72.3 主函数的调用关系图83 .系统测试93.1 操作说明93.2 测试数据103.2.1 户进入界面：103.2.2 具体功能的实现113.2.3

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

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

4、输入进行计算，系统将会为用户提供所用路径最短的出现路线，更好的满足用户需求。以下是针对咨询用户说明其最基本的模块功能。（1）进入程序后，用户可自己设置城市的个数，以及所有城市之间总共的路径，且分别用顶点和边表示城市与路径(2)用户根据自己设置的城市个数和路径数，具体输入每个路径的起始点以及每条路径的长度。(3)进入菜单选择界面(4)选择2,系统为用户进行提供任意城市的交通查询，即查询任意两个城市之间的一条最短路径。(5)选择1,系统为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路径。如若输入顶点超出范围显示错误，系统回到菜单重新选择(6)选择0,系统推出程序。1.2 功能需求

5、分析城市交通咨询系统总体的设计目标：用数据结构中的邻接矩阵作数据结构，并结合数据结构有向图的最短路径计算方法，结合相应的数据算法以及c语言的相关知识，编写一个良好的，具有可操作性的，以及能方便用户的使用，包括自定义地图，路径与城市个数可结合实际情况而言，相对操作，简便易懂并无难度。系统在菜单可根据命令进行相应的操作，已满足用户的需求。城市交通系统基本功能根据以上分析，此系统具备以下功能：(1) 用户进入后的地图创建界面(明确地图中城市的个数以及路径的个数)(2) 地图完善界面(用户自己输入地图中相关路径的起始点以及路径长度)(3) 菜单界面包含两条命令(4) 命令1求一个城市到所有城市的最短距

6、离(5) 命令2求任意的两个城市之间的最短距离(6) 回复命令0可推出程序。1.3 数据需求分析用邻接矩阵建立交通网络模块VertexTypevexsMVNum;/顶点数组，类型假定为charAdjmatrixarcsMVNumMVNum;/邻接矩阵，类型假定为int型建立邻接矩阵，用函数voidCreateMGraph(MGraph*G,intn,inte)/采用邻接矩阵表示法构造有向图Gn、e表示图的当前顶点数和边数用迪杰斯特拉算法计算某顶点到其余顶点的最短路径用函数voidDijkstra(MGraph*G,intn,inte)来定义此函数采用邻接矩阵表示法构造有向图G,n、e表示图的当

7、前顶点数和边数用弗洛伊德算法求任意一对顶点的最短路径用函数voidFloyd(MGraph*G,intn)来定义。利用费洛伊德算法，求出最短路径。1.4 小结从各种需求方面下手改编代码，并不断调试，让界面更加友好。不断地尝试上，在各种问题上不断突破，慢慢的完善代码，等最大限度的满足用户需求。这几天短时间的课程设计也让我认识到了自己在这门课程上还面临着许许多多的问题，为以后的具体实践明确了努力方向。同时，城市交通咨询系统的实现，为用户更好的解决了再实际出行时遇到的路径问题，最初的设计也为代码敲定了编写方向。再三考虑后确定了系统的功能，确定什么功能有实现必要，什么功能可有可无。在这样的基础之下使得

8、思路更加清晰2.系统设计本程序首先是用户编辑界面，用户根据自己的需求编写地图，从而加入顶点的数组之中，创建的地图用邻接矩阵存储，在从主函数之中进行调用，实现对两个算法的调用。用户在输入顶点以及边的信息都会存储，在存储成功之后会提示用户存储成功，之后进入到菜单界面，菜单界面提供两种选择口令，分别可以调运Dijkstra和Floyd算法，调用之后输入相应的口令以及要查询的城市编号，算法会根据邻接矩阵存储的地图进行计算，求出最短路径。在以后使用完系统后，可输入口令0,系统会结束一切运算，退出程序。2.1 系统设计功能菜单界面的主要功能有两个：(1)、求一个城市到所有城市的最短距离(2)、求任意的两个

9、城市之间的最短距离城市交通咨询系统主要有三个模块分别为：(1)、邻接矩阵的输入与存储构建交通网络(2)、任意两个城市的最短距离查询(3)、两个指定城市的最短距离查询主界面的模块概念图如图2-1:用户进入系统交通网络构建输入顶点和边数n,ei,j,w两个指定城市的2.2每个模块的具体功能。2.2.1采用C语言定义相关数据类型1.定义一个，用来存储顶点信息typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;void Dijkstra(MGraph *G,int v,int n);3.定义一个Floyd函数void Floyd(M

10、Graph *G,int n);2.2.2建立邻接矩阵交通网络:结果，退出系统图2.12.定义一个 Dijkstra 函数任意两个城市的开始k<=e,k+图2-2邻接矩阵构造图结构函数数据类型定义：typedefstructVertexTypevexsMAX;AdjmatrixarcsMAXMAX;MGraph;voidCreateMGraph(MGraph*G,intn,inte)/inti,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->

11、arcsij=IDF;printf("输入族边的i,j及w:n",e);for(k=1;k<=e;k+)scanf（"%d,%d,%d",&i,&j,&w）;G->arcsij=w;printf（"有向图的存储结构建立完毕！n"）;其中vexsMAX保存顶点信息,arcsMAXMAX用于保存边与边之间的信息。在构建时通过输入的边数i,j作为矩阵的行、列确定顶点的出度和入度。用邻接矩阵方法存储图。2.2.3查询指定城市到其他城市自己建的最短路程:图2-3斯应用狄克斯特拉算法来具体/现2一步的需求。基本

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

13、t;n;i+)(min=IDF;for(w=1;w<=n;w+)if(!Sw&&Dw<min)(v=w;min=Dw;Sv=1;/修改顶点u放入s中for(w=1;w<=n;w+)if(!Sw&&(Dv+G->arcsvw<Dw)Dw=Dv+G->arcsvw;Pw=v；2.2.4查询任意两个城市之间的一条最短路径:其具体的流程图如图2-5所示:用邻接矩阵保存图存储后，另外需要存一个二维数组A存放当前顶点之间的最短路径长度。分量Aij表示当前顶点i到j的最短路径长度。弗洛伊德算法的基本思维是递推产生一个矩阵序列A0,A1,A2

14、,-.Ak,An,其中Ak皿表示从顶点到vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度A皿=cost皿A(k+1)ij=minAkij,Aki+1k+1+Akk+1j弗洛伊德主要算法，若Akij已求出，顶点i到顶点k+1的路径长度为Akik+1,顶点路径长度为Ak皿,顶点k+1到顶点j的路径长度为Akk+1j,如果此时Akik+1+Akk+1j<Ak皿,则将原来的顶点i到顶点j的路径改为顶点，否则不需要修改顶点i至”的路径。k+Aki,k+1Akk+1,jAki,j图2-6若Akik+1+Akk+1j卜Akij,修改路径过程：for(k=1;k<=n;k+)for(i

15、=1;i<=n;i+)for(j=1;j<=n;j+)if(Dik+Dkj<D皿)Dij=Dik+Dkj;修改长度Pij=Pik;2.3主函数的调用关系图程序是通过进入程序之后，用户开始根据自己的实际情况来输入具体的地图参数，构建自己所需要的地图大小以及城市个数和路径长短。当输入完毕参数之后，用户进入主菜单查询界面。可根据不同的选口令，用户可以选择不同的系统功能。查询1可以进入狄克斯特函数，来求取得到一个城市到所有城市自己还能的具体的最短路径以及走法。当用户输入口令2之后，可以进入弗洛伊德函数的调用，更加提示用户输入想要查询的两个城市，系统会根据地图自动计算出所需要的最短距离

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

17、-2(2)输入具体的顶点以及边的个数:图3-3地图输入完成，有向图存储结构建立完成3.2.2、具体功能的实现1、求一个城市到所有城市之间的最短距离。查询一个顶点到其他顶点的最短路径。如下图。经过手工计算:1=>1长度=0,1=>2长度=8,1=>3长度=8+6=14,1=>4长度=8+5=13;和下图完全一致=1,2,8=22E-2,4卜5-3j6=3tL437''宣向四人存储结构律立宪甲！一m：t*±*4*求域币y二：产；u-*xh*h*L求一卜城tr到所有城t的最原距离=Z第任意的杆个城市之的聂达界高=：盾选择:1或匕注择。退出:1求工源跄

18、j三旬源；.二二畴径隹度，路径二=0I=82<-1-1+3<-2<-1=134<-2<-1点*本加求城市之间的最加笈前要*本*4*二三百二不建运丽加彳曲3盲品高=3求任意的两个城市之间的最短距离=请选择t1或L透邪0退出上图3-4为保证结果正确换一个顶点进行：如顶点2到其他的距离经过手工计算：2=>1长度=6+4=10,2=>2长度=0,2=>3长度=6,2=>4长二二二二请选择：1或2,选择口退出士1求单源路衿,输人源点v二2=踣役长度.踣役=二二二101<-3<-2二二二0263<-2=54<-2*粗皿制u0Mc

19、求城市之何的最近距离%*=1.求一个城市到所有城市的最短距离二=2.求任意的两个城市之间的最短更离=度=5;和下图完全一致图3-52、求任意的两个城市之间的最短距离例1到3之间的最短距离，经过计算可得最短距离为1=>2=>3,且路径=请选择：1或2,选择0退出；2输入源点和终点:v,w：1,3=从顶点1到3最短路径是1->2->3二二二二路径长度114_二二*宓*求城市之间的最短距离*=L求一个城市到所有城市的最短距离=二=二二2,求任意的两个城市之间的最短距离=请选择：1或，选择0退出;为14,与下图结果相同图3-6为保证结果正确换一个顶点进行：如顶点2到4之间的最短

20、路径以及距离经过计算可得2到4的最短路径是2=>4,且最短路径为5图3-73.2.3、结束程序当用户输入命令0时，结束程序图3-84.总结通过这次数据结构课程设计，我对数据结构这门课程有了更深一步的了解，使我对数据结构这门课程掌握以及运用更加灵活。同时也让我发现了自己在这门课上的不足与缺陷，同时也明确了自己在以后的类似课程中的具体学习方法。这次在应用中，我发现了自己的很多不足，在编写城市交通咨询系统的过程中，自己C语言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一次的更改，一次又一次的失败，也终于是在最后也完成了自己的要求，同时我也知道了平时用功学习的重要性。尤其是在日常学习之

21、中，对于单一的只是点也许掌握的还不错，但是自己动手太少，实践经验严重不足，且面临课程设计之时，要求多方面的只是结和编码，对于我而言还是有很大的难度的。如此次对于邻接矩阵的存储于读取，以及最短路径算法的实现，两个及其重要的算法，狄克斯特拉算法和佛洛依德算法，在具体的应用上还是有很多不足。通过此次课程设计，我也明白了对于一个完成的程序而言，想要完成它最重要的代码，最初，也是最为重要的一个部分就是算法思想，以及具体程序功能规划，只有最重要的地基部分完美实现，才可以进行接下来的具体代码编程，以及更多细节上的完美。通过这次的课程设计我有懂得了好多数据结构的知识，以前上课没有听的，不知道的，这次都有所了解

22、了，像有向图的构建，弗洛伊德算法，迪克斯特拉算法。这些知识从曾经的听说到现在的了解，进了一大步。不但如此，这次的课设也是我感觉到了数据结构的强大与神奇。渐渐的爱上他了。不仅让我了解了数据结构更加深了对它与C语言的联系的理解。因为自己的不学习，导致这次的课设变得如此的艰难。且因为自己生病住院也更是浪费了很大的时间，对于我自己做课程设计的时间就少的可怜，这也无疑是对我更大的挑战。在临近答辩，我的代码才基本完成，夜以继日的努力也终于是让我完成5 .致谢本次课程设计我遇到了极大的问题，不管是时间方面还是内容方面，自己都显得慌乱过，我能够完成本次课程设计也完全感谢舍友的支持与帮助，在难点上能够对我进行帮

23、助。尤其感谢我的知道老师张老师。感谢她在百忙之中抽出时间来为我解答疑惑，解决问题，她对我此次的课程设计有极大的帮助。再次感谢张老师。课程设计马上结束，同时也谢谢所有的负责老师，谢谢她们这几天对我们的付出，老师辛苦了。6 .附录#include<stdio.h>#include<stdlib.h>#defineMVNum100最大顶点数#defineMaxint32767enumbooleanFALSE,TRUE;typedefcharVertexType;typedefintAdjmatrix;typedefstructVertexTypevexsMVNum;/顶点数组

24、，类型假定为charAdjmatrixarcsMVNumMVNum;/邻接矩阵，类型假定为int型MGraph;intD1MVNum,P1MVNum;intDMVNumMVNum,PMVNumMVNum;/*建立有向图的储存结构*/voidCreateMGraph(MGraph*G,intn,inte)/采用邻接矩阵表示法构造有向图G,n、e表示图的当前顶点数和边数inti,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;/初

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

26、VNum,P2MVNum;intv,i,w,min;enumbooleanSMVNum;for(v=1;v<=n;v+)/初始化S和DSv=FALSE;/置空最短路径终点集D2v=G->arcsv1v;/置初始的最短路径值if(D2v<Maxint)P2v=v1;/v1是v的前趋(双亲)elseP2M=0;/v无前趋(双亲)D2v1=0;Sv1=TRUE;/S集初始时只有源点，距离为0for(i=2;i<n;i+)/其余n-1个顶点min=Maxint;for(w=1;w<=n;w+)if(!Sw&&D2w<min)v=w;min=D2w;/

27、w顶点离v1顶点更近Sv=TRUE;for(w=1;w<=n;w+)/更新当前最短路径及距离if(!Sw&&(D2M+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",v);v=P2v;printf("n");/*费

28、洛伊德算法*/voidFloyd(MGraph*G,intn)/利用费洛伊德算法，求出最短路径intij,k;for(i=1;i<=n;i+)for(j=1;j<=n;j+)(if(G->arcsij!=Maxint)Pi0=j；elsePiU=O；Dij=G->arcsiU;)for(k=1;k<=n;k+)(for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(Dik+DkU<Dij)Dij=Dik+DkU;)voidmain()(printf("*欢迎使用城市交通咨询系统*n");printf("n");printf("=n")；MGrap