交通咨询系统设计

算法与数据结构课程设计交通咨询系统设计专业计算机科学与技术班级姓名指导教师日期目录一．前言.................................................................................................................11．1设计要求......................................................................................................11．2设计思想....................................................................................................11．3设计要求......................................................................................................1二．程序流程图.................................................................................................1三．程序源代码.................................................................................................2四．编译与运行.................................................................................................6五．参考文献......................................................................................................9六．评语..............................................................................................................10评语评阅人：日期：摘要数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系。不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市之间的交通关系。这个交通系统可以回答旅客提出的各种问题。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。本次设计的交通咨询系统主要是运用C语言来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。设计者2011.7.5一.前言:1.设计内容：设计一个交通咨询系统，能让旅客咨询任一个城市到另一个城市之间的最短里程或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需费用或所需时间。该交通咨询系统设计共三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。2.设计思想：用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。3.设计要求：该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。二．程序流程图：三.程序源代码:#includestdio.h#includestdlib.h#defineMVNum100//最大顶点数#defineMaxint35000enumboolean{FALSE,TRUE};typedefcharVertextype;typedefintAdjmatrix;typedefstruct{Vertextypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵，假定为int型}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum];//文件名save.cvoidCreateMGraph(MGraph*G,intn,inte){//采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数inti,j,k,w;for(i=1;i=n;i++)//输入顶点信息G-vexs[i]=(char)i;for(i=1;i=n;i++)for(j=1;j=n;j++)G-arcs[i][j]=Maxint;//初始化邻接矩阵printf(输入%d条边的i,j及w:\n,e);for(k=1;k=e;k++){//读入e条边,建立邻接矩阵scanf(%d,%d,%d,&i,&j,&w);G-arcs[i][j]=w;}printf(有向图的存储结构建立完毕！\n);}//文件名:dijkstra.c(迪杰斯特拉算法）voidDijkstra(MGraph*G,intv1,intn){//用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径p[v]及其权D[v]//设G是有向图的邻接矩阵，若边i,j不存在，则G[i][j]=Maxint//S[v]为真当且仅当v属于S，及以求的从v1到v的最短路径intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v=n;v++){//初始化S和DS[v]=FALSE;//置空最短路径终点集D2[v]=G-arcs[v1][v];//置初始的最短路径值if(D2[v]Maxint)p2[v]=v1;//v1是的前趋（双亲）elsep2[v]=0;//v无前趋}//End_forD2[v1]=0;S[v1]=TRUE;//S集初始时只有源点，源点到源点的距离为0//开始循环，每次求的V1到某个V顶点的最短路径，并加V到S集中for(i=2;in;i++){//其余n-1个顶点min=Maxint;//当前所知离v1顶点的最近距离，设初值为∞for(w=1;w=n;w++)//对所有顶点检查if(!S[w]&&D2[w]min){//找离v1最近的顶点w，并将其赋给v，距离赋给minv=w;//在S集之外的离v1最近的顶点序号min=D2[w];//最近的距离}//W顶点距离V1顶点更近S[v]=TRUE;//将v并入S集for(w=1;w=n;w++)//更新当前最短路径及距离if(!S[w]&&(D2[v]+G-arcs[v][w]D2[w])){//修改D2[w]和p2[w]，w属于V-SD2[w]=D2[v]+G-arcs[v][w];//更新D2[w]p2[w]=v;}//End_if}//End_forprintf(路径长度路径\n);for(i=1;i=n;i++){printf(%5d,D2[i]);printf(%5d,i);v=p2[i];while(v!=0){printf(-%d,v);v=p2[v];}printf(\n);}}//文件名floyd.c(费洛伊德算法）voidFloyd(MGraph*G,intn){inti,j,k;for(i=1;i=n;i++)//设置路径长度D和路径path初值for(j=1;j=n;j++){if(G-arcs[i][j]!=Maxint)p[i][j]=j;//j是i的后继elsep[i][j]=0;D[i][j]=G-arcs[i][j];}for(k=1;k=n;k++){{//做K次迭代，每次均试图将顶点K扩充到当前求得的从i到j的最短路径pij上for(i=1;i=n;i++)for(j=1;j=n;j++){if(D[i][k]+D[k][j]D[i][j]){D[i][j]=D[i][k]+D[k][j];//修改长度p[i][j]=p[i][k];}}}}voidmain(){MGraph*G;intn,e,v,w,k;intxz=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：退出：);scanf(%d,&xz);if(xz==2){Floyd(G,n);//调用费洛伊德算法printf(输入起点和终点:v,w:);scanf(%d,%d,&v,&w);k=p[v][w];//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=p[k][w];//继续找下一个后继顶点}printf(--%d,w);//输出终点wprintf(路径长度:%d\n,D[v][w]);}if(xz==1){printf(求单源路径，输入起点v:);scanf(%d,&v);Dijkstra(G,v,n);//调用迪杰斯特拉算法}}printf(结束求最短路径，再见！\n);}五.编译及运行:编译:在第一次编译时出现了很多错误，是因为我对C语言的不熟练，比如调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出结果。最后把调到外面才OK。运行结果：下面是城市交通图57413622553812236813856517043495111579成都西安郑州北京徐州上海广州五.参考文献:数据结构（C语言版）编著严蔚敏吴伟民清华大学出版社1997数据结构课程设计编著苏仕华机械工业出版社2005数据结构—用c语言描述编著蔡明志中国水利水电出版社2006《数据结构》学习指导与训练编著蒋盛益中国水利水电出版社2003