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

2014年北京工业大学计算机学院数据结构与算法课设嗨，你好。当年为了这个该死的课设我也是和你一样急，在CSDN上各种找……但是没有。最后还好……弄出来了。C++版本题目什么的在下面，附件什么的我都在这个DOC中给你。祝你能过。2014.11.01数据结构与算法课程设计报告北京地铁查询系统学号：120701姓名：哈哈指导教师：呵呵2014年10月第1页共16页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（n0）第1行：第1条地铁线路名称（如:1号线），第1站（如：四惠东站），图上坐标（如：X1，Y1）2，运行时间（如：3），第2站（如：四惠站），图上坐标（如：X2，Y2），运行时间（如：4），…，第23站（如：苹果园站），图上坐标（如：Xn，Yn）…第i行：第i条地铁线路名称,第1站，运行时间，第2站，运行时间，…，第n站…第n行：第n条地铁线路名称,第1站，运行时间，第2站，运行时间，…，第n站第n+1行：换乘站数目m（m0）换乘编号1#：换乘站名称1（如：四惠东站），（下车线路（如：1号线），1*表示可能有若干次换乘，也可能没有换乘。每次换乘的信息为（换乘站，站名，换乘几号线）2坐标根据采用的地铁图中的相对位置来给出（由同学自己根据所选地铁图大小进行设置）第2页共16页换乘线路（如：八通线），换乘时间3（如：5））+4…换乘编号i#：换乘站名称i，下车线路，换乘线路，换乘时间…换乘编号m#：换乘站名称m，下车线路，换乘线路，换乘时间用户查询信息通过图形界面的对话框提供：包括起始站，目的站的输入框。1.2.2输出画面的要求用图形方式显示北京市地铁图，并根据客户的输入提供建议（文字展示）并以加粗的两端带红点的绿色线路形式绘制在地铁图上。1.2.3题目约定题目中的时间单位为分钟；地铁一般一站运行时间3分钟，个别长的站为5分钟。最短距离以所用时间表示1.2.4题目实现要求应用最短路径算法，求任意两站间的“最快”，“最方便”的出行方案。特别需要注意换乘站的处理。5.0代码清单#includeiostream#includefstream#includestring#includevectorusingnamespacestd;typedefstructArcNode{intadjvex;stringline;inttime;structArcNode*nextarc;}ArcNode;3换乘时间以分钟为单位4相同的换乘站可以换乘不同的地铁线路，比如西直门换乘站。第3页共16页typedefstructVNode{stringstation;intcost;stringpath;stringfrom;ArcNode*firstarc;}VNode;typedefstructTransfer{stringfrom;stringto;inttime;structTransfer*nextarc;}Transfer;typedefstructTransferStation{stringstation;Transfer*firstarc;}TransferStation;voidsplit(conststring&,conststring&,vectorstring&);intfindIndex(vectorVNode,string);intfindIndex(vectorint,int);intfindTransferTime(string,string,string);voidinitialize();stringfindOptimalPath(string,string,int&);vectorVNodeAdjList;vectorTransferStationTransferInfo;voidmain(){initialize();intcost;stringstart,des;cout欢迎使用\n;cout输入起点站:;cinstart;cout输入终点站:;cindes;第4页共16页strings=findOptimalPath(start,des,cost);cout线路为:;couts.c_str()endl;cout耗时cost分钟\nendl;intx;cinx;}voidinitialize(){ifstreamin(BaseInfo.txt);//读入文件strings;intlinesNum;stringline;vectorstringv;inttime;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];vn-cost=10000;vn-path=;vn-from=;vn-firstarc=NULL;AdjList.push_back(*vn);for(i=2;iv.size()-1;i=i+2){time=atoi(v[i].c_str());index=AdjList.size();an=newArcNode();an-line=line;第5页共16页an-adjvex=index;an-time=time;an-nextarc=vn-firstarc;//前插法AdjList[i/2-1].firstarc=an;an=newArcNode();an-line=line;an-adjvex=index-1;an-time=time;an-nextarc=NULL;vn=newVNode();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=newArcNode();an-line=line;an-adjvex=0;an-time=time;an-nextarc=vn-firstarc;AdjList.back().firstarc=an;an=newArcNode();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);第6页共16页line=v[0];index1=findIndex(AdjList,v[1]);if(index1==-1){vn=newVNode();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;iv.size()-1;i=i+2){time=atoi(v[i].c_str());index2=findIndex(AdjList,v[i+1]);if(index2==-1){vn=newVNode();vn-station=v[i+1];vn-cost=10000;vn-from=;vn-path=;vn-firstarc=NULL;AdjList.push_back(*vn);index2=AdjList.size()-1;}an=newArcNode();an-line=line;an-adjvex=index1;an-time=time;an-nextarc=AdjList[index2].firstarc;//前插法AdjList[index2].firstarc=an;an=newArcNode();an-line=line;an-adjvex=index2;an-time=time;第7页共16页an-nextarc=AdjList[index1].firstarc;AdjList[index1].firstarc=an;index1=index2;}if(i==v.size()-1){time=atoi(v[i].c_str());an=newArcNode();an-line=line;an-adjvex=startIndex;an-time=time;an-nextarc=vn-firstarc;AdjList[index1].firstarc=an;an=newArcNode();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=newTransferStation();ts-station=v[1];ts-firstarc=NULL;for(i=2;iv.size();i=i+3){t=newTransfer();t-from=v[i];t-to=v[i+1];t-time=atoi(v[i+2].c_str());t-nextarc=ts-firstarc;ts-firstarc=t;第8页共16页}TransferInfo.push_back(*ts);}}voidsplit(conststring&src,conststring&separator,vectorstring&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-