全国交通咨询模拟系统C++实现（课程设计报告）

1、全国交通咨询模拟 一、设计目的掌握线性表、栈、图结构和对文件的操作，学习屏幕编辑和菜单技术，掌握用最短路径及其搜索算法编制较综合性的程序，能用图的邻接存储结构求解最优路线问题，解决有关实际问题。得到软件设计技能的训练。二、问题描述交通咨询模拟。根据旅客的不同需要，要考虑到旅客希望在旅途中的时间尽可能短、希望旅费尽可能省等的要求。旅途用火车或飞机作为交通工具。用计算机编制程序，为旅客提供两种最优决策的交通咨询系统。三、根本要求1、对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；2、对城市间的两种交通工具：飞机和火车。对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加

2、、修改、删除；3、提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；4、旅途中的消耗的总时间应包括中转站的等候时间。其中飞机至少二小时，火车至少一小时；5、咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原那么和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟班机或列车何时到达何地。四、实现提示1、算法思路(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，

3、交通信息存于文件的后面，用fread和fwrite函数操作。(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所消耗的时间要包括中转站的等候时间或旅费。(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届

4、时在网上提供)。这些工作有不小的工作量。(5) 最优决策功能模块(fast or province)。 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最

5、省的费用)变小的城市，其相应的初始值可为，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队)中只有出发地城市，随着对栈(队)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，假设该值是局部最优值且该城市不在栈(队)中，那么进栈(队)，直至栈(队)为空。 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。(6) 主程序可

6、以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。2、数据结构本程序运用了关于图这种数据结构。他的抽象数据类型定义如下：typedef struct unDiGraph int numVerts; /结点 costAdj cost; /邻接矩阵unDiGraph,*UNG;根本操作：unDiGraph* CreateCostG()操作结果：构造带权(费用)图。unDiGraph* CreateTimeG()操作结果：构造带权时间图。构造飞机带权(费用)图。PathMat *Floyed(unDiGraph *D)操作结果：Floyed函数 求任意两点的

7、最短路径。3、算法思想 本程序运用了图的知识，构造了无向带权费用图和无向带权时间图。如图1，图2所示 图1. 十三城市之间火车费用表权值表示费用 图2. 十三城市之间火车行驶时间表 权值表示时间并利用Floyed函数求带权图两点之间的最短路径。通过对带权费用图和带权时间图求最短路径，就可以最短道从一城市到另一城市之间最省时间和最省费用的走法。 为了简洁直观，本设计对课本内的交通网进行了简化，原来的25个城市缩减为13个。但是根本实现了设计的目的。满足了根本要求。4、程序模块1 程序是用dos 版做的界面。23 程序的模块为#include <windows.h>#include &

8、lt;stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h> #include <malloc.h>/引用的文本件#define INF 65535 /定义一个最大数定为无穷值#define MAX 13typedef int costAdjMAX+1MAX+1;/图邻接矩阵从1开始记数int PathMAX+1MAX+1;/图邻接矩阵从1开始记数int o13,h;typedef struct unDiGraphint numVerts; /结点costAdj

9、cost; /邻接矩阵unDiGraph,*UNG; /图的定义costAdj B,L;void pr(int i)/选择城市void pri()/输出城市unDiGraph *CreateCostG()/构造带权(费用)图 返回首地址G：unDiGraph *CreateTimeG()/构造带权(时间)图 返回首地址G：unDiGraph *CreateFlyG()/飞机的相关信息void Floyed(unDiGraph *D,unDiGraph *M) /Floyed函数 求任意两点的最短路径：void prn_pass(int i,int j) /为了求从i到j的最短路径，只需要调用如

10、下的过程void time()/求最少时间路径。void money()/求最少花费路径void administrator()/管理员功能void main()/main函数5、 主程序#include <windows.h>#include <stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h> #include <malloc.h>#define INF 65535 /定义一个最大数定为无穷值#define MAX 23static in

11、t c_number=13;static int k=0;staticint v=0,z=0,r=0,t=0;typedef struct zhuint c_cost;int c_time;int f_cost;int f_time;zhu;zhu m20,x20,n20;typedef int costAdjMAX+1MAX+1;/图邻接矩阵从1开始记数int PathMAX+1MAX+1;/图邻接矩阵从1开始记数typedef struct unDiGraphint numVerts; /结点costAdj cost; /邻接矩阵unDiGraph,*UNG; /图的定义typedef s

12、truct 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)cin>>addi.a;switch(h)/运用switch语句。 case(0):cout<<""break;case(1) : cout<<"成都 " break; case(2) : cout<<"西安 "break; case(3) : cout<<&quo

13、t;郑州 "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<

14、;<"徐州 "break;case(11) : cout<<"北京 "break; case(12) : cout<<"天津 "break; case(13) : cout<<"上海 "break;default: cout<<addi-13.a;return 1;/输出城市列表及相应代码void pri()int i;cout<<" 城市及其代码"<<endl<<endl<<endl; cou

15、t<<" *"<<endl; for (i=1;i<=c_number;i+)cout<<i<<"."pr(i,0);cout<<endl<<" *"<<endl<<endl<<endl<<endl<<endl<<endl;/构造带权(费用)图 返回首地址G：unDiGraph *CreateCostG(int o)/火车的花费的存贮和编辑功能unDiGraph *G;int i,j;i

16、nt a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF; /初始化使G->costij为无穷。G->numVerts=c_number;G->cost16=G->cost61=96;G->cost12=G->cost21=84;G->cost23=G->cost32=51;G->cost3

17、4=G->cost43=53;G->cost45=G->cost54=40;G->cost56=G->cost65=90;G->cost58=G->cost85=67;G->cost57=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->cost3

18、10=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<<"请输入开始城市的代码"<<endl;cin>>a;cout<<"请输入结尾城市的代码"<<endl;cin>>b;cout<<"请输入你的

19、两地花费"<<endl;cin>>mv.c_cost;nv.c_cost=a;xv.c_cost=b;cout<<"请选择"<<endl;cout<<"*"<<endl;cout<<"1：继续更改城市费用"<<endl;cout<<"0:返回上一级菜单"<<endl;cout<<"*"<<endl;cin>>h;switch(h)

20、case 1: h=1;break;case 0: h=0;break;default:cout<<"选择出错"<<endl;f=v+1;while (v-) G->costnv.c_costxv.c_cost=mv.c_cost;v=f;return(G);/构造带权(时间)图 返回首地址G：unDiGraph *CreateTimeG(int o)/火车的时间的存贮和编辑功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)

21、/为G分配存储空间。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=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->co

22、st65=9;G->cost57=G->cost75=6;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->cost5

23、13=11;if (o) while(h=1)z=z+1;pri();cout<<"火车时间编辑"<<endl;cout<<"请输入开始城市的代码"<<endl;cin>>a;cout<<"请输入结尾城市的代码"<<endl;cin>>b;cout<<"请输入你的两地时间"<<endl;cin>>mz.c_time;nz.c_time=a;xz.c_time=b;cout<<

24、;"请选择"<<endl;cout<<"*"<<endl;cout<<"1：继续更改城市时间"<<endl;cout<<"0:返回上一级菜单"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"选择出错"<<

25、;endl;f=z+1;while (z-) G->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=(unDiGraph *)malloc(sizeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF;/初始

26、化使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=6;G->cost67=G->cost76=6;G->

27、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<<"请输

28、入开始城市的代码"<<endl;cin>>a;cout<<"请输入结尾城市的代码"<<endl;cin>>b;cout<<"请输入你的两地时间"<<endl;cin>>mt.f_time;nt.f_time=a;xt.f_time=b;cout<<"请选择"<<endl;cout<<"*"<<endl;cout<<"1：继续更改城市时间&qu

29、ot;<<endl;cout<<"0:返回上一级菜单"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"选择出错"<<endl;f=t+1;while (t-) G->costnt.f_timext.f_time=mt.f_time;t=f;return(G);unDiGraph *CreateCostF

30、(int o)/飞机花费的存贮和编辑功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /为G分配存储空间。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF; /初始化使G->costij为无穷。G->numVerts=c_number;G->cost16=G->cost61=960;G->cost12=G->cost21=

31、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->cost67=G->cost76=600;G->cost79=G->cost97=200;G->cost311=G->cost113=690;G->cost1112=G->cos

32、t1211=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<<"请输入开始城市的代码"<<endl;cin>>a;cout<<"请输入结尾城市

33、的代码"<<endl;cin>>b;cout<<"请输入你的两地花费"<<endl;cin>>mr.f_cost;nr.f_cost=a;xr.f_cost=b;cout<<"请选择"<<endl;cout<<"*"<<endl;cout<<"1：继续更改城市费用"<<endl;cout<<"0:返回上一级菜单"<<endl;cou

34、t<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"选择出错"<<endl;f=r+1;while (r-) G->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=

35、c_number; for(i=1;i<=n;i+) for(j=1;j<=n;j+)Aij=D->costij;/初始化矩阵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+Akj<Aij)Aij=Aik+Akj;Cij=Cik+Ckj; Pathij=k;/假设i经过k到j比i到j小，那么令Aij=Aik+Akj。 Bij=Aij;Lij=Cij; else

36、Bij=Aij;Lij=Cij;/end-for cout<<"n最短路径为: "<<endl;/end-Floyed/为了求从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<<"请输入起

37、始城市和目的城市的代码，中间以空格隔开，范围(1- "<<c_number<<")" cin>>Bcity; cin>>Ecity;/输入起始城市和终点城市的代码。 if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) cout<<"n出错啦! 输入城市号码请在1-"<<c_number&

38、lt;<"之间，且两城市不能相等!"<<endl; Floyed(CreateTimeG(0),CreateCostG(0);/调用Floyed函数。pr(Bcity,0);/ 显示起始城市。 prn_pass(Bcity,Ecity);/调用prn_pass函数，显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>5000|LBcityEcity>10000) cout<<"两地间还没有线路通过"<<endl;elsecout<<"火

39、车花的钱是"<<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

40、Bcity,Ecity;/起始成市号码和终点城市号码 int l,h=1;do pri();/输出城市列表及相应代码。 cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- "<<c_number<<")" cin>>Bcity; cin>>Ecity;/输入起始城市和终点城市的代码。 if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1

41、)&&Bcity!=Ecity) cout<<"n出错啦! "<<endl; Floyed(CreateTimeF(0),CreateCostF(0);/调用Floyed函数。pr(Bcity,0);/ 显示起始城市。 prn_pass(Bcity,Ecity);/调用prn_pass函数，显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>5000|LBcityEcity>10000) cout<<"两地间还没有线路通过"<<endl

42、;elsecout<<"飞机花的钱是"<<LBcityEcity<<"元"<<endl;cout<<"飞机花的时间是"<<BBcityEcity<<"小时"<<endl; printf("nn 1.继续最少花费查找n 2.返回主菜单n 清选择."); scanf("%d",&l); /输入1或2选择是否继续。 h=l; while(h=1); printf("n&

43、quot;);/求最少花费路径。void money() int Bcity,Ecity;/起始成市号码和终点城市号码 char l,h=1;/*unDiGraph *G;*/do pri();/输出城市列表及相应代码。cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- "<<c_number<<")" cin>>Bcity;cin>>Ecity;/输入起始城市和终点城市的代码。if (!(0<Bcity&&Bcity<c_number+1)&a

44、mp;&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) cout<<"n出错啦! "<<endl; /输入出错 Floyed(CreateCostG(0),CreateTimeG(0);/调用Floyed函数。pr(Bcity,0);/显示起始城市。prn_pass(Bcity,Ecity);/调用prn_pass函数，显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>5000|LBcityEcity>1

45、0000) cout<<"两地间还没有线路通过"<<endl;elsecout<<"火车花的钱是"<<BBcityEcity<<"元"<<endl;cout<<"火车花的时间"<<LBcityEcity<<"小时"<<endl; printf("nn 1.继续最少花费查找n 2.返回主菜单n 清选择."); scanf("%d",&

46、;l); /输入1或2选择是否继续。 h=l; while(h=1); printf("n"); /求飞机的情况void f_money() cout<<"1"<<endl;int Bcity,Ecity;/起始成市号码和终点城市号码 char l,h=1;/*unDiGraph *G;*/do cout<<"2"<<endl; pri();/输出城市列表及相应代码。cout<<"请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- "<<

47、;c_number<<")" cin>>Bcity;cin>>Ecity;/输入起始城市和终点城市的代码。if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) cout<<"n出错啦! "<<endl; /输入出错 Floyed(CreateCostF(0),CreateTimeF(0);/调用Floyed函数

48、。pr(Bcity,0);/显示起始城市。prn_pass(Bcity,Ecity);/调用prn_pass函数，显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>5000|LBcityEcity>10000) cout<<"两地间还没有线路通过"<<endl;elsecout<<"飞机花的钱是"<<BBcityEcity<<"元"<<endl;cout<<"飞机花的时间"&

49、lt;<LBcityEcity<<"小时"<<endl; printf("nn 1.继续最少花费查找n 2.返回主菜单n 清选择."); scanf("%d",&l); /输入1或2选择是否继续。 h=l; while(h=1); printf("n"); void add_city()/对城市的增加static int i=1;int j;cout<<"请输入你要增加的城市的个数"<<endl;cin>>j;for (i

50、=1;i<=j;i+)cout<<"请输入你要增加的城市名"<<endl;pr(i,1);c_number=c_number+1;cout<<"城市增加完毕"<<endl;void chose_money()/花最少钱的算法int h;cout<<"1:火车"<<endl;cout<<"2:飞机"<<endl;cout<<"请选择："<<endl;cin>>h

51、;if (h=1) money();elsef_money();void chose_time()/花最少时间的算法int h;cout<<"1:火车"<<endl;cout<<"2:飞机"<<endl;cout<<"请选择："<<endl;cin>>h;if (h=1) time();elsef_time();void edit_line()/增加编辑火车的费用CreateCostG(1);void edit_hour()/增加编辑火车的时间Crea

52、teTimeG(1);void edit_fline()/增加编辑飞机的费用CreateCostF(1);void edit_fhour()/增加编辑飞机的时间CreateTimeF(1);void administrator()/管理员功能int h=1;while (h) cout<<"*"<<endl;cout<<"1:增加城市"<<endl;cout<<"2:添加或编辑火车费用"<<endl;cout<<"3:添加或编辑火车时间"<<endl;cout<<"4:添加或编辑飞机费用"<<endl;cout<<"5:添加或编辑飞机时间"<<endl;cout<<"0:返回主菜单"<<endl;cout<<"*"<<endl;cout<<"请选择"<<endl;cin>>h;sw