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

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

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

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

5、頂點在數(shù)組中的位置，即該城市編號 int cost; /票價 trafficnodedat; typedef struct vnode citytype city; int trainnum,flightnum; /標記下面train數(shù)組和flight數(shù)組里元素個數(shù) trafficnodedat trainmax_traffic_num; /數(shù)組成員為結(jié)構(gòu)體，記錄了到達城市、起止時間、票價和班次 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; /城市數(shù)目 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(輸入班次:)