数据结构课程设计报告全国交通咨询模拟系统

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(输入班次:)