全國(guó)交通咨詢模擬系統(tǒng)實(shí)驗(yàn)報(bào)告

1、浙江工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)大作業(yè)報(bào)告 專 業(yè)： 軟件工程 _ 班 級(jí)： 軟件1101 _ 學(xué) 號(hào)： 33 _ 姓 名： _ 沈艷 _ 指導(dǎo)教師： 吳海燕 _ 2012年5 月目錄 、問題描述 二、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及核心算法描述 三、 主控及功能模塊層次結(jié)構(gòu) 四、 主要功能函數(shù)代碼 五、 功能模塊之間的調(diào)用與被調(diào)用的關(guān)系 六、 測(cè)試結(jié)果 七、課程設(shè)計(jì)小結(jié)、問題描述 全國(guó)交通咨詢模擬：處于對(duì)不同目的的旅客對(duì)交通工具有不同的要求。 例如, 因公出差的旅客希望在旅途中的時(shí)間盡可能短， 出門旅游的游客則希望旅費(fèi)盡可 能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個(gè)全國(guó)城市間的交通咨詢程序，

2、 為旅客提供兩種或三種最優(yōu)決策的交通咨詢。 【基本要求】(1)提供對(duì)城市信息進(jìn)行編輯(如：添加或刪除)的功能 (2) 城市之間有兩種交通工具：火車和飛機(jī)。提供對(duì)列車時(shí)刻表和 飛機(jī)航班進(jìn)行編輯(增設(shè)或刪除)的功能。 (3) 提供兩種最優(yōu)決策：最快到達(dá)或最省錢到達(dá)。全程只考慮一種 交通工具。 (4) 旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。 (5) 咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。由用戶輸入起始站、終 點(diǎn)站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長(zhǎng)時(shí) 間才能到達(dá)或者最少需要多少旅費(fèi)才能到達(dá)，并詳細(xì)說明依次 于何時(shí)乘坐哪一趟列車或哪一次班機(jī)到何地。 二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和核心算法設(shè)計(jì)描述：

3、1 1、根據(jù)題目中的基本要求分析，可以創(chuàng)建系統(tǒng)概念模型，流程設(shè)計(jì) 框圖如下：【測(cè)試數(shù) 1892 1100 349 17 天津大連 今魯木 216 1145 昆明 639 6 842 255 967 907 哈爾濱 305 武漢 北京 37 704. 徐州 651 672 140 深圳 安 534 上海 /825 南2昌 福州 *南寧 409 367 / - 開始 i J 丿 王界面 用戶輸入,頑取 option的值 王界面 3、核心設(shè)計(jì)：根據(jù)上面的流程圖和邏輯拆分，對(duì)這個(gè)問題有了一個(gè)比較直觀， 詳細(xì)地了解。并且從中也可得知路線的添加即數(shù)據(jù)的存儲(chǔ)是這個(gè)系統(tǒng)進(jìn)行運(yùn)作的 一個(gè)基礎(chǔ)。而為了便于數(shù)據(jù)的存

4、儲(chǔ)、添加、刪除等操作，我選擇了儲(chǔ)存文件對(duì)這 些數(shù)據(jù)進(jìn)行了存儲(chǔ)。將每個(gè)信息量放在不同的文件中， 可以更有效、直觀地對(duì)這 些數(shù)據(jù)進(jìn)行處理。 流程圖中的7個(gè)主要功能模塊在主函數(shù)中，采用輸入選項(xiàng)進(jìn)入子菜單，但是 其他操作都是在路線添加好后進(jìn)行的， 并且為了每一項(xiàng)功能進(jìn)行完后，系統(tǒng)可以以鄰接表作交通圖的存儲(chǔ)結(jié)構(gòu)，表示邊的結(jié)點(diǎn)內(nèi)除含有鄰接點(diǎn)的信息外， 包 括交通工具、路程中消耗的時(shí)間和花費(fèi)以及出發(fā)和到達(dá)的時(shí)間等多項(xiàng)屬性。 2 2、邏輯結(jié)構(gòu)拆分: 及時(shí)回到主交互界面，我采用的是無限循環(huán)形式，即 while （1） 三、主控及功能模塊層次結(jié)構(gòu)： 1、模塊說明：本系統(tǒng)分為個(gè)模塊 1、 ）主函數(shù) 2、 ）添加城市

5、 3、 ）查找城市并返回序號(hào) 4、 ）刪除城市 5、 ）添加列車 6、 ）添加航班 7、 ）刪除列車或航班 8、 ）找出最小費(fèi)用路線 9、 ）初始化系統(tǒng)數(shù)據(jù)（讀入內(nèi)存） 10、 ）找出最快路線 11、 ）計(jì)算最快路線耗費(fèi)的時(shí)間并打印 12、 ）計(jì)算最小費(fèi)用路線 13、 ）主界面 14、 ）存儲(chǔ)信息到文件 15、 ）退出、 2 2、下面是各模塊示意圖: 初始化系坦 數(shù)猱從文 冰加城帀 檔請(qǐng)入內(nèi)存 存昭信盤到文件 數(shù)貢（從文 欄讀入內(nèi)存 刪除城帀 存儲(chǔ)信總到文件 1 r q 初殆化系堀 數(shù)貢從文 檔諸入內(nèi)存 添加航班 濟(jì)加列豐 存儲(chǔ)信總到文件 地除艾進(jìn)路續(xù) r F 5 f 初蠟化孚我 割內(nèi)殍） 計(jì)

6、篦導(dǎo)快建 純耗資的町 司列川 程儲(chǔ)佶息到文斗 基本操作: TrafficNodeDat 交通工具 信息 Char n ameMAX_STRING_N UM 班次 Int starttime 出發(fā)時(shí)間 Int starttime 到達(dá)時(shí)間 Int cost 票價(jià) UNodeDat 路線 信息 Short int city 城市編號(hào) Int TrainNum 火車路線數(shù) int FlightNum 航班路線數(shù) TrafficNodeDat Trai nMAX_TRAFFIC_ NUM 火車路線信息 TrafficNodeDat FlightMAX TRAFFIC 航班路線信息 NUM 函數(shù)變量聲明

7、: #in elude #in elude #defi ne ERR 0 #defi ne OK 1 #defi ne Dij_MAXN 33 #defi ne MAX_VERTEX_NUM 31 #defi ne MAX_STRING_NUM 10 #defi ne MAX_TRAFFIC_NUM 10 con st char CityFile =D:; con st char Trai nFile =D:; con st char FlightFile =D:; typedef short int CityType; typedef struct TrafficNode char name

8、MAX_STRING_NUM; rainNum; fprin tf(fp,%dn,total); for (i=O;iCityNum;i+) for (j=0;jAdjListi.Trai nNu m;j+) fprin tf(fp,%s %s %s , AdjListi.Trai nj. name, CityNamei, CityNameAdjListi.Trai nj.E ndCity); fprin tf(fp,%2d:%2d %2d:%2d%dn, -=5pf -( lueNEnNA 七oarLueNA 七 o)Adols ( lueN*elp) Ao七su-l 一-芒運(yùn)呂坯(寸) 宀

9、 二 Una)u(d4 gsoos莖 6 一匚gsnp -09& E 匚docos莖 6 一匚gsnp -09O5E 匚 docoCDEeus莖 6 一匚gsnp-= (+EnNA 七OVOH)O4 Meor=5p&=-d&ld4 宀 nN 莖 6=dgsnp_eol (+EnNA 七OVOH)O4 (M=a)=tu6 一匚)u dordA Olleo=(d4soo4 宀 宀 gsoosu&Lgsnp AdjListCityNum.city=CityNum; AdjListCityNum.FIightNum=O; AdjListCityNum.Trai nNu

10、m=0; CityNum+; return 1; (5) 刪除城市： int DelCity (char *Name) in t city,i,j; city=SeekCity(Name); for (i=city;iCityNum-1;i+) strcpy(CityNamei,CityNamei+1); AdjListi.FIightNum=AdjListi+1.FIightNum; AdjListi.Trai nNu m=AdjListi+1.Trai nNum; for (j=0;jAdjListi.FlightNum;j+) AdjListi.Flightj.Cost=AdjListi

11、+1.Flightj.Cost; AdjListi.Flightj.E ndCity=AdjListi+1.FIightj.E ndCity; strcpy(AdjListi.Flightj. name,AdjListi+1.FIightj. name); AdjListi.Flightj.StartTime=AdjListi+1.Flightj.StartTime; AdjListi.FIightj.StopTime=AdjListi+1.FIightj.StopTime; CityNum-; return 1; (6) 添加火車路線： int InsertTrain (char *trai

12、n,char *StartCity,char *EndCity,int StartTime,int En dTime,i nt cost) int i,j; i=SeekCity(StartCity); j=SeekCity(E ndCity); AdjListi.Trai nAdjListi.Trai nN um.Cost=cost; AdjListi.Trai nAdjListi.Trai nN um.E ndCity=j; AdjListi.Trai nAdjListi.Trai nN um.StartTime=StartTime; AdjListi.Trai nAdjListi.Tra

13、i nN um.StopTime=E ndTime; strcpy(AdjListi.Trai n AdjListi.Trai nNu m. name,trai n); AdjListi.Trai nNu m+; return 1; (7) 添加航班路線： int InsertFlight(char *flight,char *StartCity,char *EndCity,int En dTime,i nt cost) int i,j; i=SeekCity(StartCity); j=SeekCity(E ndCity); AdjListi.FIightAdjListi.FIightNum

14、.Cost=cost; AdjListi.FIightAdjListi.FIightNum.E ndCity=j; AdjListi.FIightAdjListi.FIightNum.StartTime=StartTime; AdjListi.FIightAdjListi.FIightNum.StopTime=E ndTime; strcpy(AdjListi.FIightAdjListi.FIightNum. name,flight); AdjListi.FIightNum+; return 1; (8) 刪除路線： int DelPath (char *n ame) int i,j,fla

15、g=0; for (i=0;iCityNum;i+) for (j=0;jAdjListi.FIightNum;j+) if (strcmp(AdjListi.FIightj. name, name)=0)StartTime,i flag=1; break; if (flag) for (;jAdjListi.FlightNum-1;j+) AdjListi.Flightj.Cost=AdjListi.Flightj+1.Cost; AdjListi.Flightj.EndCity=AdjListi.Flightj+1.EndCity; strcpy(AdjListi.F

16、,AdjListi.Flightj+1.name); AdjListi.Flightj.StartTime=AdjListi.Flightj+1.StartTime; AdjListi.Flightj.StopTime=AdjListi.Flightj+1.StopTime; AdjListi.FlightNum-; break; for (j=0;jAdjListi.TrainNum;j+) if (strcmp(AdjListi.T,name)=0) flag=1;break; if (flag) for (;j AdjListtracki.Trai n k.Co st

17、) min=AdjListtracki.Trai nk.Cost; tmp=k; prin tf(%s ,AdjListtracki.Trai ntmp. name); startH = AdjListtracki.Trai ntmp.StartTime/60 ; startM = AdjListtracki.Trai n tmp.StartTime%60; endH = AdjListtracki.Trai n tmp.StopTime/60 ; endM = AdjListtracki.Traintmp.StopTime%60 ; if( !(startH/10) printf(0); p

18、rintf(%d:,startH); if( !(startM/10) ) printf(0); printf(%d - ,startM); if( !(endH/10) ) printf(0); printf(%d:,endH); if( !(endM/10) ) printf(0); printf(%dn,endM); raintmp.StartTime/60,AdjListtracki.Traintmp.StartTime%60,AdjListtrac ki.Traintmp.StopTime/60,AdjListtracki.Traintmp.StopTime%60); else fo

19、r(i-;i0;i-) printf(n%s:,CityNametracki); end=tracki-1;min=32767; for (k=0;kAdjListtracki.Flightk.Co st) */ if (AdjListtracki.Flightk.EndCity=end&minAdjListtracki.Flightk.C ost) min=AdjListtracki.Flightk.Cost; tmp=k; printf(%s,AdjListtracki.F); startH = AdjListtracki.Flighttmp.StartT

20、ime / 60 ; startM = AdjListtracki.Flighttmp.StartTime % 60; endH = AdjListtracki.Flighttmp.StopTime / 60 ; endM = AdjListtracki.Flighttmp.StopTime % 60 ; if( !(startH/10) ) printf(0); printf(%d:,startH); if( !(startM/10) ) printf(0); prin tf(%d - ,startM); if( !(endH/10) prin tf(0); prin tf(%d:,e nd

21、H); if( !(en dM/10) prin tf(0); prin tf(%dn,e ndM); lighttmp.StartTime 60,AdjListtracki.FIighttmp.StartTime 60,AdjListtracki.FIighttmp.StopTime 60,AdjListtracki.FIighttmp.StopTime % 60); prin tf(n%s: DESTINATION!,CityNametrack0); prin tf(nMin Cost : %dn,cost); (10) 找出最小費(fèi)用路線 void Dijkstra(i nt matxDi

22、j_MAXNDij_MAXN,i nt p_start,i nt TravelType) int PreCityDij_MAXN; .n); return -1; fscan f(fp,%d,&CityNum); for (i=0;iCityNum;i+) fscanf(fp,%s,&CityNamei); AdjListi.city=i; AdjListi.TrainNum=0; AdjListi.FlightNum=0; p_en d,i fclose(fp); fp=fopen(TrainFile,r); if (!fp) printf(nError:Cannot Ope

23、n Train File.n); return -1; fscanf(fp,%d,&num); for (i=0;inum;i+) fscanf(fp,%s,&stmp1); fscanf(fp,%s,&stmp2); fscanf(fp,%s,&stmp3); j=SeekCity(stmp2); AdjListj.TrainAdjListj.TrainNum.EndCity=SeekCity(stmp3); strcpy(AdjListj.TrainAdjListj.TrainN,stmp1); fscanf(fp,%d:%d,&hou

24、r,&minute); AdjListj.TrainAdjListj.TrainNum.StartTime=hour*60+minute; fscanf(fp,%d:%d,&hour,&minute); AdjListj.TrainAdjListj.TrainNum.StopTime=hour*60+minute; fscanf(fp,%d,&cost); AdjListj.TrainAdjListj.TrainNum.Cost=cost; AdjListj.TrainNum+; fclose(fp); fp=fopen(FlightFile,r); if (!

25、fp) prin tf(nError:Ca nnot Ope n Flight File.n); return -1; fscan f(fp,%d,&n um); for (i=0;i CurTime-StartTime) for (i=0;i=curPathNo;i+) MinPathi.City=Pathi.City; MinPathi.TraNo=Pathi.TraNo; curPath=curPathNo; MinTime=CurTime-StartTime; else curPathNo+; PathcurPathNo.City=City; if (!TravelType)

26、for (i=0;i=(CurTime%1440)&(AdjListCity.Train i.StopTime+(CurTime/1440)*1440-StartTimeMinTime) PathcurPathNo.TraNo=i; SearchMinTime(AdjListCity.Traini.EndCity,EndCity,AdjListCity.Traini.S topTime+(CurTime/1440)*1440,curPathNo,TravelType); if (AdjListCity.Traini.StartTime(CurTime%1440)&(AdjLis

27、tCity.Traini .StopTime+(CurTime/1440)*1440-StartTimeMinTime) PathcurPathNo.TraNo=i; SearchMinTime(AdjListCity.Traini.EndCity,EndCity,AdjListCity.Traini.S topTime+(CurTime/1440+1)*1440,curPathNo,TravelType); else for (i=0;i=CurTime)&(AdjListCity.FIighti.StopT ime+(CurTime/1440)*1440-StartTimeMi n

28、Time) PathcurPathNo.TraNo=i; SearchMi nTime(AdjListCity.FIighti.E ndCity,E ndCity,AdjListCity.FIighti. StopTime+(CurTime/1440)*1440,curPathNo,TravelType); if (AdjListCity.FIighti.StartTimeCurTime)&(AdjListCity.FIighti.StopTi me+(CurTime/1440)*1440-StartTimeMi nTime) PathcurPathNo.TraNo=i; Search

29、Mi nTime(AdjListCity.FIighti.E ndCity,E ndCity,AdjListCity.FIighti. StopTime+(CurTime/1440+1)*1440,curPathNo,TraveIType); return 1; (13)計(jì)算最快路線所需時(shí)間并打?。?int CalcMinTime (int StartCity,int EndCity,int TravelType) int i; int startH, startM, endH, endM;ity=StartCity; if (!TravelType) for (i=0;iAdjListSta

30、rtCity.TrainNum;i+) Path0.TraNo=i; StartTime=AdjListStartCity.Traini.StartTime; SearchMinTime(AdjListStartCity.Traini.EndCity,EndCity,AdjListStartCity .Traini.StopTime,0,TravelType); else for (i=0;iAdjListStartCity.FlightNum;i+) Path0.TraNo=i; StartTime=AdjListStartCity.Flighti.StartTime; SearchMinT

31、ime(AdjListStartCity.Flighti.EndCity,EndCity,AdjListStartCity .Flighti.StopTime,0,TravelType); if (MinTime=32767) printf(nNo access to that destination!); return 0; rainMinPath0.TraNo.StartTime; lightMinPath0.TraNo.StartTime; printf(nPath:n); for (i=0;i=curPath;i+) if (!TravelType) printf(%s : ,City

32、NameMinPathi.City,AdjListMinPathi.City.TrainMinPathi.TraNo .name); else printf(%s : ,CityNameMinPathi.City,AdjListMinPathi.City.FlightMinPathi.TraNo .name); startH AdjListMinPathi.City.TrainMinPathi.TraNo.StartTime / 60 ; startM AdjListMinPathi.City.TrainMinPathi.TraNo.StartTime % 60 ; endH AdjListM

33、inPathi.City.TrainMinPathi.TraNo.StopTime / 60 ; endM AdjListMinPathi.City.TrainMinPathi.TraNo.StopTime % 60 ; if( !(startH/10) ) printf(0); printf(%d:,startH); if( !(startM/10) ) printf(0); printf(%d - ,startM); if( !(endH/10) ) printf(0);%s %s printf(%d:,endH); if( !(endM/10) ) printf(0); printf(%

34、dn,endM); rainNum) min=32767; end=AdjListi.Trainj.EndCity; while (end=AdjListi.Trainj.EndCity&jAdjListi.TrainNum) if (AdjListi.Trainj.Costmin) min=AdjListi.Trainj.Cost; j+; else maiend=min; for (i=0;iCityNum;i+) min=32767;j=0; while (jAdjListi.FlightNum) min=32767; end=AdjListi.Flightj.EndCity;

35、while (en d=AdjListi.FIightj.E ndCity&jAdjListi.FIightNum) if (AdjListi.FIightj.Costmi n) min=AdjListi.Flightj.Cost; j+; maie nd=mi n; Dijkstra(ma,StartCity,E ndCity,TravelType); return 1; 五、功能模塊間函數(shù)的調(diào)用關(guān)系，如下圖所示： Calcm in cost(startci2 2、添加城市：輸入命令 1 1 后，按提示輸入城市名，而后返回主界面 刪除路線: In itSysData() DelPat

36、h( name) SaveSysI nfo() 添加路線： In itSysData() In sertFlight( name,s_city,e_city,s_hour*60+s_ minu te,e_hour*60+e_ minu te,cost) In sertFlight( name,s_city,e_city,s_hour*60+s_ minu te,e_hour*60+e_ minu te,cost) SaveSysI nfo() 六、調(diào)試結(jié)果: 1 1、主界面: In sertFlight(): SeekCity(StartCity) SeekCity(E ndCity) r f

37、t 0 礙看汨 J 詼適樣HnDebug誣過幕報(bào)朕h 線 nl 路 、 帀帀色r-Ak X X I I M M M M M M I I M M M M M Mwpe In VnLAF C.Gvnnand； E P：圏墻汨匚運(yùn)模世yje bj g總漁衰U.弋刑申己 j/pe In Vunr Ccinb inid-丄 Type In Vonr Connand： 半： X. 原 citycity 文件: 添加城市后的 citycity 文件:- - - - S SH H- - 專憂 路 誠(chéng)更?測(cè)最 陳加肪禺岀 仰杼雪舌正 .二 線程線 、幣幣r rlfilfi- -. . A A快 叢S:S:倉刼 加除加萼詢岀 添刪添刪查退 -citye -記李4 =回 EZ I 筈卿SMKE) 3 3、刪除城市：輸入命令 2 2 后，按提示輸入城市名，而后返回主界面 線 KK BlBl 、市羸 誠(chéng)s:.zs:.z執(zhí)最 除加除10J10J詢岀 刪厲翌3 3退 E E 寧帀幣通fe, 一威克亠笑答I I取 一加除加屠詢岀 - -1 1添里香退 二 蘭 : 2 : 2 : : : : : H HMM Type Im Vunr C 油 應(yīng)州：DFSTrNorroN? lin Cost : 12G 結(jié)果正確！ 7 7、查找最小時(shí)間花費(fèi)：輸入命令 6 6 后，按提示輸入城市名，而后返 r