數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)交通咨詢系統(tǒng)設(shè)計(jì)

1、設(shè)計(jì)題目：7.3.4交通咨詢系統(tǒng)設(shè)計(jì)P160一、設(shè)計(jì)要求1問題描述根據(jù)不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時(shí)間盡可能的短，出門旅行的旅客希望旅費(fèi)盡可能的少，而老年人則要求中轉(zhuǎn)次數(shù)少。模擬一個(gè)全國城市之間的咨詢交通程序，為旅客提供兩種或三種最優(yōu)的交通路線。2需求分析二、概要設(shè)計(jì)1主界面設(shè)計(jì)（圖2.1“交通咨詢系統(tǒng)”主菜單）2存儲結(jié)構(gòu)設(shè)計(jì)本系統(tǒng)采用圖結(jié)構(gòu)類型存儲抽象交通咨詢系統(tǒng)的信息。typedef struct TrafficNodechar nameMAX_STRING_NUM; /班次 /MAX_STRING_NUM最為10int StartTime, S

2、topTime; /起止時(shí)間 int EndCity; /該有向邊指向的頂點(diǎn)在數(shù)組中的位置，即該城市編號 int Cost; /票價(jià) TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum, FlightNum; /標(biāo)記下面Train數(shù)組和Flight數(shù)組里元素個(gè)數(shù) TrafficNodeDat TrainMAX_TRAFFIC_NUM; /數(shù)組成員為結(jié)構(gòu)體，記錄了到達(dá)城市、起止時(shí)間、票價(jià)和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM;/ int Cost; /遍歷時(shí)到達(dá)該城市的耗費(fèi)（時(shí)間或者

3、費(fèi)用） VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat;3系統(tǒng)功能設(shè)計(jì)（1）添加城市。添加一個(gè)城市的名稱（2）刪除城市。輸入一個(gè)城市名稱，刪除該城市。（3）添加交通路線。輸入起始城市、終點(diǎn)城市、航班或火車、車次、起始時(shí)間、終點(diǎn)時(shí)間和票價(jià)（4） 刪除交通路線。輸入火車或飛機(jī)的班次刪除該交通路線。（5）查詢最小費(fèi)用路線。輸入起始城市、終點(diǎn)城市、航班或火車、車次、起始時(shí)間、終點(diǎn)時(shí)間查詢最小費(fèi)用路線。三、模塊設(shè)計(jì)1模塊設(shè)計(jì) 無向網(wǎng)操作模塊工作區(qū)模塊主程序模塊 （圖2.2 模塊調(diào)用示意圖）2系統(tǒng)子程序及功能設(shè)計(jì)（1）int ShowMe

4、nu()/主菜單（2）void CopyRight()（3）int SeekCity(char *name) /尋找城市（4）int InsertCity(char *Name) /添加城市（5）int SaveSysInfo() /向程序輸入數(shù)據(jù)（6）int DelCity(char *Name) /刪除城市（7）int InsertTrain(char *train, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost)/添加火車路線（8）int InsertFlight(char *flight, ch

5、ar *StartCity, char *EndCity, int StartTime, int EndTime, int cost)/添加飛機(jī)航線（9）int DelPath(char *name)/刪除路線（10）void Dijkstra(int matxDij_MAXNDij_MAXN, int p_start, int p_end, int TravelType)（11）int InitSysData()/存儲數(shù)據(jù)（12）int SearchMinTime(CityType City, CityType EndCity, int CurTime, int curPathNo, int

6、 TravelType)/查詢最短時(shí)間（13）int CalcMinTime(int StartCity, int EndCity, int TravelType) /顯示最短時(shí)間（14）int CalcMinCost(int StartCity, int EndCity, int TravelType)/最少花費(fèi)（15）int main()/主函數(shù)3函數(shù)主要調(diào)用關(guān)系圖15main（）89112754136361223716（圖2.3函數(shù)主要調(diào)用關(guān)系圖）四、詳細(xì)設(shè)計(jì)1數(shù)據(jù)類型定義（1）全局變量的定義typedef short int CityType;/CityType 定義短整形的變量 ty

7、pedef struct TrafficNodechar nameMAX_STRING_NUM; /班次 /MAX_STRING_NUM最為10int StartTime, StopTime; /起止時(shí)間 int EndCity; /該有向邊指向的頂點(diǎn)在數(shù)組中的位置，即該城市編號 int Cost; /票價(jià) TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum, FlightNum; /標(biāo)記下面Train數(shù)組和Flight數(shù)組里元素個(gè)數(shù) TrafficNodeDat TrainMAX_TRAFFIC_NUM; /數(shù)組成員為結(jié)

8、構(gòu)體，記錄了到達(dá)城市、起止時(shí)間、票價(jià)和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM;/ int Cost; /遍歷時(shí)到達(dá)該城市的耗費(fèi)（時(shí)間或者費(fèi)用） VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat; 2系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)（1）用戶工作區(qū)模塊的設(shè)計(jì)int ShowMenu() printf(n|*歡迎使用交通咨詢系統(tǒng)*|n);printf(n|-1: 添加城市-|);printf(n|-2: 刪除城市-|);printf(n|-3: 添加交通路線-|);printf(n|-4: 刪除交通路線

9、-|); printf(n|-5: 查詢最小費(fèi)用路線-|);printf(n|-6: 查詢最快路線-|);printf(n|-7: 清除屏幕-|);printf(n|-0: 退出-|n);printf(n|*o(_)o o(_)o *|n);printf(n請輸入你的選擇:);return 1;（2）用Dijkstra算法求兩段路程的最短距離void Dijkstra_Output(int matxDij_MAXNDij_MAXN, int PreCityDij_MAXN, int p_end, int TravelType)int trackDij_MAXN;int i = 0, j, k,

10、 min, tmp, end, cost = 0;j = p_end; tracki+ = j;while (PreCityj = 0)cost += matxPreCityjj;tracki+ = j = PreCityj;printf(nTrack Way:);if (!TravelType)for (i-; i0; i-)printf(n%s:, CityNametracki);end = tracki - 1; min = 32767;for (k = 0; kAdjListtracki.Traink.Cost)min = AdjListtracki.Traink.Cost;tmp =

11、 k;printf(%s, AdjListtracki.T);printf(%2d:%2d-%2d:%2d, AdjListtracki.Traintmp.StartTime / 60, AdjListtracki.Traintmp.StartTime % 60, AdjListtracki.Traintmp.StopTime / 60, AdjListtracki.Traintmp.StopTime % 60);elsefor (i-; i0; i-)printf(n%s:, CityNametracki);end = tracki - 1; min = 32767;

12、for (k = 0; kAdjListtracki.Flightk.Cost)min = AdjListtracki.Flightk.Cost;tmp = k;printf(%s, AdjListtracki.F);printf(%2d:%2d-%2d:%2d, AdjListtracki.Flighttmp.StartTime / 60, AdjListtracki.Flighttmp.StartTime % 60, AdjListtracki.Flighttmp.StopTime / 60, AdjListtracki.Flighttmp.StopTime %

13、60);printf(n%s: DESTINATION!, CityNametrack0);printf(nMin Cost : %dn, cost);void Dijkstra(int matxDij_MAXNDij_MAXN, int p_start, int p_end, int TravelType)int PreCityDij_MAXN; /PreCityi=-1,never used; /PreCity0,the precity of City i int i, j, min, pre, pos;for (i = 0; iCityNum; i+)PreCityi = -1;PreC

14、ityp_start = -2;while (PreCityp_end = -1)min = -1;for (i = 0; iCityNum; i+)if (PreCityi != -1)for (j = 0; j0 & (min0 | matxijmin)pre = i; pos = j; min = matxij;PreCitypos = pre;Dijkstra_Output(matx, PreCity, p_end, TravelType);五、測試分析1. 添加城市在主菜單下，用戶輸入1，添加城市名稱。（圖2.4添加城市）2刪除城市在主菜單下，用戶輸入2，刪除已添加城市名稱。（圖2.

15、5刪除城市）3添加交通路線在主菜單下，用戶輸入3，已添加城市名稱。添加起始城市、終點(diǎn)城市名稱、乘車類型、乘車班次、起始時(shí)刻、終點(diǎn)時(shí)刻、和票價(jià)。 （圖2.6添加交通路線）4刪除交通路線輸入班次號，刪除交通路線（圖2.7刪除交通路線）5查詢最小費(fèi)用交通路線（圖2.8 查詢最小費(fèi)用交通路線）6查詢最快交通路線（圖2.9查詢最快交通路線）7清除屏幕8退出六、用戶手冊使用本系統(tǒng)時(shí)，用戶需先向程序添加城市后，在已有城市基礎(chǔ)上添加已有城市的路線和使用各項(xiàng)功能。 七、調(diào)試報(bào)告程序運(yùn)行無錯(cuò)誤，但當(dāng)系統(tǒng)輸入其他無儲存內(nèi)容時(shí)程序會(huì)意外中斷，代碼需要優(yōu)化。八、程序清單#include stdafx.h#include

16、 #include #include #define ERR 0 #define OK 1 #define Dij_MAXN 100 #define MAX_VERTEX_NUM 100#define MAX_STRING_NUM 100 #define MAX_TRAFFIC_NUM 100 const char CityFile = city.txt;const char TrainFile = train.txt;const char FlightFile = flight.txt;typedef short int CityType;/CityType 定義短整形的變量 typedef

17、 struct TrafficNodechar nameMAX_STRING_NUM; /班次 /MAX_STRING_NUM最為10int StartTime, StopTime; /起止時(shí)間 int EndCity; /該有向邊指向的頂點(diǎn)在數(shù)組中的位置，即該城市編號 int Cost; /票價(jià) TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum, FlightNum; /標(biāo)記下面Train數(shù)組和Flight數(shù)組里元素個(gè)數(shù) TrafficNodeDat TrainMAX_TRAFFIC_NUM; /數(shù)組成員為結(jié)構(gòu)體，記錄

18、了到達(dá)城市、起止時(shí)間、票價(jià)和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM;/ int Cost; /遍歷時(shí)到達(dá)該城市的耗費(fèi)（時(shí)間或者費(fèi)用） VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat;VNodeDat AdjListMAX_VERTEX_NUM; char CityNameMAX_VERTEX_NUMMAX_STRING_NUM; /城市名，采用第一下標(biāo)為該城市在本程序中的編號 int CityNum; /城市數(shù)目 PNodeDat PathMAX_VERTEX_NUM; /存儲臨時(shí)最小時(shí)

19、間路徑 PNodeDat MinPathMAX_VERTEX_NUM; /存儲搜索到當(dāng)前的最小時(shí)間路徑 int MinTime, StartTime;int curPath;int ShowMenu() printf(n|*歡迎使用交通咨詢系統(tǒng)*|n);printf(n|-1: 添加城市-|);printf(n|-2: 刪除城市-|);printf(n|-3: 添加交通路線-|);printf(n|-4: 刪除交通路線-|); printf(n|-5: 查詢最小費(fèi)用路線-|);printf(n|-6: 查詢最快路線-|);printf(n|-7: 清除屏幕-|);printf(n|-0: 退出

20、-|n);printf(n|*o(_)o o(_)o *|n);printf(n請輸入你的選擇:);return 1;void CopyRight()printf(n);int SeekCity(char *name) /尋找城市int i;for (i = 0; iCityNum; i+)if (strcmp(name, CityNamei) = 0) /比較函數(shù)，若相等，則返回i值return i;return -1;/=Edit Info= int SaveSysInfo() /向程序輸入數(shù)據(jù)FILE *fp; int i, j, total;fp = fopen(CityFile, w

21、); /打開CityFile文檔fprintf(fp, %dn, CityNum); /往文檔中寫城市的數(shù)量for (i = 0; iCityNum; i+)fprintf(fp, %sn, CityNamei); /往文檔中寫城市的名字fclose(fp);/將CityFile文檔關(guān)閉total = 0;fp = fopen(TrainFile, w);/打開TrainFile文檔 for (i = 0; iCityNum; i+) /計(jì)算列車班次的數(shù)量total += AdjListi.TrainNum;fprintf(fp, %dn, total); /往文檔中寫列車班次的數(shù)量for (

22、i = 0; iCityNum; i+) /for (j = 0; jAdjListi.TrainNum; j+) /往文檔中寫列車的車次、始發(fā)城市、終點(diǎn)城市fprintf(fp, %s %s %s , AdjListi.T,CityNamei,CityNameAdjListi.Trainj.EndCity);fprintf(fp, %2d:%2d %2d:%2d %dn, AdjListi.Trainj.StartTime / 60, /往文檔中寫AdjListi.Trainj.StartTime % 60,AdjListi.Trainj.StopTime / 60,Ad

23、jListi.Trainj.StopTime % 60,AdjListi.Trainj.Cost);fclose(fp); total = 0;fp = fopen(FlightFile, w);for (i = 0; iCityNum; i+)total += AdjListi.FlightNum;fprintf(fp, %dn, total);for (i = 0; iCityNum; i+)for (j = 0; j CityNum)o-;printf(未找到此城市，請重新輸入！);return 0;for (i = city; i CityNum - 1; i+) /？可能city是從

24、0開始的strcpy(CityNamei, CityNamei + 1);AdjListi.FlightNum = AdjListi + 1.FlightNum;AdjListi.TrainNum = AdjListi + 1.TrainNum;for (j = 0; j AdjListi.FlightNum; j+) /為什么沒有火車的？AdjListi.Flightj.Cost = AdjListi + 1.Flightj.Cost;AdjListi.Flightj.EndCity = AdjListi + 1.Flightj.EndCity;strcpy(AdjListi.Flightj

25、.name, AdjListi + 1.F);AdjListi.Flightj.StartTime = AdjListi + 1.Flightj.StartTime;AdjListi.Flightj.StopTime = AdjListi + 1.Flightj.StopTime;CityNum-;return 1;int InsertTrain(char *train, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost)int i, j; /InsertTrain(name,s_ci

26、ty,e_city,s_hour*60+s_minute,e_hour*60+e_minute,cost);i = SeekCity(StartCity);j = SeekCity(EndCity);AdjListi.TrainAdjListi.TrainNum.Cost = cost;AdjListi.TrainAdjListi.TrainNum.EndCity = j;AdjListi.TrainAdjListi.TrainNum.StartTime = StartTime;AdjListi.TrainAdjListi.TrainNum.StopTime = EndTime;strcpy(

27、AdjListi.TrainAdjListi.TrainN, train);AdjListi.TrainNum+; /火車的數(shù)加1return 1;int InsertFlight(char *flight, char *StartCity, char *EndCity, int StartTime, int EndTime, int cost)int i, j; i = SeekCity(StartCity);j = SeekCity(EndCity);AdjListi.FlightAdjListi.FlightNum.Cost = cost;AdjListi.FlightAd

28、jListi.FlightNum.EndCity = j;AdjListi.FlightAdjListi.FlightNum.StartTime = StartTime;AdjListi.FlightAdjListi.FlightNum.StopTime = EndTime;strcpy(AdjListi.TrainAdjListi.FlightN, flight);AdjListi.FlightNum+;return 1;int DelPath(char *name)int i, j, flag = 0;for (i = 0; iCityNum; i+)for (j = 0;

29、jAdjListi.FlightNum; j+) /注意j是從0開始的if (strcmp(AdjListi.F, name) = 0)flag = 1; break;if (flag)for (; jAdjListi.FlightNum - 1; j+) /把刪除的航班后的每個(gè)航班向前移一位AdjListi.Flightj.Cost = AdjListi.Flightj + 1.Cost;AdjListi.Flightj.EndCity = AdjListi.Flightj + 1.EndCity;strcpy(AdjListi.F, AdjLis

30、ti.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= 0)cost += matxPreCity

31、jj;tracki+ = j = PreCityj;printf(nTrack Way:);if (!TravelType)for (i-; i0; i-)printf(n%s:, CityNametracki);end = tracki - 1; min = 32767;for (k = 0; kAdjListtracki.Traink.Cost)min = AdjListtracki.Traink.Cost;tmp = k;printf(%s, AdjListtracki.T);printf(%2d:%2d-%2d:%2d, AdjListtracki.Traint

32、mp.StartTime / 60, AdjListtracki.Traintmp.StartTime % 60, AdjListtracki.Traintmp.StopTime / 60, AdjListtracki.Traintmp.StopTime % 60);elsefor (i-; i0; i-)printf(n%s:, CityNametracki);end = tracki - 1; min = 32767;for (k = 0; kAdjListtracki.Flightk.Cost)min = AdjListtracki.Flightk.Cost;tmp = k;printf

33、(%s, AdjListtracki.F);printf(%2d:%2d-%2d:%2d, AdjListtracki.Flighttmp.StartTime / 60, AdjListtracki.Flighttmp.StartTime % 60, AdjListtracki.Flighttmp.StopTime / 60, AdjListtracki.Flighttmp.StopTime % 60);printf(n%s: DESTINATION!, CityNametrack0);printf(nMin Cost : %dn, cost);void Dijkst

34、ra(int matxDij_MAXNDij_MAXN, int p_start, int p_end, int TravelType)int PreCityDij_MAXN; /PreCityi=-1,never used; /PreCity0,the precity of City i int i, j, min, pre, pos;for (i = 0; iCityNum; i+)PreCityi = -1;PreCityp_start = -2;while (PreCityp_end = -1)min = -1;for (i = 0; iCityNum; i+)if (PreCityi

35、 != -1)for (j = 0; j0 & (min0 | matxijmin)pre = i; pos = j; min = matxij;PreCitypos = pre;Dijkstra_Output(matx, PreCity, p_end, TravelType);int InitSysData()FILE *fp;int i, j, hour, minute, num, cost;char stmp1MAX_STRING_NUM;char stmp2MAX_STRING_NUM;char stmp3MAX_STRING_NUM;fp = fopen(CityFile, r);i

36、f (!fp)printf(nError:Cannot Open City File.n);return -1;fscanf(fp, %d, &CityNum);for (i = 0; iCityNum; i+)fscanf(fp, %s, &CityNamei);AdjListi.city = i;AdjListi.TrainNum = 0;AdjListi.FlightNum = 0;fclose(fp);fp = fopen(TrainFile, r);if (!fp)printf(nError:Cannot Open Train File.n);return -1;fscanf(fp,

37、 %d, &num);for (i = 0; inum; i+)fscanf(fp, %s, &stmp1); /列車的車次fscanf(fp, %s, &stmp2); /列車的始發(fā)站fscanf(fp, %s, &stmp3); /列車的終點(diǎn)站j = SeekCity(stmp2);AdjListj.TrainAdjListj.TrainNum.EndCity = SeekCity(stmp3); /將列車的車次、始發(fā)站、終點(diǎn)站、出發(fā)時(shí)間、到達(dá)時(shí)間讀出strcpy(AdjListj.TrainAdjListj.TrainN, stmp1);fscanf(fp, %d:%d,

38、&hour, &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 (!fp)printf(nError:Cannot Open Flight File.n);return -1;fscanf(fp, %d, &num);for (i = 0; iCurTime - StartTime)for (i = 0; i = curPathNo; i+)MinPathi.City = Pathi.City;MinPathi.TraNo = Pathi.TraNo;curPath = curPathNo;Min