全国交通咨询模拟系统实验报告

1、浙江工商大学计算机与信息工程学院 数据结构实验大作业报告 专 业： 软件工程 _ 班 级： 软件1101 _ 学 号： 33 _ 姓 名： _ 沈艳 _ 指导教师： 吴海燕 _ 2012年5 月目录 、问题描述 二、 数据结构设计及核心算法描述 三、 主控及功能模块层次结构 四、 主要功能函数代码 五、 功能模块之间的调用与被调用的关系 六、 测试结果 七、课程设计小结、问题描述 全国交通咨询模拟：处于对不同目的的旅客对交通工具有不同的要求。 例如, 因公出差的旅客希望在旅途中的时间尽可能短， 出门旅游的游客则希望旅费尽可 能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，

2、 为旅客提供两种或三种最优决策的交通咨询。 【基本要求】(1)提供对城市信息进行编辑(如：添加或删除)的功能 (2) 城市之间有两种交通工具：火车和飞机。提供对列车时刻表和 飞机航班进行编辑(增设或删除)的功能。 (3) 提供两种最优决策：最快到达或最省钱到达。全程只考虑一种 交通工具。 (4) 旅途中耗费的总时间应该包括中转站的等候时间。 (5) 咨询以用户和计算机的对话方式进行。由用户输入起始站、终 点站、最优决策原则和交通工具，输出信息：最快需要多长时 间才能到达或者最少需要多少旅费才能到达，并详细说明依次 于何时乘坐哪一趟列车或哪一次班机到何地。 二、数据结构设计和核心算法设计描述：

3、1 1、根据题目中的基本要求分析，可以创建系统概念模型，流程设计 框图如下：【测试数 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、核心设计：根据上面的流程图和逻辑拆分，对这个问题有了一个比较直观， 详细地了解。并且从中也可得知路线的添加即数据的存储是这个系统进行运作的 一个基础。而为了便于数据的存

4、储、添加、删除等操作，我选择了储存文件对这 些数据进行了存储。将每个信息量放在不同的文件中， 可以更有效、直观地对这 些数据进行处理。 流程图中的7个主要功能模块在主函数中，采用输入选项进入子菜单，但是 其他操作都是在路线添加好后进行的， 并且为了每一项功能进行完后，系统可以以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外， 包 括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。 2 2、逻辑结构拆分: 及时回到主交互界面，我采用的是无限循环形式，即 while （1） 三、主控及功能模块层次结构： 1、模块说明：本系统分为个模块 1、 ）主函数 2、 ）添加城市

5、 3、 ）查找城市并返回序号 4、 ）删除城市 5、 ）添加列车 6、 ）添加航班 7、 ）删除列车或航班 8、 ）找出最小费用路线 9、 ）初始化系统数据（读入内存） 10、 ）找出最快路线 11、 ）计算最快路线耗费的时间并打印 12、 ）计算最小费用路线 13、 ）主界面 14、 ）存储信息到文件 15、 ）退出、 2 2、下面是各模块示意图: 初始化系坦 数猱从文 冰加城帀 档请入內存 存昭信盘到文件 数贡（从文 栏读入內存 刪除城帀 存储信总到文件 1 r q 初殆化系堀 数贡从文 档诸入內存 添加航班 济加列丰 存储信总到文件 地除艾進路续 r F 5 f 初蜡化孚我 割内殍） 计

6、篦导快建 纯耗資的町 司列川 程储佶息到文斗 基本操作: TrafficNodeDat 交通工具 信息 Char n ameMAX_STRING_N UM 班次 Int starttime 出发时间 Int starttime 到达时间 Int cost 票价 UNodeDat 路线 信息 Short int city 城市编号 Int TrainNum 火车路线数 int FlightNum 航班路线数 TrafficNodeDat Trai nMAX_TRAFFIC_ NUM 火车路线信息 TrafficNodeDat FlightMAX TRAFFIC 航班路线信息 NUM 函数变量声明

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 一-芒运吕坯(寸) 宀

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) 找出最小费用路线 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)计算最快路线所需时间并打印： 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; 五、功能模块间函数的调用关系，如下图所示： 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() 六、调试结果: 1 1、主界面: In sertFlight(): SeekCity(StartCity) SeekCity(E ndCity) r f

37、t 0 礙看汨 J 诙适樣HnDebug诬過幕报朕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：圏墙汨匚运模世yje bj g总渔衰U.弋刑申己 j/pe In Vunr Ccinb inid-丄 Type In Vonr Connand： 半： X. 原 citycity 文件: 添加城市后的 citycity 文件:- - - - S SH H- - 專憂 路 诚更?测最 陈加肪禺岀 仰杼雪舌正 .二 线程线 、币币r rlfilfi- -. . A A快 叢S:S:倉刼 加除加萼询岀 添删添删查退 -citye -记李4 =回 EZ I 筈卿SMKE) 3 3、删除城市：输入命令 2 2 后，按提示输入城市名，而后返回主界面 线 KK BlBl 、市羸 誠s:.zs:.z執最 除加除10J10J询岀 删厉翌3 3退 E E 宁帀币通fe, 一威克亠笑答I I取 一加除加屠询岀 - -1 1添里香退 二 兰 : 2 : 2 : : : : : H HMM Type Im Vunr C 油 应州：DFSTrNorroN? lin Cost : 12G 结果正确！ 7 7、查找最小时间花费：输入命令 6 6 后，按提示输入城市名，而后返 r