交通咨询系统设计

1、交通咨询系统设计实验目的和要求1.掌握最短路径的算法；2.编写实验报告；实验内容本设计要求一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径、最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或所需费用。实验步骤1、问题分析该设计分为三个部分：l建立交通网络图的存储结构l解决单源最短路径问题l实现两个城市顶点之间的最短路径问题2、问题求解l2.1建立交通网络图的存储结构图的邻接矩阵#definemvnum50typedefstructvertextypevexsmvnum;/顶点信息adjmatrixarcsmvnummvnum;/邻接矩阵边的

2、信息mgraphl2.2单源最短路径dijkstra算法按路径长度递增产生诸顶点的最短路径l2.3任意两个顶点之间的最短路径floyd算法3、完整的程序清单4、程序运行测试#includestdafx.h#include#include#definemvnum50#definedij_maxn33#definemax_vertex_num31#definemax_string_num10#definemax_traffic_num10typedefstructtrafficnode1/8charnamemax_string_num;inttime;/intendcity/火车到达城市的编号in

3、tcost;/票价trafficnodedat;typedefstructvnodecitytypecity;/城市编号inttrainnum;/标记下面train数组里元素个数trafficnodedattrainmax_traffic_num;/数组成员为结构体，记录了到达城市、起止时间、票价和班次vnodedat;typedefstructtrafficnodecharnamemax_string_num;/班次inttime;intendcity;/火车到达城市的编号intcost;/票价trafficnodedat;typedefstructvnodecitytypecity;/城市

4、编号intflightnum;/标记下面train数组和flight数组里元素个数trafficnodedatflightmax_traffic_num;vnodedat;intmain()switch(command)case0:return0;case1:administrators();/管理员操作界面函数break;case2:user();/用户操作界面函数break;default:coutt选择序号错误!请重新选择!n;intinitsystem()voiduser()voidadministrators()intdelcity(char*name)/删除城市/删除城市2/8in

5、tcity,i,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;strcpy(a

6、djlisti.f,adjlisti+1.f);adjlisti.flightj.time=adjlisti+1.flightj.time;citynum-;return1;intdelpath(char*name)/删除路线/删除路线inti,j,flag=0;for(i=0;icitynum;i+)for(j=0;jadjlisti.flightnum;j+)if(strcmp(adjlisti.f,name)=0)flag=1;break;/找到要删除的路线，找到跳出for循环if(flag)for(;jadjlisti.

7、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.time=adjlisti.flightj+1.time;adjlisti.flightnum-;/将要删除路线后面的路线全部向前移，并将总数减1break;for(j=0;jadjlisti.trainnum;j+)3/8if(s

8、trcmp(adjlisti.t,name)=0)flag=1;break;if(flag)for(;jadjlisti.trainnum-1;j+)adjlisti.trainj.cost=adjlisti.trainj+1.cost;adjlisti.trainj.endcity=adjlisti.trainj+1.endcity;strcpy(adjlisti.t,adjlisti.trainj+1.name);adjlisti.trainj.time=adjlisti.trainj+1.time;adjlisti.trainnum-;break;

9、return1;intinsertcity(char*name)/添加某个城市/添加城市strcpy(citynamecitynum,name);adjlistcitynum.city=citynum;/设置城市编号adjlistcitynum.flightnum=0;adjlistcitynum.trainnum=0;/新增城市火车数和飞机数初始为零citynum+;/城市总数加1return1;intinsertflight(char*flight,char*startcity,char*endcity,inttime,intcost)/添加某架航班/添加飞机路线inti,j;i=seek

10、city(startcity);j=seekcity(endcity);adjlisti.flightadjlisti.flightnum.cost=cost;adjlisti.flightadjlisti.flightnum.endcity=j;adjlisti.flightadjlisti.flightnum.time=time;strcpy(adjlisti.flightadjlisti.flightn,flight);adjlisti.flightnum+;return1;4/8intinserttrain(char*train,char*startcity,char*e

11、ndcity,inttime,intcost)/添加某次列车/添加火车路线inti,j;i=seekcity(startcity);j=seekcity(endcity);adjlisti.trainadjlisti.trainnum.cost=cost;adjlisti.trainadjlisti.trainnum.endcity=j;adjlisti.trainadjlisti.trainnum.time=time;strcpy(adjlisti.trainadjlisti.trainn,train);adjlisti.trainnum+;return1;voiddijkst

12、ra(ints3030,intp_start,intp_end,inttraveltype)intprecity30;inti,j,min,pre,pos;for(i=0;icitynum;i+)precityi=-1;precityp_start=-2;while(precityp_end=-1)min=-1;for(i=0;icitynum;i+)if(precityi!=-1)/i为起始站for(j=0;j0&(min0|sijmin)pre=i;pos=j;/j为起始站中花费最小的到达站的城市编号min=sij;precitypos=pre;dijkstra_output(s,prec

13、ity,p_end,traveltype);intcalcmincost(intstartcity,intendcity,inttraveltype)/查询最小耗费路线ints3030;inti,j,min,end,flag1,flag2;5/8flag1=0;flag2=0;for(i=0;icitynum;i+)for(j=0;jcitynum;j+)sij=-1;/设空路径if(traveltype=0)/判断初始城市和终点城市是否在火车交通路线中for(i=0;icitynum;i+)for(j=0;jadjlisti.trainnum;j+)if(adjlisti.trainj.en

14、dcity=startcity)flag1=1;if(adjlisti.trainj.endcity=endcity)flag2=1;elseif(traveltype=1)/判断初始和终点城市是否在飞机交通路线中for(i=0;icitynum;i+)for(j=0;jadjlisti.flightnum;j+)if(adjlisti.flightj.endcity=startcity)flag1=1;if(adjlisti.flightj.endcity=endcity)flag2=1;if(flag1!=1&flag2!=1)printf(nt抱歉!没有您要查找的路线!);return0

15、;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;j+;/min为i城市中的最小花费，end为其路线终点站6/8siend=min;elsefor(i=0;icitynum;i+)min=32767;j=0;wh

16、ile(jadjlisti.flightnum)min=32767;end=adjlisti.flightj.endcity;while(end=adjlisti.flightj.endcity&jadjlisti.flightnum)if(adjlisti.flightj.costmin)min=adjlisti.flightj.cost;j+;siend=min;dijkstra(s,startcity,endcity,traveltype);return1;/存储数据函数intsavefile()/将火车飞机交通信息写入文件file*fp;inti,j,total;if(fp=fopen

17、(city.txt,wb)=null)coutnt无法打开文件!n;return-1;fprintf(fp,%dn,citynum);/在city文件中输入城市总数for(i=0;icitynum;i+)fprintf(fp,%sn,citynamei);/再输入城市名fclose(fp);total=0;if(fp=fopen(train.txt,wb)=null)7/8coutnt无法打开文件!n;return-1;for(i=0;icitynum;i+)total+=adjlisti.trainnum;fprintf(fp,%dn,total);/在train文件中输入火车总数for(i

18、=0;icitynum;i+)for(j=0;jadjlisti.trainnum;j+)fprintf(fp,%s%s%s,adjlisti.t,citynamei,citynameadjlisti.trainj.endcity);/输入火车车次，始发站和终点站fprintf(fp,%d%dn,adjlisti.trainj.time,adjlisti.trainj.cost);/输入发车时间和到站时间和费用fclose(fp);total=0;if(fp=fopen(flight.txt,wb)=null)coutnt无法打开文件!n;return-1;for(i=0;icitynum;i+)total+=adjlisti.flightnum;fpr