1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目： 全國交通咨詢模擬系統(tǒng) 院 （系）： 計(jì)算機(jī)工程學(xué)院 專 業(yè)： 嵌入式系統(tǒng)開發(fā)與設(shè)計(jì) 班 級(jí)： 嵌入式1091 學(xué) 生： 指導(dǎo)教師： 2011年 1月目 錄一、設(shè)計(jì)目的1二、設(shè)計(jì)內(nèi)容1三、程序設(shè)計(jì)步驟2四、調(diào)試分析33五、測試結(jié)果33六、課程設(shè)計(jì)小結(jié)36一、設(shè)計(jì)目的1實(shí)習(xí)目的通過實(shí)習(xí)，了解并初步掌握設(shè)計(jì)、實(shí)現(xiàn)較大系統(tǒng)的完整過程，包括系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開發(fā)打好基礎(chǔ)。二、設(shè)計(jì)內(nèi)容1、系統(tǒng)名稱：航空客運(yùn)訂票系統(tǒng) 設(shè)計(jì)、實(shí)現(xiàn)一個(gè)全國大城市間的交通咨詢程序，為旅客提供三種最優(yōu)決策方案：（1

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

3、何地。（3）程序的功能包括：提供對城市信息的編輯，提供列車時(shí)刻表和飛機(jī)航班表的編輯，提供三種最優(yōu)決策：最快到達(dá)、最省錢到達(dá)、最少中轉(zhuǎn)次數(shù)到達(dá)。三、程序設(shè)計(jì)步驟全國交通咨詢模擬問題描述：處于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時(shí)間盡可能的短，出門旅游的游客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個(gè)全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。 #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; /起止時(shí)間 int EndCity; /該有向邊指向的

5、頂點(diǎn)在數(shù)組中的位置，即該城市編號(hào) int Cost; /票價(jià) TrafficNodeDat; typedef struct VNode CityType 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í)間或者費(fèi)用） VNodeDat; typedef struct PNod

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

7、Menu() printf(n*MENU*n); printf(1: 添加城市n2: 刪除城市n3: 添加交通路線n4: 刪除交通路線n5: 查詢最小費(fèi)用路線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(終點(diǎn)站城市名:); scanf(%s,&e_city); printf(類型（列車0，航班1）:); scanf(%d,&traveltype); printf(輸入列車/飛機(jī)班次:); scanf(%s,&name); printf(起始時(shí)刻(00:00，24小時(shí)制):); scanf(%2d:%2d,&s_hour,&s_minute); printf(到達(dá)時(shí)刻(00:00，24小時(shí)制):); scanf(%2d:%2d,&e_hour,&e_minute); printf(票價(jià):);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(輸入班次:)