3-交通咨询系统设计-数据结构-课程设计任务书

1交通资讯系统1.系统需求分析1.1问题描述在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。1.2功能要求1.交通资讯系统提供用户三种决策方案：一是建立交通网络图的存储结构。二是某个城市到达其余各城市的最短路径。三是实现两个城市之间最短路径的问题。主要目的是给用户提供路径咨询。2.本系统规定：(1)在程序中输入城市名称时，需输入0到5的城市代号(2)在选择功能是，应输入与所选功能对应的一个整形数据。(3)程序的输出信息主要是：城市代号，某城市到达其余各城市的最短路径，两城市之间最短路径22.概要设计2.1系统总体设计图2.1系统总体设计2.2各模块的功能voidmain()主函数voidDijkstr()采用狄克斯特拉算法求从顶点v到其余个顶点的最短路径voidDisPath()由path计算最短路径voidPpath()输出各条最短路径voidFloyd()采用弗洛伊德算法求所有顶点之间的最短路径voidDisPath2()由path计算最短路径voidPpath2()输出各条最短路径交通资讯系统一个城市到其他城市两个城市之间存储交通图查询最短距离获得最佳路径查询最短距离获得最佳路径32.3相关数据结构设计1.数据结构typedefintInfoType;typedefstruct{charcityname;intno;InfoTypeinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevxs[MAXV];}MGraph;2.数据库结构：下表构成该系统的基本数据库城市代号邻接矩阵边数组城市个数路径城市名称intintintintchar3.详细设计3.1采用c语言定义相关的数据结构本系统定义了整形int,字符型char,还有结构体定义，建立图的存储结构首先定义交通图的存储结构，邻接矩阵是表示图形中顶点之间相邻关系的矩阵.设G=（V，E）是具有n(n0)个顶点的图，则邻接矩阵具有如下定义的n阶方阵Wij若vi≠vj且vi,vj∈E(G)A[i][j]=∞其他一个图的邻接矩阵表示是唯一的,除了许用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息43.2函数调用关系图3.2.1主函数voidmain(){inti,j,z,x;MGraphg;intA[][MAXV]={{INF,5,INF,7,INF,INF},{INF,INF,4,INF,INF,INF},{8,INF,INF,INF,INF,9},{INF,INF,5,INF,INF,6},{INF,INF,INF,5,INF,INF},{3,INF,INF,INF,1,INF}};g.n=6;g.e=10;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];printf(*******************交通咨询系统**********************\n);main函数z=1查看系统中的城市代号z=2;调用Dijkstra函数求v到其余各顶点的最短路径调用DisPath函数计算最短路径调用ppath函数输出各条最短路径z=3;调用Floyd函数求所有定点之间的最短路径调用ppath2函数输出各条最短路径调用DisPath2函数计算最短路径z=0退出程序5printf(*************1-查看系统中的城市代号**********\n);printf(*************2-一个城市到所有城市的最短路径**********\n);printf(*************3-任意的两个城市之间的最短路径**********\n);printf(*************0-退出**********\n);printf(\n);printf(请选择：);scanf(%d,&z);while(z!=0){switch(z){case1:printf(0——北京,1——天津,2——上海,3——广州,4——南京,5——厦门\n);printf(\n);main();scanf(%d,&z);break;case2:printf(请输入城市代号:);scanf(%d,&x);switch(x){case0:printf(以下是最短路径：\n);Dijkstra(g,x);break;case1:printf(以下是最短路径：\n);Dijkstra(g,x);break;case2:6printf(以下是最短路径：\n);Dijkstra(g,x);break;case3:printf(以下是最短路径：\n);Dijkstra(g,x);break;case4:printf(以下是最短路径：\n);Dijkstra(g,x);break;case5:printf(以下是最短路径：\n);Dijkstra(g,x);break;default:printf(输入有误，请重新输入\n);printf(\n);main();}printf(\n);main();scanf(%d,&z);break;case3:Floyd(g);printf(请选择：);printf(\n);main();scanf(%d,&z);break;case0:exit(-1);break;default:printf(输入有误，请重新输入\n);printf(\n);main();}}}73.2.2狄克斯特拉函数初始化距离和路径，将s[]置为空。将远点编号v放入s中,循环直到所有顶点的最短路径都求出，将mindis置最小长度初值，选取不在s中且具有最小距离的顶点u将顶点u加入s中，修改不在s中的顶点的距离，输出最短路径voidDijkstra(MGraphg,intv){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;ig.n;i++){dist[i]=g.edges[v][i];s[i]=0;if(g.edges[v][i]INF)path[i]=v;elsepath[i]=-1;}s[v]=1;path[v]=0;for(i=0;ig.n;i++){mindis=INF;for(j=0;jg.n;j++)if(s[j]==0&&dist[j]mindis){u=j;mindis=dist[j];}s[u]=1;for(j=0;jg.n;j++)if(s[j]==0)if(g.edges[u][j]INF&&dist[u]+g.edges[u][j]dist[j]){8dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}Dispath(dist,path,s,g.n,v);}3.2.3Ppath函数前向递归查找路径上的顶点，找到起点则返回，找顶点k的前一个顶点，输出顶点k。voidPpath(intpath[],inti,intv){intk;k=path[i];if(k==v)return;Ppath(path,k,v);printf(%d,,k);}3.2.4Dispath函数有path函数计算最短路径，搜索最短路径的所有边，输出路径上的起点，输出路径上的中间点，输出路径上的终点。voidDispath(intdist[],intpath[],ints[],intn,intv){inti;for(i=0;in;i++){if(s[i]==1&&dist[i]!=INF){printf(从%d到%d的最短路径长度为：%d\t路径为：,v,i,dist[i]);9printf(%d,,v);Ppath(path,i,v);printf(%d\n,i);}elseprintf(从%d到%d不存在路径\n,v,i);}}3.2.5弗洛伊德函数设置路径长度A和路径path初值。做k次迭代，每次均试图将顶点K扩充到点钱球得的从i到j的最短路径Pij上，修开路径长度，输出最短路径。voidFloyd(MGraphg){intpath[MAXV][MAXV],A[MAXV][MAXV];inti,j,k;for(i=0;ig.n;i++)for(j=0;jg.n;j++){A[i][j]=g.edges[i][j];path[i][j]=-1;}for(k=0;kg.n;k++){for(i=0;ig.n;i++)for(j=0;jg.n;j++)if(A[i][j]A[i][k]+A[k][j]){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}3.2.6Ppath2函数向前递归查找路径上的顶点，找到了起点则返回，，找顶点i的前一个顶点k，找顶点k的前一个顶点j。在path中递归输出从顶点i到顶点j的最短路径10voidPpath2(intpath[][MAXV],inti,intj){intk;k=path[i][j];if(k==-1)return;Ppath2(path,i,k);printf(%d,,k);Ppath2(path,k,j);}3.2.7DisPath2函数由path计算最短路径，若顶点i和顶点j之间没有边，则输出i到j没有路径，若有边则输出路劲上的起点、中间点和终点。voidDispath2(intA[][MAXV],intpath[][MAXV],intn){inti,j;printf(请输入起点和终点(i,j)：);scanf(%d,%d,&i,&j);if(A[i][j]==INF){if(i!=j)printf(从%d到%d没有路径\n,i,j);}else{printf(从%d到%d路径为：,i,j);printf(%d,,i);Ppath2(path,i,j);printf(%d,j);printf(\t路径长度为：%d\n,A[i][j]);}11}4.系统调试4.1系统调试中的问题（1）只考虑函数而忽视数据库和标点：在存储文件时，没有stdlib.h头文件；在程序中，有部分；和}遗漏。（2）控制程序功能，只能使用一次，导致整个程序无实际作用；对图的存储结构不太熟悉;没有初始化路径，致使出现了乱码；使用单个字符输入一个字符串，导致字符串输入异常；5.运行结果5.1输入界面输入界面如图5.1所示图5.1输入界面125.2显示界面显示界面如图5.2所示图5.2显示界面5.3查询界面查询一个城市到其余各城市最短路径界面如图5.3所示图5.3查询一个城市到其余各城市最短路径界面13查询两城市之间最短路径界面如图5.4所示图5.4查询两城市之间最短路径界面5.4退出界面退出界面如图5.5所示图5.5退出界面146.心得体会这次的任务分配，从难度上来说，我这个交通资讯系统并不复杂，在书本上基本上能找到一摸一样的程序，但关键是理解。平时不听课，现在要把这些整体连接起来就跟困难，虽然书上的程序能看懂，但实践设计不比理解，要是练得少，往往捉襟见肘，要学会融会贯通，就是难上加难，所以我这次就不断演练，不断打击信心，结果程序不是自己的，有时候觉得计算机语言真的好难学，我想还是练少了，酱油打多了。尽管这学期课听了很多，但效果还是不好。总的来说，这次编程还是学到了一些东西，尽管微乎其微，算法逼近是死的，但人的大脑是活的，只有不断地实践，才能找到信心，也才能学到东西，尽管这次编程是借鉴网络上的，但还是可以学到很多东西，怎样的思考方法，怎样连接是逻辑语句更加完善。所以在编程中和调试过程中要认真分析和善