《全国交通资讯模拟数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《全国交通资讯模拟数据结构课程设计报告.docx（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国交通咨询模拟系统的设计与实现1. 问题描述出于不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。2. 需求分析(1) 提供对城市信息进行编辑 ( 如 : 添加或删除 ) 的功能。(2) 城市之间有两种交通工具：火车和飞机。(3) 提供两种最优决策 : 最快到达或最省钱到达。全程只考虑一种交通工具。(4) 旅途中耗费的总时间应该包括中转站的等候时间。(5) 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优
2、决策原则和交通工具 , 输出信息 : 最快需要多长时间才能到达或者最少需要多少旅费才能到达 , 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。3. 概要设计因为全国交通咨询模拟中有众多城市之间的连接关系，为实现全国交通咨询系统的开发，采用图类型与邻接表类型来存储城市之间的信息。下面给出他们的ADT的定义。3.1 抽象数据类型定义如下：typedef struct unDiGraph int numVerts; /结点 costAdj cost; /邻接矩阵unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作结果：构造带权(费用)图。unDiGra
3、ph* CreateTimeG()操作结果：构造带权（时间）图。构造飞机带权(费用)图。PathMat *Floyed(unDiGraph *D)操作结果：Floyed函数 求任意两点的最短路径。3.2 系统功能模块设计全国交通咨询模拟系统由4个功能模块组成：添加城市、删除程序、采用火车出行、采用飞机出行下面给出功能模块图，如图3-1所示。图3-1全国交通咨询模拟功能模块图3.3主要函数调用关系图（给出ADT内基本操作的那些函数之间的函数调用关系图）如图3-2所示。图3-2 系统函数调用关系图3.4主界面设计为了实现全国交通咨询模拟系统，需要设计一个含有多菜单项的主控菜单子程序，以链接系统中各
4、个子项目的调用，为了方便用户使用本系统，本系统主控菜单的运行界面如图3-3所示。4. 详细设计实现全国交通咨询模拟系统的开发，采用图结构类型存储城市的信息。其中，各城市间的邻接关系用图的邻接矩阵类型存储；城市信息用结构体数组存储，其中每个数组元素是一个结构体变量，包含时间和费用三个分量；图的顶点的个数和边的个数由变量费用、时间大小表示，它们是整型数据。4.1 数据类型定义数据存储：有向图、邻接表函数调用：#include #include #include #include #include #include /引用的文本件#define INF 65535 /定义一个最大数定为无穷值#def
5、ine MAX 13typedef int costAdjMAX+1MAX+1;/图邻接矩阵从1开始记数int PathMAX+1MAX+1;/图邻接矩阵从1开始记数int o13,h;typedef struct unDiGraphint numVerts; /结点costAdj cost; /邻接矩阵unDiGraph,*UNG; /图的定义costAdj B,L;void pr(int i)/选择城市void pri()/输出城市unDiGraph *CreateCostG()/构造带权(费用)图 返回首地址G：unDiGraph *CreateTimeG()/构造带权(时间)图 返回首
6、地址G：unDiGraph *CreateFlyG()/飞机的相关信息void Floyed(unDiGraph *D,unDiGraph *M) /Floyed函数 求任意两点的最短路径：void prn_pass(int i,int j) /为了求从i到j的最短路径，只需要调用如下的过程void time()/求最少时间路径。void money()/求最少花费路径void administrator()/管理员功能void main()/main函数4.2 系统子程序详细设计4.2.1 求最小路径Void ShortPath_DIJ(AMGraph G, int v0,PathMatri
7、x &P, ShortpathTable &D)For(v = 0;v G.vexnum;+v) Finalv = FALSE;Dv = G.arcev0v;For( w = 0; w G.vexnum; +w ) Pvw = FALSE; If ( Dv INFINITY ) /如果有直接互通的两个顶点，直接将这个路径赋值到数组PV. Pvv0 = TRUE; Pvv = TRUE; Dv0 = 0; finalv = TRUE; /*下面开始主循环，每次求得v0到某个v顶点的最短路径，同时刷新之前的最短路径。*/ /对于除了v0之外的顶点（这个循环仅仅限制次数，i的值不用。Min = IN
8、FINITY; /假定初始的”最小值”为无穷大。For ( w = 0; w G.vexnum; +w ) If ( !finalw) /w定点在V-S中，及还未确定的顶点。 If ( Dw min) v = w; min = Dw; /随着循环进行，依与v0的距离大小，从小到达取的顶点v，并标记进final。 Finalv = TRUE; / 标记已经找到 For ( w = 0; w G.vexnum; w+ ) /更新路径 If ( !finalw & ( min + G.arcsvw) Dw = min + G.arcsvw; Pw = Pw; /把一行都给赋值 Pww = TRUE;
9、4.2.2 利用邻接表输出结果 /邻接表中表对应的链表的特点。 Typedef struct ENode Int ivex ; / 该边所指向的顶点的位置。Struct ENode*next_edge; /指向下一条弧的指针。ENode,*PENode; / 邻接表中表的顶点Typedef struct VNode Char data; /顶点信息 ENode *first_edge; /指向第一条依附该顶点的弧VNode;/ 邻接表Typedef struct LGraph Int vexnum; /图的顶点数目 Int edgnum; / 图的边的数目VNode vexsmax;LGrap
10、h5. 编码实现详见：源程序清单。6. 系统测试本程序在DOS操作系统下运行 （1 查看城市（2 选择最短时间路线的两种方式（3 选择以火车的方式出行（4 坐火车从石家庄到上海的最短时间路线与所花费的金额（5 从成都到天津的最少花费与时间（6 管理员成语（7 增添新城市 沧州（8 增添石家庄到沧州的火车费用（9 增添石家庄到沧州的火车时间（10 坐火车从石家庄到沧州的最短时间（11 采用飞机从北京到石家庄7. 结果分析1.构造带权图CreateFlyG CreateCostG和CreateTimeG：T(MAX)=O(MAX)2)2. Floyed函数 Floyed : T(n)=O(n2+n
11、3)3.显示路径函数 prn_pass : T(n)=O(n)4.本程序的空间复杂度均为S(n)=(n2); 即存放n2个节点数据辅助空间。8. 学习体会通过此次课程设计大大加深了我对数据结构这门课程的理解，而且尤其对图这章的理解，可以说有一个大的进步。学习能力也大大提高。当然通过此次课设也为我以后的道路奠定了一定的基础，认识到了基础的重要。实现全国交通咨询模拟系统的开发，采用图结构类型存储城市的信息。其中，各城市间的邻接关系用图的邻接矩阵类型存储；城市信息用结构体数组存储，其中每个数组元素是一个结构体变量，包含时间和费用三个分量；图的顶点的个数和边的个数由变量费用、时间大小表示，它们是整型数
12、据。让我对计算机有了更深的认识，对他产生了更加浓厚的兴趣。9. 源程序清单#include #include #include #include #include #include #define INF 65535 /定义一个最大数定为无穷值#define MAX 23static int c_number=13;static int k=0;staticint v=0,z=0,r=0,t=0;typedef struct jlint c_cost;int c_time;int f_cost;int f_time;jl;jl m20,x20,n20;typedef int costAdjMA
13、X+1MAX+1;/图邻接矩阵从1开始记数int PathMAX+1MAX+1;/图邻接矩阵从1开始记数typedef struct unDiGraphint numVerts; /结点costAdj cost; /邻接矩阵unDiGraph,*UNG; /图的定义typedef struct c_editchar a10;c_edit;c_edit add10;costAdj B,L;int pr(int i,int j) int h=0;if (j=0) h=i;else if (j=1)cinaddi.a;switch(h)/运用switch语句。 case(0):cout;break;
14、case(1) : cout成都 ; break; case(2) : cout兰州 ;break; case(3) : cout石家庄 ;break; case(4) : cout郑州 ;break; case(5) : cout武汉 ;break; case(6) : cout贵阳 ;break; case(7) : cout长沙 ;break; case(8) : cout广州 ;break; case(9) : cout南宁 ;break; case(10) : cout济南 ;break;case(11) : cout北京 ;break; case(12) : cout天津 ;bre
15、ak; case(13) : cout上海 ;break;default: coutaddi-13.a;return 1;/输出城市列表及相应代码void pri()int i;cout 城市及其代码endlendlendl; cout *endl; for (i=1;i=c_number;i+)couti.;pr(i,0);coutendl *endlendlendlendlendlendl;/构造带权(费用)图 返回首地址G：unDiGraph *CreateCostG(int o)/火车的花费的存贮和编辑功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;i
16、f(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;ic_number+1;i+)for(j=1;jcostij=INF; /初始化使G-costij为无穷。G-numVerts=c_number;G-cost16=G-cost61=96;G-cost12=G-cost21=84;G-cost23=G-cost32=51;G-cost34=G-cost43=53;G-cost45=G-cost54=40;G-cost56=G-cost65=90;G-cost58=G-cost85=67;G-cos
17、t57=G-cost75=67;G-cost67=G-cost76=60;G-cost79=G-cost97=25;G-cost311=G-cost113=69;G-cost1112=G-cost1211=13;G-cost1210=G-cost1012=67;G-cost310=G-cost103=34;G-cost1310=G-cost1013=65;G-cost135=G-cost513=118;if (o) while(h=1)v=v+1;pri();cout火车花费查询endl;cout请输入开始城市的数字代码a;cout请输入结尾城市的数字代码b;cout请输入你预算的两地花费金额
18、mv.c_cost;nv.c_cost=a;xv.c_cost=b;cout请选择endl;cout*-*endl;cout1：继续更改城市费用endl;cout0:返回上一级菜单endl;cout*-*h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout选择出错costnv.c_costxv.c_cost=mv.c_cost;v=f;return(G);/构造带权(时间)图 返回首地址G：unDiGraph *CreateTimeG(int o)/火车的时间的存贮和编辑功能unDiGraph *G;int i,j;int a
19、=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;ic_number+1;i+)for(j=1;jcostij=INF;/初始化使G-costij为无穷。G-numVerts=c_number;G-cost16=G-cost61=9;G-cost12=G-cost21=8;G-cost23=G-cost32=5;G-cost34=G-cost43=5;G-cost45=G-cost54=4;G-cost56=G-cost65=9;G-cost57=G-cost75=6
20、;G-cost58=G-cost85=6;G-cost67=G-cost76=6;G-cost79=G-cost97=2;G-cost311=G-cost113=6;G-cost1112=G-cost1211=1;G-cost1210=G-cost1012=6;G-cost310=G-cost103=3;G-cost1310=G-cost1013=6;G-cost135=G-cost513=11;if (o) while(h=1)z=z+1;pri();cout火车时间预算编辑endl;cout请输入开始城市的数字代码a;cout请输入结尾城市的数字代码b;cout请输入你的两地时间mz.c_
21、time;nz.c_time=a;xz.c_time=b;cout请选择endl;cout*-*endl;cout1：继续更改城市时间endl;cout0:返回上一级菜单endl;cout*-*h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout选择出现BUG！costnz.c_timexz.c_time=mz.c_time;z=f;return(G);unDiGraph *CreateTimeF(int o)/飞机的时间的存贮和编辑功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G
22、=(unDiGraph *)malloc(sizeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;ic_number+1;i+)for(j=1;jcostij=INF;/初始化使G-costij为无穷。G-numVerts=c_number;G-cost16=G-cost61=3;G-cost12=G-cost21=2;G-cost23=G-cost32=1;G-cost34=G-cost43=2;G-cost45=G-cost54=4;G-cost56=G-cost65=3;G-cost57=G-cost75=6;G-cost58=G-cost85=
23、6;G-cost67=G-cost76=6;G-cost79=G-cost97=2;G-cost311=G-cost113=6;G-cost1112=G-cost1211=1;G-cost1210=G-cost1012=2;G-cost310=G-cost103=3;G-cost1310=G-cost1013=6;G-cost135=G-cost513=1;if (o) while(h=1)t=t+1;pri();cout飞机时间编辑endl;cout请输入开始城市的数字代码a;cout请输入结尾城市的数字代码b;cout请输入你的两地时间mt.f_time;nt.f_time=a;xt.f_
24、time=b;cout请选择endl;cout*-*endl;cout1：继续更改城市时间endl;cout0:返回上一级菜单endl;cout*-*h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout选择出现BUG！costnt.f_timext.f_time=mt.f_time;t=f;return(G);unDiGraph *CreateCostF(int o)/飞机花费的存贮和编辑功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(si
25、zeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;ic_number+1;i+)for(j=1;jcostij=INF; /初始化使G-costij为无穷。G-numVerts=c_number;G-cost16=G-cost61=960;G-cost12=G-cost21=840;G-cost23=G-cost32=501;G-cost34=G-cost43=530;G-cost45=G-cost54=400;G-cost56=G-cost65=900;G-cost58=G-cost85=670;G-cost57=G-cost75=670;G-co
26、st67=G-cost76=600;G-cost79=G-cost97=200;G-cost311=G-cost113=690;G-cost1112=G-cost1211=310;G-cost1210=G-cost1012=670;G-cost310=G-cost103=340;G-cost1310=G-cost1013=650;G-cost135=G-cost513=1180;if (o) while(h=1)r=r+1;pri();cout飞机花费编辑endl;cout请输入开始城市的数字代码a;cout请输入结尾城市的数字代码b;cout请输入你的两地花费mr.f_cost;nr.f_c
27、ost=a;xr.f_cost=b;cout请选择endl;cout*-*endl;cout1：继续更改城市费用endl;cout0:返回上一级菜单endl;cout*-*h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout选择出现BUG!costnr.f_costxr.f_cost=mr.f_cost;r=f;return(G); /Floyed函数 求任意两点的最短路径：void Floyed(unDiGraph *D,unDiGraph *M) int i,j,k,n;costAdj A,C;n=c_number; fo
28、r(i=1;i=n;i+) for(j=1;jcostij;/初始化矩阵A。Cij=M-costij; Pathij=-1; /初始化矩阵p, 置-1. for(k=1;k=n;k+) /k为逐步加入的中间结点 for(i=1;i=n;i+) /i为A中行号for(j=1;j=n;j+)if(Aik+AkjAij)Aij=Aik+Akj;Cij=Cik+Ckj; Pathij=k;/若i经过k到j比i到j小，则令Aij=Aik+Akj。 Bij=Aij;Lij=Cij; elseBij=Aij;Lij=Cij;/end-for coutn最短路径为: endl;/end-Floyed/为了求从
29、i到j的最短路径，只需要调用如下的过程：void prn_pass(int i,int j) if(Pathij!=-1) prn_pass(i,Pathij);/输出最短路径经过的所有点 pr(Pathij,0);/求最少时间路径。void time()int Bcity,Ecity;/起始成市号码和终点城市号码 int l,h=1;do pri();/输出城市列表及相应代码。 cout请输入起始城市和目的城市的数字代码，中间并以空格隔开，*范围(1- c_numberBcity; cinEcity;/输入起始城市和终点城市的代码。 if (!(0Bcity&Bcityc_number+1)
30、&(0Ecity&Ecityc_number+1)&Bcity!=Ecity) coutn出错啦! 输入城市数字号码请在1-c_number之间，且两城市不能相等!5000|LBcityEcity10000) cout两地间还没有线路通过endl;elsecout火车花的金额是LBcityEcity元endl;cout火车花的时间是BBcityEcity小时endl; printf(nn 1.继续最少花费查找n 2.返回主菜单n 清选择.); scanf(%d,&l); /输入1或2选择是否继续。 h=l; while(h=1); printf(n);void f_time()int Bcit
31、y,Ecity;/起始成市号码和终点城市号码 int l,h=1;do pri();/输出城市列表及相应代码。 cout请输入起始城市和目的城市的代码，中间以空格隔开*，范围(1- c_numberBcity; cinEcity;/输入起始城市和终点城市的代码。 if (!(0Bcity&Bcityc_number+1)&(0Ecity&Ecityc_number+1)&Bcity!=Ecity) coutn出现BUG! 5000|LBcityEcity10000) cout两地间还没有线路通过endl;elsecout飞机花的金额是LBcityEcity元endl;cout飞机花的时间是BBcityEcity小时endl; printf(nn 1.继续最少花费查找n 2.返回主菜单n 清选择.); scanf(%d,&l); /输入1或2选择是否继续。