数据结构课程设计之全国铁路最佳路径问题.doc

20102011年度 第 2 学期 一、需求分析 1.问题描述：这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。2.基本功能（1）查询某站所属的铁路线 （2）要求具备新增铁路线的管理功能（3）要求具备新增车站的管理功能 （4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序3.输入输出初始数据是从views.txt、lines.txt、ways.txt三个文件中读入，在读入数据后，用户可以根据选项选择相应的功能，不同的功能有不同的数据输入/输出，比如：查询的功能是要求输入要查询的站的名称，然后输出是该站的相关信息；查询最短路径的功能则是输入起点站、终点站的名称，输出则是该的路线距离和经由站等二、 概要设计1.设计思路：核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)2.数据结构设计：存储结构: 本程序采用的是文件进行数据的存储，所以才用的是顺序存储结构，如要添加数据，直接在文件里面进行操作就行。 如下为抽象数据类型定义的模板及抽象数据类型线性表的定义如下：ADT List数据对象：D=ai| ai ElemSet,i=1,2,3，n,n0数据关系：R1=<ai-1,ai>| ai-1,ai D,i=1,2,3,，n基本操作：void readviews()初始条件：views.txt已经存在。操作结果：将 views.txt里面的数据一次存入数组viewsSIZE_view里，并将数组里的存储数据的个数赋值给全局变量view_count；void readways()初始条件：ways.txt已经存在。操作结果：将 ways.txt里面的数据一次存入数组waysSIZE_view里，并将数组里的存储数据的个数赋值给全局变量way_count；void readlines()初始条件：lines.txt已经存在。操作结果：将 lines.txt里面的数据一次存入数组linesSIZE_view里，并将数组里的存储数据的个数赋值给全局变量line_count.void search();初始条件：viewsSIZE_view存在，且里面放有相关的数据。操作结果：根据用户输入的车站名查找该车站的相关信息并输出；void addview();初始条件：views.txt已经存在。操作结果：将 views.txt里面的数据一次存入数组viewsSIZE_view里，并将数组里的存储数据的个数赋值给全局变量view_count；void addway();初始条件：ways.txt已经存在。操作结果：将 ways.txt里面的数据一次存入数组waysSIZE_view里，并将数组里的存储数据的个数赋值给全局变量way_count；void addline();初始条件：lines.txt已经存在。操作结果：将 lines.txt里面的数据一次存入数组linesSIZE_view里，并将数组里的存储数据的个数赋值给全局变量line_count.void floyed();初始条件：viewsSIZE_view、waysSIZE_view、linesSIZE_view存在并且存有相关的信息操作结果：把每个车站到人一个车的最短经由路径及此路径的距离存储在path_info path_listSIZE_viewSIZE_view数组里；void shortest_path()初始条件：path_info path_listSIZE_viewSIZE_view存在且存储相关的数据；操作结果：输出输入的两个站的最短距离及经过的所有站；void adddata(int menu)初始条件：views.txt、ways.txt、lines.txt已经存在。操作结果：如果menu=1，则添加车站数据，如果menu=2，则添加路线数据；3.软件结构设计：三、 详细设计 1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；struct view_info /*车站信息结构*/ int id; /车站的id编号char name20; /车站的名字int code; /车站的编码char shortname20; /车站的简称char LName100;/经过此站的铁路线名称viewsSIZE_view;struct line_info/铁路线信息结构int Lid; /铁路线的id编号char LName20; /铁路线的名字int start_id; /铁路线的始发站int end_id; /铁路线的终点站int dist; /铁路线长char sign5; /铁路线的通行标志 linesSIZE_line;struct way_info /铁路线上站与站之间的信息结构int station1; /前一个站int station2; /后一个站int dist; /前后站之间的距离waysSIZE_way;struct path_info /用于最短路径的查询int count; /用于存最短路径的站的个数int pathSIZE_view; ;2.主函数和其他函数的代码算法；(1)void main()readviews();/*cout<<endl<<endl;*/readlines();/*cout<<endl<<endl;*/readways();while(1)int menu;cout<<endl<<endl;cout<<" 全国铁路运输网经由系统"<<endl;cout<<"*"<<endl;cout<<" 1、增加车站信息"<<endl;cout<<" 2、增加铁路线信息"<<endl;cout<<" 3、查询车站信息"<<endl;cout<<" 4、查询最短路径"<<endl;cout<<" 5、退出界面"<<endl;cout<<"*"<<endl;cout<<"请选择你要的操作代码（1-5):"<<endl;cin>>menu;while(menu<1|menu>5)cout<<"error!please enter again:"cin>>menu;switch(menu)case 1:case 2:adddata(menu);break;case 3:while(1)search();cout<<"do you want to continue?(y/n)"<<endl;char con;cin>>con;if(con='y');else break;break;case 4:while(1)short_path();cout<<"do you want to continue?(y/n)"<<endl;char con;cin>>con;if(con='y');/*addline();*/else break;break;case 5:cout<<"谢谢使用，再会！"<<endl;exit(1);(2)void readviews()int i;ifstream infile("views.txt",ios:in); /打开文件if(!infile) /打开文件失败cerr<<"can't open views.txt!"<<endl;exit(1); for(i=0;i+)infile>>viewsi.id>>viewsi.name>>viewsi.code>>viewsi.shortname>>viewsi.LName;if(i!=0&&viewsi.id=0)break;view_count=i;infile.close();/下面是测试用的代码 cout<<setiosflags(ios:left); cout<<setw(8)<<"id"<<setw(9)<<"name"<<setw(8)<<"code"<<setw(12)<<"shortname"<<setw(10)<<"LName"<<endl; for(i=0;i<view_count;i+) cout<<setw(8)<<viewsi.id<<setw(9)<<viewsi.name<<setw(8)<<viewsi.code<<setw(12); cout<<viewsi.shortname<<viewsi.LName<<endl; cout<<resetiosflags(ios:left);(3)void readways()/读文件ways.txtint i;ifstream infile("ways.txt",ios:in);/打开文件if(!infile) /打开文件失败cerr<<"can't open ways.txt!"<<endl;exit(1);for(i=0;i+)infile>>waysi.station1>>waysi.station2>>waysi.dist;if(i!=0&&waysi.station1=0)break;way_count=i;infile.close(); /测试用，输入路段的信息/ cout<<setiosflags(ios:left);/ cout<<setw(12)<<"station1"<<setw(12)<<"station2"<<"dist"<<endl;/ for(i=0;i<way_count;i+)/ / cout<<setw(12)<<waysi.station1<<setw(12)<<waysi.station2;/ cout<<waysi.dist<<endl;/ / cout<<resetiosflags(ios:left);（4）void readlines()/读文件lines.txtint i;ifstream infile("lines.txt",ios:in);/打开文件if(!infile) /打开文件失败cerr<<"can't open lines.txt!"<<endl;exit(1);for(i=0;i+)infile>>linesi.Lid>>linesi.LName>>linesi.start_id;infile>>linesi.end_id>>linesi.dist>>linesi.sign;if(i!=0&&linesi.Lid=0)break;line_count=i;infile.close();/下面的代码为测试时用的cout<<setiosflags(ios:left);cout<<setw(8)<<"Lid"<<setw(12)<<"LName"<<setw(10)<<"start_id"cout<<setw(10)<<"end_id"<<setw(8)<<"dist"<<"sign"<<endl;for(i=0;i<line_count;i+)cout<<setw(8)<<linesi.Lid<<setw(12)<<linesi.LName<<setw(10)<<linesi.start_id;cout<<setw(10)<<linesi.end_id<<setw(8)<<linesi.dist<<linesi.sign<<endl;cout<<resetiosflags(ios:left); /这里输出文本中的信息（5）void search() /查询车站信息（所在的铁路线）cout<<"Please enter the station name:"char sta_name20;cin>>sta_name; /输入要查询的名字cout<<endl;int i,mark;for(i=0;i<view_count;i+)if(strcmp(sta_name,viewsi.name)=0)cout<<"the station informations is:n"<<endl;cout<<setiosflags(ios:left);cout<<setw(8)<<"id"<<setw(9)<<"name"<<setw(8)<<"code"<<setw(12)<<"shortname"<<setw(10)<<"LName"<<endl;cout<<setw(8)<<viewsi.id<<setw(9)<<viewsi.name<<setw(8)<<viewsi.code<<setw(12);cout<<viewsi.shortname<<viewsi.LName<<endl;cout<<resetiosflags(ios:left);break;mark=i;if(mark=view_count-1) /若没找到，输出提示cout<<"sorry, the station is not in here!"<<endl;（6）void addview()cout<<"Please enter the new view's informations:"<<endl; /输入新的车站信息cout<<"id(id>"<<viewsview_count-1.id<<"):"cin>>viewsview_count.id;while(1)if(viewsview_count.id<viewsview_count-1.id)cout<<"你输入的数据不合法！请重新输入:"cin>>viewsview_count.id;elsebreak;cout<<"name:"cin>>viewsview_count.name;cout<<"code(code>"<<viewsview_count-1.code<<"):"cin>>viewsview_count.code;while(1)if(viewsview_count.code<viewsview_count-1.code)cout<<"你输入的数据不合法！请重新输入:"cin>>viewsview_count.id;else break;cout<<"shortname:"cin>>viewsview_count.shortname;cout<<"LName:"cin>>viewsview_count.LName;ofstream outfile("views.txt",ios:app); /打开views文件，并写入数据if(!outfile)cerr<<"can't open views.txt!"exit(1);outfile<<endl<<viewsview_count.id<<" "<<viewsview_count.name<<" "outfile<<viewsview_count.code<<" "<<viewsview_count.shortname;outfile<<" "<<viewsview_count.LName<<endl;/在文件末尾添加view_count+;outfile.close(); /关闭文件cout<<"Successfully!the new station is added"<<endl;cout<<"new station number is :"<<view_count<<endl;（7）void addway()cout<<"Please enter the new way's informations:"<<endl; /输入新的车站信息cout<<"station1:"cin>>waysway_count.station1; /station1 的idcout<<"station2:"cin>>waysway_count.station2; /station2 的idcout<<"dist:"cin>>waysway_count.dist; /路段的长度ofstream outfile("ways.txt",ios:app); /打开ways.txt文件，并写入数据/*outfile<<way_count<<endl;*/if(!outfile)cerr<<"can't open ways.txt!"exit(1);outfile<<endl<<waysway_count.station1<<" "<<waysway_count.station2<<" "outfile<<waysway_count.dist<<" "<<waysway_count.station2<<" "<<waysway_count.station1;outfile<<" "<<waysway_count.dist;/在文件末尾添加way_count+;outfile.close(); /关闭文件cout<<"Successfully!the new way is added"<<endl;cout<<"new station number is :"<<way_count<<endl;(8)void addline()cout<<"Please enter the new line's informations:"<<endl; /输入新铁路信息cout<<"Lid(Lid>"<<linesline_count-1.Lid<<"):"cin>>linesline_count.Lid;while(1)if(linesline_count.Lid<linesline_count-1.Lid)cout<<"你输入的数据不合法！请重新输入:"cin>>linesline_count.Lid;elsebreak;cout<<"LName:"cin>>linesline_count.LName;cout<<"start_id:"cin>>linesline_count.start_id;cout<<"end_id:"cin>>linesline_count.end_id;cout<<"dist:"cin>>linesline_count.dist;cout<<"sign:"cin>>linesline_count.sign;ofstream outfile("lines.txt",ios:app); /打开文件，并写入数据/*outfile<<line_count+1<<endl;*/if(!outfile)cerr<<"can't open lines.txt!"exit(1);outfile<<endl<<linesline_count.Lid<<" "<<linesline_count.LName<<" "<<linesline_count.start_id;outfile<<" "<<linesline_count.end_id<<" "<<linesline_count.dist<<" "outfile<<linesline_count.sign;/在文件末尾添加line_count+;outfile.close(); /关闭文件cout<<"Successfully!the new line is added"<<endl;cout<<"new station number is :"<<line_count<<endl;(9)void floyed() /弗洛伊德算法int i,j,k,m;for(int t=0;t<=way_count;t+)i=wayst.station1;j=wayst.station2;dist_listij=wayst.dist;/把文件中的数据付给dist_listij=wayst.dist;形式for(i=0;i<=view_count;i+)for(j=0;j<=view_count;j+)if(i=j) /车站到本车站的距离赋值为零dist_listij=0;continue;dist_listij=-1; /先设置任意两点之间的距离为-1；表示这两点不通path_listij.count=0; /先设置任意两点之间的的路径的车站数为零for(k=0;k<way_count;k+) /ways文件的数据赋给dist_list数组、并记下其中任两站的路径if(waysk.station1=i&&waysk.station2=j)dist_listij=waysk.dist;path_listij.count=2;path_listij.path0=i;path_listij.path1=j;break;/下面是计算最短路径的代码for(k=0;k<=view_count;k+) for(i=0;i<=view_count;i+)for(j=0;j<=view_count;j+)if(i=k|j=k|i=j) /三个站中至两个站是相同的的话就是继续循环continue;if(dist_listik=-1|dist_listkj=-1) /i、k不通或者k、j不通继续循环continue;if(dist_listij=-1)|(dist_listij != -1) &&(dist_listik+dist_listkj<dist_listij) /i、j不通，或者是i、j通但是不是最短路径，执行下面语句dist_listij=dist_listik+dist_listkj; /求出i、j的最短距离/shortestij=shortestik+shortestkj;path_listij.count=path_listik.count+path_listkj.count-1; /求出i、j路径的站的个数/path_listij=k;for(m=0;m<path_listik.count;m+) /下面两个for语句标出i、j路径的每个站的id号，以便后面的输出最短经由路径用path_listij.pathm=path_listik.pathm;for(m=0;m<path_listkj.count;m+)path_listij.pathm+path_listik.count=path_listkj.pathm+1;(10)void shortest_path()floyed();int i,k,m;int start_num=-1,end_num=-1;string start_station,end_station;/定义起始站、终点站/下面便是输出最短经由路径的代码cout<<"Floyed table:n"cout<<"All cities in the table:n"for(i=0;i<view_count;i+) /输出可以查看的站的名称和id号cout<<setiosflags(ios:left);cout<<setw(2)<<i+1<<":"<<setw(10)<<viewsi.name;if(1+i)%5)=0&&i!=0)cout<<endl;cout<<resetiosflags(ios:left);cout<<endl;cout<<"Please input the start station name:"cin>>start_station;for(i=0;i<view_count;i+)if(start_station=viewsi.name)start_num=i;while(start_num=-1) /容错处理cout<<"你的输入有误，请重新输入！"<<endl;cout<<"Please input the start station name:"cin>>start_station;for(i=0;i<view_count;i+)if(start_station=viewsi.name)start_num=i;cout<<"Please input the end_station name:"cin>>end_station;for(i=0;i<view_count;i+)if(end_station=viewsi.name)end_num=i;while(end_num=-1) /容错处理cout<<"你的输入有误，请重新输入！"<<endl;cout<<"Please input the end_station name:"cin>>end_station;for(i=0;i<view_count;i+)if(end_station=viewsi.name)end_num=i;cout<<endl<<endl;cout<<"From "<<viewsstart_num.name<<" to "<<viewsend_num.name; /输出最短经由路径if(dist_liststart_num+1end_num+1=-1) /没有找到的情况的回应cout<<" no way."<<endl;elsecout<<" distance is "<<dist_liststart_num+1end_num+1<<", and path is:"<<endl;k=path_liststart_num+1end_num+1.path0-1;cout<<viewsk.name;for(m=1;m<path_liststart_num+1end_num+1.count;m+)k=path_liststart_num+1end_num+1.pathm-1;cout<<"->"<<viewsk.name;cout<<endl;(11)void adddata(int menu)if(menu=1)while(1)addview();cout<<"do you want to continue?(y/n)"<<endl;char con;cin>>con;if(con='y');else break;if(menu=2)while(1)addline();addway();cout<<"do you want to continue?(y/n)"<<endl;char con;cin>>con;if(con='y');else break;3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。整个程序的流程图：4.主要算法floyed算法的流程图。 接上面的出口四、 调试分析 1.实际完成的情况说明（完成的功能，支持的数据类型等）；增加车站信息 增加铁路线信息查询车站信息 查询最短路径退出界面2.程序的性能分析，包括时空分析；本程序的关键算法floyde的时间复杂度主要在于求每一站到任意站的最短经由是的for循环那有三个for循环，很明显时间复杂度为O(view_count3）即O(n3），因为没有用到链表，也没有用到什么辅助空间，所以本程序的地对空间复杂度为O（1）。3.上机过程中出现的问题及其解决方案；(1）文件的读入时，又有包含的头文件的方式的大同小异，当工程中没有要打开的文件时，没有自行建一个相关的文件；(2)刚开始弄设计的时候，由于没有经验，不知道如何去做，直到一天在网上搜的类似的代码的时候，就忽然间由头绪了，于是并仿造，最终些出了次程序；(3)在创建车站路线的数据的时候，一开始不知道怎么去做，后来看到了数据结构课本上的相关的图之后，这个问题也就解决了。4.程序中可以扩充的功能及设计实现假想。(1)可以添加删除数据的汗函数(2)可以添加从某站到某站的列车时刻表及票价，列车的类型（是快车还是普快）五、测试结果读数据的截图：功能测试的截图：六、用户手册1、初始界面 2、选择1 3、选择2 4、选择3 5、选择46、选择5七、体会与自我评价 这次的程序软件基本上运行成功，可以简单的对已经输入的数据进行计算，求全国铁路运输网最佳经由。但是程序较小，功能不全面，只是理论，并未实践。同时，这次数据结构课程设计让我们感触很深，使我们每个人都了解到的学习不应该只局限于我们的课本，因为课本上告诉我们的只是很有限的一部分，所涉及的面也是狭窄的。但是怎样在有限的范围内学习到无限的知识呢？那就要我们自己懂得竞争，懂得自学，懂得充分利用身边的任