北京理工大学数据结构课程设计专题报告公交线路查询.docx

北京理工大学数据结构课程设计专题报告公交线路查询专题设计(图)报告 题目：公交线路查询 小组成员： 问题描述 当一个用户从甲地到乙地时，由于不同需求，就有不同的交通方式及不同的交通路线。有人希望以最快速度到达，有人希望以最短距离到达，有人希望用最少的费用等。交通方式有公交车和地铁。编写一北京公交线路查询系统，通过输入起始站、终点站，为用户提供三种或以上决策的交通咨询。 设计要求 a. 提供对交通线路进行编辑功能。要求可添加或删除线路。 b. 提供两种交通工具，公交车和地铁，设定路程所需要的时间、距离及费用等参数。 c. 提供多种决策：最短距离、最快到达、最少费用、最少换乘次数等。 d. 中途不考虑等候、拥堵等消耗时间。 e. 该系统以人机对话方式进行。用户输入起始站、终点站及需求原则，系统输出乘车方案：乘什么车、乘几路车、距离、时间、费用换乘方法等相关信息。 数据结构 本程序运用了关于图这种数据结构。 它的抽象数据类型定义如下： typedef struct unDiGraph int numVerts; /结点 costAdj cost; /邻接矩阵 unDiGraph,*UNG; 基本操作： unDiGraph* CreateCostG 操作结果：构造带权(费用)图。 unDiGraph* CreateTimeG 操作结果：构造带权图。 构造地铁带权(费用)图。 PathMat *Floyed(unDiGraph *D) 操作结果：Floyed函数 求任意两点的最短路径。 设计与实现 算法思路 (1) 数据存储。站点信息(站点代码)、交通信息(站点间的里程、公交和地铁时刻)存储于磁盘文件。建议把站点信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。 (2) 数据的逻辑结构。根据设计任务的描述，其站点间的交通问题是典型的图结构，可看作为有向图，图的顶点是站点，边是站点之间所耗费的时间或车费。 (3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。 (4) 用不同的功能模块对站点信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对站点信息和交通信息进行管理即可。 (5) 最优决策功能模块(fast or province)。 读入信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放站点名及对方站点到达该元素所代表站点的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的站点有交通联系的站点(代码、里程、公交和地铁车次)。 根据具体最优决策的要求，用Dijkstra算法求出出发站点到其它各站点的最优值(最短时间或最小的费用)，搜索过程中所经过站点的局部最优信息都保存在邻接表的表头数组中。其目的站点所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的站点，其相应的初始值可为，并在表头数组对应的站点元素中保存响应的信息。开始时，栈(队)中只有出发站点，随着对栈(队)顶(首)站点有交通联系的站点求得决策值(最短时间或最小的费用)，若该值是局部最优值且该站点不在栈(队)中，则进栈(队)，直至栈(队)为空。 输出结果。从目的站点出发，搜索到出发站点，所经过的站点均入栈，再逐一出栈栈中的站点，输出保存在表头数组中对应站点的信息(对方站点的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的公交或地铁于何时到达何地；最终所需的最快需要多长时间才能到达及费用，或者最少需要多少车费才能到达及时间。 (6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。算法思想 本程序运用了图的知识 里程 时间 A-B 8 8 B-C 5 5 C-K 6 7 K-L 1 1 L-J 6 7 J-M 6 6 C-D 5 5 D-M 5 5 D-E 4 4 E-M 11 11 E-H 6 6 E-F 9 9 F-A 9 9 F-G 6 6 G-I 2 2 E-H 6 6 K L B C J 并利用Floyed函数求带权图两点之间的最短路径。通过对图表求最短路径，就可以最短道从一站点到另一站点之间最省时间和最省费用的走法。 程序模块 程序的模块为 #include <windows.h> #include <stdio.h> #include <crtdbg.h> #include <string.h> #include<iostream.h> #include <malloc.h>/引用的文本件 #define INF 65535 /定义一个最大数定为无穷值 #define MAX 13 typedef int costAdjMAX+1MAX+1;/图邻接矩阵从1开始记数 int PathMAX+1MAX+1;/图邻接矩阵从1开始记数 int o13,h; typedef struct unDiGraph int 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) /Floyed函数 求任意两点的最短路径： ： void prn_pass(int i,int j) /为了求从i到j的最短路径，只需要调用如下的过程 void time/求最少时间路径。 void money/求最少花费路径 void administrator/管理员功能 void main/main函数 测试与结论 显示站点 选择最短时间路线 选择最少花费路线 增加站点并测试 总结与思考 拿到题目的时候比较困惑，毕竟我们的C/C+学的不是很好，后来看了很多有关的例子，仔细看了书上的图部分的知识，觉得就是书上的许许多多的内容和代码，其实总体来说，应该不会特别的难。 后来，参照书上的和网上的诸多例子，一个模块一个模块的编写，调试，一个功能一个功能去完善。发现越做越顺利，又有以前用C/C+写的各个程序的代码，回头看了一下自己当年编写的程序，加上实验中对于改错的经验积累和几个学得不错的同学的帮助，我们小组的程序中的错误也一个一个的顺利解决。 其实，这个对于文本文件的操作以前也有涉及到过，但是以前的时候总是以数组或者指针的形式进行调用，这一次直接才有的是I/O流，觉得效果还是很不错的。 再后来，程序终于就基本实现了。其实，从这次实验中我们认识到，编程有很多的乐趣也有很多的技巧性和知识性。我们将在以后的日子里继续认真的学习知识，积累经验，让自己的编程能力提高。 附录 程序源代码 #include <windows.h> #include <stdio.h> #include <string.h> #include<iostream.h> #include <malloc.h> #define INF 65535 值 #define MAX 23 static int c_number=13; static int k=0; static int v=0,z=0,r=0,t=0; typedef struct zhu int c_cost; int c_time; int f_cost; int f_time; zhu; zhu m20,x20,n20; typedef int costAdjMAX+1MAX+1; int PathMAX+1MAX+1; 数 typedef struct unDiGraph int numVerts; costAdj cost; unDiGraph,*UNG; typedef struct c_edit char 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语句。 /定义一个最大数定为无穷/图邻接矩阵从1开始记数 /图邻接矩阵从1开始记 /结点 /邻接矩阵 /图的定义 case(0):cout<<""break; case(1) : cout<<"A "break; case(2) : cout<<"B "break; case(3) : cout<<"C "break; case(4) : cout<<"D "break; case(5) : cout<<"E "break; case(6) : cout<<"F "break; case(7) : cout<<"G "break; case(8) : cout<<"H "break; case(9) : cout<<"I "break; case(10) : cout<<"J "break; case(11) : cout<<"K "break; case(12) : cout<<"L "break; case(13) : cout<<"M "break; default : cout<<addi-13.a; return 1; /输出站点列表及相应代码 void pri int i; cout<<" 站点及其代码"<<endl<<endl<<endl; cout<<" *"<<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; int a=0,b=0,f,h=1; if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)return(NULL); /为G分配存储空间。 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->cost65=9; G->cost58=G->cost85=6; G->cost57=G->cost75=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=7; G->cost310=G->cost103=3; G->cost1310=G->cost1013=5; G->cost135=G->cost513=11; if (o) while(h=1) v=v+1; pri; cout<<"公交花费编辑"<<endl; cout<<"请输入开始站点的代码"<<endl; cin>>a; cout<<"请输入结尾站点的代码"<<endl; cin>>b; cout<<"请输入你的两地花费"<<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) 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) 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->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分配存储空间。 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<<"请选择"<<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<<"选择出错"<<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) return(NULL); /为G分配存储空间。 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=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=1; if (o) while(h=1) t=t+1; pri; cout<<"地铁时间编辑"<<endl; cout<<"请输入开始站点的代码"<<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：继续更改站点时间"<<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(int o)/地铁花费的存贮和编辑功能 unDiGraph *G; int i,j; int a=0,b=0,f,h=1; if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) return(NULL); /为G分配存储空间。 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=7; G->cost23=G->cost32=5; G->cost34=G->cost43=5; G->cost45=G->cost54=4; G->cost56=G->cost65=9; G->cost58=G->cost85=6; G->cost57=G->cost75=6; G->cost67=G->cost76=6; G->cost79=G->cost97=2; G->cost311=G->cost113=6; G->cost1112=G->cost1211=3; 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) r=r+1; pri; cout<<"地铁花费编辑"<<endl; cout<<"请输入开始站点的代码"<<endl; cin>>a; cout<<"请输入结尾站点的代码"<<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; cout<<"*"<<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=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 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<<"请输入起始站点和目的站点的代码，中间以空格隔开，范围(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<<"之间，且两站点不能相等!"<<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; else cout<<"公交花的钱是"<<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_number<<")" cin>>Bcity;cin>>Ecity;/输入起始站点和终点站点的代码。 if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&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; else cout<<"地铁花的钱是"<<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_number<<")" cin>>Bcity; cin>>Ecity;/输入起始站点和终点站点的代码。 if (!(0<Bcity&&Bcity<c_number+1)&&(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>10000) cout<<"两地间还没有线路通过"<<endl; else cout<<"公交花的钱是"<<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 cout<<"1"<<endl; int Bcity,Ecity;/起始成市号码和终点站点号码 char l,h=1; /*unDiGraph *G;*/ do cout<<"2"<<endl; pri;/输出站点列表及相应代码。 cout<<"请输入起始站点和目的站点的代码，中间以空格隔开，范围(1- "<<c_number<<")" cin>>Bcity;cin>>Ecity;/输入起始站点和终点站点的代码。 if (!(0<Bcity&&Bcity<c_