数据结构与算法课程设计报告-北京地铁查询系统C++版.doc

数据结构与算法课程设计报告北京地铁查询系统学 号： 12 07 01 姓 名： 哈 哈 指导教师： 呵 呵 2014年10月1.1设计的描述当今的北京，地铁已经成为绝大多数人出行的首选。截至2014年1月，北京地铁共有17条运营线路。组成覆盖北京市11个市辖区，拥有231座运营车站、总长467千米运营线路的轨道交通系统，工作日均客流约1000万人次，峰值日客运量1155.92万人次。随着地铁线路的增加，地铁规模越来越大，人们愈发的感觉到地铁的便利。特别地从出发地到目的地的乘车方案的选择也越来越多。因此，需要提供一个软件能够为人们提供出发到目的地之间“最快”或“最方便”的地铁出行方案。其中，“最快”指用时最少，“最方便”则指在换乘车少的基础上用时最少。1.2设计的需求请设计一个地铁出行帮助系统，为北京市居民提供地铁出行方案（仅限地铁出行）。提供出发地和目的地地铁站的输入窗口，提供出行建议，并图形显示出线路。出行建议信息： 出发站，站名，几号线 第2站，站名，几号线 第i站，站名，几号线 换乘站，站名，换乘几号线* *表示可能有若干次换乘，也可能没有换乘。每次换乘的信息为（换乘站，站名，换乘几号线）， 第m站，站名，几号线 目的站，站名，几号线 总用时，X分钟，换乘次数：N1.2.1输入数据要求地铁线路基础信息数据通过一个名为“BaseInfo.txt”的文本文件读入。该数据文件格式如下： 第0行：当前系统中地铁线路的条数n（n 0） 第1行：第1条地铁线路名称（如:1号线），第1站（如：四惠东站），图上坐标（如：X1，Y1） 坐标根据采用的地铁图中的相对位置来给出（由同学自己根据所选地铁图大小进行设置），运行时间（如：3），第2站（如：四惠站），图上坐标（如：X2，Y2），运行时间（如：4）， 第23站（如：苹果园站），图上坐标（如：Xn，Yn） 第i行：第i条地铁线路名称, 第1站，运行时间，第2站，运行时间， 第n站 第n行：第n条地铁线路名称, 第1站，运行时间，第2站，运行时间， 第n站 第n+1行：换乘站数目m（m 0） 换乘编号1#：换乘站名称1（如：四惠东站），（下车线路（如：1号线），换乘线路（如：八通线），换乘时间 换乘时间以分钟为单位（如：5）+ 相同的换乘站可以换乘不同的地铁线路，比如西直门换乘站。 换乘编号i#：换乘站名称i，下车线路，换乘线路，换乘时间 换乘编号m#：换乘站名称m，下车线路，换乘线路，换乘时间用户查询信息通过图形界面的对话框提供：包括起始站，目的站的输入框。1.2.2输出画面的要求 用图形方式显示北京市地铁图，并根据客户的输入提供建议（文字展示）并以加粗的两端带红点的绿色线路形式绘制在地铁图上。1.2.3题目约定l 题目中的时间单位为分钟；l 地铁一般一站运行时间3分钟，个别长的站为5分钟。l 最短距离以所用时间表示1.2.4题目实现要求l 应用最短路径算法，求任意两站间的“最快”，“最方便”的出行方案。特别需要注意换乘站的处理。5.0代码清单#include#include#include#includeusing namespace std;typedef struct ArcNodeint adjvex;string line;int time;struct ArcNode *nextarc;ArcNode;typedef struct VNodestring station;int cost;string path;string from;ArcNode *firstarc;VNode;typedef struct Transferstring from;string to;int time;struct Transfer *nextarc;Transfer;typedef struct TransferStationstring station;Transfer *firstarc;TransferStation;void split(const string&, const string&, vector&);int findIndex(vector, string);int findIndex(vector, int);int findTransferTime(string, string, string);void initialize();string findOptimalPath(string, string, int&);vector AdjList;vector TransferInfo;void main()initialize();int cost;string start,des;cout欢迎使用n;coutstart;coutdes;string s = findOptimalPath(start, des, cost);cout线路为:;couts.c_str()endl;cout耗时cost分钟nx;void initialize()ifstream in(BaseInfo.txt);/读入文件string s;int linesNum;string line;vector 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 = v0;vn = new VNode();vn-station = v1;vn-cost = 10000;vn-path = ;vn-from = ;vn-firstarc = NULL;AdjList.push_back(*vn);for(i=2; iline = line;an-adjvex = index;an-time = time;an-nextarc = vn-firstarc;/前插法AdjListi/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 = vi+1;vn-cost = 10000;vn-path = ;vn-from = ;vn-firstarc = an;AdjList.push_back(*vn);if(i = v.size()-1)time = atoi(vi.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 = AdjList0.firstarc;AdjList0.firstarc = an;while(linesNum- 1)getline(in, s);v.clear();split(s, , v);line = v0;index1 = findIndex(AdjList, v1);if(index1 = -1)vn = new VNode();vn-station = v1;vn-cost = 10000;vn-from = ;vn-path = ;vn-firstarc = NULL;AdjList.push_back(*vn);index1 = AdjList.size() - 1;startIndex = index1;for(i=2; istation = vi+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 =AdjListindex2.firstarc;/前插法AdjListindex2.firstarc = an;an = new ArcNode();an-line = line;an-adjvex = index2;an-time = time;an-nextarc = AdjListindex1.firstarc;AdjListindex1.firstarc = an;index1 = index2;if(i = v.size()-1)time = atoi(vi.c_str();an = new ArcNode();an-line = line;an-adjvex = startIndex;an-time = time;an-nextarc = vn-firstarc;AdjListindex1.firstarc = an;an = new ArcNode();an-line = line;an-adjvex = index1;an-time = time;an-nextarc = AdjListstartIndex.firstarc;AdjListstartIndex.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 = v1;ts-firstarc = NULL;for(i=2; ifrom = vi;t-to = vi+1;t-time = atoi(vi+2.c_str();t-nextarc = ts-firstarc;ts-firstarc = t;TransferInfo.push_back(*ts);void split(const string& src, const string& separator, vector& 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 v, string station)int i = v.size() - 1;while(i = 0 & strcmp(vi.station.c_str(), station.c_str() != 0)i-;return i;int findIndex(vector v, int index)int i = v.size() - 1;while(i = 0 & vi != index)i-;return i;int findTransferTime(string station, string from, string to)int time = 5;for(int i=0; ifrom = 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 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;AdjListsourceIndex.cost = 0;AdjListsourceIndex.path = source;S.push_back(sourceIndex);while(minStationIndex != destinationIndex)minTime = 10000;for(i=0; iadjvex.cost = 10000)time0 = 10000;if(Si = sourceIndex)if(an-time line;minTime = an-time;minStationIndex = an-adjvex;foreIndex = Si;from = line;AdjListsourceIndex.from = line;path0 = ;elseif(AdjListSi.from = an-line)time = AdjListSi.cost + an-time;if(time line;minTime = time;minStationIndex = an-adjvex;foreIndex = Si;from = line;path0 = ;elsetime = AdjListSi.cost + findTransferTime(AdjListSi.station, AdjListSi.from, an-line) + an-time;an0 = AdjListSi.firstarc;while(an0)if(an0-line = an-line & an0-adjvex != an-adjvex)break;an0 = an0-nextarc;if(an0 != NULL & AdjListan0-adjvex.cost != 10000)time0 = AdjListan0-adjvex.cost + an0-time + an-time;if(AdjListan0-adjvex.from != an-line)time0 += findTransferTime(AdjListan0-adjvex.station, AdjListan0-adjvex.from, an-line);if(time time0)time = time0;if(time line;minTime = time;minStationIndex = an-adjvex;foreIndex = Si;from = line;if(time = time0)if(AdjListan0-adjvex.from = line)path0 = AdjListan0-adjvex.path + , + line + , + AdjListSi.station + , + line + , + AdjListminStationIndex.station;elsepath0 = AdjListan0-adjvex.path + , + line + , + AdjListSi.station + , + line + , + AdjListminStationIndex.station;an = an-nextarc;S.push_back(minStationIndex);AdjListminStationIndex.cost = minTime;AdjListminStationIndex.from = from;if(path0 != )AdjListminStationIndex.path = path0;elseAdjListminStationIndex.path = AdjListforeIndex.path + , + line + , + AdjListminStationIndex.station;AdjListdestinationIndex.path += , + line;cost = AdjListdestinationIndex.cost;return AdjListdestinationIndex.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号线,52014年北京工业大学计算机学院数据结构与算法课设嗨，你好。当年为了这个该死的课设我也是和你一样急，在CSDN上各种找但是没有。最后还好弄出来了。C+版本题目什么的在下面，附件什么的我都在这个DOC中给你。祝你能过。2014.11.01您好，为你提供优秀的毕业论文参考资料，请您删除以下内容，O(_)O谢谢！A large group of tea merchants on camels and horses from Northwest Chinas Shaanxi province pass through a stop on the ancient Silk Road, Gansus Zhangye city during their journey to Kazakhstan, May 5, 2015. The caravan, consisting of more than 100 camels, three horse-drawn carriages and four support vehicles, started the trip from Jingyang county in Shaanxi on Sept 19, 2014. It will pass through Gansu province and Xinjiang Uygur autonomous region, and finally arrive in Almaty, formerly known as Alma-Ata, the largest city in Kazakhstan, and Dungan in Zhambyl province. The trip will cover about 15,000 kilometers and take the caravan more than one year to complete. The caravan is expected to return to Jingyang in March 2016. Then they will come back, carrying specialty products from Kazakhstan A small art troupe founded six decades ago has grown into a household name in the Inner Mongolia autonomous region. In the 1950s, Ulan Muqir Art Troupe was created by nine young musicians, who toured remote villages on horses and performed traditional Mongolian music and dances for nomadic families. The 54-year-old was born in Tongliao, in eastern Inner Mongolia and joined the troupe in 1975.He says there are 74 branch troupes across Inner Mongolia and actors give around 100 shows every year to local nomadic people. I can still recall the days when I toured with the troupe in the early 80s. We sat on the back of pickup trucks for hours. The sky was blue, and we couldnt help but sing the folk songs, Nasun says. The vastness of Inner Mongolia and the lack of entertainment options for people living there, made their lives lonely. The nomadic people were very excited about our visits, Nasun recalls. We didnt have a formal stage. The audience just sat on the grass. Usually, the performances became a big party with local people joining in. For him, the rewarding part about touring isnt just about sharing art with nomadic families but also about gaining inspiration for the music and dance. Ulan Muqir literally translates as red burgeon, and todays performers of the troupe still tour the regions villages and entertain nomadic families, but their fame has spread around the world. On May 16 and 17, nearly 100 singers and dancers from the troupe performed at Beijings Poly Theater. Their show, titled Ulan Muqir on the Grassland, depicted the history and development of the art troupe. Being from the region allowed me to embrace the culture of Inner Mongolia and being a member of the troupe showed me where I belonged, Nasun, the art troupes president, who is also a renowned tenor, tells China Daily. During a tour in 1985, he went to a village and met an elderly local man, who told him a story about his friendship with a solider from Shenyang, capital of Northeast Chinas Liaoning province, decades ago. The solider gave the old man a handmade saddle when they bid farewell. The story inspired Nasun to write Carved Saddle, a song that later became one of his most popular numbers. Now, every year, Nasun recruits young singers and dancers for the troupe. The troupe has also designed a new repertoire, which is mostly based on the daily lives of Mongolian people, especially the lives of nomadic families, and has combined contemporary musical elements with folk songs of the region. Haimu, a 25-year-old khoomei (a local variant of overtone singing) singer, joined the troupe three years ago. Along with a six-member band, he performs fast songs and soft ones that he writesall while playing the horse-head fiddle.Although I learned the piano since childhood and grew up listening to various kinds of music, to me, the folk music of Inner Mongolia is the root, he says. Performing in remote villages is pleasant. I feel at home on the boundless grasslands, and the warm people there make me feel fulfilled. The first round of spring auction season in Beijing ended last week, but it failed to create much spring in the art market. Although two pieces of Chinese painting fetched more than 100 million yuan, the decline in trading volume and sale rate showed a downturn this year. In the “Grand View: Chinese Painting Highlight” session at China Guardian 2015 spring auctions, Pan Tianshous representative work Eagle, Rock and Flora hit a record auction price of 279 million yuan, while Li Kerans masterwork Jinggang Mountain fetched 126.5 million yuan, an unexpected high in recent years. However, the trading volume fells to 1.87 billion yuan from 2.22 billion yuan in the same period the year before. The Huangchen 2015 Spring Auctions, which recorded 42.5 million yuan in total sales, experienced the same. The section number went down to 5 from 12 compared to last year. According to expert Shao Jianwu, the art market did not attract much excitement this year due to the booming stock market and the persistent problems of forgery and fake deals. The two pieces of Chinese painting notched up high price this spring due to their own