算法与数据结构课程设计《兰州道路交通网络信息查询设计说明书》

页摘要在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣。对于们关心的问题，可用一个图结构和表示交通网络系统，利用计算机建立一个交通咨询系统。关键词：交通网络，邻接矩阵，最短路径。

前言图是一种复杂的非线性结构。在人工智能，工程，数学，物理，化学，计算机学科等领域中，图结构有着广泛的应用。我们用最短路径问题，用一个人们熟悉的交通咨询系统实例来验证迪杰斯特拉算法和费洛伊德得算法。我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。设计一个兰州道路交通咨询系统，能让人们咨询从任一个地方顶点到另一地方顶点之间的最短路径。在计算机中，有多种方法存储图的信息，由于图的结构复杂，使用广泛，一般应根据实际的应用，选择适合的表示方法。常用的图的存储结构有邻接矩阵、邻接多重表和邻接表。

正文采用类c语言定义相关的数据类型采用邻接矩阵定义图typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵，假定为int型}MGraph;建立图的存储结构#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大顶点数#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵，假定为int型}MGraph;

各模块的伪码算法（1）迪杰斯特拉算法的实现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];v,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是v的前趋（双亲）elseP2[v]=0;//v无前趋}D2[v1]=0;S[v1]=TRUE;//S集初始时只有源点，源点到源点的距离为0//开始循环，每次求得v1到某个v顶点的最短路径，并加v到s集中for(i=2;i<n;i++){//其余n-1个顶点min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}//w顶点离v1顶点更近S[v]=TRUE;for(w=1;w<=n;w++)//更新当前最短路径及距离if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}//End_if}//End_forprintf("lujingchangdulujing\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");}}（2）费洛伊德得算法的实现voidFloyd(MGraph*G,intn){intD[MVNum][MVNum],P[MVNum][MVNum];i,j,k,v,w;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的后继else P[i][j]=0; D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {for(i=1;i<=n;i++)//做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上 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]; }}}}

3.函数的调用关系图主函数主函数main调用费洛伊德算法voidFloyd调用费洛伊德算法voidFloyd创建图VoidMGraph调用迪杰斯特拉算法voidDijkstra调用迪杰斯特拉算法voidDijkstra打印图的邻接矩阵VoidMGraph

4.调试分析a、调试中遇到的问题及对问题的解决方法在输入顶点和边数时，要注意输入的格式，如果在编写程序时用的输入方式是“，”，则在输入顶点和边数时必须用逗号将两个数值隔开，如要输入5和3，则正确的输入方式是：5，3。如果输入出现错误，则会出现死循环。b、算法的时间复杂度和空间复杂度时间复杂度：创建图并以邻接矩阵存储的时间复杂度为O(n)迪杰斯特拉算法的时间复杂度O（n³)费洛伊德得算法的时间复杂度O（n³)

5.测试结果abgcabgcfed兰州道路交通网图91020181581053012一个有向图因为在算法中，为了操作方便，对于图的顶点都是用序号来表示的，所以顶点的字母就用其对应的序号来操作a(1),b(2),c(3),d(4),e(5),f(6),g(7)。（1）图的邻接矩阵#defineM20#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefstruct{intV[M];intR[M][M];intvexnum;}MGraph;voidcreatgraph(MGraph*G,intn){inti,j,r1,r2;g->vexnum=n;for(i=1;i<=n;i++){g->V[i]=i;}for(i=1;i<=n;i++)for(j=1;j<=n;j++){g->R[i][j]=0;}printf("PleaseinputR(0,0END):\n");scanf("%d,%d",&r1,&r2);while(r1!=0&&r2!=0){g->R[r1][r2]=1;g->R[r2][r1]=1;scanf("%d,%d",&r1,&r2);}}voidprintgraph(MGraph*G){inti,j;for(i=1;i<=g->vexnum;i++){for(j=1;j<=g->vexnum;j++){printf("%2d",g->R[i][j]);}printf("\n");}}main(){intn;MGraph*G=(MGraph*)malloc(sizeof(MGraph));charmenu;printf("Pleaseinputthenumberofvertex:\n");scanf("%d",&n);creatgraph(g,n);printf("Thisisthelinjiejuzhenofgraph:\n");printgraph(g);}（2）求两个顶点之间的最短路径和求两个顶点之间是否有路径存在：

6.源程序（带注释）#include<stdio.h>#include<stdlib.h>#defineMVNum100//最大顶点数#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵，假定为int型}MGraph;voidCreateMGraph(MGraph*G,intn,inte){//采用邻接矩阵表示法构造有向图G，n，e表示图的当前顶点数和边数intarcs[MVNum][MVNum];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("shuru%dtiaobiandei,j,w:\n",e);for(k=1;k<=e;k++){//读入e条边，建立邻接矩阵scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("youxiangtudecunchujiegoujianliwanbi!\n");}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是v的前趋（双亲）elseP2[v]=0;//v无前趋}D2[v1]=0;S[v1]=TRUE;//S集初始时只有源点，源点到源点的距离为0//开始循环，每次求得v1到某个v顶点的最短路径，并加v到s集中for(i=2;i<n;i++){//其余n-1个顶点min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){v=w;min=D2[w];}//w顶点离v1顶点更近S[v]=TRUE;for(w=1;w<=n;w++)//更新当前最短路径及距离if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){D2[w]=D2[v]+G->arcs[v][w];P2[w]=v;}//End_if}//End_forprintf("lujingchangdulujing\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");}}voidFloyd(MGraph*G,intn){intD[MVNum][MVNum],P[MVNum][MVNum];inti,j,k,v,w;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的后继else P[i][j]=0; D[i][j]=G->arcs[i][j];}for(k=1;k<=n;k++) {for(i=1;i<=n;i++)//做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上 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]; }}}}intD1[MVNum],P1[MVNum];intD[MVNum][MVNum],P[MVNum][MVNum];voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));printf("shurutuzhongdingdiangeshuhebianshun,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);//建立图的存储结构while(xz!=0){printf("*****qiudefangzhijiandezuiduanlujing*****\n");printf("==============================\n");printf("1,qiuyigedefangdaosuoyoudefangdezuiduanlujing\n");printf("2,qiurenyilianggedefangzhijiandezuiduanlujing\n");printf("===============================\n");printf("qingxuanze:1or2,xuanze0exit:");scanf("%d",&xz);if(xz==2){Floyd(G,n);//调用费洛伊德算法printf("shuruqidianhezhongdian:v,w:");scanf("%d,%d",&v,&w);k=P[v][w];if(k==0)printf("dingdian%ddao%dwulujing!\n",v,w);else{printf("congdingdian%ddao%ddezuiduanlujingshi:%d",v,w,v);while(k!=w){printf("->%d",k);//输出后继顶点k=P[k][w];//继续找下一个后继顶点}printf("->%d",w);//输出终点wprintf("lujingchangdu:%d\n",D[v][w]);}}elseif(xz==1){printf("qiudanyuanlujing,shuruqidianv:");scanf("%d",&v);Dijkstra(G,v,n);//调用迪杰斯特拉算法}}printf("jieshuqiuzuiduanlujing,byebye!\n");}

总结在这三周的数据结构课程设计中,我的题目是:兰州道路交通网络信息查询,这三周课程设计中,通过该题目的设计过程,我加深了对图的建立和对迪杰斯特拉算法以及费洛伊德算法的理解,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展。在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很大，学到很多。

参考文献严蔚敏，陈文博编