交通咨询系统设计数据结构课程设计任务书(共21页).doc

《交通咨询系统设计数据结构课程设计任务书(共21页).doc》由会员分享，可在线阅读，更多相关《交通咨询系统设计数据结构课程设计任务书(共21页).doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 交通资讯系统1. 系统需求分析 1.1问题描述 在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。 1.2功能要求1.交通资讯系统提供用户三种决策方案：一是建立交通网络图的存储结构。二是 某个城市到达其余各城市的最短路径。三是实现两个城市之间最短路径的问题。主 要目的

2、是给用户提供路径咨询。 2.本系统规定：(1)在程序中输入城市名称时，需输入0到5的城市代号(2)在选择功 能是，应输入与所选功能对应的一个整形数据。(3)程序的输出信息主要是：城市代号，某城市到达其余各城市的最短路径，两城市之间最短路径2.概要设计2.1系统总体设计 交通资讯系统 一个城市到其他城市 两个城市之间存储交通图获得最佳路径获得最佳路径查询最短距离查询最短距离 图2.1系统总体设计2.2各模块的功能void main() 主函数void Dijkstr() 采用狄克斯特拉算法求从顶点v到其余个顶点的最短路径void DisPath() 由path计算最短路径void Ppath()

3、 输出各条最短路径void Floyd() 采用弗洛伊德算法求所有顶点之间的最短路径void DisPath2() 由path计算最短路径void Ppath2() 输出各条最短路径2.3相关数据结构设计 1.数据结构 typedef int InfoType; typedef struct char cityname; int no; InfoType info; VertexType; typedef struct int edgesMAXVMAXV;int n,e;VertexType vxsMAXV; MGraph;2. 数据库结构：下表构成该系统的基本数据库城市代号邻接矩阵边数组城市

4、个数路径城市名称intintintintchar3.详细设计 3.1采用c语言定义相关的数据结构本系统定义了整形int,字符型char,还有结构体定义，建立图的存储结构首先定义交通图的存储结构，邻接矩阵是表示图形中顶点之间相邻关系的矩阵.设G=（V，E）是具有n(n0)个顶点的图，则邻接矩阵具有如下定义的n阶方阵Wij 若vivj 且E(G)Aij= 其他一个图的邻接矩阵表示是唯一的,除了许用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息 3.2函数调用关系图3.2.1主函数 main函数z=1查看系统中的城市代号z=0退出程序z=3;调用

5、Floyd函数求所有定点之间的最短路径z=2;调用Dijkstra函数求v到其余各顶点的最短路径调用DisPath2函数计算最短路径调用DisPath函数计算最短路径调用ppath函数输出各条最短路径调用ppath2函数输出各条最短路径 void main()int i,j,z,x;MGraph g;int AMAXV=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;f

6、or(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Aij; printf(* 交通咨询系统 *n); printf(* 1-查看系统中的城市代号 *n); printf(* 2-一个城市到所有城市的最短路径 *n); printf(* 3-任意的两个城市之间的最短路径 *n); printf(* 0-退出 *n); printf(n); printf(请选择：);scanf(%d,&z); while(z!=0) switch(z) case 1: printf(0北京,1天津,2上海,3广州,4南京,5厦门n); printf(n); main(); scan

7、f(%d,&z); break; case 2: printf(请输入城市代号:); scanf(%d,&x); switch(x) case 0: printf(以下是最短路径：n);Dijkstra(g,x);break; case 1: printf(以下是最短路径：n);Dijkstra(g,x);break; case 2: printf(以下是最短路径：n);Dijkstra(g,x);break; case 3: printf(以下是最短路径：n);Dijkstra(g,x);break; case 4: printf(以下是最短路径：n);Dijkstra(g,x);break

8、; case 5: printf(以下是最短路径：n);Dijkstra(g,x);break; default : printf(输入有误，请重新输入n); printf(n); main(); printf(n);main(); scanf(%d,&z);break; case 3: Floyd(g);printf(请选择：);printf(n);main(); scanf(%d,&z);break; case 0: exit(-1);break; default: printf(输入有误，请重新输入n); printf(n); main(); 3.2.2狄克斯特拉函数 初始化距离和路径，

9、将s置为空。将远点编号v放入s中,循环直到所有顶点的最短路径都求出，将mindis置最小长度初值，选取不在s中且具有最小距离的顶点u将顶点u加入s中，修改不在s中的顶点的距离，输出最短路径void Dijkstra(MGraph g,int v) int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1;sv=1;pathv=0;for(i=0;ig.n;i+) mindis=INF; for(j

10、=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1;for(j=0;jg.n;j+)if(sj=0)if(g.edgesujINF&distu+g.edgesujdistj)distj=distu+g.edgesuj;pathj=u; Dispath(dist,path,s,g.n,v);3.2.3 Ppath函数 前向递归查找路径上的顶点，找到起点则返回，找顶点k的前一个顶点，输出顶点k。void Ppath(int path,int i,int v)int k;k=pathi;if(k=v) return;Ppath(path,

11、k,v);printf(%d,k);3.2.4 Dispath函数 有path函数计算最短路径，搜索最短路径的所有边，输出路径上的起点，输出路径上的中间点，输出路径上的终点。void Dispath(int dist,int path,int s,int n,int v)int i;for(i=0;in;i+) if(si=1&disti!=INF) printf(从%d到%d的最短路径长度为：%dt路径为：,v,i,disti); printf(%d,v); Ppath(path,i,v); printf(%dn,i);else printf(从%d到%d不存在路径n,v,i);3.2.5弗

12、洛伊德函数 设置路径长度A和路径path初值。做k次迭代，每次均试图将顶点K扩充到点钱球得的从i到j的最短路径Pij上，修开路径长度，输出最短路径。void Floyd(MGraph g) int pathMAXVMAXV,AMAXVMAXV; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jAik+Akj) Aij=Aik+Akj; pathij=k; 3.2.6 Ppath2函数 向前递归查找路径上的顶点，找到了

13、起点则返回，找顶点i的前一个顶点k，找顶点k的前一个顶点j。在path中递归输出从顶点i到顶点j的最短路径void Ppath2(int pathMAXV,int i,int j) int k;k=pathij; if(k=-1)return;Ppath2(path,i,k);printf(%d,k);Ppath2(path,k,j);3.2.7 DisPath2函数 由path计算最短路径，若顶点i和顶点j之间没有边，则输出i到j没有路径，若有边则输出路劲上的起点、中间点和终点。void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; prin

14、tf(请输入起点和终点(i,j)：); scanf(%d,%d,&i,&j); if(Aij=INF) if(i!=j) printf(从%d到%d没有路径n,i,j);elseprintf(从%d到%d路径为：,i,j); printf(%d,i); Ppath2(path,i,j); printf(%d,j); printf(t路径长度为：%dn,Aij);4.系统调试4.1系统调试中的问题（1） 只考虑函数而忽视数据库和标点：在存储文件时，没有头文件；在程序中，有部分；和遗漏。（2） 控制程序功能，只能使用一次，导致整个程序无实际作用；对图的存储结构不太熟悉;没有初始化路径，致使出现了乱

15、码；使用单个字符输入一个字符串，导致字符串输入异常；5.运行结果5.1输入界面输入界面如图 5.1所示 图5.1 输入界面5.2显示界面显示界面如图5.2所示 图5.2 显示界面5.3查询界面查询一个城市到其余各城市最短路径界面如图5.3所示 图5.3查询一个城市到其余各城市最短路径界面查询两城市之间最短路径界面如图5.4所示 图5.4查询两城市之间最短路径界面5.4退出界面退出界面如图5.5所示 图5.5退出界面6.心得体会 这次的任务分配，从难度上来说，我这个交通资讯系统并不复杂，在书本上基本上能找到一摸一样的程序，但关键是理解。平时不听课，现在要把这些整体连接起来就跟困难，虽然书上的程序

16、能看懂，但实践设计不比理解，要是练得少，往往捉襟见肘，要学会融会贯通，就是难上加难，所以我这次就不断演练，不断打击信心，结果程序不是自己的，有时候觉得计算机语言真的好难学，我想还是练少了，酱油打多了。尽管这学期课听了很多，但效果还是不好。 总的来说，这次编程还是学到了一些东西，尽管微乎其微，算法逼近是死的，但人的大脑是活的，只有不断地实践，才能找到信心，也才能学到东西，尽管这次编程是借鉴网络上的，但还是可以学到很多东西，怎样的思考方法，怎样连接是逻辑语句更加完善。所以在编程中和调试过程中要认真分析和善于发现问题并及时解决的习惯，不懂得及时问老师或其他同学通过本次实验，掌握了最短路径的问题，并结

17、合图的存储结构，狄克斯特拉算法、弗洛伊德算法等解决交通资讯系统的设计问题，源程序打出来后有多处错误，大小写错误、符号错误、遗漏错误。7.附录7.1源代码#include#include#include string.h#define INF 32767#define MAXV 10typedef int InfoType;typedef structchar cityname; int no; InfoType info;VertexType;typedef structint edgesMAXVMAXV;int n,e;VertexType vxsMAXV;MGraph;void Ppath

18、(int path,int i,int v)int k;k=pathi;if(k=v) return;Ppath(path,k,v);printf(%d,k);void Dispath(int dist,int path,int s,int n,int v)int i;for(i=0;in;i+) if(si=1&disti!=INF) printf(从%d到%d的最短路径长度为：%dt路径为：,v,i,disti); printf(%d,v); Ppath(path,i,v); printf(%dn,i);else printf(从%d到%d不存在路径n,v,i);void Dijkstra

19、(MGraph g,int v) int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1;sv=1;pathv=0;for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1;for(j=0;jg.n;j+)if(sj=0)if(g.edgesujINF&distu+g.ed

20、gesujdistj)distj=distu+g.edgesuj;pathj=u; Dispath(dist,path,s,g.n,v);void Ppath2(int pathMAXV,int i,int j) int k;k=pathij; if(k=-1)return;Ppath2(path,i,k);printf(%d,k);Ppath2(path,k,j);void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; printf(请输入起点和终点(i,j)：); scanf(%d,%d,&i,&j); if(Aij=INF) if(i!=

21、j) printf(从%d到%d没有路径n,i,j);elseprintf(从%d到%d路径为：,i,j); printf(%d,i); Ppath2(path,i,j); printf(%d,j); printf(t路径长度为：%dn,Aij);void Floyd(MGraph g) int pathMAXVMAXV,AMAXVMAXV; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jAik+Akj) Aij=

22、Aik+Akj; pathij=k; Dispath2(A,path,g.n); void main()int i,j,z,x;MGraph g;int AMAXV=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.edgesij=Aij; printf(* 交通咨询系统 *n); printf(* 1-查

23、看系统中的城市代号 *n); printf(* 2-一个城市到所有城市的最短路径 *n); printf(* 3-任意的两个城市之间的最短路径 *n); printf(* 0-退出 *n); printf(n); printf(请选择：);scanf(%d,&z); while(z!=0) switch(z) case 1: printf(0北京,1天津,2上海,3广州,4南京,5厦门n); printf(n); main(); scanf(%d,&z); break; case 2: printf(请输入城市代号:); scanf(%d,&x); switch(x) case 0: prin

24、tf(以下是最短路径：n);Dijkstra(g,x);break; case 1: printf(以下是最短路径：n);Dijkstra(g,x);break; case 2: printf(以下是最短路径：n);Dijkstra(g,x);break; case 3: printf(以下是最短路径：n);Dijkstra(g,x);break; case 4: printf(以下是最短路径：n);Dijkstra(g,x);break; case 5: printf(以下是最短路径：n);Dijkstra(g,x);break; default : printf(输入有误，请重新输入n);

25、 printf(n); main(); printf(n);main(); scanf(%d,&z);break; case 3: Floyd(g);printf(请选择：);printf(n);main(); scanf(%d,&z);break; case 0: exit(-1);break; default: printf(输入有误，请重新输入n); printf(n); main(); 7.2参考文献数据库教程（第三版） 李春葆 尹为民 李蓉蓉 蒋晶珏 喻丹丹 编著 M清华大学出版社数据库教程上机实验指导（第三版） 李春葆 尹为民 李蓉蓉 蒋晶珏 喻丹丹 编著M清华大学出版社8. 评分表计算机与通信学院课程设计评分表课程名称： 数据结构 项 目评 价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩 教师签名： 日 期： 专心-专注-专业