数据结构全国交通模拟系统.doc

全国交通模拟系统课程设计报告姓名： 唐文龙 班级： 2班 学号： 411417080216 学院： 华信学院 专业： 计算机科学与技术 指导： 日期：2013.06.20 30目录1 需求分析11.1 概述11.2 数据需求11.3 功能性需求11.4 其他需求12 概要设计23 详细设计43.1 记录的定义43.2 子程序说明53.3 子程序的算法说明53.3.1主函数流程图64 系统实现74.1开发环境84.2运行界面94.3测试用例105 总 结116.参 考 文 献11附录：源程序.111 需求分析 出于不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。1.1 概述程序的功能包括： 提供对城市信息的编辑， 提供列车时刻表和飞机航 班表的编辑，提供两种最优决策：最快到达、最省钱到达。1.2 数据需求输入列 车或飞机编号时需输入一个整型数据； 输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据；在选择功能时，应输入与所选功能对应的一个整型数据。1.3 功能性需求总体功能描述(1) 提供对城市信息进行编辑的功能。(2) 城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑的功能。(3) 提供两种最优决策 : 最快到达或最省钱到达。全程只考虑一种交通工具，不考虑回程；(4) 旅途中耗费的总时间应该包括中转站的等候时间。(5) 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具 , 输出信息 : 最快需要多长时间才能到达或者最少需要多少旅费才能到达。1.4 其他需求（1）具有可靠性，可用性。（2）简单，便捷。（3）清晰，易懂。2 概要设计采用模块化的程序设计方法，即将较大的任务按照一定的原则分为一个个较小的任务，然后分别设计各个小任务。划分出来的模块相对独立但又相关，且容易理解。 图1 模块1图1.模块1图2.模块2(1) 数据存储。城市信息、交通信息存储于磁盘文件。(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间或旅费。(3) 数据的存储结构。这里建议采用邻接表作为数据的存储结构。(4) 用不同的功能模块对城市信息和交通信息进行编辑。(5) 最优决策功能模块。 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市。 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息及最终结果。即最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。(6) 主程序可以有系统界面、菜单；在程序运行过程中可以反复操作。3 详细设计3.1 结构体的定义本程序运用了关于图这种数据结构。他的抽象数据类型定义如下：typedef struct unDiGraph int numVerts; /结点 costAdj cost; /邻接矩阵unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作结果：构造带权(费用)图。unDiGraph* CreateTimeG()操作结果：构造带权（时间）图。PathMat *Floyed(unDiGraph *D)操作结果：Floyed函数 求任意两点的最短路径。3.2基本操作 typedef struct unDiGraphint numVerts; /结点costAdj 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) 操作要求：图G存在操作结果：Floyed函数 求任意两点的最短路径void prn_pass(int i,int j) /基本操作：为了求从i到j的最短路径，只需要调用如下的过程void time()操作结果：求最少时间路径。void money()操作结果：求最少花费路径void administrator()操作结果：管理员功能void main()/main函数3.3 算法说明利用Floyed函数求带权图两点之间的最短路径。通过对带权费用图和带权时间图求最短路径，就可以最短道从一城市到另一城市之间最省时间和最省费用的走法3.3.1主函数流程图 图3.主函数流程图3.3.2 pri函数流程图 图4 pri函数流程图3.3.3 增加城市流程图图5 增加城市函数流程图4 系统实现本节介绍了系统实现的开发环境，包括硬件环境，软件环境，以及运行界面展示。最后显示了该系统实现后每个功能的实现结果4.1开发环境1.硬件环境电脑型号： 组装机.处理器： Pentium G630 2.7GHz主板： 技嘉H61mds2内存： 4G显卡： HD Graphics Family2.软件环境 操作系统：Windows XP. 开发软件：Microsoft Visual C+ 6.0.4.2运行界面 图6 主菜单界面 图7 查看城市 图8 石家庄到北京火车 图9 石家庄到北京飞机 图10 管理员界面 图11 飞机花费编辑4.3测试用例时间的最少花费和最短时间的铁路乘车路线。例如：在最短时间路线选择时，如果输入11（北京）和8（广州），系统就会自动给出最短路径为：北京 郑州 武汉 株洲 广州。 当输入出错时，系统会提示出错信息，并返回输入窗口让用户重新输入。5. 总 结.构造带权图CreateFlyG CreateCostG和CreateTimeG：T(MAX)=O(MAX)2)通过实习让我了解到任何事情只有努力之后才能完成的更好。6.参 考 文 献1 许卓群等，数据结构，高等教育出版社，2000年2 刘坤起.张有华.数据结构题型.题集.题解M.科学出版社 2005年11月附录.源程序#include #include #include #include #include #include #define INF 65535 /定义一个最大数定为无穷值#define MAX 23static int c_number=14;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 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;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天津 ;break; case(13) : cout上海 ;break; case(14) : cout石家庄 ;break;default: coutaddi-14.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;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=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-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-cost310=G-cost103=34;G-cost1310=G-cost1013=65;G-cost135=G-cost513=118;G-cost1411=G-cost1114=43;G-cost142=G-cost214=110;G-cost143=G-cost314=60; if (o) while(h=1)v=v+1;pri();cout火车花费编辑endl;cout请输入开始城市的代码a;cout请输入结尾城市的代码b;cout请输入你的两地花费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=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;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;G-cost1411=G-cost1114=3;G-cost142=G-cost214=7;G-cost143=G-cost314=3;if (o) while(h=1)z=z+1;pri();cout火车时间编辑endl;cout请输入开始城市的代码a;cout请输入结尾城市的代码b;cout请输入你的两地时间mz.c_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选择出错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;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=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=4;G-cost1411=G-cost1114=1;G-cost142=G-cost214=3;G-cost143=G-cost314=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_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选择出错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(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=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-cost67=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;G-cost1411=G-cost1114=340;G-cost142=G-cost214=700;G-cost143=G-cost314=400;if (o) while(h=1)r=r+1;pri();cout飞机花费编辑endl;cout请输入开始城市的代码a;cout请输入结尾城市的代码b;cout请输入你的两地花费mr.f_cost;nr.f_cost=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选择出错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; for(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/为了求从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)&(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 Bcity,Ecity;/起始成市号码和终点城市号码 int l,h=1;do pri();/输出城市列表及相应代码。 cout请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- c_numberBcity; cinEcity;/输入起始城市和终点城市的代码。 if (!(0Bcity&Bcityc_number+1)&(0Ecity&Ecityc_number+1)&Bcity!=Ecity) coutn出错啦! 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 money() int Bcity,Ecity;/起始成市号码和终点城市号码 char l,h=1;/*unDiGraph *G;*/do pri();/输出城市列表及相应代码。cout请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- c_numberBcity;cinEcity;/输入起始城市和终点城市的代码。if (!(0Bcity&Bcityc_number+1)&(0Ecity&Ecityc_number+1)&Bcity!=Ecity) coutn出错啦! 5000|LBcityEcity10000) cout两地间还没有线路通过endl;elsecout火车花的钱是BBcityEcity元endl;cout火车花的时间LBcityEcity小时endl; printf(nn 1.继续最少花费查找n 2.返回主菜单n 清选择.); scanf(%d,&l); /输入1或2选择是否继续。 h=l; while(h=1); printf(n); /求飞机的情况void f_money() cout1endl;int Bcity,Ecity;/起始成市号码和终点城市号码 char l,h=1;/*unDiGraph *G;*/do cout2endl; pri();/输出城市列表及相应代码。cout请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- c_numberBcity;cinEcity;/输入起始城市和终点城市的代码。if (!(0Bcity&Bcityc_number+1)&(0Ecity&Ecityc_number+1)&Bcity!=Ecity) coutn出错啦! 5000|LBcityEcity10000) cout两地间还没有线路通过endl;elsecout飞机花的钱是BBcityEcity元endl;cout飞机花的时间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请输入你要增加的城市的个数j;for (i=1;i=j;i+)cout请输入你要增加的城市名endl;pr(i,1);c_number=c_number+1;cout城市增加完毕endl;void chose_money()/花最少钱的算法int h;cout1:火车endl;cout2:飞机endl;cout请选择：h;if (h=1) money();elsef_money();void chose_time()/花最少时间的算法i