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

全国交通咨询模拟


问题描述：处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。


#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[] ="E:\\city.txt";
const char TrainFile[] ="E:\\train.txt";
const char FlightFile[] ="E:\\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;

//==================================================================================

int ShowMenu()
{
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;i{
if (strcmp(name,CityName[i])==0)
{
return i;
}
}
return -1;
}

//=============================================Edit Info====================================================

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].En

dCity]);
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;
}

int InsertCity (char *Name)
{
strcpy(CityName[CityNum],Name);
AdjList[CityNum].city=CityNum;
AdjList[CityNum].FlightNum=0;
AdjList[CityNum].TrainNum=0;
CityNum++;
return 1;
}

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;
}

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;
}

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[AdjList[i].FlightNum].StartTime=StartTime;
AdjList[i].Flight[AdjList[i].FlightNum].StopTime=EndTime;
strcpy(AdjList[i].Train[AdjList[i].FlightNum].name,flight);
AdjList[i].FlightNum++;
return 1;
}

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].Fligh

t[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;
}

//==============================================Check Info================================================

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;
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);
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;kif (AdjList[track[i]].Train[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);
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);
}

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);
}


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;
}

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].St

opTime+(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;
}

int CalcMinTime (int StartCity,int EndCity,int TravelType)
{
int i;
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);
printf(" %2d:%2d-%2d:%2d\n",AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StartTime/60,AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StartTime%60,AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StopTime/60,AdjList[MinPath[i].City].Train[MinPath[i].TraNo].StopTime%60);
}
printf("%s: DESTINATION!",CityName[EndCity]);
printf("\nTime Cost: %2d:%2d",MinTime/60,MinTime%60);
return 1;
}

int CalcMinCost (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;
}
}
}
Dijk

stra(ma,StartCity,EndCity,TravelType);
return 1;
}

//========================================Main ()=================================================

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 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;
}
CalcMinTime(startcity,endcity,traveltype);
printf("\n");
break;
}
}
}