数据结构专题设计报告—北京公交查询_城市公交查询系统设计
数据结构专题设计报告—北京公交查询由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“城市公交查询系统设计”。
图专题设计报告
题目：公交线路查询成员：组长：
张俭伟 组员：
邵
青
杨梓艺
赵
欣
李
哲
宁立跃
彭少龙 时间：2013年4月30
日
一、问题描述
随着经济和科技的高速发展，城市的公共交通建设进程加快。北京作为一个国际化大都市，其公共交通网络已日趋完善。但随着一条条交通线路的开始运行，调整路线，或被其它路线取代而停用，城市复杂的公共交通网络有时也给市民出行造成了不小的困扰。一个用户从甲地到乙地，有多种交通方式及多种交通路线。而由于对速度，距离，交通方式，及费用等方面的不同需要，用户需要有多种满足不同需求的方案以备选择。常见的交通方式有公交车和地铁。本次专题就为人机交互的北京公交线路查询系统。用户只需输入起始站、终点站，系统即可为用户提供三种或以上决策的交通咨询。
二、具体要求
a.提供对交通线路进行编辑功能。要求可添加或删除线路。
b.提供两种交通工具，公交车和地铁，设定路程所需要的时间、距离及费用等参数。
c.提供多种决策：最短距离、最快到达、最少费用、最少换乘次数等。d.中途不考虑等候、拥堵等消耗时间。
e.该系统以人机对话方式进行。用户输入起始站、终点站及需求原则，系统输出乘车方案：乘什么车、乘几路车、距离、时间、费用换乘方法等相关信息。
三、数据结构与算法分析
1）可以以邻接表作交通图的存储结构，表示边的结构内除包含有邻接点的信息外，还应包括交通工具、路程时间和费用等多种属性。
2）使用图的基本算法：插入、删除、排序、深度优先级搜索和广度优先搜索等算法。
四、算法设计与实现
1、流程图
由于算法较为明朗，这里只对其中较为复杂的部分——通过全链表的线路结构建立邻接链表这一过程给出流程图。
2、算法设计思路及特点
1）迪克斯特拉（Dijkstra）算法
按路径长度递增逐步产生最短路径 2）线路结构
在线路存储处理上，我们小组采用了链表结构进行存储线路： 站点链结点结构 StationData 线路链结点结构 RouteData
3）图结构
我们有四种搜索路径方式：最短距离、最短时间、最少换乘、最少花费。
a.用来搜索最短距离和最短时间的路径时是只考虑相邻的两个站点，所以在整个图结构中边数较小。为了节省空间资源，我们采用了邻接链表的方式来存储图。
b.用来搜索最少换乘与最少花费的路径时需要考虑到一个站点所有可能0换乘到达的站点，所以整个图结构中边数较多，所以采用了邻接矩阵的结构。
3、程序代码（有备注，见附录）
五、测试与结论
1、采用VC进行编译调试（代码界面）
2、主界面（用户体验界面）
按照提示输入1.管理员（管理权限系统权限，增加、删除、查询路线站点）
2.普通用户（查询路线站点）
3、管理员权限测试
1）登录需输入正确密码
2）管理员功能选择界面
3）管理员增加路线界面
通过输入站点、时间间隔和距离间隔新建一条9号地铁线，保存。此时，显示全部线路的界面中新建的线路subway9已存在。
4）管理员删除线路界面
通过输入线路的名称，确定是否删除此线路。
4、用户权限测试
1）用户功能选择界面
2）查询站点测试
输入要查询的站点，系统会显示出经过此站点的全部路线。如此用例中，输入“西直门”，西直门为换乘站，系统给出了经过此站的2条线路的详细情况。
3）用户搜索路线（最核心的功能）
首先先展示我们测试使用的路径图片。
首先是最短距离的测试。
最少时间的测试。
最少换乘——最短距离模式。
最少换乘——最短时间模式。
最少花费——最短距离模式。
最少花费——最短时间模式。
4）、输入两个报错用例 a.以管理员身份登录
以管理员身份登录系统时需要输入密码，若输入错误，则系统提示“密码错误，返回主界面”。b.用户查询报错
用户站点查询时，输入站点名错误，系统提示“无此站点，重新输入。”
六、小组分工
邵青：编写了最短时间、最短距离部分的搜索函数
杨梓艺：编写了建立邻接链表部分的函数
赵欣：编写了最少换乘、最少花费部分的搜索函数 李哲：负责编写了建立邻接矩阵的函数，并编写了路线链表与该部分相关的函数 彭少龙：编写了路线链表的全部函数
宁立跃：构思、讨论并给出Dijkstra算法的模板及程序其他方面的构思，供其他组员使用，张俭伟：构思、讨论并给出Dijkstra算法的模板及程序其他方面的构思，供其他组员使用
七、总结与思考
通过大家的共同努力，完成了最后一次的专题程序设计。小组的各位成员都在本次设计中学习到了很多。
1）专业方面。我们对图和链表的结构从书面了解，逐步熟悉到能够掌握结构用法并运用到本次的图专题程序设计中。小组成员的基于C++编程的能力又得到了进一步的提升。
2）本次专题的主题为“北京公交查询系统”。题目与生活联系非常紧密，这就要求我们的程序设计一定要理论与实践相结合，同时考虑到交通网络中各种复杂的重叠，交叉及往返等情况，统筹兼顾。让小组成员都学会把专业中的编程更深入有效地运用到实际生活中去。
3）完成专题设计中组内合作是非常重要的。组内成员不断的进行思考与沟通，完善分工，提升了协作能力。
附录：
#include #include #include using namespace std;
#define MAX 200 #define Infinity 65535 #define PASSWORD “123”
string paword();
/******************************存储格式********************************** 线路名 线路类型 线路费用
站名1 距下一站时间 距下一站距离 站名2。。。。。。。。#（表示该线路结束）
*************************************************************************/
/******************************线路链表部分***********************************/
cla StationData { public:
string sn;
//站点名
int distance,time,number;//距下一站的距离和时间
StationData *next;
StationData *former;
StationData()
{
distance = time = number = 0;
next = former = NULL;
} };
cla RouteData { public:
string rn;
//公交路线名
int type;
//类型
float fee;
//费用
StationData *link;
RouteData *next;
RouteData()
{
link = NULL;
next = NULL;
} };
cla Route { public:
RouteData *head;
int num;
Route()
{
head = NULL;
num = 0;
}
void Creat();
RouteData * Find(string s);
void Add();
void Dele();
void Save();
void ShowOneRoute(RouteData * p);
void Showall();
RouteData * FindRoute(string one,string two);
double MinWay(string one,string two,int way);
double MinWayMoney(string one,string two,int way);
RouteData * MinWayReturnRouteData(string one,string two,int way);
int TwoStationDistantAndShowRoute(RouteData *point,string one,string two,int &t);
void CheckRoute();
void CheckStation();};
void Route::CheckRoute(){
string rr;point2:
cout
cout
cin >> rr;
cout
RouteData * p = head;
int tf = 0;
while(p!= NULL)
{
if(p->rn == rr)
{
tf = 1;
ShowOneRoute(p);
break;
}
p = p->next;
}
if(tf == 0)
{
cout
system(“pause”);
goto point2;
}
cout
system(“pause”);}
void Route::CheckStation(){
string;point3:
cout
cout
cin >>;
cout
int tf = 0;
RouteData * p = head;
while(p!=NULL)
{
StationData * q = p->link;
while(q!=NULL)
{
if(q->sn ==)
{
tf = 1;
ShowOneRoute(p);
cout
break;
}
q = q->next;
}
p = p->next;
}
if(tf == 0)
{
cout
system(“pause”);
goto point3;
}
system(“pause”);}
double Route::MinWayMoney(string one,string two,int way){
RouteData * f = head;
RouteData * m = NULL;
int min,min0,mark;
min = Infinity;
while(f!= NULL)
{
min0 = 0;
StationData * p = f->link;
while(p->next!= NULL && p->sn!= one && p->sn!= two)p = p->next;
if(p->next == NULL)min0 = Infinity;
else if(p->sn == one)
{
while(p->sn!= two&&p->next!=NULL)
{
if(way == 1)mark = p->distance;
else if(way == 2)mark = p->time;
min0 = min0 + mark;
p = p->next;
}
if(p->sn!= two)min0 = Infinity;
if(min > min0){min = min0;m = f;}
}
else if(p->sn == two)
{
while(p->sn!= one && p->next!=NULL)
{
if(way == 1)mark = p->distance;
else if(way == 2)mark = p->time;
min0 = min0 + mark;
p = p->next;
}
if(p->sn!= one)min0 = Infinity;
if(min > min0){min = min0;m = f;}
}
f = f->next;
}
double d;
if(min == Infinity)d =(double)min;
else d = m->fee +((float)min)/1000;
return d;}
int Route::TwoStationDistantAndShowRoute(RouteData two,int &t){
RouteData *n = point;
int distant = 0;
StationData *p = n->link;
StationData *start;
int tf = 0;
while(p!= NULL)
{
if(p->sn == one){start = p;break;}
p = p->next;
}
p = start;
while(p!=NULL)
{
if(p->sn == two){tf = 1;break;}
p = p->next;
}
one,string *point,string
p = start;
while(p!= NULL)
{
if(p->sn == two){tf = 2;break;}
p = p->former;
}
if(tf == 1)
{
p = start;
distant = distant + p->distance;
t = t + p->time;
p = p->next;
while(p->sn!= two)
{
cout sn
distant = distant + p->distance;
t = t + p->time;
p = p->next;
}
}
else if(tf == 2)
{
p = start;
distant = distant + p->former->distance;
t = t + p->former->time;
p = p->former;
while(p->sn!= two)
{
cout sn
distant = distant + p->former->distance;
t = t + p->former->time;
p = p->former;
}
}
return distant;}
double Route::MinWay(string one,string two,int way){
RouteData * f = head;
RouteData * m = NULL;
int min,min0,mark;
min = Infinity;
while(f!= NULL)
{
min0 = 0;
StationData * p = f->link;
while(p->next!= NULL && p->sn!= one && p->sn!= two)p = p->next;
if(p->next == NULL)min0 = Infinity;
else if(p->sn == one)
{
while(p->sn!= two&&p->next!=NULL)
{
if(way == 1)mark = p->distance;
else if(way == 2)mark = p->time;
min0 = min0 + mark;
p = p->next;
}
if(p->sn!= two)min0 = Infinity;
if(min > min0){min = min0;m = f;}
}
else if(p->sn == two)
{
while(p->sn!= one && p->next!=NULL)
{
if(way == 1)mark = p->distance;
else if(way == 2)mark = p->time;
min0 = min0 + mark;
p = p->next;
}
if(p->sn!= one)min0 = Infinity;
if(min > min0){min = min0;m = f;}
}
f = f->next;
}
double d;
if(min == Infinity)d =(double)min;
else d = 1 +((float)min)/1000;
return d;}
RouteData * Route::MinWayReturnRouteData(string one,string two,int way){
RouteData * f = head;
RouteData * m = NULL;
int min,min0,mark;
min = Infinity;
while(f!= NULL)
{
min0 = 0;
StationData * p = f->link;
while(p->next!= NULL && p->sn!= one && p->sn!= two)p = p->next;
if(p->next == NULL)min0 = Infinity;
else if(p->sn == one)
{
while(p->sn!= two&&p->next!=NULL)
{
if(way == 1)mark = p->distance;
else if(way == 2)mark = p->time;
min0 = min0 + mark;
p = p->next;
}
if(p->sn!= two)min0 = Infinity;
if(min > min0){min = min0;m = f;}
}
else if(p->sn == two)
{
while(p->sn!= one && p->next!=NULL)
{
if(way == 1)mark = p->distance;
else if(way == 2)mark = p->time;
min0 = min0 + mark;
p = p->next;
}
if(p->sn!= one)min0 = Infinity;
if(min > min0){min = min0;m = f;}
}
f = f->next;
}
return m;}
RouteData * Route::FindRoute(string one,string two){
RouteData * f = head;
while(f!= NULL)
{
StationData * p = f->link;
while(p->next!= NULL)
{
if(p->sn == one && p->next->sn == two)return f;
else if(p->sn == two && p->next->sn == one)return f;
p = p->next;
}
f = f->next;
} }
RouteData * Route::Find(string s){
RouteData * n = head;
while(n!= NULL)
{
if(n->rn == s)return n;
n = n->next;
}
return n;}
void Route::Dele(){
Showall();
string s;
RouteData * n;
point3:
cout
cin >> s;
n = Find(s);
if(n == NULL)
{point4:
cout
int i;
cin >> i;
if(i == 1)goto point3;
else if(i == 2);
else goto point4;
}
else
{
ShowOneRoute(n);
point5:
cout
char ch;
cin >> ch;
if(ch == 'Y' || ch == 'y')
{
RouteData * p = head;
while(p->next!= n)p = p->next;
p->next = n->next;
Save();
}
else if(ch == 'N' || ch == 'n');
else goto point5;
} }
void Route::Showall(){
RouteData * n = head;
while(n!= NULL)
{
ShowOneRoute(n);
cout
n = n->next;
} }
void Route::ShowOneRoute(RouteData * p){
if(p->type == 0)cout
else cout
cout rn
StationData * n = p->link;
while(n!= NULL)
{
if(n->next!= NULL)
cout sn time distance
else cout sn;
n = n->next;
}
cout
void Route::Creat(){
RouteData * p = head;
fstream f(“.data.txt”,ios::in);
string;
f >>;
while(!= “end”)
{
num++;
RouteData * n = new RouteData;
StationData * w = n->link;
n->rn =;
f >> n->type >> n->fee;
if(head == NULL){head = n;p = head;}
else
{
p->next = n;
p = n;
}
string s;
f >> s;
while(s!= “#”)
{
StationData * pp = new StationData;
pp->sn = s;
f >> pp->time >> pp->distance;
if(n->link == NULL){n->link = pp;w = n->link;pp->former = NULL;}
else
{
w->next = pp;
pp->former = w;
w = pp;
}
f >> s;
}
f >>;
} }
void Route::Add(){
RouteData *nr = new RouteData;
cout
cout
cin >> nr->rn;
point1:
cout
cin >> nr->type;
if(nr->type == 0)
{
cout
nr->fee = 2;
}
else if(nr->type == 1)
{
cout
cin >> nr->fee;
}
else
{
cout
goto point1;
}
StationData * w = nr->link;
cout
cout
string s;
cin >> s;
while(s!= “#”)
{
StationData * pp = new StationData;
pp->sn = s;
cout
cin >> pp->time;
cout
cin >> pp->distance;
if(nr->link == NULL){nr->link = pp;w = nr->link;}
else
{
w->next = pp;
w = pp;
}
cout
cin >> s;
}
ShowOneRoute(nr);
point2:
cout
char ch;
cin >> ch;
if(ch == 'Y' || ch == 'y')
{
RouteData * k = head;
if(head == NULL){head = nr;k = nr;}
else
{
while(k->next!= NULL)k = k->next;
k->next = nr;
}
num++;
}
else if(ch == 'N' || ch == 'y');
else goto point2;}
void Route::Save(){
fstream f(“.data.txt”,ios::out);
if(!f)return;
RouteData * r = head;
while(r!= NULL)
{
StationData * s = r->link;
f rn type fee
while(s!= NULL)
{
f sn time distance
s = s->next;
}
f
r = r->next;
}
f
f.close();}
/******************************图部***********************************/
cla lineroute { public:
string sn;
RouteData *r;
lineroute *next;
lineroute()
{
分
r = NULL;
next = NULL;
} };
cla Line { public:
string sn;
string rn;
int type;
float fee;
Line *next;
Line()
{
next = NULL;
} };
//边尾节点信息结构体 struct edgeNode {
int no;//尾接点序号
int dtime,dlong;//边权值
RouteData *r;
edgeNode *next;//其下一条邻接边尾节点指针 };
//节点信息结构体 struct vexNode {
string sn;//节点名称
edgeNode *link;//与其相连的边的尾节点链表指针 };
struct Queue {
int no;//队列中节点序号
int cost;//以此为尾节点的边的权值 };
cla Graph { public:
//优先队列
Queue priQue[MAX];
//节点数组
vexNode adjlist[MAX];
//指定源点到节点i的最短路径花费
int lowcost[MAX];
//指定源点到节点i路径中，节点i的前驱节点序号
int parent[MAX];
int vexNumber;
Line *s;
void CreatGraph(Route &R);
void keep_min_heap(int &num,const int k);
void heap_insert(int &num,int no,int cost);
Queue heap_extract_min(int &num);
void print_it(Route &R,int v);
void DijkstraDistance(Route &R,string start,string end);
void DijkstraTime(Route &R,string start,string end);
int FindNumber(string sn);
void CreatLine(int v);
void MinMoney(Route &R,string start,string end,int way);
void MinChange(Route &R,string start,string end,int way);};/*****最大值：Infinity*******/
void Graph::MinMoney(Route &R,string start,string end,int way){
int v0,v1,n,w;
n = vexNumber;
v0 = FindNumber(start);
v1 = FindNumber(end);
double shortest[MAX];
double EDGE[n][n];
int final[MAX]={0};
int path[MAX][MAX]={0};
/*****建立邻接矩阵******/
int i,j;
for(i = 0;i
{
for(j = 0;j
{
if(i == j)
{
EDGE[i][j] = Infinity;
continue;
}
string one = adjlist[i].sn;
string two = adjlist[j].sn;
EDGE[i][j] = R.MinWayMoney(one,two,way);
}
}
/******初始化数组******/
int order = 1;
int step = 1;
int min_i;
double min_shortest;
for(i = 0;i
{
shortest[i] = EDGE[v0][i];
for(j = 0;j
if(EDGE[v0][i]
}
shortest[v0] = 0;
final[v0] = order;
path[v0][v0] = step;
/*****算法部分*****/
for(i = 1;i
{
min_shortest = Infinity;
for(j = 0;j
{
if(!final[j] && shortest[j]
{
min_i = j;
min_shortest = shortest[j];
}
}
if(!path[min_i][min_i])path[min_i][min_i] = ++step;
else step = path[min_i][min_i];
final[min_i] = ++order;
for(j = 0;j
{
if(!final[j] &&(min_shortest + EDGE[min_i][j]
{
shortest[j] = min_shortest + EDGE[min_i][j];
for(int l = 0;l
path[j][j] = path[min_i][min_i] + 1;
}
}
}
/********路线生成*******/
lineroute *linep = NULL,*ttt;
ttt = linep;
int times;
for(times = 1;times
{
for(i = 0;i
{
if(path[v1][i]==times)
{
lineroute *newl = new lineroute;
newl->sn = adjlist[i].sn;
if(ttt == NULL){linep = newl;ttt = linep;}
else {ttt->next = newl;ttt = newl;}
}
}
}
/*****完善路线节点*****/
ttt = linep;
while(ttt->next!= NULL)
{
ttt->r = R.MinWayReturnRouteData(ttt->sn,ttt->next->sn,way);
ttt = ttt->next;
}
/*****显示路线*****/
float cost = 0;int distance = 0;
int t = 0;
ttt = linep;
cost = cost + ttt->r->fee;
cout sn r->rn;
distance = distance R.TwoStationDistantAndShowRoute(ttt->r,ttt->sn,ttt->next->sn,t);
ttt = ttt->next;
while(ttt->next!= NULL)
{
cost = cost + ttt->r->fee;
cout sn
cout sn r->rn;
distance = distance R.TwoStationDistantAndShowRoute(ttt->r,ttt->sn,ttt->next->sn,t);
ttt = ttt->next;
+
+
}
cout sn
cout
cout
void Graph::MinChange(Route &R,string start,string end,int way){
int v0,v1,n,w;
n = vexNumber;
v0 = FindNumber(start);
v1 = FindNumber(end);
double shortest[MAX];
double EDGE[n][n];
int final[MAX]={0};
int path[MAX][MAX]={0};
/*****建立邻接矩阵******/
int i,j;
for(i = 0;i
{
for(j = 0;j
{
if(i == j)
{
EDGE[i][j] = Infinity;
continue;
}
string one = adjlist[i].sn;
string two = adjlist[j].sn;
EDGE[i][j] = R.MinWay(one,two,way);
}
}
/******初始化数组******/
int order = 1;
int step = 1;
int min_i;
double min_shortest;
for(i = 0;i
{
shortest[i] = EDGE[v0][i];
for(j = 0;j
if(EDGE[v0][i]
}
shortest[v0] = 0;
final[v0] = order;
path[v0][v0] = step;
/*****算法部分*****/
for(i = 1;i
{
min_shortest = Infinity;
for(j = 0;j
{
if(!final[j] && shortest[j]
{
min_i = j;
min_shortest = shortest[j];
}
}
if(!path[min_i][min_i])path[min_i][min_i] = ++step;
else step = path[min_i][min_i];
final[min_i] = ++order;
for(j = 0;j
{
if(!final[j] &&(min_shortest + EDGE[min_i][j]
{
shortest[j] = min_shortest + EDGE[min_i][j];
for(int l = 0;l
path[j][j] = path[min_i][min_i] + 1;
}
}
}
/********路线生成*******/
lineroute *linep = NULL,*ttt;
ttt = linep;
int times;
for(times = 1;times
{
for(i = 0;i
{
if(path[v1][i]==times)
{
lineroute *newl = new lineroute;
newl->sn = adjlist[i].sn;
if(ttt == NULL){linep = newl;ttt = linep;}
else {ttt->next = newl;ttt = newl;}
}
}
}
/*****完善路线节点*****/
ttt = linep;
while(ttt->next!= NULL)
{
ttt->r = R.MinWayReturnRouteData(ttt->sn,ttt->next->sn,way);
ttt = ttt->next;
}
/*****显示路线*****/
float cost = 0;int distance = 0;
int t = 0;
ttt = linep;
cost = cost + ttt->r->fee;
cout sn r->rn;
distance = distance + R.TwoStationDistantAndShowRoute(ttt->r,ttt->sn,ttt->next->sn,t);
ttt = ttt->next;
while(ttt->next!= NULL)
{
cost = cost + ttt->r->fee;
cout sn
cout sn r->rn;
distance = distance + R.TwoStationDistantAndShowRoute(ttt->r,ttt->sn,ttt->next->sn,t);
ttt = ttt->next;
}
cout sn
cout
cout
void Graph::CreatGraph(Route &R){
//建立节点信息
RouteData *rp = R.head;
int n = 0;
while(rp!= NULL)
{
StationData *sp = rp->link;
while(sp!= NULL)
{
int i,tf = 0;
for(i = 0;i
{
if(adjlist[i].sn == sp->sn)
{
tf = 1;
sp->number = i;
break;
}
}
if(tf == 0)
{
adjlist[n].sn = sp->sn;
adjlist[n].link = NULL;
lowcost[n] = Infinity;
parent[n] = n;
sp->number = n;
n++;
}
sp = sp->next;
}
rp = rp->next;
}
vexNumber = n;
//建立边
edgeNode *ep;
rp = R.head;
while(rp!= NULL)
{
StationData *sp = rp->link;
while(sp!= NULL)
{
int v1,v2;
v1 = sp->number;
if(sp->former!= NULL)
{
v2 = sp->former->number;
ep = new edgeNode;
ep->no = v2;
ep->dlong = sp->former->distance;
ep->dtime = sp->former->time;
ep->r = rp;
ep->next = adjlist[v1].link;
adjlist[v1].link = ep;
}
if(sp->next!= NULL)
{
v2 = sp->next->number;
ep = new edgeNode;
ep->no = v2;
ep->dlong = sp->distance;
ep->dtime = sp->time;
ep->r = rp;
ep->next = adjlist[v1].link;
adjlist[v1].link = ep;
}
sp = sp->next;
}
rp = rp->next;
} }
void Graph::keep_min_heap(int &num,const int k){
int l = 2*k;
int r = 2*k + 1;
int smallest = k;
if(l
if(r
if(smallest!= k)
{
Queue temp = priQue[smallest];
priQue[smallest] = priQue[k];
priQue[k] = temp;
keep_min_heap(num,smallest);
} }
void Graph::heap_insert(int &num,int no,int cost){
num +=1;
priQue[num].no = no;
priQue[num].cost = cost;
int i = num;
while(i>1&&priQue[i/2].cost>priQue[i].cost)
{
Queue temp = priQue[i];
priQue[i] = priQue[i/2];
priQue[i/2] = temp;
i = i/2;
} }
Queue Graph::heap_extract_min(int &num){
if(num
Queue min = priQue[1];
priQue[1] = priQue[num];
num-=1;
keep_min_heap(num,1);
return min;}
void Graph::CreatLine(int v){
if(parent[v] == v)
{
Line *p = new Line;
p->sn = adjlist[v].sn;
p->next = s;
s = p;
}
else
{
CreatLine(parent[v]);
Line *p = new Line;
p->sn = adjlist[v].sn;
p->next = s;
s = p;
} }
void Graph::print_it(Route &R,int v){
s = NULL;
CreatLine(v);
Line *p = s;
Line *n = NULL;
while(p!= NULL)
{
Line *ppp = new Line;
*ppp = *p;
ppp->next = n;
n = ppp;
p = p->next;
}
p = n;
while(p->next!= NULL)
{
RouteData * routedata = R.FindRoute(p->sn,p->next->sn);
p->fee = routedata->fee;
p->rn = routedata->rn;
p->type = routedata->type;
p=p->next;
}
int change = 0;
float money = 0;
p = n;
cout sn rn;
money = money + p->fee;
while(p->next->next!= NULL)
{
if(p->rn == p->next->rn)
{
p = p->next;
cout sn
}
else if(p->rn!= p->next->rn)
{
int t1 = p->type;
int t2 = p->next->type;
p = p->next;
cout sn sn rn
money = money + p->fee;
change++;
}
}
p = p->next;
cout sn
cout
int i,number;
for(i = 0;i
{
if(adjlist[i].sn == sn)
{
number = i;
break;
}
}
return number;}
void Graph::DijkstraDistance(Route &R,string start,string end){
int v0,v1;
v0 = FindNumber(start);
v1 = FindNumber(end);
int v =v0;
lowcost[v0] = 0;
Queue queue;
int i,num = 0;
for(i=0;i
{
edgeNode *p = adjlist[v0].link;
while(p!= NULL)
{
if(lowcost[v0] + p->dlong no])
{
lowcost[p->no] = lowcost[v0] + p->dlong;
parent[p->no] = v0;
heap_insert(num,p->no,lowcost[p->no]);
}
p = p->next;
}
queue = heap_extract_min(num);
v0 = queue.no;
}
//mincost = 0;
cout
print_it(R,v1);
cout
void Graph::DijkstraTime(Route &R,string start,string end){
int v0,v1;
v0 = FindNumber(start);
v1 = FindNumber(end);
int v =v0;
lowcost[v0] = 0;
Queue queue;
int i,num = 0;
for(i=0;i
{
edgeNode *p = adjlist[v0].link;
while(p!= NULL)
{
if(lowcost[v0] + p->dtime no])
{
lowcost[p->no] = lowcost[v0] + p->dtime;
parent[p->no] = v0;
heap_insert(num,p->no,lowcost[p->no]);
}
p = p->next;
}
queue = heap_extract_min(num);
v0 = queue.no;
}
//mincost = 0;
cout
print_it(R,v1);
cout
/******************************主函数***********************************/
void Manager(Route &R){
string c1;
while(1)
{
system(“cls”);
cout
cout
管理员n“;
cout
cout
请选择选项对线路进行操作
****n”;
cout
1.显示全部线路
****n“;
cout
2.建立新线路
****n”;
cout
3.删除线路
****n“;
cout
4.查询一条线路
****n”;
cout
5.查询站点
****n“;
cout
6.保存目前线路
****n”;
cout
7.返回上一级
****n“;
cout
cout
选项：”;
cin >> c1;
system(“cls”);
if(c1 == “1”)
{
R.Showall();
system(“pause”);
system(“cls”);
}
else if(c1 == “2”)
{
R.Add();
system(“pause”);
}
else if(c1 == “3”)
{
R.Dele();
system(“pause”);
}
else if(c1 == “4”)
{
R.CheckRoute();
}
else if(c1 == “5”)
{
R.CheckStation();
}
else if(c1 == “6”)
{
R.Save();
cout
system(“pause”);
}
else if(c1 == “7”)
{
break;
}
else
{
cout
system(“pause”);
}
}
system(“cls”);}
void User(Route &R){
string c1,c2;
while(1)
{
system(“cls”);
cout
cout
欢迎使用北京公交路线查询系统n“;
cout
cout
请选择您需要的服务
****n”;
cout
1.查询一条线路
****n“;
cout
2.查询站点
****n”;
cout
3.搜索路线
****n“;
cout
4.返回上一级
****n”;
cout
cout
选项：“;
cin >> c1;
system(”cls“);
if(c1 == ”1“)
{
R.CheckRoute();
}
else if(c1 == ”2“)
{
R.CheckStation();
}
else if(c1 == ”3“)
{
cout
Graph G;
G.CreatGraph(R);
string start,end;
point4:
cout
cin >> start;
cout
cin >> end;
if(start == end)
{
cout
system(”pause“);
goto point4;
}
cout
cout
cout
请选择路线查询方式
****n”;
cout
1.最短距离
****n“;
cout
2.最短时间
****n”;
cout
3.最少换乘
****n“;
cout
4.最少花费
****n”;
cout
cout
选项：“;
cin >> c2;
if(c2 == ”1“)
{
cout
G.DijkstraDistance(R,start,end);
cout
system(”pause“);
system(”cls“);
}
else if(c2 == ”2“)
{
cout
G.DijkstraTime(R,start,end);
cout
system(”pause“);
system(”cls“);
}
else if(c2 == ”3“)
{
cout
cout
请选择最少换乘模式
****n”;
cout
1.最短距离
****n“;
cout
2.最短时间
****n”;
cout
cout
选项：“;
int whatever;
cin >> whatever;
cout
G.MinChange(R,start,end,whatever);
cout
system(”pause“);
system(”cls“);
}
else if(c2 == ”4“)
{
cout
cout
请选择最少花费模式
****n”;
cout
1.最短距离
****n“;
cout
2.最短时间
****n”;
cout
cout
选项：“;
int whatever;
cin >> whatever;
cout
G.MinMoney(R,start,end,whatever);
cout
system(”pause“);
system(”cls“);
}
}
else if(c1 == ”4“)break;
else
{
cout
system(”pause“);
}
}
system(”cls“);}
int main(){
string pawd;
string c;
Route R;
int i;
R.Creat();
while(1)
{
system(”cls“);
cout
cout
欢迎使用北京公交路线查询系统n”;
cout
cout
请选择您的身份
****n“;
cout
1.管理员
****n”;
cout
2.普通用户
****n“;
cout
cout
选项：”;
cin >> c;
if(c == “1”)
{
cout
cout
pawd = paword();
if(pawd!= PASSWORD)
{
cout
system(“pause”);
}
else
{
system(“cls”);
Manager(R);
}
}
else if(c == “2”)
{
system(“cls”);
User(R);
}
else
{
cout
system(“pause”);
}
}
return 0;}
string paword()
//密码 { string psw;//用于存密码的字符串；
int length;
char temp_c;
while(1)
{
temp_c=getch();//输入一个字符
if(temp_c!=char(13))//判断该字符是否为回车，如果是则退出while
{
switch(temp_c)
{
case 8:
if(length!=0)
{
cout
psw=psw.substr(0,length-1);
length--;
}
else;
break;
default:
cout
psw+=temp_c;//连成字符串；
length++;
break;
}
}
else break;
}
return psw;}
