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

1、20102011年度 第 2 学期 一、需求分析 1.问题描述：这是上海铁路局目前仍在使用的行包托运软件中的一部分内部算法。该题目采用1995年年底我国铁路运输网的真实数据进行编程和运行验证。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00b客货运禁行,01b货运通行专线，10b客运通行专线，11b客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。2.基本功能（1）查询某站所属的铁路线 （2）要求具备

2、新增铁路线的管理功能（3）要求具备新增车站的管理功能 （4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序3.输入输出初始数据是从views.txt、lines.txt、ways.txt三个文件中读入，在读入数据后，用户可以根据选项选择相应的功能，不同的功能有不同的数据输入/输出，比如：查询的功能是要求输入要查询的站的名称，然后输出是该站的相关信息；查询最短路径的功能则是输入起点站、终点站的名称，输出则是该的路线距离和经由站等二、 概要设计1.设计思路：核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数

3、据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)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里，并将数

4、组里的存储数据的个数赋值给全局变量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存在，且里面放有相关的数据。操作结果：根据用户输入的

5、车站名查找该车站的相关信息并输出；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_v

6、iew里，并将数组里的存储数据的个数赋值给全局变量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 me

7、nu)初始条件：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 l

8、id; /铁路线的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; ;

9、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、增加车站信息"<

10、;<endl;cout<<" 2、增加铁路线信息"<<endl;cout<<" 3、查询车站信息"<<endl;cout<<" 4、查询最短路径"<<endl;cout<<" 5、退出界面"<<endl;cout<<"*"<<endl;cout<<"请选择你要的操作代码（1-5):"<<endl;cin>>menu;

11、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

12、(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(!in

13、file) /打开文件失败cerr<<"can't open views.txt!"<<endl;exit(1); for(i=0;i+)infile>>viewsi.id>>>>viewsi.code>>viewsi.shortname>>viewsi.lname;if(i!=0&&viewsi.id=0)break;view_count=i;infile.close();/下面是测试用的代码 cout<<setiosflags(i

14、os: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<<

15、;setw(9)<<<<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<<"

16、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"<

17、;<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.txt

18、int 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&a

19、mp;&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)<<&qu

20、ot;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;cou

21、t<<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,)=0)cout<<"the station info

22、rmations 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

23、(8)<<viewsi.id<<setw(9)<<<<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!&

24、quot;<<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&l

25、t;<"你输入的数据不合法！请重新输入:"cin>>viewsview_count.id;elsebreak;cout<<"name:"cin>>viewsview_;cout<<"code(code>"<<viewsview_count-1.code<<"):"cin>>viewsview_count.code;while(1)if(viewsview_count.code<viewsview

26、_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(!ou

27、tfile)cerr<<"can't open views.txt!"exit(1);outfile<<endl<<viewsview_count.id<<" "<<viewsview_<<" "outfile<<viewsview_count.code<<" "<<viewsview_count.shortname;outfile<<" "<

28、<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 inf

29、ormations:"<<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&q

30、uot;,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<

31、;<" "<<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 numb

32、er 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&l

33、t;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_i

34、d;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);out

35、file<<endl<<linesline_count.lid<<" "<<linesline_count.lname<<" "<<linesline_count.start_id;outfile<<" "<<linesline_count.end_id<<" "<<linesline_count.dist<<" "outfile<<linesline_

36、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.statio

37、n2;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数组、并记下其中任

38、两站的路径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=-

39、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

40、; /求出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=-

41、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)<<

42、;;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=)start_num=i;while(start_num=-1) /容错处理cout<<

43、"你的输入有误，请重新输入！"<<endl;cout<<"please input the start station name:"cin>>start_station;for(i=0;i<view_count;i+)if(start_station=)start_num=i;cout<<"please input the end_station name:"cin>>end_station;for(i=0;i<view_count;i+)i

44、f(end_station=)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=)end_num=i;cout<<endl<<endl;cout<<"

45、;from "<<viewsstart_<<" to "<<viewsend_; /输出最短经由路径if(dist_liststart_num+1end_num+1=-1) /没有找到的情况的回应cout<<" no way."<<endl;elsecout<<" distance is "<<dist_liststart_num+1end_num+1<<", and path is:&q

46、uot;<<endl;k=path_liststart_num+1end_num+1.path0-1;cout<<;for(m=1;m<path_liststart_num+1end_num+1.count;m+)k=path_liststart_num+1end_num+1.pathm-1;cout<<"->"<<;cout<<endl;(11)void adddata(int menu)if(menu=1)while(1)addview();cout<

47、;<"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.主要函数的程序流程图，实现设计中主程序和其他子模块的

48、算法，以流程图的形式表示。整个程序的流程图：4.主要算法floyed算法的流程图。 接上面的出口四、 调试分析 1.实际完成的情况说明（完成的功能，支持的数据类型等）；增加车站信息 增加铁路线信息查询车站信息 查询最短路径退出界面2.程序的性能分析，包括时空分析；本程序的关键算法floyde的时间复杂度主要在于求每一站到任意站的最短经由是的for循环那有三个for循环，很明显时间复杂度为o(view_count3）即o(n3），因为没有用到链表，也没有用到什么辅助空间，所以本程序的地对空间复杂度为o（1）。3.上机过程中出现的问题及其解决方案；(1）文件的读入时，又有包含的头文件的方式的大同小

49、异，当工程中没有要打开的文件时，没有自行建一个相关的文件；(2)刚开始弄设计的时候，由于没有经验，不知道如何去做，直到一天在网上搜的类似的代码的时候，就忽然间由头绪了，于是并仿造，最终些出了次程序；(3)在创建车站路线的数据的时候，一开始不知道怎么去做，后来看到了数据结构课本上的相关的图之后，这个问题也就解决了。4.程序中可以扩充的功能及设计实现假想。(1)可以添加删除数据的汗函数(2)可以添加从某站到某站的列车时刻表及票价，列车的类型（是快车还是普快）五、测试结果读数据的截图：功能测试的截图：六、用户手册1、初始界面 2、选择1 3、选择2 4、选择3 5、选择46、选择5七、体会与自我评价

50、 这次的程序软件基本上运行成功，可以简单的对已经输入的数据进行计算，求全国铁路运输网最佳经由。但是程序较小，功能不全面，只是理论，并未实践。同时，这次数据结构课程设计让我们感触很深，使我们每个人都了解到的学习不应该只局限于我们的课本，因为课本上告诉我们的只是很有限的一部分，所涉及的面也是狭窄的。但是怎样在有限的范围内学习到无限的知识呢？那就要我们自己懂得竞争，懂得自学，懂得充分利用身边的任何资源。应该说，我们在这次的课程设计中学到了很多知识，这并不仅仅包括书本上的知识，更重要的是我们学会了如何去和别人交流，怎样用语言去实现自己的想法，在这个过程中使我懂得了勤学好问的重要性。虽然在我的程序中有一

51、部分是从网上搜索得来的，但我竭力将所获得的信息变成自己的资源。在了解和看懂的基础上有所改变和创新，但是在我的程序软件中还有部分的不足。同时，通过这次课程设计，我们都意识到了自己动手实践的弱势，特别是在编程方面，只有通过上机编程才能充分的了解自己的不足。相信通过这次的课程设计，更让我深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这也是一笔很大的资源。在以后的时间中，我应该利用更多的时间去上机实验，多编写程序，相信不久后我的编程能力都会有很大的提高。经过这次课程设计，通过对程序的编制，调试和运行，使我更好的掌握了图基本性质和关于选址问题的解决方法，熟悉了各种调用的数据类型，在调试和

52、运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。在整个课程程序中，我们充分应用和调用各个程序模块，从而实现了此次程序设计的所应该有的功能。在本组看来这就是我们在课程设计是比较成功的，而在这个过程中，让

53、我们感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识（floyd算法），充分的发挥了我们的主动性，使我们自主的去学习。源代码#include <fstream>#include <iostream>#include <string>#include <cstdio>#include <iomanip>#include <cstdlib>#define size_view 50#define size_line 100#define size_way 300#define maxnode 30 /定义

54、最多节点数#define maxcost 10000 using namespace std;struct view_info /*城市信息结构*/ int id;char name20; int code;char shortname20;char lname100;/经过此站的铁路线名称viewssize_view;struct line_info/铁路线信息结构int lid;char lname20;int start_id; /始发站int end_id; /终点站int dist; /铁路线长char sign5; /通行标志linessize_line;struct way_in

55、fo /铁路度的信息结构int station1;int station2;int dist;wayssize_way;struct path_info /用于最短路径的查询int count;int pathsize_view;int view_count,line_count,way_count; /用来存储文件中有多少条记录int dist_listsize_viewsize_view; /定义一个数组struct path_info path_listsize_viewsize_view; /定义一个path_info结构体变量，void readviews();void readwa

56、ys();void readlines();void search();void addview();void addway();void addline();void shortest_path();void floyed();void adddata(int menu);void main()readviews();/*cout<<endl<<endl;*/readlines();/*cout<<endl<<endl;*/readways();while(1)int menu;cout<<endl<<endl;cout

57、<<" 全国铁路运输网经由系统"<<endl;cout<<"*"<<endl;cout<<" 1、增加车站信息"<<endl;cout<<" 2、增加铁路线信息"<<endl;cout<<" 3、查询车站信息"<<endl;cout<<" 4、查询最短路径"<<endl;cout<<" 5、退出界面"&

58、lt;<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

59、 you want to continue?(y/n)"<<endl;char con;cin>>con;if(con='y');else break;break;case 4:while(1)shortest_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);void readviews()int i;ifstream infile("views.txt",ios:in); /打开文件/吧文件中的个