全國鐵路最短路徑經(jīng)由問題

1、中南大學數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題 目 全國鐵路最短路徑經(jīng)由問題 學生姓名 任秋崢 指導教師 李登 學 院 信息科學與工程學院 學 號 0909090711 專業(yè)班級 電子信息專業(yè)0901班 完成時間 2011年6月30號 目錄第一章、課程設(shè)計題目31、問題描述32、基本要求33、實現(xiàn)提示4第二章、全國鐵路最短路徑經(jīng)由問題的具體實現(xiàn)62.1 需求分析62.2 概要設(shè)計61、設(shè)計思路62、設(shè)計方案72.3詳細設(shè)計101、定義結(jié)構(gòu)體102、輸出車站信息103、輸出鐵路信息114、輸出道路的信息115、查詢車站的功能116、增加車站信息127、增加鐵路信息128、最短路徑的實現(xiàn)129、實現(xiàn)所有函數(shù)功能1

2、32.4 測試分析131、測試數(shù)據(jù)132、測試過程143、測試結(jié)果142.5用戶使用說明141 程序運行環(huán)境142 主界面142.6小結(jié)171 調(diào)試過程中遇到的主要問題及解決過程172.7總結(jié)和體會172.8 附錄181、源程序代碼182、參考文獻29第一章、課程設(shè)計題目1、問題描述題目為全國鐵路最短路徑經(jīng)由問題該題目采用我國鐵路運輸網(wǎng)的數(shù)據(jù)進行編程和運行驗證。鐵路運輸網(wǎng)絡(luò)中由鐵路線和火車站的兩個主要概念，譬如：1號鐵路線表示京廣線，2號鐵路線表示京滬線等。鐵路線對象包括鐵路線編號,鐵路線名稱，起始站編號,終點站編號,該鐵路線長度，通行標志(00b客貨運禁行,01b貨運通行專線，10b客運通行

3、專線，11b客貨運通行)?；疖囌緦ο蟀ㄋ鶎勹F路線編號，車站代碼，車站名，車站簡稱，離該鐵路線起點站路程及終點站路程。2、基本要求（1）查詢某站所屬的鐵路線（2）要求具備新增鐵路線的管理功能（3）要求具備新增車站的管理功能（4）針對客運，貨運情況能計算任何一個起始車站到任何一個終點站之間的最短路徑。并且要求能夠顯示出該最短路徑的各個火車站的經(jīng)由順序3、實現(xiàn)提示要在計算機上建立一個交通咨詢系統(tǒng)則主要采取圖的結(jié)構(gòu)來表示實際的交通網(wǎng)路。我們可以將其轉(zhuǎn)換為一個源點到另一個源點的最短路徑，這里我應用了floyd的算法。下圖為簡單交通線路成都上海包頭蘭州北京鄭州徐州西安南昌昆明貴陽株洲 廣州程序分別采用三

4、個結(jié)構(gòu)體來存儲信息。views存儲車站信息車站身份編號車站名車站編碼車站簡稱車站所屬鐵路線line存儲鐵路信息鐵路編碼鐵路名字起始站編碼終點站編碼通行標志ways存儲道路信息車站1車站2兩站間距離也可以將以上信息也存入三個文件夾中，在程序中利用fread函數(shù)把信息從文件中讀出賦給三個結(jié)構(gòu)體。 在實現(xiàn)查找車站功能時，首先利用fread函數(shù)從文件中讀取數(shù)據(jù)，再調(diào)用strcmp函數(shù)比較輸入車站名與文件存貯的車站名，如果相同，就輸出該車站名的相關(guān)信息。 實現(xiàn)最短路徑時，利用floyd的算法。 在實現(xiàn)增加信息功能時可以利用fprintf函數(shù)和fscanf函數(shù)向文件中輸入信息，同時文件中記錄個數(shù)增加1.第

5、二章、全國鐵路最短路徑經(jīng)由問題的具體實現(xiàn)2.1 需求分析1、可以直接向客戶輸出所有鐵路和城市的信息2、可以為客戶提供查詢車站的功能3、可以為客戶提供查詢從一個車站到另一個車站的最短路徑的功能4、可以及時增加新的鐵路和車站信息。2.2 概要設(shè)計1、設(shè)計思路用文件存儲信息，從文件中讀取信息存儲在views、lines、ways三個結(jié)構(gòu)體中。再構(gòu)造函數(shù)，分別實現(xiàn)輸出、查詢、最短路徑、增加信息等功能。在用switch和while的循環(huán)語句來調(diào)用上述函數(shù)來實現(xiàn)功能，屬于模塊化實現(xiàn)功能。main增加車站信息增加鐵路信息查詢車站信息最短路徑退出case1case2case3case4case52、設(shè)計方案r

6、eadviews ()、readlines、readways()函數(shù)分別實現(xiàn)輸出車站、鐵路、道路信息。從文件中讀取信息賦給結(jié)構(gòu)體，循環(huán)輸出。search（）實現(xiàn)查詢車站功能。利用fread函數(shù)把文件中的信息賦給結(jié)構(gòu)體后，調(diào)用strcmp函數(shù)比較輸入車站名，如果相同，就輸出該車站的相關(guān)信息。add views ()函數(shù)實現(xiàn)增加車站信息，可以調(diào)用fwrite或者fprintf函數(shù)向文件中寫入信息。 floyd（）函數(shù)實現(xiàn)最短路徑的查詢 addllines（）函數(shù)實現(xiàn)增加鐵路線的信息，可以調(diào)用fwrite或者fprintf函數(shù)向文件中寫入信息。 利用switch循環(huán)，在case1case5情況下，分

7、別調(diào)用以上函數(shù)的功能。 構(gòu)建三個結(jié)構(gòu)體，分別存放城市、鐵路、道路的信息。數(shù)據(jù)結(jié)構(gòu)中圖的定義和術(shù)語為以下：adt graph數(shù)據(jù)對象v ：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系r：r=vrvr=|v,w(-v且p(v,w),表示從v到w的弧，謂詞p(v,w)定義了弧的意義或信息基本操作p：creategraph(&g,v,vr);初始條件：v是圖的頂點集，vr是圖中弧的集合。操作結(jié)果：按v和vr的定義構(gòu)造圖gdestroygraph(&g);初始條件：圖g存在操作結(jié)果：銷毀圖glocatevex(g,u);初始條件：圖g存在，u一g中頂點有相同特征操作結(jié)果：若g中存在頂點u, 則

8、返回該頂點在圖中位置；否則返回其它信息。getvex(g,v);初始條件：圖g存在，v是g中某個頂點操作結(jié)果：返回v的值。putvex(&g,v,value);初始條件：圖g存在，v是g中某個頂點操作結(jié)果：對v賦值valuefirstadjvex(g,v);初始條件：圖g存在，v是g中某個頂點操作結(jié)果：返回v的第一個鄰接頂點。若頂點在g中沒有鄰接頂點，則返回“空”nextadjvex(g,v,w);初始條件：圖g存在,v是g中某個頂點,w是v的鄰接頂點。操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點。若w是v的最后一個鄰接點，則返回“空insertvex(&g,v);初始條件：圖g存在，v和圖

9、中頂點有相同特征操作結(jié)果：在圖g中增添新頂點vdeletevex(&g,v);初始條件：圖g存在，v是g中某個頂點操作結(jié)果：刪除g中頂點v及其相關(guān)的弧insertacr(&g,v,w);初始條件：圖g存在，v和w是g中兩個頂點操作結(jié)果：在g中增添弧,若g是無向的，則還增添對稱弧deletearc(&g,v,w);初始條件：圖g存在，v和w是g中兩個頂點操作結(jié)果：在g中刪除弧,若g是無向的，則還刪除對稱弧dfstraverser(g,v,visit();初始條件：圖g存在，v是g中某個頂點，visit是頂點的應用函數(shù)操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖g，并對每個頂點調(diào)用函數(shù)visit一次。一旦v

10、isit()失敗，則操作失敗。bfstraverse(g,v,visit();初始條件：圖g存在，v是g中某個頂點，visit是頂點的應用函數(shù)操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖g，并對每個頂點調(diào)用函數(shù)visit一次。一旦visit()失敗，則操作失敗。adt graph2.3詳細設(shè)計1、定義結(jié)構(gòu)體struct view_info 存放車站信息的結(jié)構(gòu)體 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; 最短路徑的路徑個數(shù) int pathsize_view; 表明通過的車站 path_listsi

12、ze_viewsize_view ;2、輸出車站信息首先打開views這個文件，用一個for循環(huán)，再調(diào)用fread函數(shù)把文件中的信息按照順序賦給view_info結(jié)構(gòu)體，再輸出到終端上。其算法描述如下：void readviews() 打開文件views.txt文件 for（fread 函數(shù)對文件的信息讀取賦給view_info結(jié)構(gòu)體并且不為0)輸出車站車站身份編碼、車站名字、車站編碼、車站簡寫、車站所屬的鐵路線記錄文件中信息的個數(shù)關(guān)閉文件3、輸出鐵路信息void readlines() 打開文件lines.txt文件 for（fread 函數(shù)對文件的信息讀取賦給line_info結(jié)構(gòu)體并且不

13、為0)輸出車站鐵路身份編碼、鐵路名字、起始車站編碼、終點站編碼、通行標志記錄文件中信息的個數(shù)關(guān)閉文件 4、輸出道路的信息void readways() 打開文件ways.txt文件 for（fread 函數(shù)對文件的信息讀取賦給way_info結(jié)構(gòu)體并且不為0)輸出車站1、車站2、兩車站間距離記錄文件中信息的個數(shù)關(guān)閉文件5、查詢車站的功能void search()輸入你要查詢的車站名稱打開文件viewsfor(i文件中記錄個數(shù))把文件中的信息賦給結(jié)構(gòu)體調(diào)用strcmp比較結(jié)構(gòu)體中車站名字與輸入車站名字，如果兩者相等輸出該車站的相關(guān)信息如果查找到文件中的最后一個信息仍不能找到輸出“不能找到所要查詢

14、的車站“6、增加車站信息addviews()輸入新車站身份編碼、車站名字、車站編碼、車站簡寫、車站所屬的鐵路線，并將其存入到view_info結(jié)構(gòu)體中打開文件將該新信息寫入到文件中7、增加鐵路信息void addline() 輸入新鐵路身份編碼、鐵路名字、起始車站編碼、終點站編碼、通行標志，并將其存入到line_info結(jié)構(gòu)體中打開文件將該新信息寫入到文件中8、最短路徑的實現(xiàn)floyd（）把所有路徑的長度賦給一個二維數(shù)組，二維數(shù)組可以表示該路徑的起始和終點把所有路徑的起點和終點賦給i和j;在起始點和終點間找一點k,首先考慮（i，k）(k,j)是否存在，如如果存在，比較（i,j）與(i,k,j)

15、的長度，取長度較短者為i到j(luò)得一個最短路徑。在路徑上在加一個頂點也是如此比較，取較短者作為最短路徑經(jīng)過多次比較后，便會得到最短路徑的頂點集合輸出這些頂點的對應的車站名稱9、實現(xiàn)所有函數(shù)功能main()輸出鐵路、車站、路徑信息情況一：增加鐵路信息情況二：增加車站信息情況三：查詢車站信息情況四：查詢最短路徑情況五：退出2.4 測試分析1、測試數(shù)據(jù)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、測試過程分別調(diào)用各個函數(shù)，輸入一個車站名字，看是否能查詢到車站信息。輸入起始站點和終點站的代碼，檢測是否能查詢到最短路徑。增加新的車站和鐵路信息，檢測是否能夠?qū)懭胛募?、測試結(jié)果能夠查詢到車站信息，并且最短路徑也符合實際情況，

20、同時也可以向文件中添加新的車站和鐵路信息。2.5用戶使用說明1 程序運行環(huán)境程序名為railway.exe，運行環(huán)境為windows xp。2 主界面運行程序后首先顯示圖3-5-2 所示程序主界面。1、增加新的車站信息選擇此項后，會出現(xiàn)以下的提示按照提示依次輸入車站名字編碼等，最終程序?qū)@示所有的信息，證明程序已經(jīng)添加新的信息2、增加鐵路信息將會出現(xiàn)以下界面按照提示依次輸出，最終程序?qū)@示所有的信息，證明程序已經(jīng)添加新的信息。3、查詢車站信息會出現(xiàn)以下界面以上是查詢到輸入車站的情況，當輸入的車站不能夠查詢到的時候，會出現(xiàn)以下提示4、查詢最短路徑時會出現(xiàn)以下提示然后輸入起始站和終點站的編碼，

21、就會有最短路徑的出現(xiàn)2.6小結(jié)1 調(diào)試過程中遇到的主要問題及解決過程首先是在從文件中讀取數(shù)據(jù)并存入到數(shù)組的過程中，因為文件中有中文，但因電腦解碼器的問題最終輸出的為亂碼，所以最終只有把中文改成了英文。然后在最短路徑的設(shè)計問題上，我沒有考慮到雙向的問題，所以導致圖畫的不合理。在增加信息到文件中的時候，信息增加到了文件的開頭，我的目的是要增加到文件的末尾。程序中有些變量可以作為全局變量來定義，但是我卻過多的定義了。2.7總結(jié)和體會這次的課程設(shè)計的內(nèi)容是用c語言實現(xiàn)全國鐵路最短路徑經(jīng)由問題，這對我來說是個很具有挑戰(zhàn)性的任務，雖然只做了一個很簡單的鐵路路線，但通過兩個星期的設(shè)計也從中學到了不少東西，更

22、深刻的理解了課本中的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。同時再次深刻理解了c+中類的思想和實現(xiàn)，文件的概念和相關(guān)操作，以及有關(guān)數(shù)據(jù)結(jié)構(gòu)的很多知識。根據(jù)實際問題的需要，對個方面的優(yōu)缺點加以綜合平衡，從中選擇比較適宜的實現(xiàn)方法。在本次課程設(shè)計中，我明白了理論與實際相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫程序的能力，培養(yǎng)了基本的，良好的程序設(shè)計技能。提高綜合運用所學知識的能力。在這次課程設(shè)計中曾遇到了不少問題，就單憑我一個人的能力很難準時有效的完成這次的課程設(shè)計，在此要要感謝我的老師同學，他們?yōu)槲姨岢隽撕芏嘤杏玫慕ㄗh，幫助我完成了這次的課

23、程設(shè)計。最后也要感謝我們學校為我們提供良好的編程環(huán)境，使我們能夠按時完成任務。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 存放車站信息的結(jié)構(gòu)體 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; 最短路徑的路徑個數(shù) 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結(jié)構(gòu)體,并且把車站信息輸出到終端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結(jié)構(gòu)體,并且把道路信息輸出到終端上 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結(jié)構(gòu)體,并且把鐵路信息輸出到終端上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;對比輸入的車名和結(jié)構(gòu)體中車站名字，如果相同，就輸出該車站的相關(guān)信息。 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;將路徑長度賦給數(shù)組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;