交通咨询系统设计说明书

1、.wd.wdPAGE7 / NUMPAGES7.wd目录一前言.111设计要求.112设计思想.113设计要求.1二程序流程图.1三程序源代码.2四编译与运行.6五课程总结.9前言:1.设计内容：在交通网络非常兴旺，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图构造来表示交通网络系统，利用计算机建设一个交通咨询系统。图中顶点表示城市之间的交通关系。这个交通系统可以答复旅客提出的各种问题。比方任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。本次设计的交通咨询系统主要是

2、运用C语言来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。设计一个交通咨询系统，能让旅客咨询任一个城市到另一个城市之间的最短里程或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需费用或所需时间。该交通咨询系统设计共三局部，一是建设交通网络图的存储构造；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。2.设计思想：用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。3.设计要求：该交通咨询系统要完成城市网络图的存储，并要实现求

3、任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三局部，一是建设交通网络图的存储构造；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。二程序流程图：程序源代码:#include#include#define MVNum 100 /最大顶点数#define Maxint 35000enum booleanFALSE,TRUE;typedef char Vertextype;typedef int Adjmatrix; typedef struct Vertextype vexsMVNum; /顶点数组， 类型假定为char型Adjm

4、atrix arcsMVNum MVNum; / 邻接矩阵， 假定为int型 MGraph; int D1MVNum, p1MVNum; int DMVNumMVNum,pMVNumMVNum;/文件名save.c void CreateMGraph(MGraph *G,int n,int e) /采用邻接矩阵表示法构造有向图G,n,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

5、(k=1;karcsij=w; printf (有向图的存储构造建设完毕！ n); /文件名:dijkstra.c(迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n) /用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径pv及其权Dv /设G是有向图的邻接矩阵，假设边不存在，那么Gij=Maxint /Sv为真当且仅当v属于S，及以求的从v1到v的最短路径 int D2MVNum, p2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;varcsv1v; /置初始的最短路径值 if(D2v

6、 Maxint) p2v=v1; /v1是的前趋双亲 else p2v=0; /v 无前趋 / End_for D2v1=0;Sv1=TRUE; /S集初始时只有源点， 源点到源点的距离为0/开场循环，每次求的V1到某个V顶点的最短路径，并加V到S集中 for(i=2;in;i+) /其余n-1个顶点 min=Maxint; / 当前所知离v1顶点的最近距离，设初值为 for(w=1;w=n;w+) /对所有顶点检查 if(!Sw & D2wmin) /找离v1最近的顶点w，并将其赋给v，距离赋给min v=w; /在S集之外的离v1最近的顶点序号min=D2w; /最近的距离 /W顶点距离V

7、1顶点更近 Sv=TRUE; /将v并入S集 for(w=1;warcsvwarcsvw; /更新D2w p2w=v; /End_if /End_for 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); /文件名 floyd.c(费洛伊德算法void Floyd(MGraph *G, int n)int i, j, k;for(i=1;i=n;i+) /设置路径长度D和路径path初值for(j=1;j

8、arcsij!=Maxint)pij=j; /j是i的后继elsepij=0;Dij=G-arcsij;for(k=1;k=n;k+) /做K次迭代，每次均试图将顶点K扩大到当前求得的从i到j的最短路径pij上for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj%d,k); /输出后继顶点k=pkw; /继续找下一个后继顶点printf(-%d,w); / 输出终点wprintf( 路径长度:%dn,Dvw); if(xz=1) printf(求单源路径，输入起点v :); scanf(%d, &v); Dijkstra(G,v,n); /调用迪杰斯特拉算法 printf(完毕求最短路径，再见！n);编译及运行:编译: 在第一次编译时出现了很多错误，是因为我对C语言的不熟练，比方调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出结果。最后把调到外面才OK。运行结果：下面是城市交通图五.课程总结通过此次课程设计大大加深了我对数据构造这门课程的理解，而且尤其对图这章的理解，可以说有一个大的进步。学习能力也大大