全国铁路最短路径经由问题

1、中南大学数据结构课程设计报告题 目 全国铁路最短路径经由问题 学生姓名 任秋峥 指导教师 李登 学 院 信息科学与工程学院 学 号 0909090711 专业班级 电子信息专业0901班 完成时间 2011年6月30号 目录第一章、课程设计题目31、问题描述32、基本要求33、实现提示4第二章、全国铁路最短路径经由问题的具体实现62.1 需求分析62.2 概要设计61、设计思路62、设计方案72.3详细设计101、定义结构体102、输出车站信息103、输出铁路信息114、输出道路的信息115、查询车站的功能116、增加车站信息127、增加铁路信息128、最短路径的实现129、实现所有函数功能1

2、32.4 测试分析131、测试数据132、测试过程143、测试结果142.5用户使用说明141 程序运行环境142 主界面142.6小结171 调试过程中遇到的主要问题及解决过程172.7总结和体会172.8 附录181、源程序代码182、参考文献29第一章、课程设计题目1、问题描述题目为全国铁路最短路径经由问题该题目采用我国铁路运输网的数据进行编程和运行验证。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00b客货运禁行,01b货运通行专线，10b客运通行

3、专线，11b客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。2、基本要求（1）查询某站所属的铁路线（2）要求具备新增铁路线的管理功能（3）要求具备新增车站的管理功能（4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序3、实现提示要在计算机上建立一个交通咨询系统则主要采取图的结构来表示实际的交通网路。我们可以将其转换为一个源点到另一个源点的最短路径，这里我应用了floyd的算法。下图为简单交通线路成都上海包头兰州北京郑州徐州西安南昌昆明贵阳株洲 广州程序分别采用三

4、个结构体来存储信息。views存储车站信息车站身份编号车站名车站编码车站简称车站所属铁路线line存储铁路信息铁路编码铁路名字起始站编码终点站编码通行标志ways存储道路信息车站1车站2两站间距离也可以将以上信息也存入三个文件夹中，在程序中利用fread函数把信息从文件中读出赋给三个结构体。 在实现查找车站功能时，首先利用fread函数从文件中读取数据，再调用strcmp函数比较输入车站名与文件存贮的车站名，如果相同，就输出该车站名的相关信息。 实现最短路径时，利用floyd的算法。 在实现增加信息功能时可以利用fprintf函数和fscanf函数向文件中输入信息，同时文件中记录个数增加1.第

5、二章、全国铁路最短路径经由问题的具体实现2.1 需求分析1、可以直接向客户输出所有铁路和城市的信息2、可以为客户提供查询车站的功能3、可以为客户提供查询从一个车站到另一个车站的最短路径的功能4、可以及时增加新的铁路和车站信息。2.2 概要设计1、设计思路用文件存储信息，从文件中读取信息存储在views、lines、ways三个结构体中。再构造函数，分别实现输出、查询、最短路径、增加信息等功能。在用switch和while的循环语句来调用上述函数来实现功能，属于模块化实现功能。main增加车站信息增加铁路信息查询车站信息最短路径退出case1case2case3case4case52、设计方案r

6、eadviews ()、readlines、readways()函数分别实现输出车站、铁路、道路信息。从文件中读取信息赋给结构体，循环输出。search（）实现查询车站功能。利用fread函数把文件中的信息赋给结构体后，调用strcmp函数比较输入车站名，如果相同，就输出该车站的相关信息。add views ()函数实现增加车站信息，可以调用fwrite或者fprintf函数向文件中写入信息。 floyd（）函数实现最短路径的查询 addllines（）函数实现增加铁路线的信息，可以调用fwrite或者fprintf函数向文件中写入信息。 利用switch循环，在case1case5情况下，分

7、别调用以上函数的功能。 构建三个结构体，分别存放城市、铁路、道路的信息。数据结构中图的定义和术语为以下：adt graph数据对象v ：v是具有相同特性的数据元素的集合，称为顶点集。数据关系r：r=vrvr=|v,w(-v且p(v,w),表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息基本操作p：creategraph(&g,v,vr);初始条件：v是图的顶点集，vr是图中弧的集合。操作结果：按v和vr的定义构造图gdestroygraph(&g);初始条件：图g存在操作结果：销毁图glocatevex(g,u);初始条件：图g存在，u一g中顶点有相同特征操作结果：若g中存在顶点u, 则

8、返回该顶点在图中位置；否则返回其它信息。getvex(g,v);初始条件：图g存在，v是g中某个顶点操作结果：返回v的值。putvex(&g,v,value);初始条件：图g存在，v是g中某个顶点操作结果：对v赋值valuefirstadjvex(g,v);初始条件：图g存在，v是g中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在g中没有邻接顶点，则返回“空”nextadjvex(g,v,w);初始条件：图g存在,v是g中某个顶点,w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空insertvex(&g,v);初始条件：图g存在，v和图

9、中顶点有相同特征操作结果：在图g中增添新顶点vdeletevex(&g,v);初始条件：图g存在，v是g中某个顶点操作结果：删除g中顶点v及其相关的弧insertacr(&g,v,w);初始条件：图g存在，v和w是g中两个顶点操作结果：在g中增添弧,若g是无向的，则还增添对称弧deletearc(&g,v,w);初始条件：图g存在，v和w是g中两个顶点操作结果：在g中删除弧,若g是无向的，则还删除对称弧dfstraverser(g,v,visit();初始条件：图g存在，v是g中某个顶点，visit是顶点的应用函数操作结果：从顶点v起深度优先遍历图g，并对每个顶点调用函数visit一次。一旦v

10、isit()失败，则操作失败。bfstraverse(g,v,visit();初始条件：图g存在，v是g中某个顶点，visit是顶点的应用函数操作结果：从顶点v起广度优先遍历图g，并对每个顶点调用函数visit一次。一旦visit()失败，则操作失败。adt graph2.3详细设计1、定义结构体struct view_info 存放车站信息的结构体 int id; 车站身份编码 char name20; 车站名字 int code; 车站编码 char shortname20; 车站简写 char lname100; 车站所属的铁路线views size_view; struct line_

11、info 铁路信息 int lid; 铁路身份编码 char lname20; 铁路名字 int start_id; 起始车站编码 int end_id; 重点车站编码 int dist; 铁路线长度 char sign10; 通行标志linessize_line;struct way_info 道路信息 int station1; 车站1 int station2; 车站2 int dist; 两车站间距离wayssize_way;struct path_info 最短路径 int count; 最短路径的路径个数 int pathsize_view; 表明通过的车站 path_listsi

12、ze_viewsize_view ;2、输出车站信息首先打开views这个文件，用一个for循环，再调用fread函数把文件中的信息按照顺序赋给view_info结构体，再输出到终端上。其算法描述如下：void readviews() 打开文件views.txt文件 for（fread 函数对文件的信息读取赋给view_info结构体并且不为0)输出车站车站身份编码、车站名字、车站编码、车站简写、车站所属的铁路线记录文件中信息的个数关闭文件3、输出铁路信息void readlines() 打开文件lines.txt文件 for（fread 函数对文件的信息读取赋给line_info结构体并且不

13、为0)输出车站铁路身份编码、铁路名字、起始车站编码、终点站编码、通行标志记录文件中信息的个数关闭文件 4、输出道路的信息void readways() 打开文件ways.txt文件 for（fread 函数对文件的信息读取赋给way_info结构体并且不为0)输出车站1、车站2、两车站间距离记录文件中信息的个数关闭文件5、查询车站的功能void search()输入你要查询的车站名称打开文件viewsfor(i文件中记录个数)把文件中的信息赋给结构体调用strcmp比较结构体中车站名字与输入车站名字，如果两者相等输出该车站的相关信息如果查找到文件中的最后一个信息仍不能找到输出“不能找到所要查询

14、的车站“6、增加车站信息addviews()输入新车站身份编码、车站名字、车站编码、车站简写、车站所属的铁路线，并将其存入到view_info结构体中打开文件将该新信息写入到文件中7、增加铁路信息void addline() 输入新铁路身份编码、铁路名字、起始车站编码、终点站编码、通行标志，并将其存入到line_info结构体中打开文件将该新信息写入到文件中8、最短路径的实现floyd（）把所有路径的长度赋给一个二维数组，二维数组可以表示该路径的起始和终点把所有路径的起点和终点赋给i和j;在起始点和终点间找一点k,首先考虑（i，k）(k,j)是否存在，如如果存在，比较（i,j）与(i,k,j)

15、的长度，取长度较短者为i到j得一个最短路径。在路径上在加一个顶点也是如此比较，取较短者作为最短路径经过多次比较后，便会得到最短路径的顶点集合输出这些顶点的对应的车站名称9、实现所有函数功能main()输出铁路、车站、路径信息情况一：增加铁路信息情况二：增加车站信息情况三：查询车站信息情况四：查询最短路径情况五：退出2.4 测试分析1、测试数据views中的信息10000 beijingzhan 0 jing jingguangxianinghuxianjingbaoxianjinghaxianjingjiuxian10001 zhengzhouzhan 1 zheng jingguangxia

16、nlonghaixian10002 zhuzhouzhan 2 zhu jingguangxianxiangqianxian 10003 xuzhouzhan 3 xu jinghuxianlonghaixian 10004 shanghaizhan 4 hu jinghuxianhuhangxian10005 nanchangzhan 5 chang zheganxianjingjiuxian10006 xianzhan 6 xi ningxixianlonghaixianbaoxixian10007 baotouzhan 7 bao jingbaoxianbaolanxianbaoxixi

17、an10008 lanzhouzhan 8 lan longhaixian、baolanxian10009 chengduzhan 9 cheng baochengxianchengkunxianchengyuxian10010 guiyangzhan 10 gui xiangqianxian10011 guangzhouzhan 11 guang jingguangxianguangjiuxian10012 kunmingzhan 12 kun chengkunxianguikunxianline.txt的信息20000 jingguangxian 10000 10011 2294 11b2

18、0001 jinghuxian 10000 10004 1463 11b20002 jingbaoxian 10000 10007 810 11b20003 guikunxian 10010 10012 532 11b20004 chengkunxian 10009 10012 397 11b 20005 longhaixian 10003 10008 1759 11b20006 xiangqianxian 10002 10010 905 11bways.txt中的信息0 1 812 1 0 812 1 2 921 2 1 921 0 3 721 3 0 721 3 4 563 4 3 563

19、 1 4 981 4 1 981 4 5 357 5 4 357 2 5 471 5 2 471 1 6 671 6 1 671 0 7 392 7 0 392 7 8 975 8 7 975 6 8 290 8 6 290 6 9 561 9 6 561 9 12 291 12 9 291 10 12 376 12 10 376 2 10 469 10 2 4692、测试过程分别调用各个函数，输入一个车站名字，看是否能查询到车站信息。输入起始站点和终点站的代码，检测是否能查询到最短路径。增加新的车站和铁路信息，检测是否能够写入文件。3、测试结果能够查询到车站信息，并且最短路径也符合实际情况，

20、同时也可以向文件中添加新的车站和铁路信息。2.5用户使用说明1 程序运行环境程序名为railway.exe，运行环境为windows xp。2 主界面运行程序后首先显示图3-5-2 所示程序主界面。1、增加新的车站信息选择此项后，会出现以下的提示按照提示依次输入车站名字编码等，最终程序将会显示所有的信息，证明程序已经添加新的信息2、增加铁路信息将会出现以下界面按照提示依次输出，最终程序将会显示所有的信息，证明程序已经添加新的信息。3、查询车站信息会出现以下界面以上是查询到输入车站的情况，当输入的车站不能够查询到的时候，会出现以下提示4、查询最短路径时会出现以下提示然后输入起始站和终点站的编码，

21、就会有最短路径的出现2.6小结1 调试过程中遇到的主要问题及解决过程首先是在从文件中读取数据并存入到数组的过程中，因为文件中有中文，但因电脑解码器的问题最终输出的为乱码，所以最终只有把中文改成了英文。然后在最短路径的设计问题上，我没有考虑到双向的问题，所以导致图画的不合理。在增加信息到文件中的时候，信息增加到了文件的开头，我的目的是要增加到文件的末尾。程序中有些变量可以作为全局变量来定义，但是我却过多的定义了。2.7总结和体会这次的课程设计的内容是用c语言实现全国铁路最短路径经由问题，这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的铁路路线，但通过两个星期的设计也从中学到了不少东西，更

22、深刻的理解了课本中的内容。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻理解了c+中类的思想和实现，文件的概念和相关操作，以及有关数据结构的很多知识。根据实际问题的需要，对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的，良好的程序设计技能。提高综合运用所学知识的能力。在这次课程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这次的课程设计，在此要要感谢我的老师同学，他们为我提出了很多有用的建议，帮助我完成了这次的课

23、程设计。最后也要感谢我们学校为我们提供良好的编程环境，使我们能够按时完成任务。2.8 附录1、源程序代码#include#include#include#define size_view 70#define size_line 100#define size_way 300#define maxnode 30#define max 1000 struct view_info 存放车站信息的结构体 int id; 车站身份编码 char name20; 车站名字 int code; 车站编码 char shortname20; 车站简写 char lname100; 车站所属的铁路线views

24、size_view; struct line_info 铁路信息 int lid; 铁路身份编码 char lname20; 铁路名字 int start_id; 起始车站编码 int end_id; 重点车站编码 int dist; 铁路线长度 char sign10; 通行标志linessize_line;struct way_info 道路信息 int station1; 车站1 int station2; 车站2 int dist; 两车站间距离wayssize_way;struct path_info 最短路径 int count; 最短路径的路径个数 int pathsize_vi

25、ew; 表明通过的车站 path_listsize_viewsize_view ;void readviews() file *fp; int i; if(fp=fopen(views.txt,rb)=null) printf(ncannot open file strike any key exit!); exit(0); printf( id name code shortname lname n );for(i=0;fread(&viewsi,sizeof(struct view_info),1,fp)!=0;i+)printf(%d%-10s%d%-10s%dn, viewsi.id,

26、, viewsi.code, viewsi.shortname, viewsi.lname);view_count=i+1;fclose(fp); 把文件中的信息赋给station_info结构体,并且把车站信息输出到终端void readways() file *fp; int i; if(fp=fopen(ways.txt,rb)=null) printf(ncannot open file strike any key exit!); exit(0); printf(station1 station2 dist); for(i=0;isize_way;i+)fsca

27、nf(fp,%d%d%d,&waysi.station1,&waysi.station2,&waysi.dist);printf(%d %d %dn,waysi.station1,waysi.station2,waysi.dist); 把文件中的信息赋给way_info结构体,并且把道路信息输出到终端上 fclose(fp); void readlines() file *fp; int i; if(fp=fopen(lines.txt,rb)=null) printf(ncannot open file strike any key exit!); exit(0);printf(lid ln

28、ame start_id end_id dist sign);for(i=0; fread(&linesi,sizeof(struct line_info),1,fp)!=0;i+)printf(%d%-10s%d%-10d%d%-10sn, linesi.lid,linesi.lname,linesi.start_id, linesi.end_id, linesi.dist, linesi.sign);把文件中的信息赋给line_info结构体,并且把铁路信息输出到终端上line_count=i+1;fclose(fp);void search () file *fp; int i,mark

29、; char sta_name20; printf(please enter the station name:); scanf(%s,sta_name ) ; if(fp=fopen(views.txt,r+)=null) printf(ncannot open file strike any key exit!); exit(0);for(i=0;iview_count;i+)fread(&viewsi,sizeof(struct view_info),1,fp);fclose(fp); for(i=0;i view_count;i+) if(strcmp(sta_name,views i

30、.name)=0) printf(the stations informations is:n); printf( id name code shortname lname); printf(%d %s %d %s %d, viewsi.id,, viewsi.code, viewsi.shortname, viewsi.lname); break;对比输入的车名和结构体中车站名字，如果相同，就输出该车站的相关信息。 mark=i; if(mark=( view_count -1) printf(sorry,the station is not in here); voi

31、d addview() file *fp; int i; printf(please enter the new views informations:); printf(id:); scanf(%d,&viewsview_count.id); printf(name:); scanf(%s,viewsview_); printf(code); scanf(%d,&viewsview_count.code); printf(shortname:); scanf(%s,viewsview_count.shortname); printf(lname:); scanf(%s,

32、viewsview_count.lname); if(fp=fopen(views.txt,r+)=null) printf(ncannot open file strike any key exit!); exit(0); for(i=view_count;iview_count+1;i+) fwrite(&viewsi,sizeof(struct view_info),1,fp);将新的信息按顺序输入到文件中 fclose(fp); printf(successfully! the new station is added); printf(now station number is %d

33、:,view_count); void addway()file *fp; if(fp=fopen(ways.txt,r+)=null) printf(ncannot open file strike any key exit!); exit(0); printf(please enter the new ways informations:); printf(station1); scanf(%d,&waysway_count.station1); printf(station2:); scanf(%d,&waysway_count.station2); printf(dist:); sca

34、nf(%d,&waysway_count.dist); fprintf(fp,%d %d %d ,waysway_count.station1,waysway_count.station2,waysway_count.dist); 将新的路径信息输出到文件中 fclose(fp); printf(successfully! the new station is added); way_count=way_count+1; printf(now station number is:%d,way_count); void addline() file *fp; if(fp=fopen(lines.

35、txt,r+)=null) printf(ncannot open file strike any key exit!); exit(0); printf(please enter the new lines informations:); printf(lid:); scanf(%d,&linesline_count.lid); printf(lname:); scanf(%s,linesline_count.lname); printf(start_id:); scanf(%d,&linesline_count.start_id); printf(end_id:); scanf(%d,&l

36、inesline_count.end_id); printf(dist:); scanf(%d,&linesline_count.dist); printf(sign:); scanf(%s,linesline_count.sign); fprintf(fp,%d %s %d %d %d %s, linesline_count.lid, linesline_count.lname, linesline_count.start_id, linesline_count.end_id,linesline_count.dist, linesline_count.sign);将新的铁路信息输出到文件中

37、fclose(fp); printf(successfully! the new line is added); line_count=line_count+1; printf(now line number is:%d,line_count); void floyed() int i, j, k, m,t, start_num, end_num; int dist_listsize_viewsize_view; int shortestsize_viewsize_view; view_count=view_count+1; for(i=1;i=view_count;i+) for(j=1;j

38、=view_count;j+) dist_listij=maxcost; for( t=0;t=way_count;t+) i=wayst.station1; j=wayst.station2; dist_listij=wayst.dist;将路径长度赋给数组dist_list for (i =0; i view_count; i+) for (j= 0; jview_count; j+) if (i = j) dist_listij = 0; continue; dist_listij = -1; path_listij.count = 0; for (k = 0; k way_count; k+) if (waysk.station1 = i & waysk.station2 = j) dist_listij = waysk.dist; path_listij.count = 2; path_listij.path0 = i; path_listij.path1 = j; 把文件中的路径起始点和终点分别赋给i和j break; for (k = 0; k= view_count-1; k+) for (i = 0; i view_count; i+) for (j = 0; j view_count;