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

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

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

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

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

5、st; 令口接矩阵unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG（）操作结果：构造带权（费用）图。unDiGraph* CreateTimeG（）操作结果：构造带权（时间）图。构造飞机带权（费用）图。PathMat *Floyed（unDiGraph *D）操作结果：Floyed函数 求任意两点的最短路径。18五、调用关系图unDiGraph（图）Floyed函数 求任意两点的最短路径CreateCostG（构造带权 费用）CreateTimeG （构造带权时间）六、程序代码#include <windows.h>#include <st

6、dio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h>#include <malloc.h>#define INF 10000 /定义一个最大数定为无穷值#define MAX 7static int cnumber=7;static int k=0;static int v=0,z=0;/定义静态变量typedef struct zhu/定义结构体 zhuint ccost;/定义结构变量int ctime;zhu;zhu m20,x20,n20;/定义数组为str

7、uct zhu类型数组，且三个数组分别储存添加后的数据，且表示花费 m,起点n,和终点xtypedef int costAdjMAX+1MAX+1;/定义图的邻接矩阵，并从 1开始int PathMAX+1MAX+1;/ 路程矩阵，表示经过存放的点 ktypedef struct unDiGraph int numV;/ 结点costAdj cost;/ 邻接矩阵unDiGraph,*UNG;typedef struct cedit char a10;cedit;cedit add10;costAdj B,L;/ 功能一 输出相应的城市信息int pr(int i,int j)/print h

8、=0;if (j=0)h=i;else if (j=1)cin>>addi.a;switch (h)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<<"

9、break;case(7) : cout<<" break;return 1;void pri()/ 声明 pri函数表输出功能成都 "广州 "上海徐州 "郑州 "西安 "北京 "pr 函数输出代码为i 的城市信息int i;cout<<" 城市以及其代码"<<endl;cout<<"*"<<endl;for(i=1;i<=cnumber;i+)cout<<i<<"."pr(i

10、,0);cout<<"*"<<endl;/构造CostG图，表示其费用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+

11、)for(j=1;j<=cnumber;j+) G->costij=INF;/ 初始化矩阵cost 每一项，使其无穷大G->numV=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=

12、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 表示编辑的火车花费的组数，三个编辑数组中的存放代码pri();cout<<" 火车花费编辑"<<endl;cout<<" 请输入开始城市的代码"<<endl;cin>>a;cout<<" 请输入目的城市的代码"<&

13、lt;endl;cin>>b;cout<<" 请输入你的两地花费"<<endl;cin>>mv.ccost;nv.ccost=a;xv.ccost=b;cout<<" 请选择 "<<endl;cout<<"*”<<endl;cout<<"1 ：继续更改城市费用"<<endl;cout<<"0: 返回上一级菜单"<<endl;cout<<"*”

14、<<endl;cin>>h;switch(h) case 1:h=1;break;case 0:h=0;break;default:cout<<" 选择出错"<<endl;f=v+1;/初始定义变量f为1,全局变量v为0,即1=0+1while (v+) /v+ 代表的意思G->costnv.ccostxv.ccost=mv.ccost;v=f;return(G);/构造TimeG图，表示其花费时间unDiGraph *CreateTimeG(int o)/ 火车的时间的存贮和编辑功能unDiGraph *G;int i

15、,j;/ 循环变量int a=0,b=0,f,h=1;/a,b 表增加城市的代码if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) / 为 G分配存储空o(return(NULL);for(i=1;i<=cnumber+1;i+)(for(j=1;j<=cnumber+1;j+)(G->costij=INF;/初始化使 G->costij为无穷。G->numV=cnumber;G->cost16=G->cost61=9;G->cost12=G->cost21=8;G->cost23=G->c

16、ost32=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+1pri();cout<<”火车时间编辑"<<endl;cout<

17、;<"请输入开始城市的代码"<<endl;cin>>a;cout<<"请输入结尾城市的代码"<<endl;cin>>b;cout<<"请输入你的两地时间"<<endl;cin>>mz.ctime;nz.ctime=a;xz.ctime=b;cout<<"请选择"<<endl;cout<<"*”<<endl;cout<<"1 ：继续更改城

18、市时间"<<endl;cout<<"0: 返回上一级菜单"<<endl;cout<<"<<endl;*”cin>>h;switch(h) case 1:h=1;break;case 0:h=0;break;default:cout<<" 选择出错"<<endl;f=z+1;/ 全局静态变量z, 初始值为0while (z+)G->costnz.ctimexz.ctime=mz.ctime;z=f;return(G);/Floyed 函

19、数 求任意两点的最短路径：void Floyed(unDiGraph *D,unDiGraph *M)/ 图 D Mint i,j,k,n;/i,j为循环变量,k 表中间节点的变量costAdj A,C;/A C为图，临时表示两种最佳路线组成的矩阵，定义 costAdjn=cnumber;for(i=1;i<=n;i+)for(j=1;j<=n;j+)Aij=D->costij;/ 初始化矩阵A,C。Cij=M->costij;Pathij=-1;/ 初始化权矩阵pfor(k=1;k<=n;k+) /k 为逐步加入的中间结点for(i=1;i<=n;i+)

20、/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小，则选择经过 K 个中间点之后，i,j 两点的最佳路径。Bij=Aij;/ 构造 A C 两个任意节点上的最优路径所建造的矩阵，并分别赋给B L 代表时间与花费Lij=Cij; elseBij=Aij;Lij=Cij;/end for 循环cout<<"n 最短路径为: "<<endl;/end-Floyed/ 为了求从i 到 j 的最短路径，只需要调用如下的

21、过程：void prn_pass(int i,int j)if(Pathij!=-1)prn_pass(i,Pathij);/ 输出最短路径经过的所有点个数kpr(Pathij,0);/ 求最少时间路径。void time()int Bcity,Ecity;/ 起始成市号码和终点城市号码int l,h=1;/ 定义变量l hdo pri();/ 输出城市列表及相应代码。cout<<" 请输入起始城市和目的城市的代码，中间以空格隔开"<<endl;cin>>Bcity;cin>>Ecity;/ 输入起始城市和终点城市的代码。if

22、(!(0<Bcity&&Bcity<cnumber+1)&&(0<Ecity&&Ecity<cnumber+1)&&Bcity!=Eci ty)cout<<"n 出错啦 ! 输入城市号码请在1-7 之间， 且两城市代码不能相等 !"<<endl;Floyed(CreateTimeG(0),CreateCostG(0);/ 调用 Floyed 函数。pr(Bcity,0);/显示起始城市。prn_pass(Bcity,Ecity);/ 调用 prn_pass 函数，

23、 显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>8000|LBcityEcity>8000)cout<<" 两地间还没有线路通过"<<endl;elsecout<<" 火车花的时间是"<<BBcityEcity<<" 小时 "<<endl;cout<<" 输入 0. 返回主菜单"<<endl;scanf("%d",&l); /h=l

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

25、ber+1)&&Bcity!=Eci ty)cout<<"n 出错啦 ! 输入城市号码请在1-7 之间，且两城市代码不能相等 !"<<endl; / 输入出错Floyed(CreateCostG(0),CreateTimeG(0);/ 调用 Floyed 函数。pr(Bcity,0);/ 显示起始城市。prn_pass(Bcity,Ecity);/ 调用 prn_pass 函数， 显示最短路径经过的城市。pr(Ecity,0);/ 显示终点城市。if (LBcityEcity>8000|BBcityEcity>8000)

26、cout<<" 两地间还没有线路通过"<<endl; elsecout<<" 火车花的钱是"<<BBcityEcity<<" 元 "<<endl;cout<<" 输入 0. 返回主菜单"<<endl;scanf("%d",&l); / h=l; while(h=1);void add_city()/ 对城市的增加static int i=1;int j;cout<<" 请

27、输入你要增加的城市的个数"<<endl;cin>>j;for (i=1;i<=j;i+)cout<<" 请输入你要增加的城市名"<<endl;pr(i,1);/将添加的内容放置于add数组中，并以i为代码cnumber=cnumber+1;cout<<" 城市增加完毕"<<endl;void chose()/ 选择最少时间或最小花费int h;cout<<"1: 最小花费"<<endl;cout<<"2

28、: 最小时间"<<endl;cout<<" 请选择："<<endl;cin>>h;if (h=1) money(); else time();void edit_line()/ 增加编辑火车的费用CreateCostG(1);void edit_hour()/ 增加编辑火车的时间CreateTimeG(1);void administrator()/ 管理员功能int h=1;while (h) cout<<"*"<<endl;cout<<"1: 增加

29、城市"<<endl;cout<<"2: 添加或编辑火车费用"<<endl;cout<<"3: 添加或编辑火车时间"<<endl;cout<<"0: 返回主菜单"<<endl;cout<<"*"<<endl;cout<<" 请选择 "<<endl;cin>>h;switch(h) case 1 :add_city();break;case 2 e

30、dit_line();break;case 3:edit_hour();break;case 0:h=0;break;default:cout<<" 选择出错！"<<endl;/ 主函数void main()char n;int x;while(x!=0)cout<<endl;cout<<" 输入你希望查询的种类代码，你将得到最佳方案!"<<endl;cout<<"* 全 国 交 通 网 络 模 拟 系 统*”<<endl;cout<<"*"<<endl;cout<<"*"<<endl;cout<<"*"<<endl;cout&l