题目8：全国铁路运输网最佳经由问题

1、课程设计报告（本科）课程：数据结构学号：1210441019、1210441004 1210441020姓名：葛程、徐双双杜明辉班级：2012级物联网工程班教师：程敏时间：2014.01.02计算机科学与技术系设计名称：全国铁路运输网最佳经由问题设计内容、目的与要求：实验内容：铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离

2、该铁路线起点站路程及终点站路程。实验要求：（1）查询某站所属的铁路线（2）要求具备新增铁路线的管理功能（3）要求具备新增车站的管理功能（4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序计划与进度安排：11.1 11.10大体规划几部分函数，设计基本的铁路图，今后在基本图上实验铁路的基本管理功能。11.1111.30各组员完成自己的功能函数，并尽量达到要求。12.112.15 组员一起完成函数的组建及基本辅助函数功能的实现。12.1612.25 组员各自拿到所有的程序，开始个人调试与完善。12.2612.30 组员一起

3、讨论最后的方案，并做最后的优化。 设计过程、步骤（可加页）：一：设计过程：将铁路网抽象成图，然后查询中国现有的铁路网结构图，选取合适的站点数目，构造一个简单的铁路图，在构造的铁路图上实现设计的要求。用结构体创建图，然后再图的基础上实现算法要求。通过对题目的分析我们觉得会用到会用到数据结构的邻接矩阵的存储图的定义，图的遍历算法（深度优先遍历），两点间最短路径查询（迪杰斯特拉算法）。使用文件的存储方式，对数据进行存储。现行的铁路图：最后简单化的铁路网如下：typedef struct int id;char name20;char des100; vinfo;/站点typedef structin

4、t distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMAX_V_NUM;/邻接矩阵typedef struct vinfo vexsMAX_V_NUM;/站点数组AdjMatrix arcs;int vexnum,arcnum;MGraph;/图 主函数客货运及两个站点的最短路径查询函数站点查询介绍函数站点、铁路线的管理函数客运查询站点管理路线管理货运查询两站间查询二：函数的声明和调用:void welcome();/欢迎界面void search_vex_info();/站点信息介绍void search_rantwo_short();/查询任意两个

5、站点之间的一条最短简单路径void map_manage();/站点线路修改扩充void search_two_allpath();/查询两站点间所有路径void search_kh_path();/客货运类别路径查询void about();/关于void create_map();/初始化地图void save_map();/将程序中的图结构体写入数据文件int input_num_check(int min,int max);/数字输入检验void shortest_path_ota(int begin);/生成某一站点到所有其它站点的最短路径数据void print_fgx();/输出

6、独占一行的分割线void map_add_vex();/新增站点void map_add_road();/新增道路void map_revise_vex();/修改站点void map_revise_road();/修改道路(引导界面)void map_reroad_in(int vid);/修改道路(公用嵌入函数)void map_delete_vex();/删除站点void map_delete_road();/删除道路(引导界面)void map_re_arc(int bid,int fid,int kind,int xid);/修改道路(模块函数) 若修改终点:调用前需确保xid(新终

7、点)与原终点不相同void map_de_arc(int bid,int fid);/删除道路(模块函数)void DFS_allpath(int bid,int fid,int k);/寻找两点间所有路径并输出void search_kh_kh(int kind);/查找所有符合类别的路径void DFS_allpath_kh(int bid,int fid,int k,int kind);/寻找两点间所有路径并判断该路径上到道路是否全为客/货运线路 int DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind);/人客/货运线路 判断较长路

8、径是否完全包含较短路径int DFS_allpath_kh_test(int a_i,int b_i)结果与分析（可以加页）： 设计体会与建议： 这次的程序软件基本上运行成功，可以简单的对已经输入的数据进行计算，求全国铁路运输网最佳经由。但是程序较小，功能不全面，只是理论，并未实践。经过这次课程设计，通过对程序的编制，调试和运行，使我更好的掌握了图基本性质和关于选址问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现

9、。课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。 在整个课程程序中，我们充分应用和调用各个程序模块，从而实现了此次程序设计的所应该有的功能。在本组看来这就是我们在课程设计是比较成功的，而在这个过程中，让我们感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们自主的去学习。附录：#include <stdio.h>#

10、include <string.h>#include <stdlib.h>#include <ctype.h>#include <math.h>#include <io.h>#include <conio.h>#define MAX_V_NUM 100#define MAX 60000typedef struct int id;char name20;char des100; vinfo;/站点typedef structint distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMA

11、X_V_NUM;/邻接矩阵typedef struct vinfo vexsMAX_V_NUM;/站点数组AdjMatrix arcs;int vexnum,arcnum;MGraph;/图MGraph G;/图Gint input_exit = 0;/退出操作 /ota最短路径存储用变量 int PMAX_V_NUMMAX_V_NUM; /最短路径中间点记录int DMAX_V_NUM; /到各点的最短路径int SorderMAX_V_NUM; /最短路径根点由小到大排序/路径探寻存储用变量(使用前后必须重置为0)int pathMAX_V_NUM; /路径站点int visitedMAX

12、_V_NUM; /访问标志int path_num; /所有路径数int best_l; /目前最短的总长度int bestl_num; /目前总长度最短的路径途经站点个数/客运货运路径函数用存储数组int path_khMAX_V_NUMMAX_V_NUM;/存储暂时满足条件的客货运路径int path_kh_vnumMAX_V_NUM;/记录每条路径途经的站点数int path_num_bak;/备份所有路径数/* 函数声明*/void welcome();/欢迎界面void search_vex_info();/站点信息介绍void search_rantwo_short();/查询任意

13、两个站点之间的一条最短简单路径void map_manage();/站点线路修改扩充/void search_two_allpath();/查询两站点间所有路径void search_kh_path();/客货运类别路径查询void create_map();/初始化地图void save_map();/将程序中的图结构体写入数据文件int input_num_check(int min,int max);/数字输入检验void shortest_path_ota(int begin);/生成某一站点到所有其它站点的最短路径数据void print_fgx();/输出独占一行的分割线void

14、map_add_vex();/新增站点void map_add_road();/新增道路void map_revise_vex();/修改站点void map_revise_road();/修改道路(引导界面)void map_reroad_in(int vid);/修改道路(公用嵌入函数)void map_delete_vex();/删除站点void map_delete_road();/删除道路(引导界面)void map_re_arc(int bid,int fid,int kind,int xid);/修改道路(模块函数) 若修改终点:调用前需确保xid(新终点)与原终点不相同void

15、 map_de_arc(int bid,int fid);/删除道路(模块函数)void DFS_allpath(int bid,int fid,int k);/寻找两点间所有路径并输出void search_kh_kh(int kind);/查找所有符合类别的路径void DFS_allpath_kh(int bid,int fid,int k,int kind);/寻找两点间所有路径并判断该路径上到道路是否全为客/货运线路 int DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind);/人客/货运线路 判断较长路径是否完全包含较短路径in

16、t DFS_allpath_kh_test(int a_i,int b_i);/输出前检测 判断较长路径是否完全包含较短路径void main() int step = -1,choose = 1;create_map();do welcome();printf("请输入功能序号:");step = input_num_check(0,3);if(input_exit = 1) input_exit = 0;step = -1;choose = 0;else switch(step)case 1:search_vex_info();break;case 2:map_mana

17、ge();break;case 3:search_kh_path();break;default:choose = 0; while(choose != 0);printf("n*n您已成功退出,欢迎下次使用,再见!n按任意键关闭窗口");getch();/在你需要暂停的位置暂停一下，当你按一下任意键它又会继续往下执行！void welcome() int i;printf("*n");printf(" n");printf(" 全国铁路网最佳经由系统 n");printf(" n");prin

18、tf(" <功能选择列表> n");printf(" 1.站点介绍查询 n");printf(" 2.站点道路修改扩充 n");printf(" 3.客货查询 n");printf(" 0.退出系统 n");printf(" n");printf("*n");/printf("共有%d个站点 %d条道路 最大值MAX为%d 最多%d个顶点",G.vexnum,G.arcnum,MAX,MAX_V_NUM);print_fgx

19、();printf("可供查询的站点:n");for(i=0;i<G.vexnum;i+) printf("【%d】%s ",G.vexsi.id,G.); if(i%5 = 4 && i != 0) printf("n");print_fgx();void search_vex_info()int vid; do printf("请输入站点ID(e:退出):"); vid = input_num_check(0,G.vexnum-1); if(input_exit = 1

20、) input_exit = 0; system("cls"); return; print_fgx();printf("站点【%s】介绍:%s",G.,G.vexsvid.des);print_fgx();while(1);void search_rantwo_short()int bid,fid,i,j; do printf("请输入起点ID(e:退出):"); bid = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0; sy

21、stem("cls");return; printf("请输入终点ID(e:退出):");fid = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0; system("cls"); return;shortest_path_ota(bid); print_fgx();printf("【%d】%s 到 【%d】%s 的最短路径:",G.vexsbid.id,G.,G.vexsfid.id,G.vexsfid.nam

22、e);print_fgx();for(i=0;i<G.vexnum;i+) j = Sorderi;if(Pfidj = 1) printf("【%d】%s->",G.vexsj.id,G.); printf("全程共%dkm",Dfid);print_fgx();while(1);void map_manage()int select;do printf("(1.新增站点 2.新增线路 3.修改站点 4.修改线路 5.删除站点 6.删除线路 e:退出)n请输入操作编号:");select = inpu

23、t_num_check(1,6);if(input_exit = 1) input_exit = 0;system("cls");return;switch(select) case 1:map_add_vex();break;case 2:map_add_road();break;case 3:map_revise_vex();break;case 4:map_revise_road();break;case 5:map_delete_vex();break;case 6:map_delete_road();break;default:exit(1);while(1);v

24、oid search_kh_path()int select;int sign=0;do printf("(1.货运 2.客运 3两站间最短路径查询 e:退出)n请输入操作编号:");select = input_num_check(1,3);if(input_exit = 1)input_exit = 0;system("cls");return;switch(select)case 1:search_kh_kh(1);break;case 2:search_kh_kh(2);break;case 3:search_rantwo_short();bre

25、ak;default:exit(1);while(1);/初始化地图void create_map()if(access("mmapdata.mdat",0) = 0) FILE *fp;fp = fopen("mmapdata.mdat","rb");if(!fp) printf("n数据文件打开失败!n"); exit(1);fread(&G,sizeof(MGraph),1,fp);fclose(fp);else int i,j;/站点数与道路数赋值G.vexnum = 16;G.arcnum = 2

26、0;/站点编号赋值for(i=0;i<G.vexnum;i+)G.vexsi.id = i;/站点名称赋值strcpy(G.,"北京站");strcpy(G.,"郑州站");strcpy(G.,"株洲站");strcpy(G.,"广州站");strcpy(G.,"天津站");strcpy(G.,"连云港站");strcpy(G.,&

27、quot;上海站");strcpy(G.,"南昌站");strcpy(G.,"九龙站");strcpy(G.,"包头站");strcpy(G.,"乌鲁木齐站");strcpy(G.,"兰州站");strcpy(G.,"宝鸡站");strcpy(G.,"成都站");strcpy(G.vexs14.nam

28、e,"昆明站");strcpy(G.,"贵阳");/站点介绍赋值strcpy(G.vexs0.des,"京广线、京九线、京哈线等、");strcpy(G.vexs1.des,"京广线");strcpy(G.vexs2.des,"京广线");strcpy(G.vexs3.des,"京广线");strcpy(G.vexs4.des,"有待补充");strcpy(G.vexs5.des,"有待补充");strcpy(G.

29、vexs6.des,"有待补充");strcpy(G.vexs7.des,"京九线");strcpy(G.vexs8.des,"京九线");strcpy(G.vexs9.des,"京包线");strcpy(G.vexs10.des,"有待补充");strcpy(G.vexs11.des,"有待补充");strcpy(G.vexs12.des,"有待补充");strcpy(G.vexs13.des,"有待补充");strcpy(G.vex

30、s14.des,"有待补充");strcpy(G.vexs15.des,"有待补充");for(i=0;i<MAX_V_NUM;i+)for(j=0;j<MAX_V_NUM;j+)G.arcsij.distance = MAX;G.arcs01.distance=300;G.arcs01.kind=1;G.arcs04.distance=100;G.arcs04.kind=2;G.arcs09.distance=300;G.arcs09.kind=2;G.arcs15.distance=400;G.arcs15.kind=1;G.arcs11

31、2.distance=200;G.arcs112.kind=1;G.arcs12.distance=300;G.arcs12.kind=1;G.arcs23.distance=400;G.arcs23.kind=1;G.arcs27.distance=300;G.arcs27.kind=2;G.arcs215.distance=250;G.arcs215.kind=2;G.arcs45.distance=200;G.arcs45.kind=2;G.arcs56.distance=300;G.arcs56.kind=2;G.arcs67.distance=200;G.arcs67.kind=2;

32、G.arcs78.distance=500;G.arcs78.kind=2;G.arcs911.distance=350;G.arcs911.kind=2;G.arcs1011.distance=800;G.arcs1011.kind=1;G.arcs1112.distance=200;G.arcs1112.kind=1;G.arcs1213.distance=300;G.arcs1213.kind=2;G.arcs1314.distance=200;G.arcs1314.kind=2;G.arcs1415.distance=350;G.arcs1415.kind=2;for(i=0;i<

33、;G.vexnum;i+)for(j=0;j<G.vexnum;j+)if(i>j)G.arcsij = G.arcsji;save_map();/将程序中的图结构体写入数据文件void save_map()FILE *fp;fp = fopen("mmapdata.mdat","wb");if(!fp)printf("n数据文件打开失败!n"); exit(1);fwrite(&G,sizeof(MGraph),1,fp);fclose(fp);/数字输入检验int input_num_check(int min

34、,int max) int id,isright=0; do scanf("%d",&id);if(id<=max && id>=min) isright = 1;else if(getchar() = 'e') input_exit = 1;return 0;printf("输入有误,请重新输入(e:退出):");while(isright != 1);return id;void print_fgx()printf("n-n");void shortest_path_ota(in

35、t begin) /Dijkstra(迪杰斯特拉)算法 int i,k=0,v,w,finalMAX_V_NUM,min,m;/初始化for(v=0;v<G.vexnum;v+) finalv = 0; Dv = G.arcsbeginv.distance;for(w=0;w<G.vexnum;w+) Pvw = 0; if(Dv<MAX) Pvbegin = 1; Pvv = 1; Dbegin = 0; finalbegin = 1; Sorderk = begin;for(i=1;i<G.vexnum;i+) min = MAX;for(w=0;w<G.ve

36、xnum;w+) if(!finalw) if(Dw<min) v = w; min = Dw; finalv = 1; if(v != begin) k+; Sorderk = v; /记录最短路径递增的站点队列for(w=0;w<G.vexnum;w+) if(!finalw && (min + G.arcsvw.distance < Dw) Dw = min + G.arcsvw.distance;for(m=0;m<G.vexnum;m+) Pwm = Pvm;Pww = 1; void DFS_allpath(int bid,int fid,i

37、nt k)int i,j;if(pathk = fid) for(i=0;i<k;i+) printf("【%d】%s ->",G.vexspathi.id,G.);printf("【%d】%s",G.vexspathk.id,G.);print_fgx();path_num+;elsefor(j=0;j<G.vexnum;j+) if(G.arcspathkj.distance<MAX && visitedj=0) visitedj = 1;pathk+1

38、= j;DFS_allpath(bid,fid,k+1);visitedj = 0; /退回上一节点 void map_add_vex()int vid=G.vexnum;int ifgo,order,nearid,newroad=0;do if(vid>=MAX_V_NUM)printf("站点数已达到最大值%d,按任意键返回!",MAX_V_NUM);getchar();getchar();system("cls");welcome();return;printf("新站点的编号为【%d】,是否继续?(1.继续 e:退出):"

39、;,vid);ifgo = input_num_check(1,1);if(input_exit = 1) input_exit = 0;system("cls");welcome();return;G.vexsvid.id = vid;printf("请输入新站点的名称:");scanf("%s",&G.);printf("请输入新站点的介绍:");scanf("%s",&G.vexsvid.des);printf("添加站点成功!"

40、);print_fgx();G.vexnum+;G.arcnum+=newroad;save_map();vid+;while(1);void map_add_road()int bid,fid;do printf("请输入新增道路起始站点ID(e:退出):");bid = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0;system("cls");welcome();return;printf("请输入新增道路终止站点ID(e:退出):");fid =

41、input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0;system("cls");welcome();return;if(fid = bid) printf("终点与起点重复!n");continue;if(G.arcsbidfid.distance<MAX) printf("道路已存在!n");continue;print_fgx();printf("您正在添加道路【%d】%s ->【%d】%s:n",G.vexsbid.id,

42、G.,G.vexsfid.id,G.);printf("请输入新建道路的长度（km）:");scanf("%d",&G.arcsbidfid.distance);printf("请输入新建道路的类型(1.货运 2.客运):");scanf("%d",&G.arcsbidfid.kind);printf("添加道路成功!");print_fgx();G.arcsfidbid = G.arcsbidfid;G.arcnum+;save_

43、map(); while(1);void map_revise_vex()int vid,choose,i;do printf("请输入需要修改的站点ID(e:退出):");vid = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0;system("cls");welcome();return;print_fgx();printf("站点信息预览:【%d】%s 介绍:%s n",G.vexsvid.id,G.,G.vexsvid.d

44、es);print_fgx();for(i=0;i<G.vexnum;i+) if(G.arcsvidi.distance<MAX) printf("【%d】%s ->【%d】%s 道路信息:长度 %dkm ",G.vexsvid.id,G.,G.vexsi.id,G.,G.arcsvidi.distance);if(G.arcsvidi.kind = 1) printf("类型 货运"); else printf("类型 客运");print_fgx();printf(&

45、quot;请输入需要修改的对象(1.名称 2.信息 3.线路):");scanf("%d",&choose);if(choose = 1) printf("请输入新的站点名称:"); scanf("%s",&G.);else if(choose = 2) printf("请输入新的站点信息:"); scanf("%s",&G.vexsvid.des); else if(choose = 3) map_reroad_in(vid); els

46、e printf("输入错误!n"); continue; save_map();print_fgx();printf("修改成功!n");while(1);/修改道路(引导界面)void map_revise_road()int vid;do printf("请输入需要修改的道路的起点(e:退出):");vid = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0;system("cls");welcome();return;map_r

47、eroad_in(vid);save_map();print_fgx();printf("修改成功!n");while(1);/修改道路void map_reroad_in(int vid)int fid,ekind,pass=0,passt=1;do printf("请输入需要修改的道路的终点(e:退出):"); fid = input_num_check(0,G.vexnum-1); if(input_exit = 1) input_exit = 0; else if(G.arcsvidfid.distance = MAX | fid = vid) prin