全国交通咨询模拟系统

#include
#include

#define ERR 0
#define OK 1
#define Dij_MAXN 33


#define MAX_VERTEX_NUM 31
#define MAX_STRING_NUM 10
#define MAX_TRAFFIC_NUM 10

const char CityFile[] ="D:\\city.txt";
const char TrainFile[] ="D:\\train.txt";
const char FlightFile[] ="D:\\flight.txt";


typedef short int CityType;

typedef struct TrafficNode
{
char name[MAX_STRING_NUM]; //班次
int StartTime,StopTime; //起止时间
int EndCity; //该有向边指向的顶点在数组中的位置，即该城市编号
int Cost; //票价
} TrafficNodeDat;

typedef struct VNode
{
CityType city;
int TrainNum,FlightNum; //标记下面Train数组和Flight数组里元素个数
TrafficNodeDat Train[MAX_TRAFFIC_NUM]; //数组成员为结构体，记录了到达城市、起止时间、票价和班次
TrafficNodeDat Flight[MAX_TRAFFIC_NUM]; // int Cost; //遍历时到达该城市的耗费（时间或者费用）
} VNodeDat;


typedef struct PNode
{
int City;
int TraNo;
} PNodeDat;

VNodeDat AdjList[MAX_VERTEX_NUM]; //System Info
char CityName[MAX_VERTEX_NUM][MAX_STRING_NUM]; //城市名，采用第一下标为该城市在本程序中的编号
int CityNum; //城市数目

PNodeDat Path[MAX_VERTEX_NUM]; //存储临时最小时间路径
PNodeDat MinPath[MAX_VERTEX_NUM]; //存储搜索到当前的最小时间路径

int MinTime,StartTime;
int curPath;



//四、主函数中的各个调用的函数代码具体如下：
//（1）显示菜单：
int ShowMenu()
{
printf("\n************MENU************\n");
printf("1: 添加城市\n2: 删除城市\n3: 添加交通路线\n4: 删除交通路线\n5: 查询最小费用路线\n6: 查询最快路线\n0: 退出");
printf("\n****************************\n");
printf("\nType In Your Command:");
return 1;
}
//（2）查找城市并返回城市序号：
int SeekCity (char *name)
{
int i;
for (i=0;i{
if (strcmp(name,CityName[i])==0)
{
return i;
}
}
return -1;
}
//（3）储存信息到文件：
int SaveSysInfo()
{
FILE *fp;int i,j,total;
fp=fopen(CityFile,"w");
fprintf(fp,"%d\n",CityNum);
for (i=0;i{
fprintf(fp,"%s\n",CityName[i]);
}
fclose(fp);total=0;
fp=fopen(TrainFile,"w");
for (i=0;i{
total+=AdjList[i].TrainNum;
}
fprintf(fp,"%d\n",total);
for (i=0;i{
for (j=0;j{
fprintf(fp,"%s %s %s ", AdjList[i].Train[j].name,
CityName[i],
CityName[AdjList[i].Train[j].EndCity]);
fprintf(fp,"%2d:%2d %2d:%2d %d\n", AdjList[i].Train[j].StartTime/60,
AdjList[i].Train[j].StartTime%60,
AdjList[i].Train[j].StopTime/60,

AdjList[i].Train[j].StopTime%60,
AdjList[i].Train[j].Cost);
}
}
fclose(fp);total=0;
fp=fopen(FlightFile,"w");
for (i=0;i{
total+=AdjList[i].FlightNum;
}
fprintf(fp,"%d\n",total);
for (i=0;i{
for (j=0;j{
fprintf(fp,"%s %s %s ", AdjList[i].Flight[j].name,
CityName[i],
CityName[AdjList[i].Flight[j].EndCity]);
fprintf(fp,"%2d:%2d %2d:%2d %d\n", AdjList[i].Flight[j].StartTime/60,
AdjList[i].Flight[j].StartTime%60,
AdjList[i].Flight[j].StopTime/60,
AdjList[i].Flight[j].StopTime%60,
AdjList[i].Flight[j].Cost);
}
}
fclose(fp);return 1;
}
//（4）添加城市：
int InsertCity (char *Name)
{
strcpy(CityName[CityNum],Name);
AdjList[CityNum].city=CityNum;
AdjList[CityNum].FlightNum=0;
AdjList[CityNum].TrainNum=0;
CityNum++;
return 1;
}
//（5）删除城市：
int DelCity (char *Name)
{
int city,i,j;
city=SeekCity(Name);
for (i=city;i{
strcpy(CityName[i],CityName[i+1]);
AdjList[i].FlightNum=AdjList[i+1].FlightNum;
AdjList[i].TrainNum=AdjList[i+1].TrainNum;
for (j=0;j{
AdjList[i].Flight[j].Cost=AdjList[i+1].Flight[j].Cost;
AdjList[i].Flight[j].EndCity=AdjList[i+1].Flight[j].EndCity;
strcpy(AdjList[i].Flight[j].name,AdjList[i+1].Flight[j].name);
AdjList[i].Flight[j].StartTime=AdjList[i+1].Flight[j].StartTime;
AdjList[i].Flight[j].StopTime=AdjList[i+1].Flight[j].StopTime;
}
}
CityNum--;
return 1;
}
//（6）添加火车路线：
int InsertTrain (char *train,char *StartCity,char *EndCity,int StartTime,int EndTime,int cost)
{
int i,j;
i=SeekCity(StartCity);
j=SeekCity(EndCity);
AdjList[i].Train[AdjList[i].TrainNum].Cost=cost;
AdjList[i].Train[AdjList[i].TrainNum].EndCity=j;
AdjList[i].Train[AdjList[i].TrainNum].StartTime=StartTime;
AdjList[i].Train[AdjList[i].TrainNum].StopTime=EndTime;
strcpy(AdjList[i].Train[AdjList[i].TrainNum].name,train);
AdjList[i].TrainNum++;
return 1;
}
//（7）添加航班路线：
int InsertFlight(char *flight,char *StartCity,char *EndCity,int StartTime,int EndTime,int cost)
{
int i,j;
i=SeekCity(StartCity);
j=SeekCity(EndCity);
AdjList[i].Flight[AdjList[i].FlightNum].Cost=cost;
AdjList[i].Flight[AdjList[i].FlightNum].EndCity=j;
AdjList[i].Flight[AdjL

ist[i].FlightNum].StartTime=StartTime;
AdjList[i].Flight[AdjList[i].FlightNum].StopTime=EndTime;
strcpy(AdjList[i].Flight[AdjList[i].FlightNum].name,flight);
AdjList[i].FlightNum++;
return 1;
}
//（8）删除路线：
int DelPath (char *name)
{
int i,j,flag=0;
for (i=0;i{
for (j=0;jif (strcmp(AdjList[i].Flight[j].name,name)==0)
{
flag=1;
break;
}
if (flag)
{
for (;j{
AdjList[i].Flight[j].Cost=AdjList[i].Flight[j+1].Cost;
AdjList[i].Flight[j].EndCity=AdjList[i].Flight[j+1].EndCity;
strcpy(AdjList[i].Flight[j].name,AdjList[i].Flight[j+1].name);
AdjList[i].Flight[j].StartTime=AdjList[i].Flight[j+1].StartTime;
AdjList[i].Flight[j].StopTime=AdjList[i].Flight[j+1].StopTime;
}
AdjList[i].FlightNum--;
break;
}
for (j=0;jif (strcmp(AdjList[i].Train[j].name,name)==0)
{
flag=1;break;
}
if (flag)
{
for (;j{
AdjList[i].Train[j].Cost=AdjList[i].Train[j+1].Cost;
AdjList[i].Train[j].EndCity=AdjList[i].Train[j+1].EndCity;
strcpy(AdjList[i].Train[j].name,AdjList[i].Train[j+1].name);
AdjList[i].Train[j].StartTime=AdjList[i].Train[j+1].StartTime;
AdjList[i].Train[j].StopTime=AdjList[i].Train[j+1].StopTime;
}
AdjList[i].TrainNum--;
break;
}
}
return 1;
}
//（9）打印最小费用路线：
void Dijkstra_Output(int matx[Dij_MAXN][Dij_MAXN],int PreCity[Dij_MAXN],int p_end,int TravelType)
{
int track[Dij_MAXN];
int i=0,j,k,min,tmp,end,cost=0;

int startH, startM, endH, endM;//定义四个变量:startH 出发的小时，startM 出发的分钟， endH 到达的小时， endM 到达的分钟

j=p_end;track[i++]=j;
while (PreCity[j]>=0)
{
cost+=matx[PreCity[j]][j];
track[i++]=j=PreCity[j];
}
printf("\nTrack Way:");
if (!TravelType)
{
for(i--;i>0;i--)
{
printf("\n%s:",CityName[track[i]]);
end=track[i-1];min=32767;
for (k=0;kif (AdjList[track[i]].Train[k].EndCity==end&&min>AdjList[track[i]].Train[k].Cost)
{
min=AdjList[track[i]].Train[k].Cost;
tmp=k;
}

printf("%s ",AdjList[track[i]].Train[tmp].name);
startH = AdjList[track[i]].Train[tmp].StartTime/60 ;
startM = AdjList[track[i]].Train[tmp].StartTime%60;
endH = AdjList[track[i]].Train[tmp].StopTime/60 ;
endM = AdjList[track[i]].Train[tmp].StopTime%60 ;

if( !(startH/10) )
{
printf("0");
}
printf("%d:",startH);

if( !(startM/10) )
{
printf("0");
}
printf("%d -- ",startM);

if( !(endH/10) )
{
printf("0");
}
printf("%d:",endH);

if( !(endM/10) )
{
printf("0");
}
printf("%d\n",endM);

//printf("%2d:%2d-%2d:%2d",AdjList[track[i]].Train[tmp].StartTime/60,AdjList[track[i]].Train[tmp].StartTime%60,AdjList[track[i]].Train[tmp].StopTime/60,AdjList[track[i]].Train[tmp].StopTime%60);
}
}
else
{
for(i--;i>0;i--)
{
printf("\n%s:",CityName[track[i]]);
end=track[i-1];min=32767;
for (k=0;k
//这句错了，AdjList[track[i]].Train[k].EndCity改为AdjList[track[i]].Flight[k].EndCity！
/*if (AdjList[track[i]].Train[k].EndCity==end&&min>AdjList[track[i]].Flight[k].Cost)
{ */
if (AdjList[track[i]].Flight[k].EndCity==end&&min>AdjList[track[i]].Flight[k].Cost)
{
min=AdjList[track[i]].Flight[k].Cost;
tmp=k;
}
printf("%s",AdjList[track[i]].Flight[tmp].name);



startH = AdjList[track[i]].Flight[tmp].StartTime / 60 ;
startM = AdjList[track[i]].Flight[tmp].StartTime % 60;
endH = AdjList[track[i]].Flight[tmp].StopTime / 60 ;
endM = AdjList[track[i]].Flight[tmp].StopTime % 60 ;

if( !(startH/10) )
{
printf("0");
}
printf("%d:",startH);

if( !(startM/10) )
{
printf("0");
}
printf("%d -- ",startM);

if( !(endH/10) )
{
printf("0");
}
printf("%d:",endH);

if( !(endM/10) )
{
printf("0");
}
printf("%d\n",endM);

//printf("%2d:%2d-%2d:%2d",AdjList[track[i]].Flight[tmp].StartTime / 60,AdjList[track[i]].Flight[tmp].StartTime % 60,AdjList[track[i]].Flight[tmp].StopTime / 60,AdjList[track[i]].Flight[tmp].StopTime % 60);
}
}
printf("\n%s: DESTINATION!",CityName[track[0]]);
printf("\nMin Cost : %d\n",cost);
}
//（10）找出最小费用路线
void Dijkstra(int matx[Dij_MAXN][Dij_MAXN],int p_start,int p_end,int TravelType)
{

int PreCity[Dij_MAXN]; //PreCity[i]==-1,never used;
//PreCity>0,the precity of City i

int i,j,min,pre,pos;
for (i=0;i{
PreCity[i]=-1;
}
PreCity[p_start]=-2;
while (PreCity[p_end]==-1)
{
min=-1;
for (i=0;iif (PreCity[i]!=-1)
{
for (j=0;jif (PreCity[j]==-1&&matx[i][j]>0&&(min<0||matx[i][j]{
pre=i;pos=j;min=matx[i][j];
}
}
PreCity[pos]=pre;
}
Dijkstra_Output(matx,PreCity,p_end,TravelType);
}
//（11）初始化系统数据：
int InitSysData ()
{
FILE *fp;int i,j,hour,minute,num,cost;
char stmp1[MAX_STRING_NUM];
char stmp2[MAX_STRING_NUM];
char stmp3[MAX_STRING_NUM];

fp=fopen(CityFile,"r");
if (!fp)
{
printf("\nError:Cannot Open City File...\n");
return -1;
}
fscanf(fp,"%d",&CityNum);
for (i=0;i{
fscanf(fp,"%s",&CityName[i]);
AdjList[i].city=i;
AdjList[i].TrainNum=0;
AdjList[i].FlightNum=0;
}
fclose(fp);
fp=fopen(TrainFile,"r");
if (!fp)
{
printf("\nError:Cannot Open Train File...\n");
return -1;
}
fscanf(fp,"%d",&num);
for (i=0;i{
fscanf(fp,"%s",&stmp1);
fscanf(fp,"%s",&stmp2);
fscanf(fp,"%s",&stmp3);
j=SeekCity(stmp2);
AdjList[j].Train[AdjList[j].TrainNum].EndCity=SeekCity(stmp3);
strcpy(AdjList[j].Train[AdjList[j].TrainNum].name,stmp1);
fscanf(fp,"%d:%d",&hour,&minute);
AdjList[j].Train[AdjList[j].TrainNum].StartTime=hour*60+minute;
fscanf(fp,"%d:%d",&hour,&minute);
AdjList[j].Train[AdjList[j].TrainNum].StopTime=hour*60+minute;
fscanf(fp,"%d",&cost);
AdjList[j].Train[AdjList[j].TrainNum].Cost=cost;
AdjList[j].TrainNum++;
}
fclose(fp);
fp=fopen(FlightFile,"r");
if (!fp)
{
printf("\nError:Cannot Open Flight File...\n");
return -1;
}
fscanf(fp,"%d",&num);
for (i=0;i{
fscanf(fp,"%s",&stmp1);
fscanf(fp,"%s",&stmp2);
fscanf(fp,"%s",&stmp3);
j=SeekCity(stmp2);
AdjList[j].Flight[AdjList[j].FlightNum].EndCity=SeekCity(stmp3);

strcpy(AdjList[j].Flight[AdjList[j].FlightNum].name,stmp1);
fscanf(fp,"%d:%d",&hour,&minute);
AdjList[j].Flight[AdjList[j].FlightNum].StartTime=hour*60+minute;
fscanf(fp,"%d:%d",&hour,&minute);
AdjList[j].Flight[AdjList[j].FlightNum].StopTime=hour*60+minute;
fscanf(fp,"%d",&cost);
AdjList[j].Flight[AdjList[j].FlightNum].Cost=cost;
AdjList[j].FlightNum++;
}
fclose(fp);
return 1;
}
//（12）找出最快路线：
int SearchMinTime (CityType City,CityType EndCity,int CurTime,int curPathNo,int TravelType)
{
int i;
if (City==EndCity)
{
if (MinTime>CurTime-StartTime)
{
for (i=0;i<=curPathNo;i++)
{
MinPath[i].City=Path[i].City;
MinPath[i].TraNo=Path[i].TraNo;
curPath=curPathNo;
}
MinTime=CurTime-StartTime;
}
}
else
{
curPathNo++;
Path[curPathNo].City=City;
if (!TravelType)
{
for (i=0;i{
if ((AdjList[City].Train[i].StartTime>=(CurTime%1440))&&(AdjList[City].Train[i].StopTime+(CurTime/1440)*1440-StartTime{
Path[curPathNo].TraNo=i;
SearchMinTime(AdjList[City].Train[i].EndCity,EndCity,AdjList[City].Train[i].StopTime+(CurTime/1440)*1440,curPathNo,TravelType);

}
if ((AdjList[City].Train[i].StartTime<(CurTime%1440))&&(AdjList[City].Train[i].StopTime+(CurTime/1440)*1440-StartTime{
Path[curPathNo].TraNo=i;
SearchMinTime(AdjList[City].Train[i].EndCity,EndCity,AdjList[City].Train[i].StopTime+(CurTime/1440+1)*1440,curPathNo,TravelType);
}
}
}
else
{
for (i=0;i{
if ((AdjList[City].Flight[i].StartTime>=CurTime)&&(AdjList[City].Flight[i].StopTime+(CurTime/1440)*1440-StartTime{
Path[curPathNo].TraNo=i;
SearchMinTime(AdjList[City].Flight[i].EndCity,EndCity,AdjList[City].Flight[i].StopTime+(CurTime/1440)*1440,curPathNo,TravelType);

}
if ((AdjList[City].Flight[i].StartTime{
Path[curPathNo].TraNo=i;

SearchMinTime(AdjList[City].Flight[i].EndCity,EndCity,AdjList[City].Flight[i].StopTime+(CurTime/1440+1)*1440,curPathNo,TravelType);
}
}
}
}
return 1;
}
//（13）计算最快路线所需时间并打印：
int CalcMinTime (int StartCity,int EndCity,int TravelType)
{
int i;
int startH, startM, endH, endM;//定义四个变量:startH 出发的小时，startM 出发的分钟， endH 到达的小时， endM 到达的分钟
MinTime=32767;curPath=0;
Path[0].City=StartCity;
if (!TravelType)
{
for (i=0;i{
Path[0].TraNo=i;
StartTime=AdjList[StartCity].Train[i].StartTime;
SearchMinTime(AdjList[StartCity].Train[i].EndCity,EndCity,AdjList[StartCity].Train[i].StopTime,0,TravelType);

}
}
else
{
for (i=0;i{
Path[0].TraNo=i;
StartTime=AdjList[StartCity].Flight[i].StartTime;
SearchMinTime(AdjList[StartCity].Flight[i].EndCity,EndCity,AdjList[StartCity].Flight[i].StopTime,0,TravelType);

}
}
if (MinTime==32767)
{
printf("\nNo access to that destination!");
return 0;
}
// if (!TravelType)
// StartTime=AdjList[StartCity].Train[MinPath[0].TraNo].StartTime;
// else
// StartTime=AdjList[StartCity].Flight[MinPath[0].TraNo].StartTime;
printf("\nPath:\n");
for (i=0;i<=curPath;i++)
{
if (!TravelType)
printf("%s : %s ",CityName[MinPath[i].City],AdjList[MinPath[i].City].Train[MinPath[i].TraNo].name);
else
printf("%s : %s ",CityName[MinPath[i].City],AdjList[MinPath[i].City].Flight[MinPath[i].TraNo].name);


startH = AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StartTime / 60 ;
startM = AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StartTime % 60 ;
endH = AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StopTime / 60 ;
endM = AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StopTime % 60 ;

if( !(startH/10) )
{
printf("0");
}
printf("%d:",startH);

if( !(startM/10) )
{
printf("0");
}
printf("%d -- ",startM);

if( !(endH/10) )
{
printf("0");
}
printf("%d:",endH);

if( !(endM/10) )
{
printf("0");
}
printf("%d\n",endM);
//printf(" %2S:%2S-%2S:%2S\n",startH);
}
printf("%s: DESTINATION!",CityName[EndCity]);
printf("\nTime Cost: %2d hour - %2d minute",MinTime/60,MinTime%60);
return 1;
}
//（14）计算最小费用路线：
int Ca

lcMinCost (int StartCity,int EndCity,int TravelType)
{
int ma[Dij_MAXN][Dij_MAXN];
int i,j,min,end;
for (i=0;ifor (j=0;jma[i][j]=-1;
if (TravelType==0)
{
for (i=0;i{
min=32767;j=0;
while (j{
min=32767;
end=AdjList[i].Train[j].EndCity;
while (end==AdjList[i].Train[j].EndCity&&j{
if (AdjList[i].Train[j].Cost{
min=AdjList[i].Train[j].Cost;
}
j++;
}
ma[i][end]=min;
}
}
}
else
{
for (i=0;i{
min=32767;j=0;
while (j{
min=32767;
end=AdjList[i].Flight[j].EndCity;
while (end==AdjList[i].Flight[j].EndCity&&j{
if (AdjList[i].Flight[j].Cost{
min=AdjList[i].Flight[j].Cost;
}
j++;
}
ma[i][end]=min;
}
}
}
Dijkstra(ma,StartCity,EndCity,TravelType);
return 1;
}

//函数构成：
int main()
{
char name[MAX_STRING_NUM];
char s_city[MAX_STRING_NUM];
char e_city[MAX_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: //添加城市
InitSysData();
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("%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("输入班次:");
scanf("%s",&name);
DelPath(name);
SaveSysInfo();
printf("System Info Save OK!\n");
break;
case 5: //最小耗费
InitSysData();
printf("\n起始城市:");
scanf("%s",&name);
startcity=SeekCity(name);
if (startcity<0)
{
printf("Error City Name:No such city!\n");
break;
}
printf("终点城市:");
scanf("%s",&name);
endcity=SeekCity(name);
if (endcity<0)
{
printf("Error City Name:No such city!\n");
break;
}
printf("类型(列车0,航班1) :");
scanf("%d",&traveltype);
if (traveltype!=0&&traveltype!=1)
{
printf("Error Input!");
break;
}
CalcMinCost(startcity,endcity,traveltype);
printf("\n");
break;
case 6: //最短时间路线
InitSysData();
printf("\n起始城市:");
scanf("%s",&name);
startcity=SeekCity(name);
if (startcity<0)
{
printf("Error Cit

y Name:No such city!\n");
break;
}
printf("终点城市:");
scanf("%s",&name);
endcity=SeekCity(name);
if (endcity<0)
{
printf("Error City Name:No such city!\n");
break;
}
printf("类型(列车0,航班1) :");
scanf("%d",&traveltype);
if (traveltype!=0&&traveltype!=1)
{
printf("Error Input!");
break;
}
CalcMinTime(startcity,endcity,traveltype);
printf("\n");
break;
}
}
}