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

专题设计(图)报告题目：公交线路查询小组成员：问题描述当一个用户从甲地到乙地时，由于不同需求，就有不同的交通方式及不同的交通路线。

有人希望以最快速度到达，有人希望以最短距离到达，有人希望用最少的费用等。

交通方式有公交车和地铁。

编写一北京公交线路查询系统，通过输入起始站、终点站，为用户提供三种或以上决策的交通咨询。

设计要求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) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。

算法思想本程序运用了图的知识并利用Floyed函数求带权图两点之间的最短路径。

通过对图表求最短路径，就可以最短道从一站点到另一站点之间最省时间和最省费用的走法。

程序模块程序的模块为#include <windows.h>#include <stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h>#include <malloc.h>//引用的文本件#define INF 65535 //定义一个最大数定为无穷值#define MAX 13typedef int costAdj[MAX+1][MAX+1];//图邻接矩阵从1开始记数int Path[MAX+1][MAX+1];//图邻接矩阵从1开始记数int o[13],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 23static 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 m[20],x[20],n[20];typedef int costAdj[MAX+1][MAX+1]; //图邻接矩阵从1开始记数int Path[MAX+1][MAX+1]; //图邻接矩阵从1开始记数typedef struct unDiGraph{int numVerts; //结点costAdj cost; //邻接矩阵}unDiGraph,*UNG; //图的定义typedef struct c_edit{char a[10];}c_edit;c_edit add[10];costAdj B,L;int pr(int i,int j){int h=0;if(j==0) {h=i;}else if(j==1) {cin>>add[i].a;}switch(h)//运用switch语句。

{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<<add[i-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<<en dl<<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分配存储空间。