2014年北京工业大学计算机学院数据结构
与算法课设
嗨，你好。
当年为了这个该死的课设我也是和你一样急，在CSDN上各种找……但是没有。
最后还好……弄出来了。
C++版本
题目什么的在下面，附件什么的我都在这个
DOC中给你。
祝你能过。
2014.11.01
数据结构与算法课程设计报告北京地铁查询系统
学号： 12 07 01
姓名：哈哈
指导教师：呵呵
2014年10月
1.1设计的描述
当今的北京，地铁已经成为绝大多数人出行的首选。
截至2014年1月，北京地铁共有17条运营线路。
组成覆盖北京市11个市辖区，拥有231座运营车站、总长467千米运营线路的轨道交通系统，工作日均客流约1000万人次，峰值日客运量1155.92万人次。
随着地铁线路的增加，地铁规模越来越大，人们愈发的感觉到地铁的便利。
特别地从出发地到目的地的乘车方案的选择也越来越多。
因此，需要提供一个软件能够为人们提供出发到目的地之间“最快”或“最方便”的地铁出行方案。
其中，“最快”指用时最少，“最方便”则指在换乘车少的基础上用时最少。
1.2设计的需求
请设计一个地铁出行帮助系统，为北京市居民提供地铁出行方案（仅限地铁出行）。
提供出发地和目的地地铁站的输入窗口，提供出行建议，并图形显示出线路。
出行建议信息：
•出发站，站名，几号线
•第2站，站名，几号线
•…
•第i站，站名，几号线
•…
•[换乘站，站名，换乘几号线]* 1，
•第m站，站名，几号线
•目的站，站名，几号线
•总用时，X分钟，换乘次数：N
1.2.1输入数据要求
地铁线路基础信息数据通过一个名为“BaseInfo.txt”的文本文件读入。
该数据文件格式如下：
•第0行：当前系统中地铁线路的条数n（n > 0）
•第1行：第1条地铁线路名称（如:1号线），第1站（如：四惠东站），图上坐标（如：X1，Y1）2，运行时间（如：3），第2站（如：四惠站），图上坐标
（如：X2，Y2），运行时间（如：4），…，第23站（如：苹果园站），图上
坐标（如：X n，Y n）
•…
•第i行：第i条地铁线路名称, 第1站，运行时间，第2站，运行时间，…，第n站
•…
•第n行：第n条地铁线路名称, 第1站，运行时间，第2站，运行时间，…，第n站
•第n+1行：换乘站数目m（m > 0）
•换乘编号1#：换乘站名称1（如：四惠东站），（下车线路（如：1号线），
1*表示可能有若干次换乘，也可能没有换乘。
每次换乘的信息为（换乘站，站名，换乘几号线）2坐标根据采用的地铁图中的相对位置来给出（由同学自己根据所选地铁图大小进行设置）
换乘线路（如：八通线），换乘时间3（如：5））+4
•…
•换乘编号i#：换乘站名称i，下车线路，换乘线路，换乘时间
•…
•换乘编号m#：换乘站名称m，下车线路，换乘线路，换乘时间
用户查询信息通过图形界面的对话框提供：
包括起始站，目的站的输入框。
1.2.2输出画面的要求
用图形方式显示北京市地铁图，并根据客户的输入提供建议（文字展示）并以加粗的两端带红点的绿色线路形式绘制在地铁图上。
1.2.3题目约定
●题目中的时间单位为分钟；
●地铁一般一站运行时间3分钟，个别长的站为5分钟。
●最短距离以所用时间表示
1.2.4题目实现要求
●应用最短路径算法，求任意两站间的“最快”，“最方便”的出行方案。
特别需要
注意换乘站的处理。
5.0代码清单
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
using namespace std;
typedef struct ArcNode
{
int adjvex;
string line;
int time;
struct ArcNode *nextarc;
}ArcNode;
3换乘时间以分钟为单位
4相同的换乘站可以换乘不同的地铁线路，比如西直门换乘站。
typedef struct VNode
{
string station;
int cost;
string path;
string from;
ArcNode *firstarc;
}VNode;
typedef struct Transfer
{
string from;
string to;
int time;
struct Transfer *nextarc;
}Transfer;
typedef struct TransferStation
{
string station;
Transfer *firstarc;
}TransferStation;
void split(const string&, const string&, vector<string>&); int findIndex(vector<VNode>, string);
int findIndex(vector<int>, int);
int findTransferTime(string, string, string);
void initialize();
string findOptimalPath(string, string, int&);
vector<VNode> AdjList;
vector<TransferStation> TransferInfo;
void main()
{
initialize();
int cost;
string start,des;
cout<<"欢迎使用\n";
cout<<"输入起点站:";
cin>>start;
cout<<"输入终点站:";
cin>>des;
string s = findOptimalPath(start, des, cost);
cout<<"线路为:";
cout<<s.c_str()<<endl;
cout<<"耗时"<<cost<<"分钟\n"<<endl;
int x;
cin>>x;
}
void initialize()
{
ifstream in("BaseInfo.txt"); //读入文件
string s;
int linesNum;
string line;
vector<string> v;
int time;
VNode *vn;
ArcNode *an;
Transfer *t;
TransferStation *ts;
int i, index, startIndex;
int index1, index2;
getline(in, s);
linesNum = atoi(s.c_str());
getline(in, s);
split(s, ",", v);
line = v[0];
vn = new VNode();
vn->station = v[1];
vn->cost = 10000;
vn->path = "";
vn->from = "";
vn->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 = new ArcNode();
an->line = line;
an->adjvex = index;
an->time = time;
an->nextarc = vn->firstarc; //前插法AdjList[i/2-1].firstarc = an;
an = new ArcNode();
an->line = line;
an->adjvex = index - 1;
an->time = time;
an->nextarc = NULL;
vn = new VNode();
vn->station = v[i+1];
vn->cost = 10000;
vn->path = "";
vn->from = "";
vn->firstarc = an;
AdjList.push_back(*vn);
}
if(i == v.size()-1)
{
time = atoi(v[i].c_str());
an = new ArcNode();
an->line = line;
an->adjvex = 0;
an->time = time;
an->nextarc = vn->firstarc;
AdjList.back().firstarc = an;
an = new ArcNode();
an->line = line;
an->adjvex = index;
an->time = time;
an->nextarc = AdjList[0].firstarc;
AdjList[0].firstarc = an;
}
while(linesNum-- > 1)
{
getline(in, s);
v.clear();
split(s, ",", v);
line = v[0];
index1 = findIndex(AdjList, v[1]);
if(index1 == -1)
{
vn = new VNode();
vn->station = v[1];
vn->cost = 10000;
vn->from = "";
vn->path = "";
vn->firstarc = NULL;
AdjList.push_back(*vn);
index1 = AdjList.size() - 1;
}
startIndex = index1;
for(i=2; i<v.size()-1; i=i+2)
{
time = atoi(v[i].c_str());
index2 = findIndex(AdjList, v[i+1]);
if(index2 == -1)
{
vn = new VNode();
vn->station = v[i+1];
vn->cost = 10000;
vn->from = "";
vn->path = "";
vn->firstarc = NULL;
AdjList.push_back(*vn);
index2 = AdjList.size() - 1;
}
an = new ArcNode();
an->line = line;
an->adjvex = index1;
an->time = time;
an->nextarc =AdjList[index2].firstarc; //前插法AdjList[index2].firstarc = an;
an = new ArcNode();
an->line = line;
an->adjvex = index2;
an->time = time;
an->nextarc = AdjList[index1].firstarc;
AdjList[index1].firstarc = an;
index1 = index2;
}
if(i == v.size()-1)
{
time = atoi(v[i].c_str());
an = new ArcNode();
an->line = line;
an->adjvex = startIndex;
an->time = time;
an->nextarc = vn->firstarc;
AdjList[index1].firstarc = an;
an = new ArcNode();
an->line = line;
an->adjvex = index1;
an->time = time;
an->nextarc = AdjList[startIndex].firstarc;
AdjList[startIndex].firstarc = an;
}
}
getline(in, s);
linesNum = atoi(s.c_str());
while (linesNum-- > 0)
{
getline(in, s);
v.clear();
split(s, ",", v);
ts = new TransferStation();
ts->station = v[1];
ts->firstarc = NULL;
for(i=2; i<v.size(); i=i+3)
{
t = new Transfer();
t->from = v[i];
t->to = v[i+1];
t->time = atoi(v[i+2].c_str());
t->nextarc = ts->firstarc;
ts->firstarc = t;
}
TransferInfo.push_back(*ts);
}
}
void split(const string& src, const string& separator, vector<string>& dest) {
string str = src;
string substring;
string::size_type start = 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 != string::npos);
substring = str.substr(start);
dest.push_back(substring);
}
int findIndex(vector<VNode> v, string station)
{
int i = v.size() - 1;
while(i >= 0 && strcmp(v[i].station.c_str(), station.c_str()) != 0)
{
i--;
}
return i;
}
int findIndex(vector<int> v, int index)
{
int i = v.size() - 1;
while(i >= 0 && v[i] != index)
{
i--;
}
return i;
}
int findTransferTime(string station, string from, string to)
{
int time = 5;
for(int i=0; i<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 && t->to == to)
{
time = t->time;
break;
}
t = t->nextarc;
}
break;
}
}
return time;
}
string findOptimalPath(string source, string destination, int& cost) //Dijkstra算法
{
int sourceIndex, destinationIndex;
vector<int> S;
int minStationIndex = -1;
int minTime;
int foreIndex;
string from, line;
ArcNode *an, *an0;
int time, time0=10000;
string path0 = "";
int i;
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; i<S.size(); i++)
{
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->time;
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->time;
if(time < minTime)
{
line = an->line;
minTime = time;
minStationIndex = an->adjvex;
foreIndex = S[i];
from = line;
path0 = "";
}
}
else
{
time = AdjList[S[i]].cost +
findTransferTime(AdjList[S[i]].station, AdjList[S[i]].from, an->line) + an->time;
an0 = AdjList[S[i]].firstarc;
while(an0)
{
if(an0->line == an->line && an0->adjvex !=
an->adjvex)
{
break;
}
an0 = an0->nextarc;
}
if(an0 != NULL && AdjList[an0->adjvex].cost != 10000)
{
time0 = AdjList[an0->adjvex].cost + an0->time + an->time;
if(AdjList[an0->adjvex].from != an->line)
{
time0 +=
findTransferTime(AdjList[an0->adjvex].station, AdjList[an0->adjvex].from,
an->line);
}
if(time > time0)
{
time = time0;
}
}
if(time < minTime)
{
line = an->line;
minTime = time;
minStationIndex = an->adjvex;
foreIndex = S[i];
from = line;
if(time == time0)
{
if(AdjList[an0->adjvex].from == line)
{
path0 = AdjList[an0->adjvex].path + "," + line + "," + AdjList[S[i]].station + "," + line + "," +
AdjList[minStationIndex].station;
}
else
{
path0 = AdjList[an0->adjvex].path + "," + line + "," + AdjList[S[i]].station + "," + line + "," +
AdjList[minStationIndex].station;
}
}
}
}
}
}
an = an->nextarc;
}
}
S.push_back(minStationIndex);
AdjList[minStationIndex].cost = minTime;
AdjList[minStationIndex].from = from;
if(path0 != "")
{
AdjList[minStationIndex].path = path0;
}
else
{
AdjList[minStationIndex].path = AdjList[foreIndex].path + "," + line + "," + AdjList[minStationIndex].station;
}
}
AdjList[destinationIndex].path += "," + line;
cost = AdjList[destinationIndex].cost;
return AdjList[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,黄村火车站,3,黄村西大街,3,清源路,3,枣园,3,高米店南,3,高米店北,3,西红门,3,新宫,3,公益西桥,3,角门西,3,马家堡,3,北京南站,3,陶然亭,3,菜市口,3,宣武门,3,西单,3,灵境胡同,3,西四,3,平安里,3,新街口,3,西直门,3,动物园,3,国家图书馆,3,魏公村,3,人民大学,3,海淀黄庄,3,中关村,3,北京大学东
门,3,圆明园,3,西苑,3,北宫门,3,安河桥北
5号线,天通苑北,3,天通苑,3,天通苑南,3,立水桥,3,立水桥南,3,北苑路北,3,大屯路东,3,惠新西街北口,3,惠新西街南口,3,和平西桥,3,和平里北街,3,雍和宫,3,北新桥,3,张自忠路,3,东四,3,灯市口,3,东单,3,崇文门,3,磁器口,3,天坛东门,3,蒲黄榆,3,刘家窑,3,宋家
庄
6号线,海淀五路居,3,慈寿寺,3,花园桥,3,白石桥南,3,车公庄西,3,车公庄,3,平安里,3,北海北,3,南锣鼓巷,3,东四,3,朝阳门,3,东大桥,3,呼家楼,3,金台路,3,十里堡,3,青年
路,3,褡裢坡,3,黄渠,3,常营,3,草房
8号线,朱辛庄,3,育知路,3,平西府,3,回龙观东大街,3,霍营,3,育新,3,西小口,3,永泰庄,3,林萃桥,3,森林公园南门,3,奥林匹克公园,3,奥体中心,3,北土城,3,安华桥,3,鼓楼大
街,3,什刹海,3,南锣鼓巷
9号线,郭公庄,3,丰台科技园,3,科怡路,3,丰台南路,3,丰台东大街,3,七里庄,3,六里桥,3,六里桥东,3,北京西站,3,军事博物馆,3,白堆子,3,白石桥南,3,国家图书馆
10号线,巴沟,3,苏州街,3,海淀黄庄,3,知春里,3,知春路,3,西土城,3,牡丹园,3,健德门,3,北土城,3,安贞门,3,惠新西街南口,3,芍药居,3,太阳宫,3,三元桥,3,亮马桥,3,农业展览馆,3,团结湖,3,呼家楼,3,金台夕照,3,国贸,3,双井,3,劲松,3,潘家园,3,十里河,3,分钟寺,3,成寿寺,3,宋家庄,3,石榴庄,3,大红门,3,角门东,3,角门西,3,草桥,3,纪家庙,3,首经贸,3,丰台站,3,泥洼,3,西局,3,六里桥,3,莲花桥,3,公主坟,3,西钓鱼台,3,慈寿寺,3,车道
沟,3,长春桥,3,火器营,3
13号线,西直门,3,大钟寺,3,知春路,3,五道口,3,上地,3,西二旗,3,龙泽,3,回龙观,3,霍营,3,立水桥,3,北苑,3,望京西,3,芍药居,3,光熙门,3,柳芳,3,东直门
32
1#,公主坟,1号线,10号线,5,10号线,1号线,5
2#,军事博物馆,1号线,9号线,5,9号线,1号线,5
3#,复兴门,1号线,2号线,5,2号线,1号线,5
4#,西单,1号线,4号线,5,4号线,1号线,5
5#,东单,1号线,5号线,5,5号线,1号线,5
6#,建国门,1号线,2号线,5,2号线,1号线,5
7#,国贸,1号线,10号线,5,10号线,1号线,5
8#,宣武门,2号线,4号线,5,4号线,2号线,5
9#,崇文门,2号线,5号线,5,5号线,2号线,5
10#,朝阳门,2号线,6号线,5,6号线,2号线,5
11#,东直门,2号线,13号线,5,13号线,2号线,5
12#,雍和宫,2号线,5号线,5,5号线,2号线,5
13#,鼓楼大街,2号线,8号线,5,8号线,5号线,5
14#,西直门,2号线,4号线,5,4号线,2号线,5,2号线,13号线,5,13号线,2号线,5,4号
线,13号线,5,13号线,4号线,5
15#,车公庄,2号线,6号线,5,6号线,2号线,5
16#,海淀黄庄,4号线,10号线,5,10号线,4号线,5
17#,国家图书馆,4号线,9号线,5,9号线,4号线,5
18#,平安里,4号线,6号线,5,6号线,4号线,5
19#,角门西,4号线,10号线,5,10号线,4号线,5
20#,立水桥,5号线,13号线,5,13号线,5号线,5
21#,惠新西街南口,5号线,10号线,5,10号线,5号线,5
22#,东四,5号线,6号线,5,6号线,5号线,5
23#,宋家庄,5号线,10号线,5,10号线,5号线,5
24#,慈寿寺,6号线,10号线,5,10号线,6号线,5
25#,白石桥南,6号线,9号线,5,9号线,6号线,5
26#,南锣鼓巷,6号线,8号线,5,8号线,6号线,5
27#,呼家楼,6号线,10号线,5,10号线,6号线,5
28#,霍营,8号线,13号线,5,13号线,8号线,5
29#,北土城,8号线,10号线,5,10号线,8号线,5
30#,六里桥,9号线,10号线,5,10号线,9号线,5
31#,知春路,10号线,13号线,5,13号线,10号线,5
32#,芍药居,10号线,13号线,5,13号线,10号线,5。
