題目8：全國鐵路運輸網最佳經由問題

1、精選優(yōu)質文檔-傾情為你奉上課程設計報告（本科）課程：數據結構學號：、 姓名：葛程、徐雙雙杜明輝班級：2012級物聯網工程班教師：程敏時間：2014.01.02計算機科學與技術系專心-專注-專業(yè)設計名稱：全國鐵路運輸網最佳經由問題設計內容、目的與要求：實驗內容：鐵路運輸網絡中由鐵路線和火車站的兩個主要概念，譬如：1號鐵路線表示京廣線，2號鐵路線表示京滬線等。鐵路線對象包括鐵路線編號,鐵路線名稱，起始站編號,終點站編號,該鐵路線長度，通行標志(00B客貨運禁行,01B貨運通行專線，10B客運通行專線，11B客貨運通行)。火車站對象包括所屬鐵路線編號，車站代碼，車站名，車站簡稱，離該鐵路線起點站路程

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

3、做最后的優(yōu)化。 設計過程、步驟（可加頁）：一：設計過程：將鐵路網抽象成圖，然后查詢中國現有的鐵路網結構圖，選取合適的站點數目，構造一個簡單的鐵路圖，在構造的鐵路圖上實現設計的要求。用結構體創(chuàng)建圖，然后再圖的基礎上實現算法要求。通過對題目的分析我們覺得會用到會用到數據結構的鄰接矩陣的存儲圖的定義，圖的遍歷算法（深度優(yōu)先遍歷），兩點間最短路徑查詢（迪杰斯特拉算法）。使用文件的存儲方式，對數據進行存儲。現行的鐵路圖：最后簡單化的鐵路網如下：typedef struct int id;char name20;char des100; vinfo;/站點typedef structint distanc

4、e;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();/輸出獨占一行的分割線v

6、oid 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)結果與分析（可以加頁）： 設計體會與建議： 這次的程序軟件基本上運行成功，可以簡單的對已經輸入的數據進行計算，求全國鐵路運輸網最佳經由。但是程序較小，功能不全面，只是理論，并未實踐。經過這次課程設計，通過對程序的編制，調試和運行，使我更好的掌握了圖基本性質和關于選址問題的解決方法，熟悉了各種調用的數據類型，在調試和運行過程中使我更加的了解和熟悉程序運行的環(huán)境，提高了我對程序調試分析的能力和對錯誤的糾正能力。這次數據結構的程序設計，對于我來說是一個挑戰(zhàn)。我對數據結構的學習在程序的設計中也有所體現。課程設計是培養(yǎng)學

9、生綜合運用所學知識、發(fā)現、提出、分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié)，是對學生實際工作能力的具體訓練和考察過程。隨著科學技術發(fā)展的日新月異，當今計算機應用在生活中可以說得是無處不在。因此作為二十一世紀的大學來說掌握計算機開發(fā)技術是十分重要的。 在整個課程程序中，我們充分應用和調用各個程序模塊，從而實現了此次程序設計的所應該有的功能。在本組看來這就是我們在課程設計是比較成功的，而在這個過程中，讓我們感覺收獲最大的就是我們都能利用這次課程設計學到很多我們在課本上沒有的知識，充分的發(fā)揮了我們的主動性，使我們自主的去學習。附錄：#include #include #include #includ

10、e #include #include #include #define MAX_V_NUM 100#define MAX 60000typedef struct int id;char name20;char des100; vinfo;/站點typedef structint distance;int kind;ArcCell, AdjMatrixMAX_V_NUMMAX_V_NUM;/鄰接矩陣typedef struct vinfo vexsMAX_V_NUM;/站點數組AdjMatrix arcs;int vexnum,arcnum;MGraph;/圖MGraph G;/圖Gint i

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

12、AX_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();/客貨運類別路徑查詢

13、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 ma

14、p_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(i

15、nt 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);/輸出前檢測 判斷較長路徑是否完全包含較短路徑void main() int step = -1,choose = 1;create_map();

16、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_manage();break;case 3:search_kh_path();break;default:choose = 0; while(choose != 0);printf(n*n您已成功退出,歡迎下次使用,再見!n按任意鍵關閉窗口);getch(

17、);/在你需要暫停的位置暫停一下，當你按一下任意鍵它又會繼續(xù)往下執(zhí)行！void welcome() int i;printf(*n);printf( n);printf( 全國鐵路網最佳經由系統(tǒng) n);printf( n);printf( n);printf( 1.站點介紹查詢 n);printf( 2.站點道路修改擴充 n);printf( 3.客貨查詢 n);printf( 0.退出系統(tǒng) n);printf( n);printf(*n);/printf(共有%d個站點 %d條道路 最大值MAX為%d 最多%d個頂點,G.vexnum,G.arcnum,MAX,MAX_V_NUM);prin

18、t_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();print

19、f(站點【%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 =

20、 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 map_manage()int select;do printf(1.新增站點 2.

21、新增線路 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:

22、map_delete_road();break;default:exit(1);while(1);void 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:

23、search_rantwo_short();break;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 = 20;/站點編號賦值for(i=0;iG.vexnum;

24、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.,烏魯木

25、齊站);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,有待補充);strc

26、py(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,有待補充);strcpy(G.vexs15.des,有待補充);for(i=0;iMAX_V_NUM;i+)for(j=0;jMAX_V_NUM;j+)G.arcsi

27、j.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.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.distan

28、ce=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;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.a

29、rcs1112.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;iG.vexnum;i+)for(j=0;jj)G.arcsij = G.arcsji;save_map();/將程序中的圖結構體寫入數據文件void save_map()FILE *fp;fp = fopen(mmapdata.mdat,wb);if(

30、!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()prin

31、tf(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;

32、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;

33、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】,是否繼續(xù)?

34、(1.繼續(xù) 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);vo

35、id 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 = bid

36、) printf(終點與起點重復!n);continue;if(G.arcsbidfid.distance【%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

37、+;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 介紹:%s n,G.vexsvid.id,G.,G.vexsvid.des);print_fgx();for(i=0;iG.ve

38、xnum;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(請輸入新的站點名稱:); scanf(%s,&G.vexs

39、);else if(choose = 2) printf(請輸入新的站點信息:); scanf(%s,&G.vexsvid.des); else if(choose = 3) map_reroad_in(vid); else 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-

40、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;do printf(請輸入需要修改的道路的終點(e:退出):); fid = input_num_check(0,G.vexnum-1); if(input_exit = 1) input_exit = 0; else if(G.arcsvidfid.distance =