題目8：全國鐵路運輸網(wǎng)最佳經(jīng)由問題

1、課程設計報告（本科）課程: 學號: 姓名: 班級: 教師: 時間:數(shù)據(jù)結構1210441019 12104410041210441020葛程、徐雙雙杜明輝2012級物聯(lián)網(wǎng)工程班程敏2014.01.02計算機科學與技術系設計名稱：全國鐵路運輸網(wǎng)最佳經(jīng)由問題 設計內容、目的與要求：實驗內容:鐵路運輸網(wǎng)絡中由鐵路線和火車站的兩個主要概念，譬如：1號鐵路線表示京廣線，2號鐵路線表示京滬線等。鐵路線對象包括鐵路線編號，鐵路線名稱，起始站編號，終點站編號，該鐵路 線長度，通行標志(00B客貨運禁行，01B貨運通行專線，10B客運通行專線，11B 客貨運通行)。火車站對象包括所屬鐵路線編號，車站代碼，車站名

2、，車站簡稱，離該鐵路 線起點站路程及終點站路程。實驗要求：(1)查詢某站所屬的鐵路線(2)要求具備新增鐵路線的管理功能(3)要求具備新增車站的管理功能(4)針對客運，貨運情況能計算任何一個起始車站到任何一個終點站之間的最 短路徑。并且要求能夠顯示出該最短路徑的各個火車站的經(jīng)由順序 計劃與進度安排：11.1 11.10大體規(guī)劃幾部分函數(shù)，設計基本的鐵路圖，今后在基本圖上實 驗鐵路的基本管理功能。11.11 11.30各組員完成自己的功能函數(shù)，并盡量達到要求。12.1 12.15組員一起完成函數(shù)的組建及基本輔助函數(shù)功能的實現(xiàn)。12.16 12.25組員各自拿到所有的程序，開始個人調試與完善。12.

3、26 12.30組員一起討論最后的方案，并做最后的優(yōu)化。設計過程、步驟(可加頁)：一：設計過程：將鐵路網(wǎng)抽象成圖，然后查詢中國現(xiàn)有的鐵路網(wǎng)結構圖，選取合適的站點數(shù)目， 構造一個簡單的鐵路圖，在構造的鐵路圖上實現(xiàn)設計的要求。用結構體創(chuàng)建圖， 然后再圖的基礎上實現(xiàn)算法要求。通過對題目的分析我們覺得會用到會用到數(shù)據(jù) 結構的鄰接矩陣的存儲圖的定義，圖的遍歷算法(深度優(yōu)先遍歷)，兩點間最短路徑查詢(迪杰斯特拉算法)。使用文件的存儲方式，對數(shù)據(jù)進行存儲。32現(xiàn)行的鐵路圖:產(chǎn)艮武上想r.k-* I *一工*卜甲蟲冒蒯、品E加噌舶T*升na 夫qJtwi/E恤工” 11 f 口. 4i.fta 2*i、勺I“

4、3單強門戶WAfe 工*， 產(chǎn)胃下盟 :矍 .，, I*白把修 ,WfKN最后簡單化的鐵路網(wǎng)如下:typedef structint id;char name20;char des100;vinfo;/ 站點 typedef struct int distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMAX_V_NUM; 令口接矩陣 typedef structvinfo vexsMAX_V_NUM;/ 站點數(shù)組AdjMatrix arcs;int vexnum,arcnum;MGraph;/ 圖二：函數(shù)的聲明和調用：void welcome。;/歡迎界面v

5、oid 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();/將程序中的圖結構體寫入數(shù)據(jù)文件int input_num_check(int min,int max);/數(shù)字輸入檢驗void shorte

6、st_path_ota(int begin);/ 生成某一站點到所有其它站點的最短路 徑數(shù)據(jù)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);/ 修改道路(公用嵌入函數(shù))void map_delete_vex();/ 刪除站點void map_delete_road();/ 刪除道路(引導界面)void map_r

7、e_arc(int bid,int fid,int kind,int xid);/修改道路(模塊函數(shù))若修改終點：調用前需確保xid(新終點)與原終點不相同void map_de_arc(int bid,int fid);/刪除道路(模塊函數(shù))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);/尋找兩點間所有路徑并判斷該路徑上到道路是否全為客/貨運線路in

8、t DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind);/人客/ 貨運線路判斷較長路徑是否完全包含較短路徑int DFS_allpath_kh_test(int a_i,int b_i)結果與分析(可以加頁)：b l g 允E P4藝七 二| T可 x可供喜迎妁苦點: ,場】北京B.Jl1鄭州工0北京；仁糙鸚/占當尚 口】廣州藍 口【天津站 鼻血,餐褊超包酒Hi后廣電站點北京站介招二京廣技 京九弒、京哈線等、 ,清輸入謠點1D3;退出區(qū), E:作業(yè) DebugX5Up.eKE需柒殺竄魯;兩站間最短路徑查詢 量人起點ID 退出 就人終點退出）

9、;30 :退出）SBa喘藕翰昆明站E151貴糖01北京站到r31廣州站的最短路徑二M d匕京站一 CiJ Wh|3fi- 12株洲站一13】廣州站一涇程共10酬風 贏入j西益k退出”口cl請請請充目查修 變川道查系 B點點貸出 站至某可供查詢的站點二B北氮4】連基H】株也設計體會與建議：這次的程序軟件基本上運行成功，可以簡單的對已經(jīng)輸入的數(shù)據(jù)進行計算， 求全國鐵路運輸網(wǎng)最佳經(jīng)由。但是程序較小，功能不全面，只是理論，并未實踐 經(jīng)過這次課程設計，通過對程序的編制，調試和運行，使我更好的掌握了圖基本 性質和關于選址問題的解決方法，熟悉了各種調用的數(shù)據(jù)類型，在調試和運行過 程中使我更加的了解和熟悉程序

10、運行的環(huán)境， 提高了我對程序調試分析的能力和對錯誤的糾正能力。這次數(shù)據(jù)結構的程序設計，對于我來說是一個挑戰(zhàn)。我對數(shù)據(jù)結構的學習在程序的設計中也有所體現(xiàn)。 課程設計是培養(yǎng)學生綜合運用所學知 識、發(fā)現(xiàn)、提出、分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié)，是對學生實 際工作能力的具體訓練和考察過程。 隨著科學技術發(fā)展的日新月異，當今計算機 應用在生活中可以說得是無處不在。因此作為二十一世紀的大學來說掌握計算機 開發(fā)技術是十分重要的。在整個課程程序中，我們充分應用和調用各個程序模塊，從而實現(xiàn)了此次程 序設計的所應該有的功能。在本組看來這就是我們在課程設計是比較成功的， 而 在這個過程中，讓我們感覺收獲最

11、大的就是我們都能利用這次課程設計學到很多 我們在課本上沒有的知識，充分的發(fā)揮了我們的主動性，使我們自主的去學習。附錄：#include #include #include #include #include #include #include #define MAX_V_NUM 100#define MAX 60000 typedef structint id;char name20;char des100;vinfo;/ 站點typedef structint distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMAX_V_NUM;/ 鄰接矩陣typed

12、ef structvinfo vexsMAX_V_NUM;/ 站點數(shù)組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; /

13、 訪問標志int path_num; / 所有路徑數(shù)int best_l; / 目前最短的總長度int bestl_num; / 目前總長度最短的路徑途經(jīng)站點個數(shù)/客運貨運路徑函數(shù)用存儲數(shù)組int path_khMAX_V_NUMMAX_V_NUM;/ 存儲暫時滿足條件的客貨運路徑int path_kh_vnumMAX_V_NUM;/ 記錄每條路徑途經(jīng)的站點數(shù)int path_num_bak;/ 備份所有路徑數(shù)/*函數(shù)聲明*/void welcome();/ 歡迎界面void search_vex_info();/ 站點信息介紹void search_rantwo_short();/ 查詢任意

14、兩個站點之間的一條最短簡單路徑void map_manage();/ 站點線路修改擴充/void search_two_allpath();/ 查詢兩站點間所有路徑void search_kh_path();/ 客貨運類別路徑查詢void create_map();/ 初始化地圖void save_map();/ 將程序中的圖結構體寫入數(shù)據(jù)文件int input_num_check(int min,int max);/ 數(shù)字輸入檢驗void shortest_path_ota(int begin);/ 生成某一站點到所有其它站點的最短路徑數(shù)據(jù)void print_fgx();/ 輸出獨占一行的

15、分割線void map_add_vex();/ 新增站點void map_add_road();/ 新增道路void map_revise_vex();/ 修改站點void map_revise_road();/ 修改道路(引導界面)void map_reroad_in(int vid);/ 修改道路(公用嵌入函數(shù))void map_delete_vex();/ 刪除站點void map_delete_road();/ 刪除道路(引導界面)void map_re_arc(int bid,int fid,int kind,int xid);/ 修改道路(模塊函數(shù)) 若修改終點:調用前需確保 xi

16、d( 新終點)與原終點不相同void map_de_arc(int bid,int fid);/ 刪除道路 (模塊函數(shù) )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);/ 人

17、客 /貨運線路 判斷較長路徑是否完全包含較短路徑int DFS_allpath_kh_test(int a_i,int b_i);/ 輸出前檢測判斷較長路徑是否完全包含較短路徑void main()int step = -1,choose = 1;create_map();dowelcome();printf( 請輸入功能序號:);step = input_num_check(0,3);if(input_exit = 1)input_exit = 0;step = -1;choose = 0;elseswitch(step)case 1:search_vex_info();break;case

18、 2:map_manage();break;case 3:search_kh_path();break; default:choose = 0;while(choose != 0);printf(n*n您已成功退出 , 歡迎下次使用 , 再見 !n 按任意鍵關閉窗口 );getch();/在你需要暫停的位置暫停一下，當你按一下任意鍵它又會繼續(xù)往下執(zhí)行! void welcome() int i;printf(”*n);n);printf(printf(全國鐵路網(wǎng)最佳經(jīng)由系統(tǒng)n);printf(n);printf( printf( printf( printf( printf( printf(n

19、);1 . 站點介紹查詢n);2 .站點道路修改擴充n);3 .客貨查詢n);0.退出系統(tǒng)n);n);printf(*/ 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

20、search_vex_info()int vid;doprintf( 請輸入站點 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

21、= 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 .vexs

22、,G.vexsfid.id,G .);print_fgx();for(i=0;i,G.vexsj.id,G .);printf( 全程共 %dkm,Dfid);print_fgx();while(1); void map_manage() int select;doprintf(1. 新增站點2.新增線路3.修改站點 4.修改線路 5.刪除站點 6.刪除線路e:退出)n請輸入操作編號：”)；select = input_num_check(1,6);if(input_exit = 1) input_exit = 0;system(cl

23、s);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;doprintf(1.貨運2.客運3兩站間最短路徑查詢e:退

24、出)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();break; default:exit(1);while(1);/初始化地圖void create_map() if(access(mmapdata.mdat,0) = 0) FILE *fp;fp = f

25、open(mmapdata.mdat,rb); if(!fp)printf(n 數(shù)據(jù)文件打開失敗!n); exit(1);fread(&G ,sizeof(MGraph),1,fp); fclose(fp); elseint i,j;/站點數(shù)與道路數(shù)賦值G.vexnum = 16;G.arcnum = 20;/站點編號賦值for(i=0;iG .vexnum;i+) G.vexsi.id = i;/站點名稱賦值strcpy(G., 北京站);strcpy(G., 鄭州站);strcpy(G., 株洲站);strcpy(G.vexs3.

26、name, 廣州站);strcpy(G., 天津站);strcpy(G., 連云港站 );strcpy(G., 上海站);strcpy(G., 南昌站);strcpy（G., 九龍站）;strcpy（G., 包頭站）;strcpy（G., 烏魯木齊站）;strcpy（G., 蘭州站）;strcpy（G., 寶雞站）;strcpy（G., 成都站）;strcpy（G.,

27、 昆明站）;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, 京包線

28、）;strcpy（G.vexs10.des, 有待補充）;strcpy（G.vexs11.des,有待補充）;strcpy（G.vexs12.des, 有待補充）;strcpy（G.vexs13.des, 有待補充）;strcpy（G.vexs14.des, 有待補充）;strcpy（G.vexs15.des, 有待補充）;for（i=0;iMAX_V_NUM;i+）for（j=0;jMAX_V_NUM;j+） G.arcsij.distance = MAX;G.arcs01.distance=300;G .arcs01.kind=1;G.arcs04.distance=100;G .arcs

29、04.kind=2;G.arcs09.distance=300;G .arcs09.kind=2;G.arcs15.distance=400;G .arcs15.kind=1;G.arcs112.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.distanc

30、e=200;G .arcs45.kind=2;G.arcs56.distance=300;G .arcs56.kind=2;G.arcs67.distance=200;G .arcs67.kind=2;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.arcs121

31、3.kind=2;G.arcs1314.distance=200;G .arcs1314.kind=2;G.arcs1415.distance=350;G.arcs1415.kind=2;for(i=0;iG .vexnum;i+)for(j=0;jj)G.arcsij = G.arcsji;save_map();/將程序中的圖結構體寫入數(shù)據(jù)文件void save_map()FILE *fp;fp = fopen(mmapdata.mdat,wb);if(!fp)printf(n 數(shù)據(jù)文件打開失敗!n); exit(1);fwrite(&G ,sizeof(MGraph),1,fp);fclo

32、se(fp);/數(shù)字輸入檢驗int input_num_check(int min,int max)int id,isright=0;doscanf(%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(nn);void shortest_path_ota(int begin) /Dijkstra( 迪杰斯特拉)算法int i,k=0,

33、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 =

34、 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( 【

35、%d 】 %s,G.vexspathk.id,G .);print_fgx();path_num+;elsefor(j=0;jG .vexnum;j+)if(G .arcspathkj.distance=MAX_V_NUM)printf(站點數(shù)已達到最大值 d,按任意鍵返回匚MAX_V_NUM);getchar();getchar();system(cls);welcome();return;printf(新站點的編號為【d】，是否繼續(xù)？(1.繼續(xù)e:退出):,vid);ifgo = input_num_check(1,1);if(input_exit = 1)in

36、put_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;doprintf( 請輸入新增道路起始站點 ID(e: 退出 ):

37、);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 = bid)printf( 終點與起點重復!n);continue;if(G.arcsbidfid.distanceprin

38、t_fgx();printf( 您 正 在 添 加 道 路 【 %d 】 %s【%d】 %s:n,G.vexsbid.id,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+;

39、save_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 介 紹 :%sn,G.vexsvid.id,G .,G .vexsvid.des);print_fgx(

40、);for(i=0;iG .vexnum;i+)if(G .arcsvidi.distance 【 %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( 請輸入需要修改的對象(1.名稱 2.信息3.線路 ):);scanf(%d,&choose);if(choose = 1)printf(

41、請輸入新的站點名稱:);scanf(%s,&G .);else if(choose = 2)printf( 請輸入新的站點信息 :);scanf(%s,&G .vexsvid.des);else if(choose = 3) map_reroad_in(vid);elseprintf( 輸入錯誤 !n); continue;save_map();print_fgx();printf( 修改成功 !n);while(1);/修改道路(引導界面)void map_revise_road()int vid;doprintf(請輸入需要修改的道路的起點(e:退出):)；vid

42、= input_num_check(0,G .vexnum-1);if(input_exit = 1)input_exit = 0;system(cls);welcome(); return;map_reroad_in(vid);save_map();print_fgx();printf( 修改成功 !n);while(1);/修改道路void map_reroad_in(int vid)int fid,ekind,pass=0,passt=1;doprintf(請輸入需要修改的道路的終點 (e:退出):)； fid = input_num_check(0,G .vexnum-1);if(in

43、put_exit = 1)input_exit = 0;else if(G.arcsvidfid.distance = MAX | fid = vid) printf( 道路不存在或端點重復!n);else pass = 1;while(pass != 1);if(pass = 1) pass = 0;doprintf(您需要修改線路 d】s -d】s的n(1.終點2.長度3.類型):,G .vexsvid.id,G .,G .vexsfid.id,G .);scanf(%d,&ekind);if(ekind = 1) int xid;do printf( 請輸入道路的新終點 :);xid = input_num_check(0,G .vexnum-1); if(input_exit = 1) input_exit = 0;else if(G.arcsvidxid.distance MAX | xid = vid) printf( 新道路已存在或端點重復!n);else pass = 1;while(pass != 1);map_re_arc(vid,fid,3,xid);else if(ekind = 2)map_re_arc(vid,fid,1,-1);else if(ekind = 3) map_r