全国铁路运输网最佳经由问题课程设计报告

中南大学数据结构课程设计报告 题 目 全国铁路运输网最佳经由问题 学生姓名 卢达明 指导教师 林立新 学 院 信息科学与工程学院 学 号 专业班级 通信工程1001班 完成时间 2012年7月3号 目录第1章 课程设计题目 31.1 问题描述1.2 基本要求 第2章 全国铁路运输网最佳经由问题52.1数据结构的设计2.2 软件模块结构图2.3 程序设计思想2.4 程序流程图2.5 源程序第3章 程序的调试与分析与使用573.1调试分析与测试数据3.2用户使用手册第4章 心得体会674.1 心得体会第1章 课程设计题目 1.1问题描述该题目采用我国铁路运输网的数据进行编程和运行验证。图如下(详细可在网上搜索全国铁路局管辖线路示意图)，可以不要这么详细，只要全国的主干线就可以了。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。1.2基本要求（1） 基本要求 查询某站所属的铁路线（2） 要求具备新增铁路线的管理功能（3） 要求具备新增车站的管理功能（4） 针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序第二章 全国铁路运输网最佳经由问题2.1数据结构的设计 本次采用了邻接矩阵的结构体和图的结构体用以存储图形数据。且本次图应为无相图。定义如下。typedef struct int id;char name20;char des100; vinfo;/站点typedef struct int distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMAX_V_NUM;/邻接矩阵typedef struct vinfo vexsMAX_V_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;/图最短路径查询：迪杰斯特拉算法。两站之间的所有路径：深度优先遍历。2.2软件模块结构图 123 452.3程序设计思想核心问题: 求最短路径(我们的程序参考的是数据结构课本中的“迪杰斯特拉算法”)数据模型（逻辑结构）: 带权无向图 。（采用2.1中所述的结构体，并且本程序采用的是文件存储数据。初次运行时需要写入站点和线路以及各方面的信息。在之后的操作中，进行的各种信息更改都会在程序运行中自动保存到文件中。）根据6的基本功能编写6个函数，再根据各个函数所需实现的功能编写所需的嵌套的函数。逐层解决。最后进行调试运行。2.4程序流程图int main(); /主函数void welcome(); /欢迎界面void search_vex_info();/站点信息介绍void search_rantwo_short();/查询任意两个站点之间的一条最短简单路径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 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 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);/人客/货运线路 判断较长路径是否完全包含较短路径int DFS_allpath_kh_test(int a_i,int b_i);/输出前检测 判断较长路径是否完全包含较短路径2.5源程序 /* 引用系统头文件*/#include #include #include #include #include #include #include /* 宏定义*/#define MAX_V_NUM 100#define MAX 60000/* 结构体定义*/typedef struct int id;char name20;char des100; vinfo;/站点typedef struct int distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMAX_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_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();/查询任意两个站点之间的一条最短简单路径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();/输出独占一行的分割线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(新终点)与原终点不相同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);/人客/货运线路 判断较长路径是否完全包含较短路径int DFS_allpath_kh_test(int a_i,int b_i);/输出前检测 判断较长路径是否完全包含较短路径/* 主函数 次主函数*/int main() int step = -1,choose = 1;create_map();do welcome();printf(请输入功能序号:);step = input_num_check(0,6);if(input_exit = 1) input_exit = 0;step = -1;choose = 0;else switch(step) case 1:search_vex_info();break;case 2:search_rantwo_short();break;case 3:search_two_allpath();break;case 4:map_manage();break;case 5:search_kh_path();break;case 6:about();break;default:choose = 0; while(choose != 0);printf(n*n您已成功退出,欢迎下次使用,再见!n按任意键关闭窗口);getch();void welcome() int i;printf(*n);printf(* *n);printf(* 全国铁路网最佳经由系统 *n);printf(* *n);printf(* *n);printf(* 1.站点介绍查询 *n);printf(* 2.两站点最短路径查询 *n);printf(* 3.两站点所有路径查询 *n);printf(* 4.站点道路修改扩充 *n);printf(* 5.客货运路径查询 *n);printf(* 6.关于 *n);printf(* 0.退出系统 *n);printf(* *n);printf(*n);printf(共有%d个站点 %d条道路 最大值MAX为%d 最多%d个顶点,G.vexnum,G.arcnum,MAX,MAX_V_NUM);print_fgx();printf(可供查询的站点:n);for(i=0;iG.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) 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; system(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.);print_fgx();for(i=0;i,G.vexsj.id,G.); printf(全程共%dkm,Dfid);print_fgx();while(1);void search_two_allpath()int bid,fid,i; do printf(请输入起点ID(e:退出):); bid = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0; system(cls); return; printf(请输入终点ID(e:退出):); fid = input_num_check(0,G.vexnum-1); if(input_exit = 1) input_exit = 0; system(cls); return; if(bid = fid) printf(终点与起点相同!n);continue; for(i=0;iMAX_V_NUM;i+) pathi = 0;visitedi = 0;path_num = 0;visitedbid = 1;path0 = bid;print_fgx();printf(【%d】%s 到 【%d】%s 的所有路径:,G.vexsbid.id,G.,G.vexsfid.id,G.);print_fgx();DFS_allpath(bid,fid,0);printf(共找到%d条路径,path_num);print_fgx();for(i=0;iMAX_V_NUM;i+) pathi = 0; visitedi = 0;path_num = 0;while(1);void map_manage()int select;do printf(1.新增站点 2.新增线路 3.修改站点 4.修改线路 5.删除站点 6.删除线路 e:退出)n请输入操作编号:);select = input_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);void search_kh_path()int select;int sign=0;do printf(1.货运 2.客运 e:退出)n请输入操作编号:);select = input_num_check(1,2);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;default:exit(1);while(1);void about()system(cls);printf(n);printf( n);printf( 中南大学 n);printf( 全国铁路网最佳经由系统 n);printf( 姓名 n);printf( 信息科学与工程学院 n);printf( 班级 n);printf( n);printf(n);printf( 按任意键返回:);getch();system(cls);/* 地图的初始化与保存*/初始化地图void create_map()if(access(mapdata.mdat,0) = 0) FILE *fp;fp = fopen(mapdata.mdat,rb);if(!fp) printf(n数据文件打开失败!n); exit(1);fread(&G,sizeof(MGraph),1,fp);fclose(fp);else int i,j;/站点数与道路数赋值G.vexnum = 15;G.arcnum = 20;/站点编号赋值for(i=0;iG.vexnum;i+)G.vexsi.id = i;/站点名称赋值strcpy(G.,郑州站);strcpy(G.,兰州站);strcpy(G.,呼和浩特站);strcpy(G.,北京站);strcpy(G.,天津站);strcpy(G.,徐州站);strcpy(G.,上海站);strcpy(G.,南昌站);strcpy(G.,株洲站);strcpy(G.,柳州站);strcpy(G.,贵阳站);strcpy(G.,昆明站);strcpy(G.,成都站);strcpy(G.,西安站);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.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.vexs14.des,地方打工);for(i=0;iMAX_V_NUM;i+)for(j=0;jMAX_V_NUM;j+)G.arcsij.distance = MAX;G.arcs12.distance = 1145; G.arcs12.kind = 2;G.arcs23.distance = 668; G.arcs23.kind = 2;G.arcs34.distance = 137; G.arcs34.kind = 1;G.arcs45.distance = 674; G.arcs45.kind = 2;G.arcs56.distance = 651; G.arcs56.kind = 2;G.arcs67.distance = 825; G.arcs67.kind = 2;G.arcs78.distance = 367; G.arcs78.kind = 1;G.arcs89.distance = 672; G.arcs89.kind =2;G.arcs910.distance = 607; G.arcs910.kind = 2;G.arcs1011.distance = 639; G.arcs1011.kind = 1;G.arcs1112.distance = 1100; G.arcs1112.kind = 1;G.arcs1213.distance = 842; G.arcs1213.kind = 2;G.arcs113.distance = 676; G.arcs113.kind = 2;G.arcs013.distance = 511; G.arcs013.kind = 2;G.arcs03.distance = 392; G.arcs03.kind = 2;G.arcs014.distance = 534; G.arcs014.kind = 1;G.arcs05.distance = 349; G.arcs05.kind = 2;G.arcs814.distance = 409; G.arcs814.kind = 2;G.arcs1012.distance = 967; G.arcs1012.kind = 2;G.arcs810.distance = 907; G.arcs810.kind = 2;for(i=0;iG.vexnum;i+)for(j=0;jj)G.arcsij = G.arcsji;save_map();/将程序中的图结构体写入数据文件void save_map()FILE *fp;fp = fopen(mapdata.mdat,wb);if(!fp)printf(n数据文件打开失败!n); exit(1);fwrite(&G,sizeof(MGraph),1,fp);fclose(fp);/* 辅助功能函数*/数字输入检验int input_num_check(int min,int max) int id,isright=0; do scanf(%d,&id);if(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(int begin) /Dijkstra(迪杰斯特拉)算法 int i,k=0,v,w,finalMAX_V_NUM,min,m;/初始化for(v=0;vG.vexnum;v+) finalv = 0; Dv = G.arcsbeginv.distance;for(w=0;wG.vexnum;w+) Pvw = 0; if(DvMAX) Pvbegin = 1; Pvv = 1; Dbegin = 0; finalbegin = 1; Sorderk = begin;for(i=1;iG.vexnum;i+) min = MAX;for(w=0;wG.vexnum;w+) if(!finalw) if(Dwmin) v = w; min = Dw; finalv = 1; if(v != begin) k+; Sorderk = v; /记录最短路径递增的站点队列for(w=0;wG.vexnum;w+) if(!finalw & (min + G.arcsvw.distance Dw) Dw = min + G.arcsvw.distance;for(m=0;mG.vexnum;m+) Pwm = Pvm;Pww = 1; void DFS_allpath(int bid,int fid,int k)int i,j;if(pathk = fid) for(i=0;i,G.vexspathi.id,G.);printf(【%d】%s,G.vexspathk.id,G.);print_fgx();path_num+;elsefor(j=0;jG.vexnum;j+) if(G.arcspathkj.distance=MAX_V_NUM)printf(站点数已达到最大值%d,按任意键返回!,MAX_V_NUM);getchar();getchar();system(cls);welcome();return;printf(新站点的编号为【%d】,是否继续?(1.继续 e:退出):,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(添加站点成功!);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 = input_num_check(0,G.vexnum-1);if(input_exit = 1) input_exit = 0;system(cls);welcome();return;if(fid = bi