1、數據結構課程設計報告題 目： 全國交通咨詢模擬系統 院 （系）： 計算機工程學院 專 業： 嵌入式系統開發與設計 班 級： 嵌入式1091 學 生： 指導教師： 2011年 1月目 錄一、設計目的1二、設計內容1三、程序設計步驟2四、調試分析33五、測試結果33六、課程設計小結36一、設計目的1實習目的通過實習，了解并初步掌握設計、實現較大系統的完整過程，包括系統分析、編碼設計、系統集成、以及調試分析，熟練掌握數據結構的選擇、設計、實現以及操作方法，為進一步的應用開發打好基礎。二、設計內容1、系統名稱：航空客運訂票系統 設計、實現一個全國大城市間的交通咨詢程序，為旅客提供三種最優決策方案：（1

2、）時間最短（2）費用最小（3）中轉次數最少，以使上述業務可以借助計算機來完成。2、要求：該程序所做的工作的是模擬全國交通咨詢，為旅客提供三種最優決策的交通咨詢。此程序規定：（1） 在程序中輸入城市名稱時，需輸入10個字母以內的字母串；輸入列車或飛機編號時需輸入一個整型數據；輸入列車或飛機的費用時需輸入一個實型數據；輸入列車或飛機開始時間和到達時間時均需輸入兩個整型數據（以hh：mm的形式）；在選擇功能時，應輸入與所選功能對應的一個整型數據。（2）程序的輸出信息主要是：最快需要多少時間才能到達，或最少需要多少旅費才能到達，或最少需要多少次中轉到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到

3、何地。（3）程序的功能包括：提供對城市信息的編輯，提供列車時刻表和飛機航班表的編輯，提供三種最優決策：最快到達、最省錢到達、最少中轉次數到達。三、程序設計步驟全國交通咨詢模擬問題描述：處于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能的短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優決策的交通咨詢。 #include#include #include #define ERR 0 #define OK 1 #define Dij_MAXN 33 #define MAX_VERTEX_

4、NUM 31 #define MAX_STRING_NUM 10 #define MAX_TRAFFIC_NUM 10 const char CityFile =E:city.txt; const char TrainFile =E:train.txt; const char FlightFile =E:flight.txt; typedef short int CityType; typedef struct TrafficNode char nameMAX_STRING_NUM; /班次 int StartTime,StopTime; /起止時間 int EndCity; /該有向邊指向的

5、頂點在數組中的位置，即該城市編號 int Cost; /票價 TrafficNodeDat; typedef struct VNode CityType city; int TrainNum,FlightNum; /標記下面Train數組和Flight數組里元素個數 TrafficNodeDat TrainMAX_TRAFFIC_NUM; /數組成員為結構體，記錄了到達城市、起止時間、票價和班次 TrafficNodeDat FlightMAX_TRAFFIC_NUM; / int Cost; /遍歷時到達該城市的耗費（時間或者費用） VNodeDat; typedef struct PNod

6、e int City; int TraNo; PNodeDat; VNodeDat AdjListMAX_VERTEX_NUM; /System Info char CityNameMAX_VERTEX_NUMMAX_STRING_NUM; /城市名，采用第一下標為該城市在本程序中的編號 int CityNum; /城市數目 PNodeDat PathMAX_VERTEX_NUM; /存儲臨時最小時間路徑 PNodeDat MinPathMAX_VERTEX_NUM; /存儲搜索到當前的最小時間路徑 int MinTime,StartTime; int curPath; /= int Show

7、Menu() printf(n*MENU*n); printf(1: 添加城市n2: 刪除城市n3: 添加交通路線n4: 刪除交通路線n5: 查詢最小費用路線n6: 查詢最快路線n0: 退出); printf(n*n); printf(nType In Your Command:); return 1; int SeekCity (char *name) int i; for (i=0;iCityNum;i+) if (strcmp(name,CityNamei)=0) return i; return -1; /=Edit Info= int SaveSysInfo() FILE *fp;i

8、nt i,j,total; fp=fopen(CityFile,w); fprintf(fp,%dn,CityNum); for (i=0;iCityNum;i+) fprintf(fp,%sn,CityNamei); fclose(fp);total=0; fp=fopen(TrainFile,w); for (i=0;iCityNum;i+) total+=AdjListi.TrainNum; fprintf(fp,%dn,total); for (i=0;iCityNum;i+) for (j=0;jAdjListi.TrainNum;j+) fprintf(fp,%s %s %s ,

9、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, AdjListi.Trainj.StopTime%60, AdjListi.Trainj.Cost); fclose(fp);total=0; fp=fopen(FlightFile,w); for (i=0;iCityNu

10、m;i+) total+=AdjListi.FlightNum; fprintf(fp,%dn,total); for (i=0;iCityNum;i+) for (j=0;jAdjListi.FlightNum;j+) fprintf(fp,%s %s %s , AdjListi.F, CityNamei, CityNameAdjListi.Flightj.EndCity); fprintf(fp,%2d:%2d %2d:%2d %dn, AdjListi.Flightj.StartTime/60, AdjListi.Flightj.StartTime%60, AdjL

11、isti.Flightj.StopTime/60, AdjListi.Flightj.StopTime%60, AdjListi.Flightj.Cost); fclose(fp);return 1; int InsertCity (char *Name) strcpy(CityNameCityNum,Name); AdjListCityNum.city=CityNum; AdjListCityNum.FlightNum=0; AdjListCityNum.TrainNum=0; CityNum+; return 1; int DelCity (char *Name) int city,i,j

12、; city=SeekCity(Name); for (i=city;iCityNum-1;i+) strcpy(CityNamei,CityNamei+1); AdjListi.FlightNum=AdjListi+1.FlightNum; AdjListi.TrainNum=AdjListi+1.TrainNum; for (j=0;jAdjListi.FlightNum;j+) AdjListi.Flightj.Cost=AdjListi+1.Flightj.Cost; AdjListi.Flightj.EndCity=AdjListi+1.Flightj.EndCity; strcpy

13、(AdjListi.F,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; i=SeekCity(Star

14、tCity); j=SeekCity(EndCity); AdjListi.TrainAdjListi.TrainNum.Cost=cost; AdjListi.TrainAdjListi.TrainNum.EndCity=j; AdjListi.TrainAdjListi.TrainNum.StartTime=StartTime; AdjListi.TrainAdjListi.TrainNum.StopTime=EndTime; strcpy(AdjListi.TrainAdjListi.TrainN,train); AdjListi.TrainNum+; return 1;

15、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.FlightAdjListi.FlightNum.EndCity=j; AdjListi.FlightAdjListi.FlightNum.StartTime=StartTime; AdjLis

16、ti.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;jAdjListi.FlightNum;j+) if (strcmp(AdjListi.F,name)=0) flag=1;break; if (flag) for (;j

17、AdjListi.FlightNum-1;j+) AdjListi.Flightj.Cost=AdjListi.Flightj+1.Cost; AdjListi.Flightj.EndCity=AdjListi.Flightj+1.EndCity; strcpy(AdjListi.F,AdjListi.Flightj+1.name); AdjListi.Flightj.StartTime=AdjListi.Flightj+1.StartTime; AdjListi.Flightj.StopTime=AdjListi.Flightj+1.StopTime; AdjListi

18、.FlightNum-;break; for (j=0;jAdjListi.TrainNum;j+) if (strcmp(AdjListi.T,name)=0) flag=1;break; if (flag) for (;j=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.Tra

19、ink.Cost) min=AdjListtracki.Traink.Cost; tmp=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); else for(i-;i0;i-) printf(n%s:,CityNametracki

20、); end=tracki-1;min=32767; 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.Flighttm

21、p.StopTime%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; P

22、reCityp_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); int InitSysData () FILE *fp;int i,j,hour,minute,num,cost; char stmp1MAX_STRING_NUM; char stmp

23、2MAX_STRING_NUM; char stmp3MAX_STRING_NUM; fp=fopen(CityFile,r); if (!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)

24、 printf(nError:Cannot Open 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

25、,&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(

26、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; MinTime=CurTime-StartTime; else curPathNo+; PathcurPathNo.City=City; if (!TravelType) for (i=0;i=(CurTime%1

27、440)&(AdjListCity.Traini.StopTime+(CurTime/1440)*1440-StartTimeMinTime) PathcurPathNo.TraNo=i; SearchMinTime(AdjListCity.Traini.EndCity,EndCity,AdjListCity.Traini.StopTime+(CurTime/1440)*1440,curPathNo,TravelType); if (AdjListCity.Traini.StartTime(CurTime%1440)&(AdjListCity.Traini.StopTime+(CurTime/

28、1440)*1440-StartTimeMinTime) PathcurPathNo.TraNo=i; SearchMinTime(AdjListCity.Traini.EndCity,EndCity,AdjListCity.Traini.StopTime+(CurTime/1440+1)*1440,curPathNo,TravelType); else for (i=0;i=CurTime)&(AdjListCity.Flighti.StopTime+(CurTime/1440)*1440-StartTimeMinTime) PathcurPathNo.TraNo=i; SearchMinT

29、ime(AdjListCity.Flighti.EndCity,EndCity,AdjListCity.Flighti.StopTime+(CurTime/1440)*1440,curPathNo,TravelType); if (AdjListCity.Flighti.StartTimeCurTime)&(AdjListCity.Flighti.StopTime+(CurTime/1440)*1440-StartTimeMinTime) PathcurPathNo.TraNo=i; SearchMinTime(AdjListCity.Flighti.EndCity,EndCity,AdjLi

30、stCity.Flighti.StopTime+(CurTime/1440+1)*1440,curPathNo,TravelType); return 1; int CalcMinTime (int StartCity,int EndCity,int TravelType) int i; MinTime=32767;curPath=0; Path0.City=StartCity; if (!TravelType) for (i=0;iAdjListStartCity.TrainNum;i+) Path0.TraNo=i; StartTime=AdjListStartCity.Traini.St

31、artTime; SearchMinTime(AdjListStartCity.Traini.EndCity,EndCity,AdjListStartCity.Traini.StopTime,0,TravelType); else for (i=0;iAdjListStartCity.FlightNum;i+) Path0.TraNo=i; StartTime=AdjListStartCity.Flighti.StartTime; SearchMinTime(AdjListStartCity.Flighti.EndCity,EndCity,AdjListStartCity.Flighti.St

32、opTime,0,TravelType); if (MinTime=32767) printf(nNo access to that destination!); return 0; / if (!TravelType) / StartTime=AdjListStartCity.TrainMinPath0.TraNo.StartTime; / else / StartTime=AdjListStartCity.FlightMinPath0.TraNo.StartTime; printf(nPath:n); for (i=0;i=curPath;i+) if (!TravelType) prin

33、tf(%s : %s,CityNameMinPathi.City,AdjListMinPathi.City.TrainMinPathi.TraN); else printf(%s : %s,CityNameMinPathi.City,AdjListMinPathi.City.FlightMinPathi.TraN); printf( %2d:%2d-%2d:%2dn,AdjListMinPathi.City.TrainMinPathi.TraNo.StartTime/60,AdjListMinPathi.City.TrainMinPathi.TraNo.StartTim

34、e%60,AdjListMinPathi.City.TrainMinPathi.TraNo.StopTime/60,AdjListMinPathi.City.TrainMinPathi.TraNo.StopTime%60); printf(%s: DESTINATION!,CityNameEndCity); printf(nTime Cost: %2d:%2d,MinTime/60,MinTime%60); return 1; int CalcMinCost (int StartCity,int EndCity,int TravelType) int maDij_MAXNDij_MAXN; i

35、nt i,j,min,end; for (i=0;iCityNum;i+) for (j=0;jCityNum;j+) maij=-1; if (TravelType=0) for (i=0;iCityNum;i+) min=32767;j=0; while (jAdjListi.TrainNum) min=32767; end=AdjListi.Trainj.EndCity; while (end=AdjListi.Trainj.EndCity&jAdjListi.TrainNum) if (AdjListi.Trainj.Costmin) min=AdjListi.Trainj.Cost;

36、 j+; maiend=min; else for (i=0;iCityNum;i+) min=32767;j=0; while (jAdjListi.FlightNum) min=32767; end=AdjListi.Flightj.EndCity; while (end=AdjListi.Flightj.EndCity&jAdjListi.FlightNum) if (AdjListi.Flightj.Costmin) min=AdjListi.Flightj.Cost; j+; maiend=min; Dijkstra(ma,StartCity,EndCity,TravelType);

37、 return 1; /=Main ()= int main() char nameMAX_STRING_NUM; char s_cityMAX_STRING_NUM; char e_cityMAX_STRING_NUM; int Command,cost; int startcity,endcity,traveltype; int s_hour,s_minute,e_hour,e_minute; while (1) ShowMenu(); scanf(%d,&Command); switch (Command) case 0: /退出 return 0; case 1: /添加城市 Init

38、SysData(); printf(n輸入城市名:); scanf(%s,&name); InsertCity(name); SaveSysInfo(); printf(System Info Save OK!n); break; case 2: /刪除城市 InitSysData(); printf(n輸入城市名:); scanf(%s,&name); DelCity(name); SaveSysInfo(); printf(System Info Save OK!n); break; case 3: /添加路線 InitSysData(); printf(起始站城市名:); scanf(%

39、s,&s_city); printf(終點站城市名:); scanf(%s,&e_city); printf(類型（列車0，航班1）:); scanf(%d,&traveltype); printf(輸入列車/飛機班次:); scanf(%s,&name); printf(起始時刻(00:00，24小時制):); scanf(%2d:%2d,&s_hour,&s_minute); printf(到達時刻(00:00，24小時制):); scanf(%2d:%2d,&e_hour,&e_minute); printf(票價:);scanf(%d,&cost); if (traveltype) InsertFlight(name,s_city,e_city,s_hour*60+s_minute,e_hour*60+e_minute,cost); else InsertTrain(name,s_city,e_city,s_hour*60+s_minute,e_hour*60+e_minute,cost); SaveSysInfo(); printf(System Info Save OK!n); break; case 4: /刪除路線 InitSysData(); printf(輸入班次:)