数据结构课程设计全国交通咨询系统

1、太原工业学院计算机工程系数据结构课程设计设计题目：全国交通网络咨询系统1班级：计算机科学与技术学号：132054103姓名：陈敏指导教师：刘海静目录一、课程设计题目 1二、需求分析 1三、测试数据 2四、概要设计2五、调用关系图3六、程序代码 3七、测试结果 14八、心得体会及总结 14数据结构课程设计一、课程设计题目全国交通网络咨询系统二、需求分析1、实现功能对城市信息（城市名、城市间的里程）进行编辑：具备添加、修改、删除功能；对城市间的交通工具：火车。对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除；提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；咨

2、询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。2、设计思路（1）数据存储。城市信息（城市名、代码）、交通信息（城市间的里程、各航班和列车时刻 ） 存储于磁盘文件。在实验中本想用文本储存数据， 但操作不熟悉，而是改用图的邻接矩阵 储 存原始信息，而后用数组进行添加删改（2）数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为无向图，图的顶点是城市，边是城市之间所耗

3、费的时间（要包括中转站的时间）或旅费。（3）数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，这里建议采用 邻接矩阵作为数据的存储结构。（4）用不同的功能模块对城市信息和交通信息进行 编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计， 也可参考有关程序（届时在网上提供）。这些工作有不小的工作量。（5）最优决策功能模块 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系

4、的城市 （代码、里程、列车车次）。 根据具体最优决策的要求，用floyd算法求出出发城市到其它各城市的最优值（最短时间 或最小的费用），搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。其相应的初始值可为并在表头数组对应的城市元素中保存响应的信息。 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序 运行过程中可以反复操作。三、测试数据:四、概要设计本程序运用了关于图这种数据结构。它的抽象数据类型定义如下：typedef struct un DiGraphint num Verts; /纟吉点 costA

5、dj cost; 邻接矩阵un DiGraph,*UNG;基本操作：un DiGraph* CreateCostG（）操作结果：构造带权（费用）图。un DiGraph* CreateTimeG（）操作结果：构造带权（时间）图。构造飞机带权（费用）图。PathMat *Floyed（u nDiGraph *D）操作结果：Floyed函数 求任意两点的最短路径。五、调用关系图un DiGraph （图）Floyed函数 求任意两点的最短路径CreateCostG（构造带权 费用）CreateTimeG （构造带权时间）六、程序代码#i nclude #i nclude #in clude #in

6、clude #i nclude#i nclude #defi ne INF 10000 /定义一个最大数定为无穷值#defi ne MAX 7static int cnu mber=7;static int k=0;static in t v=0,z=0;定义静态变量typedef struct zhu定义结构体 zhuin t ccost;/定义结构变量int ctime;zhu;zhu m20,x20,n20;定义数组为struct zhu类型数组，且三个数组分别储存添加后的数据，且表示花费 m起点n，和终点xtypedef in t costAdjMAX+1MAX+1; 定义图的邻接矩阵

7、，并从 1开始int PathMAX+1MAX+1;/路程矩阵，表示经过存放的点ktypedef struct un DiGraphint numV;/ 结点costAdj cost;/ 邻接矩阵u nDiGraph,*UNG;14typedef struct cedit char a10; cedit; cedit add10;costAdj B,L;/ 功能一 输出相应的城市信息int pr(int i,int j)/pr 函数表输出功能int h=0;if (j=0)h=i;else if (j=1)cinaddi.a;switch (h)case(0) : cout;break;cas

8、e(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;return 1;void pri() 声明pri函数，即利用pr函数输出代码为i 的城市信息int i;cout 城市以及其代码 endl;cout*、endl;for(i=1;i=cnumber;i+)couti.;pr(i,0);cout*、endl;/ 构造 Cost

9、G 图，表示其费用unDiGraph *CreateCostG(int o)/火车的花费的存贮和编辑功能unDiGraph *G;int i;int j;/ 定义的 i,j 做循环变量int a=0,b=0,f=1,h=1;/f 变量初始为 1， h 初始值为 1，a=0,b=0 临时表示 开始城市代码以及目的城市代码if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /为 G 图分配存储空间。 return(NULL);for(i=1;i=cnumber;i+) for(j=1;jcostij=INF;/ 初始化矩阵 cost 每一项，使其无穷大G-nu

10、mV=cnumber;G-cost16=G-cost61=90;G-cost12=G-cost21=84;G-cost23=G-cost32=51;G-cost25=G-cost52=67;G-cost34=G-cost43=53;G-cost45=G-cost54=40;G-cost47=G-cost74=88;G-cost56=G-cost65=90;G-cost57=G-cost75=67;G-cost67=G-cost76=60;if (o)while(h=1)/h 初始值为 1v=v+1;/V 为全局静态变量，初始值为 0 ,v 表示编辑的火车花费的组数， 三个编辑数组中的存放代码p

11、ri();cout 火车花费编辑 endl;cout 请输入开始城市的代码 a;cout 请输入目的城市的代码 b;cout 请输入你的两地花费 mv.ccost;nv.ccost=a;xv.ccost=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.ccostxv.ccost=mv.ccost;v=f; return(G);/构造TimeG图，表

12、示其花费时间unDiGraph *CreateTimeG(int o)/ 火车的时间的存贮和编辑功能 unDiGraph *G; int i,j;/ 循环变量 int a=0,b=0,f,h=1;/a,b 表增加城市的代码if(!(G=(unDiGraph*)malloc(sizeof(unDiGraph) /为 G分配存储空间。 return(NULL);for(i=1;i=cnumber+1;i+) for(j=1;jcostij=INF;/ 初始化使 G-costij 为无穷。 G-numV=cnumber;G-cost16=G-cost61=9; G-cost12=G-cost21=8

13、;G-cost23=G-cost32=5;G-cost25=G-cost52=3;G-cost34=G-cost43=5;G-cost45=G-cost54=4;G-cost47=G-cost75=6;G-cost56=G-cost65=9;G-cost57=G-cost75=6;G-cost67=G-cost76=6;if (o)while(h=1) z=z+1;/ 全局静态变量，初始值为 0. 即 1=0+1 pri();cout 火车时间编辑 endl; cout 请输入开始城市的代码 a;cout 请输入结尾城市的代码 b;cout 请输入你的两地时间 mz.ctime; nz.cti

14、me=a; xz.ctime=b;cout 请选择 endl;*/*endl;cout1 ：继续更改城市时间 endl; cout0: 返回上一级菜单 endl; cout* h; switch(h) case 1: h=1; break;case 0:h=0; break;default: cout 选择出错 costnz.ctimexz.ctime=mz.ctime;z=f; return(G);/Floyed 函数 求任意两点的最短路径： void Floyed(unDiGraph *D,unDiGraph *M)/图 D McostAdjint i,j,k,n;/i,j 为循环变量 ,

15、k 表中间节点的变量 costAdj A,C;/A C 为图，临时表示两种最佳路线组成的矩阵，定义 B Ln=cnumber; for(i=1;i=n;i+)for(j=1;jcostij;/ 初始化矩阵 A,C。 Cij=M-costij;Pathij=-1; / 初始化权矩阵 p 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小，则选择经过 K个中间点之后， i,j 两

16、点的最佳路径。Bij=Aij;/构造 A C 两个任意节点上的最优路径所建造的矩阵，并分别赋给 B L 代表时间与花费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);/输出最短路径经过的所有点个数 kpr(Pathij,0);/ 求最少时间路径。void time()int Bcity,Ecity;/ 起始成市号码和终点城市号

17、码int l,h=1;/ 定义变量 l hdo pri();/ 输出城市列表及相应代码。cout 请输入起始城市和目的城市的代码，中间以空格隔开 Bcity;cinEcity;/ 输入起始城市和终点城市的代码。if (!(0Bcity&Bcitycnumber+1)&(0Ecity&Ecitycnumber+1)&Bcity!=Eci ty)coutn 出错啦! 输入城市号码请在 1-7 之间，且两城市代码不能 相等!8000|LBcityEcity8000)cout 两地间还没有线路通过 endl;elsecout 火车花的时间是 BBcityEcity小时 endl;cout 输入 0.

18、返回主菜单 endl;scanf(%d,&l); /h=l; while(h=1);/ 求最少花费路径。void money()int Bcity,Ecity;/ 起始成市号码和终点城市号码char l,h=1;do pri();/ 输出城市列表及相应代码。cout 请输入起始城市和目的城市的代码，中间以空格隔开 Bcity;cinEcity;/ 输入起始城市和终点城市的代码。if (!(0Bcity&Bcitycnumber+1)&(0Ecity&Ecitycnumber+1)&Bcity!=Eci ty)coutn 出错啦 ! 输入城市号码请在 1-7 之间，且两城市代码不能 相等!800

19、0|BBcityEcity8000)cout 两地间还没有线路通过 endl;elsecout火车花的钱是BBcityEcityvv元endl;cout 输入 0. 返回主菜单 endl;scanf(%d,&l); /h=l; while(h=1);void add_city()/ 对城市的增加static int i=1;int j;cout 请输入你要增加的城市的个数 j;for (i=1;i=j;i+)cout 请输入你要增加的城市名 endl;pr(i,1);将添加的内容放置于add数组中，并以i为代码cnumber=cnumber+1;cout 城市增加完毕 endl;void ch

20、ose()/ 选择最少时间或最小花费int h;cout1: 最小花费 endl;cout2: 最小时间 endl; cout 请选择： h;if (h=1) money();elsetime();void edit_line()/ 增加编辑火车的费用CreateCostG(1);void edit_hour()/ 增加编辑火车的时间CreateTimeG(1);void administrator()/ 管理员功能int h=1;while (h) *endl;cout1: 增加城市 endl;cout2: 添加或编辑火车费用 endl;cout3: 添加或编辑火车时间 endl;cout0

21、: 返回主菜单 endl;cout*endl;cout 请选择 h;switch(h) case 1 :add_city();break;case 2: edit_line();break;case 3:edit_hour();break;case 0:h=0;break; default:cout 选择出错！ endl;/ 主函数 void main() char n; int x; while(x!=0) coutendl;cout 输入你希望查询的种类代码，你将得到最佳方案 !endl;cout * 全 国 交 通 网 络 模 拟 系 统*、endl;cout*endl;cout*endl;cout*endl;cout*endl;cout*endl;cout主菜单1. 查 看 城 市2. 选 择 最 短 时 间 路 线3. 选择最 节约费用路线4. 管 理 员 程 序0.