北京工业大学2014数据结构课设北京地铁查询C++版

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分钟，换乘次数：N1.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内容：以下内容直接复制粘贴，一个也别删！包括数字91号线,四惠东,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,积水潭,34号线,天宫院,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,火器营,313号线,西直门,3,大钟寺,3,知春路,3,五道口,3,上地,3,西二旗,3,龙泽,3,回龙观,3,霍营,3,立水桥,3,北苑,3,望京西,3,芍药居,3,光熙门,3,柳芳,3,东直门321#,公主坟,1号线,10号线,5,10号线,1号线,52#,军事博物馆,1号线,9号线,5,9号线,1号线,53#,复兴门,1号线,2号线,5,2号线,1号线,54#,西单,1号线,4号线,5,4号线,1号线,55#,东单,1号线,5号线,5,5号线,1号线,56#,建国门,1号线,2号线,5,2号线,1号线,57#,国贸,1号线,10号线,5,10号线,1号线,58#,宣武门,2号线,4号线,5,4号线,2号线,59#,崇文门,2号线,5号线,5,5号线,2号线,510#,朝阳门,2号线,6号线,5,6号线,2号线,511#,东直门,2号线,13号线,5,13号线,2号线,512#,雍和宫,2号线,5号线,5,5号线,2号线,513#,鼓楼大街,2号线,8号线,5,8号线,5号线,514#,西直门,2号线,4号线,5,4号线,2号线,5,2号线,13号线,5,13号线,2号线,5,4号线,13号线,5,13号线,4号线,515#,车公庄,2号线,6号线,5,6号线,2号线,516#,海淀黄庄,4号线,10号线,5,10号线,4号线,517#,国家图书馆,4号线,9号线,5,9号线,4号线,518#,平安里,4号线,6号线,5,6号线,4号线,519#,角门西,4号线,10号线,5,10号线,4号线,520#,立水桥,5号线,13号线,5,13号线,5号线,521#,惠新西街南口,5号线,10号线,5,10号线,5号线,522#,东四,5号线,6号线,5,6号线,5号线,523#,宋家庄,5号线,10号线,5,10号线,5号线,524#,慈寿寺,6号线,10号线,5,10号线,6号线,525#,白石桥南,6号线,9号线,5,9号线,6号线,526#,南锣鼓巷,6号线,8号线,5,8号线,6号线,527#,呼家楼,6号线,10号线,5,10号线,6号线,528#,霍营,8号线,13号线,5,13号线,8号线,529#,北土城,8号线,10号线,5,10号线,8号线,530#,六里桥,9号线,10号线,5,10号线,9号线,531#,知春路,10号线,13号线,5,13号线,10号线,532#,芍药居,10号线,13号线,5,13号线,10号线,5。