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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目： 全國交通咨詢模擬系統(tǒng) 院 （系）： 計(jì)算機(jī)工程學(xué)院 專 業(yè)： 嵌入式系統(tǒng)開發(fā)與設(shè)計(jì) 班 級： 嵌入式1091 學(xué) 生： 指導(dǎo)教師： 2011年 1月36目 錄一、設(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)決策方案：

2、（1）時(shí)間最短（2）費(fèi)用最小（3）中轉(zhuǎn)次數(shù)最少，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成。2、要求：該程序所做的工作的是模擬全國交通咨詢，為旅客提供三種最優(yōu)決策的交通咨詢。此程序規(guī)定：（1） 在程序中輸入城市名稱時(shí)，需輸入10個(gè)字母以內(nèi)的字母串；輸入列車或飛機(jī)編號時(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í)乘坐哪一趟列車或哪一次班

3、機(jī)到何地。（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_verte

4、x_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ù)組中的位置，即該城市編號 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 pn

6、ode int city; int trano; pnodedat; vnodedat adjlistmax_vertex_num; /system info char citynamemax_vertex_nummax_string_num; /城市名，采用第一下標(biā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 sh

7、owmenu() 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

8、;int 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;icity

10、num;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, ad

11、jlisti.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

12、,j; 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; strc

13、py(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(st

14、artcity); 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; adjl

16、isti.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 (

17、;jadjlisti.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; adjlis

18、ti.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.t

19、raink.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:,citynametrac

20、ki); 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.flight

21、tmp.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;

22、 precityp_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 st

23、mp2max_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 (!f

24、p) 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:

25、%d,&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) print

26、f(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

27、%1440)&(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+(curtim

28、e/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; searchmi

29、ntime(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,adj

30、listcity.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.

31、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; searchmintime(adjliststartcity.flighti.endcity,endcity,adjliststartcity.flighti.

32、stoptime,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) pr

33、intf(%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.startt

34、ime%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;

35、 int 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.cos

36、t; 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: /添加城市 in

38、itsysdata(); 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(輸入班次:)