数据结构和算法课程设计报告-北京地铁查询系统C++版Word下载.docx
《数据结构和算法课程设计报告-北京地铁查询系统C++版Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构和算法课程设计报告-北京地铁查询系统C++版Word下载.docx（18页珍藏版）》请在冰点文库上搜索。
第1条地铁线路名称（如:
1号线），第1站（如：
四惠东站），图上坐标（如：
X1，Y1）2，运行时间（如：
3），第2站（如：
四惠站），图上坐标（如：
X2，Y2），运行时间（如：
4），…，第23站（如：
苹果园站），图上坐标（如：
Xn，Yn）
第i行：
第i条地铁线路名称,第1站，运行时间，第2站，运行时间，…，第n站
第n行：
第n条地铁线路名称,第1站，运行时间，第2站，运行时间，…，第n站
1*表示可能有若干次换乘，也可能没有换乘。
每次换乘的信息为（换乘站，站名，换乘几号线）
2坐标根据采用的地铁图中的相对位置来给出（由同学自己根据所选地铁图大小进行设置）
第17页
共18页
第n+1行：
换乘站数目m（m>
换乘编号1#：
换乘站名称1（如：
四惠东站），（下车线路（如：
1号线），换乘线路（如：
八通线），换乘时间3（如：
5））+4
换乘编号i#：
换乘站名称i，下车线路，换乘线路，换乘时间
换乘编号m#：
换乘站名称m，下车线路，换乘线路，换乘时间
用户查询信息通过图形界面的对话框提供：
包括起始站，目的站的输入框。
1.2.2输出画面的要求
用图形方式显示北京市地铁图，并根据客户的输入提供建议（文字展示）并以加粗的两端带红点的绿色线路形式绘制在地铁图上。
1.2.3题目约定
l题目中的时间单位为分钟；
l地铁一般一站运行时间3分钟，个别长的站为5分钟。
l最短距离以所用时间表示
1.2.4题目实现要求
l应用最短路径算法，求任意两站间的“最快”，“最方便”的出行方案。
特别需要注意换乘站的处理。
5.0代码清单
#include<
iostream>
#include<
fstream>
string>
vector>
usingnamespacestd;
typedefstructArcNode
{
intadjvex;
stringline;
3换乘时间以分钟为单位
4相同的换乘站可以换乘不同的地铁线路，比如西直门换乘站。
inttime;
structArcNode*nextarc;
}ArcNode;
typedefstructVNode
stringstation;
intcost;
stringpath;
stringfrom;
ArcNode*firstarc;
}VNode;
typedefstructTransfer
stringfrom;
stringto;
inttime;
structTransfer*nextarc;
}Transfer;
typedefstructTransferStation
Transfer*firstarc;
}TransferStation;
voidsplit（conststring&
conststring&
vector<
&
）;
intfindIndex（vector<
VNode>
string）;
intfindIndex（vector<
int>
int）;
intfindTransferTime（string,string,string）;
voidinitialize（）;
stringfindOptimalPath（string,string,int&
vector<
AdjList;
vector<
TransferStation>
TransferInfo;
voidmain（）
initialize（）;
stringstart,des;
cout<
<
"
欢迎使用\n"
;
输入起点站:
cin>
>
start;
cout<
输入终点站:
cin>
des;
strings=findOptimalPath（start,des,cost）;
线路为:
s.c_str（）<
endl;
耗时"
cost<
分钟\n"
intx;
x;
}
voidinitialize（）
ifstreamin（"
BaseInfo.txt"
//读入文件strings;
intlinesNum;
stringline;
v;
VNode*vn;
ArcNode*an;
Transfer*t;
TransferStation*ts;
inti,index,startIndex;
intindex1,index2;
getline（in,s）;
linesNum=atoi（s.c_str（））;
getline（in,s）;
split（s,"
"
v）;
line=v[0];
vn=newVNode（）;
vn->
station=v[1];
cost=10000;
path="
vn->
from="
firstarc=NULL;
AdjList.push_back（*vn）;
for（i=2;
i<
v.size（）-1;
i=i+2）
time=atoi（v[i].c_str（））;
index=AdjList.size（）;
an=newArcNode（）;
an->
line=line;
an->
adjvex=index;
time=time;
nextarc=vn->
firstarc;
//前插法
AdjList[i/2-1].firstarc=an;
adjvex=index-1;
nextarc=NULL;
station=v[i+1];
firstarc=an;
AdjList.push_back（*vn）;
if（i==v.size（）-1）
adjvex=0;
AdjList.back（）.firstarc=an;
nextarc=AdjList[0].firstarc;
AdjList[0].firstarc=an;
while（linesNum-->
1）
v.clear（）;
split（s,"
index1=findIndex（AdjList,v[1]）;
if（index1==-1）
index1=AdjList.size（）-1;
startIndex=index1;
index2=findIndex（AdjList,v[i+1]）;
if（index2==-1）
index2=AdjList.size（）-1;
adjvex=index1;
nextarc=AdjList[index2].firstarc;
AdjList[index2].firstarc=an;
an=newArcNode（）;
adjvex=index2;
nextarc=AdjList[index1].firstarc;
AdjList[index1].firstarc=an;
index1=index2;
adjvex=startIndex;
nextarc=AdjList[startIndex].firstarc;
AdjList[startIndex].firstarc=an;
while（linesNum-->
ts=newTransferStation（）;
ts->
ts->
for（i=2;
v.size（）;
i=i+3）
t=newTransfer（）;
t->
from=v[i];
t->
to=v[i+1];
time=atoi（v[i+2].c_str（））;
nextarc=ts->
firstarc=t;
TransferInfo.push_back（*ts）;
src,conststring&
separator,vector<
dest）
stringstr=src;
stringsubstring;
string:
:
size_typestart=0,index;
do
index=str.find_first_of（separator,start）;
if（index!
=string:
npos）
substring=str.substr（start,index-start）;
dest.push_back（substring）;
start=str.find_first_not_of（separator,index）;
if（start==string:
npos）return;
}while（index!
npos）;
substring=str.substr（start）;
v,stringstation）
inti=v.size（）-1;
while（i>
=0&
strcmp（v[i].station.c_str（）,station.c_str（））!
=0）
i--;
returni;
v,intindex）
v[i]!
=index）
intfindTransferTime（stringstation,stringfrom,stringto）
inttime=5;
for（inti=0;
TransferInfo.size（）;
i++）
if（strcmp（TransferInfo[i].station.c_str（）,station.c_str（））==0）
Transfer*t=TransferInfo[i].firstarc;
while（t）
if（t->
from==from&
to==to）
time=t->
time;
break;
t=t->
nextarc;
break;
returntime;
stringfindOptimalPath（stringsource,stringdestination,int&
cost）
//Dijkstra算法
intsourceIndex,destinationIndex;
S;
intminStationIndex=-1;
intminTime;
intforeIndex;
stringfrom,line;
ArcNode*an,*an0;
inttime,time0=10000;
stringpath0="
inti;
sourceIndex=findIndex（AdjList,source）;
destinationIndex=findIndex（AdjList,destination）;
if（sourceIndex==-1||destinationIndex==-1）
return"
ERROR"
AdjList[sourceIndex].cost=0;
AdjList[sourceIndex].path=source;
S.push_back（sourceIndex）;
while（minStationIndex!
=destinationIndex）
minTime=10000;
for（i=0;
S.size（）;
an=AdjList[S[i]].firstarc;
while（an）
if（AdjList[an->
adjvex].cost==10000）
time0=10000;
if（S[i]==sourceIndex）
if（an->
time<
minTime）
line=an->
line;
minTime=an->
minStationIndex=an->
adjvex;
foreIndex=S[i];
from=line;
AdjList[sourceIndex].from=line;
path0="
else
if（AdjList[S[i]].from==an->
line）
time=AdjList[S[i]].cost+an->
if（time<
minTime=time;
path0="
time=AdjList[S[i]].cost+findTransferTime（AdjList[S[i]].station,AdjList[S[i]].from,an->
line）+an-
an0=AdjList[S[i]].firstarc;
while（an0）
adjvex）
if（an0->
line==an->
line&
an0->
adjvex!
=an-
an0=an0->
10000）
if（an0!
=NULL&
AdjList[an0->
adjvex].cost!
=
time0=AdjList[an0->
adjvex].cost+an0->
time+
if（AdjList[an0->
adjvex].from!
=an->
time0+=findTransferTime（AdjList[an0-
adjvex].station,AdjList[an0->
adjvex].from,an->
line）;
if（time>
time0）
time=time0;
if（time<
if（time==time0）
adjvex].from==line）
path0=AdjList[an0->
adjvex].path+"
+line+"
+AdjList[S[i]].station+"
+line+"
+AdjList[minStationIndex].station;
an=an->
S.push_back（minStationIndex）;
AdjList[minStationIndex].cost=minTime;
AdjList[minStationIndex].from=from;
if（path0!
="
）
AdjList[minStationIndex].path=path0;
AdjList[minStationIndex].path=AdjList[foreIndex].path+"
AdjList[destinationIndex].path+="
+line;
cost=AdjList[destinationIndex].cost;
returnAdjList[destinationIndex].path;
6.0课程感想
附页：
代码所需txt
名称：
BaseInfo.txt
内容：
以下内容直接复制粘贴，一个也别删！
包括数字
9
1号线,四惠东,3,四惠,3,大望路,3,国贸,3,永安里,3,建国门,3,东单,3,王府井,3,天安门
东,3,天安门西,3,西单,3,复兴门,3,南礼士路,3,木樨地,3,军事博物馆,3,公主坟,3,万寿
路,3,五棵松,3,玉泉路,3,八宝山,3,八角游乐园,3,古城,3,苹果园
2号线,西直门,3,车公庄,3,阜成门,3,复兴门,3,长椿街,3,宣武门,3,和平门,3,前门,3,崇
文门,3,北京站,3,建国门,3,朝阳门,3,东四十条,3,东直门,3,雍和宫,3,安定门,3,鼓楼大街,3,积水潭,3
4号线,天宫院,3,生物医药基地,3,义和庄,3,黄村火
升级会员 