交通咨询系统.doc

大学算法与数据结构课程设计报告 题 目： 交通咨询系统 设 计 者： 25045012专业班级： 本网络 学 号： 指导教师： 所属系部： 计算机科学与技术系2012年06月03日 目 录1 问题描述及要求12 需求分析13 算法思想描述14 概要设计45 详细设计56 测试数据及分析97课程设计总结118 参考资料11这是我老师给我的题目我所真实上交的作品，在VC+6.0上完美运行，文档上也有截图。对于上传分享了这作品，我想说明两点：一是我这个程序，不是绝对原创，但是所参考的那个程序是不完美的首先界面并不友好，我已经重新设计了文字提示界面；原程序有个bug，就是在目的地和出发地重合的时候显示距离是无穷大，正确明显为0，我在老师的帮助下进行了修改算法解决了这个问题，在此我感谢我的指导老师龙老师认真负责对我进行指导，也很感谢原程序的作者为我提供程序主体和基本思路。这个word文档的其他部分90%是自己完成的（不否认有部分是参考了别人的）。二是若有人想借鉴本作品，希望改得体无完肤，因为程序的算法和提示语我的个人风格很浓，容易辨认，如果你的老师不巧只需浏览了一次，真的可以一眼辨认你是网上抄的。写给 想借鉴本文档的 网友交通咨询系统1 问题描述及要求 设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。设计要求： 1.建立交通网络网的存储结构。 2.总体设计要画流程图。 3.提供程序测试方案。 4.界面友好。2 需求分析 根据要求，需要在系统中建立无向图。系统应该有高度灵活性，可以由用户根据当前交通网络图输入初始数据，并且可以更改。系统根据用户的输入建立无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功能供用户选择。3 算法思想描述 首先总体的思想步骤是：交通咨询管理系统建立无向图进行功能选择设置城市之间道路距离输入城市和道路数量情况建立交通网咨询一个城市到任意城市距离咨询任意两个城市间最短距离狄克斯特拉算法的具体流程图如下：开 始初始化距离和路径i=1j=1;j+;jn弗洛伊德算法的具体流程图如下：开 始初始化距离和路径设为从到的只以集合中的节点为中间节点的最短路径的长度输出结果最短路径经过点k最短路径不经过点k4 概要设计系统应该分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。1、 建立图的存储结构：无向图首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。Ai，j= 一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息2、 单源最短路径：狄克斯特拉算法初始化S和D，置空最短路径终点集，置初始的最短路径值； Sv1=TRUE；Dv1=0；/S集初始时只有源点，源点到源点的距离为0； while（S集中顶点数n） 开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离； 3、 任意一对顶点间最短路径：弗洛伊德算法假设为从到的只以集合中的节点为中间节点的最短路径的长度。1. 若最短路径经过点k，则；2. 若最短路径不经过点k，则。因此，最短路径。5 详细设计程序源代码如下：/交通咨询系统#include#include#define Num 300 /定义常量Num#define Maxint 32767enum booleanFALSE,TRUE; /定义布尔类型typedef char VertexType;typedef int Adjmatrix;typedef struct VertexType vexsNum; Adjmatrix arcsNumNum;MGraph;int D1Num,P1Num;int DNumNum,PNumNum;void CreateMGraph(MGraph *G,int n,int e); /构建城市的无向图的声明void Dijkstra(MGraph *G,int v1,int n); /狄克斯特拉算法的声明void Floyd(MGraph *G,int n); /弗洛伊德算法的声明void main() MGraph *G; /定义无向图G int n,e,v,w,k; int m=1; G=(MGraph *)malloc(sizeof(MGraph); printf(欢迎使用【交通咨询系统】！本系统约定：n1.记一个城市为一个点，点用从1开始按顺序的编号表示，两个城市的连线为一条边；n2.程序要求输入的文本都是按回车进行确认；n3.程序输入输出均不带单位，单位默认为“公里”。nn); printf(系统需要知道地图的结构，请输入顶点个数和边数，用“,”号隔开：n); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); /调用CreateMGraph有向图函数 while(m!=0) printf(=n); printf(请输入数字：n); printf(0 : 退出n); printf(1 : 求一个城市到其他所有城市的最短路径n); printf(2 : 求任意的两个城市之间的最短路径n); scanf(%d,&m); if(m=2) Floyd(G,n); printf(请输入起点和终点，用“,”号隔开：n); scanf(%d,%d,&v,&w); k=Pvw; if(k=0) printf(n输出的结果：n顶点%d到%d无路径!n,v,w); else printf(n输出的结果：n从顶点%d到%d的最短路径是: %d,v,w,v); while(k!=w) printf(%d,k); k=Pkw; printf(%d,w); printf(n 路径长度: %dn,Dvw); else if(m=1) printf(请输入起点编号：n); scanf(%d,&v); Dijkstra(G,v,n); printf(程序已结束！谢谢您的使用！n);void CreateMGraph(MGraph *G,int n,int e) /构建城市的无向图 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; /距离初始化 if(i=j) G-arcsij=0; printf(n请输入%d条边的两端点序号和长度，用“,”号隔开n例如：1号城市到2号城市的长度为3，则输入1,2,3）: n,e); for(k=1;karcsij=w; /建立城市之间的距离 G-arcsji=w; printf(n地图的结构建立成功！n);void Dijkstra(MGraph *G,int v1,int n) /狄克斯特拉算法求一个城市到任意一个城市的距离 int D2Num,P2Num; int v,i,w,min; enum boolean SNum; for (v=1;varcsv1v; /距离初始化 if(D2vMaxint) / 路径初始化 P2v=v1; else P2v=0; P2v1=0;Sv1=TRUE; /源点V1放入s中 for(i=2;in;i+) /循环直至所有顶点的最都求出 min=Maxint; /Maxint置最小长度初值 for(w=1;w=n;w+) /选不在S中且有最小顶点w if(!Sw&D2wmin) v=w;min=D2w; Sv=TRUE; for(w=1;warcsvwarcsvw; P2w=v; printf(n输出的结果：n); printf(路径长度 路径n); /输出最短路径 for(i=1;i=n;i+) printf(%5d,D2i); printf(%10d,i); v=P2i; while(v!=0) printf(%d,v); v=P2v; printf(n); void Floyd(MGraph *G,int n) /用弗洛伊德算法求任意两顶点最短距离int i,j,k; /定义三个变量for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) /距离初始化Pij=j; /路径初始化elsePij=0;Dij=G-arcsij;for(k=1;k=n;k+) /以k为源点循环求出所有顶点的最短路径for(i=1;i=n;i+) /i为已知最短路径的顶点for(j=1;j=n;j+) /j为未知最短路径的顶点 if(Dik+DkjDij)Dij=Dik+Dkj;Pij=Pik;6 测试数据及分析 假如某交通网络上有4个城市（序号为1,2,3,4），4个城市之中有5条道路（不同长度），交通网络图如下图所示：打开本系统，界面如图：输入4,5之后按下键盘上的回车键：根据交通网络图输入线路数据后按回车：选择1回车后，再输入城市2，求得出的结果如下：选择2后，要计算1到3的最短距离和路径，输入1,3，得到结果，并与输入3,1的输出结果作对比如下：7课程设计总结 在我对作品完成了最后的调试和运行之后，紧张的一个星期的课程设计终于暂时告一段落。这个课程设计的课题虽然总体来说难度不大，因为在书上可以找到很多例子供参考。但是由于平时经常不认真听课，虽然看得明例题，但是要用到自己的作品中还是造有一定的压力。对此我因为过去的学习态度而懊悔。但是课程设计是个锻炼自己的极好机会，缺失的知识现在得补上！并且设计的过程是发现自身知识空点的最好的机会，以往不会遇到的情况，在实践练习中一一浮出水面，面对着它