运行若有问题,私信。
代码如下:
#include"stdio.h"#include"stdlib.h"#include"string.h"#define MAX_VERTEX_NUM 30#define NULL 0#define MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 10#define False 0#define True 1#define INFINITY 10000typedef struct{int number;float expenditure;int begintime[2];int arrivetime[2];}Vehide;typedef struct{Vehide stata[MAX_ROUTE_NUM];int last;}infolist;typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;infolist info;}ArcNode;typedef struct VNode{char cityname[10];ArcNode *planefirstarc,*trainfirstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,planearcnum,trainarcnum;}ALGraph;typedef struct Node{int adjvex;int route;struct Node *next;}Node;typedef struct QNode{int adjvex;struct QNode *next;}QNode;typedef struct{QNode *front;QNode *rear;}LinkQueue;typedef struct TimeNode{int adjvex;int route;int begintime[2];int arrivetime[2];struct TimeNode *child[MAX_ROUTE_NUM];}TimeNode,*TimeTree;struct arc{int co;char vt[10];char vh[10];int bt[2];int at[2];float mo;}a[MAX_ARC_SIZE];char city[MAX_VERTEX_NUM][10];int TTime[2];int time[2];int time1[2];int time2[2];int c[MAX_VERTEX_NUM];int d[MAX_VERTEX_NUM];void Administer(ALGraph *G);void cityedit(ALGraph *G);void CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph(ALGraph *G);void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM]);void createtrainfile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void DestoryTimeTree(TimeTree p);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final);void flightedit(ALGraph *G);void initgraph(ALGraph *G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void MinTime(infolist arcs,int *time,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final);void TimeTreeDispose(Node *head,infolist (*arcs)[MAX_VERTEX_NUM]);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1);void UserDemand(ALGraph G);void VisitTimeTree(TimeTree p);int main(){ALGraph G;int i;printf("请选择程序功能:\n");printf("1=管理员管理\n2=用户咨询\n3=显示交通系统\n4=退出\n");printf("选择?");scanf("%d",&i);getchar();while(i!=4){switch(i){case 1:Administer(&G);break;case 2:UserDemand(G);break;case 3:PrintGraph(&G);break;}printf("\n请选择程序功能:\n");printf("1=管理员管理\n2=用户咨询\n3=显示交通系统\n4=退出\n");printf("选择?");scanf("%d",&i);getchar();}return 1;}void Administer(ALGraph *G)/*显示管理员管理项目选择界面*/{int i;printf("\n请选择管理项目:\n");printf("1=初始化交通系统\n2=城市编辑\n3=飞机航班编辑\n4=列车车次编辑\n5=返回上一级菜单\n");printf("选择?");scanf("%d",&i);getchar();while(i!=5){ switch(i){case 1:initgraph(G); //初始化交通系统break;case 2:cityedit(G);//城市编辑break;case 3:flightedit(G); //飞机航班编辑break;case 4:trainedit(G); //列车车次编辑break;}printf("\n请选择管理项目:\n");printf("1=初始化交通系统\n2=城市编辑\n3=飞机航班编辑\n4=列车车次编辑\n5=返回上一级菜单\n");printf("选择?");scanf("%d",&i);getchar();}}void initgraph(ALGraph *G)//初始化交通系统/*初始化交通系统方式选择界面*/{int i;printf("\n请选择初始化方式:\n");printf("1=键盘\n2=文档\n");printf("选择?");scanf("%d",&i);getchar();switch(i){case 1:createcityfile();createplanefile();createtrainfile();CreateGraph(G);break;case 2:CreateGraph(G);break;}}void createcityfile()/*创建城市名称文档*/{int i=0;int j;char flag='y';FILE *fp;printf("\n请输入城市名称的信息:\n");while(flag=='y'||flag=='Y'){printf("城市名称:");gets(city[i]);i++;printf("继续输入?(Y/n)");scanf("%c",&flag);getchar();}printf("\n");if((fp=fopen("city.txt","w"))==NULL){printf("无法打开文件!\n");return;}for(j=0;j<i;j++)fprintf(fp,"%s ",city[j]);fclose(fp);}void createplanefile()/*创建飞机航班文档*/{int code,bt[2],at[2]; //code航班编号,bt出发时间,at到达时间float money;int i;int count;char vt[10],vh[10],flag; //vt起始城市,vh目标城市FILE *fp;flag='y';count=0;while(flag=='Y'||flag=='y')/*flag为标志位,初值为1*/{printf("请输入飞机航班的信息:\n"); //提示"输入航班信息"printf("飞机航班编号:"); //输入航班codescanf("%d",&code);getchar();printf("起始城市:"); //输入航班的出发城市vtgets(vt);printf("目的城市:"); //输入航班的到达城市vhgets(vh);printf("航班费用:"); //输入机票价格moneyscanf("%f",&money);getchar();printf("起飞时间:"); //输入航班的出发时间btscanf("%d:%d",&bt[0],&bt[1]);getchar();while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&bt[0],&bt[1]);getchar();}printf("到达时间:"); //输入航班的到达时间atscanf("%d:%d",&at[0],&at[1]);getchar();while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&at[0],&at[1]);getchar();}a[count].co=code; // a 为程序头部定义的结构体strcpy(a[count].vt,vt);strcpy(a[count].vh,vh);a[count].bt[0]=bt[0];a[count].bt[1]=bt[1];a[count].at[0]=at[0];a[count].at[1]=at[1];a[count].mo=money;count++; //计数值count+1printf("继续输入?(Y/n)"); //提示"是否要继续输入航班信息:"scanf("%c",&flag);getchar();printf("\n");}if((fp=fopen("plane.txt","w"))==NULL) //航班文件不能以读写形式打开printf("\n无法打开文件!\n"); //提示"无法打开文件"fprintf(fp,"%d\n",count); //将计数值count写入航班车文件for(i=0;i<count;i++)fprintf(fp,"%d %s %s %d:%d %d:%d %f\n",a[i].co,a[i].vt,a[i].vh,a[i].bt[0],a[i].bt[1],a[i].at[0],a[i].at[1],a[i].mo);fclose(fp); //关闭航班文件}void createtrainfile()/*创建列车车次文档*/{int code,bt[2],at[2];float money;int i;int count;char vt[10],vh[10],flag;FILE *fp;flag='y';count=0;while(flag=='y'||flag=='Y'){printf("请输入列车车次的信息:\n");printf("列车车次编号:");scanf("%d",&code);getchar();printf("起始城市:");gets(vt);printf("目的城市:");gets(vh);printf("车次费用:");scanf("%f",&money);getchar();printf("发车时间:");scanf("%d:%d",&bt[0],&bt[1]);getchar();while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&bt[0],&bt[1]);getchar();}printf("到达时间:");scanf("%d:%d",&at[0],&at[1]);getchar();while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&at[0],&at[1]);getchar();}a[count].co=code;strcpy(a[count].vt,vt);strcpy(a[count].vh,vh);a[count].bt[0]=bt[0];a[count].bt[1]=bt[1];a[count].at[0]=at[0];a[count].at[1]=at[1];a[count].mo=money;count++;printf("继续输入?(Y/n)");scanf("%c",&flag);getchar();printf("\n");}if((fp=fopen("train.txt","w"))==NULL)printf("\n无法打开文件!\n");fprintf(fp,"%d\n",count);for(i=0;i<count;i++)fprintf(fp,"%d %s %s %d:%d %d:%d %f\n",a[i].co,a[i].vt,a[i].vh,a[i].bt[0],a[i].bt[1],a[i].at[0],a[i].at[1],a[i].mo);fclose(fp);}int LocateVertex(ALGraph *G,char *v)/*城市名在交通系统中定位操作,找出城市名在图中对应结点位置*/{int j,k;j=-1;for(k=0;k<G->vexnum;k++)if(strcmp(G->vertices[k].cityname,v)==0) //第k个结点中的城市名与传过来的城市名相同{j=k; /*记录位置*/break;}return(j);}void CreateGraph(ALGraph *G)/*用city,planea,train三个文档创建城市交通系统*/{int i,j,k;int arc_num;int count1,count2;int m,t;ArcNode *p,*q;FILE *fp;i=0;if((fp=fopen("city.txt","r"))==NULL) //打开城市文件,文件指针返回值为空{printf("\n无法打开文件!\n");return;}while(!feof(fp)) //文件不为空{fscanf(fp,"%s",city[i]);i++;}fclose(fp); //关闭文件j=0;while(j<i){strcpy(G->vertices[j].cityname,city[j]);//将 city[i] 中的内容复制到图的结构体的结点数组中;G->vertices[j].planefirstarc=NULL; // 图的结构体其他项赋初值;G->vertices[j].trainfirstarc=NULL;j++;}G->vexnum=i;if((fp=fopen("plane.txt","r"))==NULL)printf("\n无法打开文件!\n");k=0;fscanf(fp,"%d",&count1); //打开航班信息文件"plane.txt"while(k<count1){fscanf(fp,"%d %s %s %d:%d %d:%d %f",&a[k].co,&a[k].vt,&a[k].vh,&a[k].bt[0],&a[k].bt[1],&a[k].at[0],&a[k].at[1],&a[k].mo);k++;}fclose(fp); //关闭文件k=0; //a的计数变量k=0arc_num=0; //弧的计数变量 arc_num=0while(k<count1){i=LocateVertex(G,a[k].vt); //调用函数 LocateVertex(G,a[k].vt)得到起始结点的位置 ij=LocateVertex(G,a[k].vh); //调用函数 LocateVertex(G,a[k].vh)得到起始结点的位置 jq=G->vertices[i].planefirstarc;m=0;while(q!=NULL){if(q->adjvex==j) //弧 q中的邻接顶点与j相等{t=q->info.last+1; // 将数组a[i] 中的内容都复制到弧q中q->info.stata[t].number=a[k].co;q->info.stata[t].expenditure=a[k].mo;q->info.stata[t].begintime[0]=a[k].bt[0];q->info.stata[t].begintime[1]=a[k].bt[1];q->info.stata[t].arrivetime[0]=a[k].at[0];q->info.stata[t].arrivetime[1]=a[k].at[1];q->info.last=t;m=1;break;}q=q->nextarc;}if(m==0){p=(ArcNode*)malloc(sizeof(ArcNode)); //开辟一个弧结点p->adjvex=j; //将数组a[i]中的内容都复制到新的弧结点中p->info.stata[0].number=a[k].co;p->info.stata[0].expenditure=a[k].mo;p->info.stata[0].begintime[0]=a[k].bt[0];p->info.stata[0].begintime[1]=a[k].bt[1];p->info.stata[0].arrivetime[0]=a[k].at[0];p->info.stata[0].arrivetime[1]=a[k].at[1];p->info.last=0;p->nextarc=G->vertices[i].planefirstarc;G->vertices[i].planefirstarc=p; // 将弧结点连接到适当的位置中去arc_num++;}k++;}G->planearcnum=arc_num;if((fp=fopen("train.txt","r"))==NULL){printf("\n无法打开文件!\n");return;}k=0;fscanf(fp,"%d",&count2); //打开列车信息文件"plane.txt"while(k<count2){fscanf(fp,"%d %s %s %d:%d %d:%d %f",&a[k].co,&a[k].vt,&a[k].vh,&a[k].bt[0],&a[k].bt[1],&a[k].at[0],&a[k].at[1],&a[k].mo);k++;}fclose(fp); //关闭文件k=0; //a的计数变量k=0;arc_num=0; // 弧的计数变量 arc_num=0;while(k<count2){i=LocateVertex(G,a[k].vt); // 调用函数 LocateVertex(G,a[k].vt)得到起始结点的位置 ij=LocateVertex(G,a[k].vh); // 调用函数 LocateVertex(G,a[k].vh)得到起始结点的位置 jq=G->vertices[i].trainfirstarc;m=0;while(q!=NULL){if(q->adjvex==j) //弧 q中的邻接顶点与j相等{t=q->info.last+1; //将数组a[i] 中的内容都复制到弧q中q->info.stata[t].number=a[k].co;q->info.stata[t].expenditure=a[k].mo;q->info.stata[t].begintime[0]=a[k].bt[0];q->info.stata[t].begintime[1]=a[k].bt[1];q->info.stata[t].arrivetime[0]=a[k].at[0];q->info.stata[t].arrivetime[1]=a[k].at[1];q->info.last=t;m=1;break;}q=q->nextarc;}if(m==0){p=(ArcNode*)malloc(sizeof(ArcNode)); //开辟一个弧结点p->adjvex=j; //将数组a[i]中的内容都复制到新的弧结点中p->info.stata[0].number=a[k].co;p->info.stata[0].expenditure=a[k].mo;p->info.stata[0].begintime[0]=a[k].bt[0];p->info.stata[0].begintime[1]=a[k].bt[1];p->info.stata[0].arrivetime[0]=a[k].at[0];p->info.stata[0].arrivetime[1]=a[k].at[1];p->info.last=0;p->nextarc=G->vertices[i].trainfirstarc;G->vertices[i].trainfirstarc=p; //将弧结点连接到适当的位置中去arc_num++;}k++;}G->trainarcnum=arc_num;}int save(ALGraph *G)/*保存城市交通系统到相应的文档*/{int i,j,k,t;ArcNode *q;FILE *fp;j=0;while(j<G->vexnum){strcpy(city[j],G->vertices[j].cityname);j++;}i=0;if((fp=fopen("city.txt","w"))==NULL)printf("\n错误,无法打开文件!\n");while(i<G->vexnum){fprintf(fp,"%s ",city[i]);i++;}fclose(fp);k=0;for(i=0;i<G->vexnum;i++){q=G->vertices[i].planefirstarc;while(q!=NULL){for(t=0;t<=q->info.last;t++){strcpy(a[k].vt,G->vertices[i].cityname);strcpy(a[k].vh,G->vertices[q->adjvex].cityname);a[k].co=q->info.stata[t].number;a[k].mo=q->info.stata[t].expenditure;a[k].bt[0]=q->info.stata[t].begintime[0];a[k].bt[1]=q->info.stata[t].begintime[1];a[k].at[0]=q->info.stata[t].arrivetime[0];a[k].at[1]=q->info.stata[t].arrivetime[1];k++;}q=q->nextarc;}}if((fp=fopen("plane.txt","w"))==NULL){printf("\n无法打开文件!\n");return 0;}i=0;fprintf(fp,"%d\n",k);while(i<k){if(fprintf(fp,"%d %s %s %d:%d %d:%d %f\n",a[i].co,a[i].vt,a[i].vh,a[i].bt[0],a[i].bt[1],a[i].at[0],a[i].at[1],a[i].mo)<0)printf("\n文件写入错误!\n");i++;}fclose(fp);k=0;for(i=0;i<G->vexnum;i++){q=G->vertices[i].trainfirstarc;while(q!=NULL){for(t=0;t<=q->info.last;t++){strcpy(a[k].vt,G->vertices[i].cityname);strcpy(a[k].vh,G->vertices[q->adjvex].cityname);a[k].co=q->info.stata[t].number;a[k].mo=q->info.stata[t].expenditure;a[k].bt[0]=q->info.stata[t].begintime[0];a[k].bt[1]=q->info.stata[t].begintime[1];a[k].at[0]=q->info.stata[t].arrivetime[0];a[k].at[1]=q->info.stata[t].arrivetime[1];k++; }q=q->nextarc;}}if((fp=fopen("train.txt","w"))==NULL){printf("\n无法打开文件!\n");return 0;}i=0;fprintf(fp,"%d\n",k);while(i<k){if(fprintf(fp,"%d %s %s %d:%d %d:%d %f\n",a[i].co,a[i].vt,a[i].vh,a[i].bt[0],a[i].bt[1],a[i].at[0],a[i].at[1],a[i].mo)<0)printf("\n文件写入错误!\n");i++;}fclose(fp);return 1;}void cityedit(ALGraph *G)/*显示城市编辑项目选择界面*/{int i;printf("\n请选择城市编辑项目:\n");printf("1=增加城市\n2=删除城市\n");printf("选择?");scanf("%d",&i);getchar();if(i==1)EnterVertex(G);if(i==2)DeleteVertex(G);}void EnterVertex(ALGraph *G)/*增加城市*/{char v[10],c;int i;printf("\n请输入新增城市的名称:");gets(v);i=LocateVertex(G,v);if(i>=0&&i<G->vexnum){printf("\n错误!此城市已存在\n");return;}else{printf("\n确认?(Y/n)");c=getchar();getchar();if(c=='Y'||c=='y'){i=G->vexnum;strcpy(G->vertices[i].cityname,v);G->vertices[i].planefirstarc=NULL;G->vertices[i].trainfirstarc=NULL;G->vexnum=i+1;save(G);}elsereturn;}}void DeleteVertex(ALGraph *G) // G是程序头部定义的结构体/*删除城市*/{int i,j,k,n;char v[10],c;ArcNode *p,*q,*m;printf("\n请输入删除的城市:"); //提示"输入删除城市名"gets(v);printf("\n确认?(Y/n)"); //提示"是否确定要删除(Y/n)"c=getchar();getchar();if(c=='Y'||c=='y'){n=0; //0是记数标志,控制循环次数while(n<G->vexnum&&strcmp(G->vertices[n].cityname,v)!=0) //n<图G表头接点总个数&&图G的存储城市名与v不同,G表头结点总个数比实际大1n++; //记数值n+1if(n==G->vexnum) //n==图G表头结点总个数printf("\n错误!无法找到此城市!\n"); //提示"无法找到此城市"else{i=LocateVertex(G,v); //利用G函数找到此城市名所处在G中位置p=G->vertices[i].planefirstarc;while(p!=NULL){q=p;p=p->nextarc;free(q); //删除从此结点出发的所有航班弧}p=G->vertices[i].trainfirstarc;while(p!=NULL){q=p;p=p->nextarc;free(q); //删除从此结点出发的所有列车弧}for(j=i;j<G->vexnum-1;j++){strcpy(G->vertices[j].cityname,G->vertices[j+1].cityname); //将G第j个结点的信息依前移1位G->vertices[j].planefirstarc=G->vertices[j+1].planefirstarc;G->vertices[j].trainfirstarc=G->vertices[j+1].trainfirstarc;}G->vertices[j].planefirstarc=NULL; //将G第j个结点的信息置空G->vertices[j].trainfirstarc=NULL;for(k=0;k<G->vexnum-1;k++) //以下是删除所有指向此结点的航班弧{p=G->vertices[k].planefirstarc;while(p!=NULL){if(p->adjvex>i){p->adjvex=p->adjvex-1;q=p;p=p->nextarc; //p指向下一条飞机弧}else if(p->adjvex==i) //该弧指向的顶点位置(p->adjvex )== i{if(p==G->vertices[k].planefirstarc) //p指向图G中k结点的第一条飞机弧{m=p;G->vertices[k].planefirstarc=p->nextarc; //将图G中k结点的第二条飞机弧改为第一弧p=p->nextarc; //p指向下一条飞机弧free(m); //释放(m)}else{q->nextarc=p->nextarc; //将p的下一条弧赋给q的下一条弧m=p;p=p->nextarc; //p指向下一条飞机弧free(q); //释放(q)}}else{q=p;p=p->nextarc; //p指向下一条飞机弧}}}for(k=0;k<G->vexnum-1;k++) ///*以下是删除所有指向此结点的列车弧*/{p=G->vertices[k].trainfirstarc; //p指向图G中k结点的第一条列车弧while(p!=NULL){if(p->adjvex>i) //该弧指向的顶点位置(p->adjvex)>i{p->adjvex=p->adjvex-1; //将该弧指向顶点位置-1q=p;p=p->nextarc; //p指向下一条列车弧}else if(p->adjvex==i) //该弧指向的顶点位置(p->adjvex)==i{if(p==G->vertices[k].trainfirstarc)//p指向图G中k结点的第一条列车{m=p;G->vertices[k].trainfirstarc=p->nextarc; //将图G中k结点的第二条列车弧改为第一弧p=p->nextarc;free(m);}else{q->nextarc=p->nextarc;m=p;p=p->nextarc;free(q);}}else{q=p;p=p->nextarc;}}}}G->vexnum--;save(G);}elsereturn;}void flightedit(ALGraph *G)/*飞机航班编辑项目选择界面*/{int i;// char q;printf("\n请选择飞机航班编辑项目:\n");printf("1=新增航班\n2=删除航班\n");printf("选择?");scanf("%d",&i);getchar();if(i==1)EnterplaneArc(G);if(i==2)DeleteplaneArc(G);}void trainedit(ALGraph *G)/*列车车次编辑项目选择界面*/{int i;//char q;printf("\n请选择列车车次编辑项目:\n");printf("1=新增车次\n2=删除车次\n");printf("选择?");scanf("%d",&i);getchar();if(i==1)EntertrainArc(G);if(i==2)DeletetrainArc(G);}void EnterplaneArc(ALGraph *G)/*增加飞机航班*/{int i,j,bt[2],at[2];int code;float money;int m,t;char vt[10],vh[10],c;ArcNode *p,*q;printf("\n请输入新增飞机航班的信息:\n");printf("飞机航班编号:");scanf("%d",&code);getchar();printf("起始城市:");gets(vt);printf("目的城市:");gets(vh);printf("航班费用:");scanf("%f",&money);getchar();printf("起飞时间:");scanf("%d:%d",&bt[0],&bt[1]);getchar();while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&bt[0],&bt[1]);getchar();}printf("到达时间:");scanf("%d:%d",&at[0],&at[1]);getchar();while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&at[0],&at[1]);getchar();}printf("\n确认?(Y/n)");c=getchar();getchar();if(c=='Y'||c=='y'){i=LocateVertex(G,vt);j=LocateVertex(G,vh);if(i==-1){printf("\n错误!无法找到起始城市\n");return;}if(j==-1){printf("\n错误!无法找到到达城市\n");return;}q=G->vertices[i].planefirstarc;m=0;while(q!=NULL){if(q->adjvex==j){t=q->info.last+1;q->info.stata[t].number=code;q->info.stata[t].expenditure=money;q->info.stata[t].begintime[0]=bt[0];q->info.stata[t].begintime[1]=bt[1];q->info.stata[t].arrivetime[0]=at[0];q->info.stata[t].arrivetime[1]=at[1];q->info.last=t;m=1;break;}q=q->nextarc;}if(m==0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info.stata[0].number=code;p->info.stata[0].expenditure=money;p->info.stata[0].begintime[0]=bt[0];p->info.stata[0].begintime[1]=bt[1];p->info.stata[0].arrivetime[0]=at[0];p->info.stata[0].arrivetime[1]=at[1];p->info.last=0;p->nextarc=G->vertices[i].planefirstarc;G->vertices[i].planefirstarc=p;G->planearcnum++;}save(G);}elsereturn;}void EntertrainArc(ALGraph *G)/*增加列车车次*/{int i,j,bt[2],at[2];int code;float money;int m,t;char vt[10],vh[10],c;ArcNode *p,*q;printf("\n请输入新增列车车次的信息:\n");printf("列车车次编号:");scanf("%d",&code);getchar();printf("起始城市:");gets(vt);printf("目的城市:");gets(vh);printf("车次费用:");scanf("%f",&money);getchar();printf("发车时间:");scanf("%d:%d",&bt[0],&bt[1]);getchar();while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&bt[0],&bt[1]);getchar();}printf("到达时间:");scanf("%d:%d",&at[0],&at[1]);getchar();while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60){printf("\n时间输入有误,请重新输入\n");scanf("%d:%d",&at[0],&at[1]);getchar();}printf("\n确认?(Y/n)");c=getchar();getchar();if(c=='Y'||c=='y'){i=LocateVertex(G,vt);j=LocateVertex(G,vh);if(i==-1){printf("\n错误!无法找到起始城市\n");return;}if(j==-1){printf("\n错误!无法找到到达城市\n");return;}q=G->vertices[i].trainfirstarc;m=0;while(q!=NULL){if(q->adjvex==j){t=q->info.last+1;q->info.stata[t].number=code;q->info.stata[t].expenditure=money;q->info.stata[t].begintime[0]=bt[0];q->info.stata[t].begintime[1]=bt[1];q->info.stata[t].arrivetime[0]=at[0];q->info.stata[t].arrivetime[1]=at[1];q->info.last=t;m=1;break;}q=q->nextarc;}if(m==0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info.stata[0].number=code;p->info.stata[0].expenditure=money;p->info.stata[0].begintime[0]=bt[0];p->info.stata[0].begintime[1]=bt[1];p->info.stata[0].arrivetime[0]=at[0];p->info.stata[0].arrivetime[1]=at[1];p->info.last=0;p->nextarc=G->vertices[i].trainfirstarc;G->vertices[i].trainfirstarc=p;G->trainarcnum++;}save(G);}elsereturn;}int DeleteplaneArc(ALGraph *G)/*删除飞机航班*/{int i,j;int code;char vt[10],vh[10],c;int n;int k;ArcNode *p,*q;printf("\n请输入删除飞机航班的信息:\n");printf("飞机航班的编号:");scanf("%d",&code);getchar();printf("起始城市:");gets(vt);printf("目的城市:");gets(vh);printf("\n确认?(Y/n)");c=getchar();getchar();if(c=='Y'||c=='y'){i=LocateVertex(G,vt);j=LocateVertex(G,vh);if(i==-1){printf("\n错误!无法找到起始城市\n");return 0;}if(j==-1){printf("\n错误!无法找到目的城市\n");return 0;}p=G->vertices[i].planefirstarc;q=p;while(p!=NULL){if(p->adjvex==j){n=-1;for(k=0;k<=p->info.last;k++){if(p->info.stata[k].number==code){n=k;break;}}if(n!=-1)if(p->info.last==0){if(q==p)G->vertices[i].planefirstarc=p->nextarc;elseq->nextarc=p->nextarc;free(p);}else{for(k=n;k<p->info.last;k++){p->info.stata[k].number=p->info.stata[k+1].number;p->info.stata[k].expenditure=p->info.stata[k+1].expenditure;p->info.stata[k].begintime[0]=p->info.stata[k+1].begintime[0];p->info.stata[k].begintime[1]=p->info.stata[k+1].begintime[1];p->info.stata[k].arrivetime[0]=p->info.stata[k+1].arrivetime[0];p->info.stata[k].arrivetime[1]=p->info.stata[k+1].arrivetime[1];}p->info.last=p->info.last-1;}elseprintf("\n在此两城市之间无法找到No.%d飞机航班\n",code);save(G);return 0;}q=p;p=p->nextarc;}if(p==NULL)printf("\n在此两城市之间无飞机航班存在\n");}elsereturn 1;return 1;}int DeletetrainArc(ALGraph *G)/*删除列车车次*/{int i,j;int code;char vt[10],vh[10],c;int n;int k;ArcNode *p,*q;printf("\n请输入删除列车车次的信息:\n");printf("列车车次的编号:");scanf("%d",&code);getchar();printf("起始城市:");gets(vt);printf("目的城市:");gets(vh);printf("\n确认?(Y/n)");c=getchar();getchar();if(c=='Y'||c=='y'){i=LocateVertex(G,vt);j=LocateVertex(G,vh);if(i==-1){printf("\n错误!无法找到起始城市\n");return 0;}if(j==-1){printf("\n错误!无法找到目的城市\n");return 0;}p=G->vertices[i].trainfirstarc;q=p;while(p!=NULL){if(p->adjvex==j){n=-1;for(k=0;k<=p->info.last;k++){if(p->info.stata[k].number==code){n=k;break;}}if(n!=-1)if(p->info.last==0){if(q==p)G->vertices[i].trainfirstarc=p->nextarc;elseq->nextarc=p->nextarc;free(p);}else{for(k=n;k<p->info.last;k++){p->info.stata[k].number=p->info.stata[k+1].number;p->info.stata[k].expenditure=p->info.stata[k+1].expenditure;p->info.stata[k].begintime[0]=p->info.stata[k+1].begintime[0];p->info.stata[k].begintime[1]=p->info.stata[k+1].begintime[1];p->info.stata[k].arrivetime[0]=p->info.stata[k+1].arrivetime[0];p->info.stata[k].arrivetime[1]=p->info.stata[k+1].arrivetime[1];}p->info.last=p->info.last-1;}elseprintf("\n在此两城市之间无法找到No.%d列车车次\n",code);save(G);return 0;}q=p;p=p->nextarc;}if(p==NULL)printf("\n在此两城市之间无列车车次存在\n");}elsereturn 0;return 1;}void UserDemand(ALGraph G)/*用户咨询项目选择界面*/{int i;char q;printf("\n请选择咨询项目:\n");printf("1=最少旅行费用\n2=最少旅行时间\n3=最少旅行中转次数\n4=返回上一级菜单\n");printf("选择?");scanf("%d",&i);getchar();while(i!=4){switch(i){case 1:DemandDispose(1,G);break; /*最少费用,时间,中转次数*/case 2:DemandDispose(2,G);break; case 3:DemandDispose(3,G);break; }printf("按回车继续\n");scanf("%c",&q);scanf("%c",&q);printf("请选择咨询项目:\n");printf("1=最少旅行费用\n2=最少旅行时间\n3=最少旅行中转次数\n4=返回上一级菜单\n");printf("选择?");scanf("%d",&i);getchar();}return ;}void DemandDispose(int n,ALGraph G)/*用户咨询选择信息输入界面,通过该子程序调用其他咨询子程序*/{char q;ArcNode *plane,*train;infolist planearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM],trainarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int i,j,k,final[MAX_VERTEX_NUM],T[MAX_VERTEX_NUM][2];float M[MAX_VERTEX_NUM];for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)for(k=0;k<MAX_ROUTE_NUM;k++){planearcs[i][j].stata[k].expenditure=INFINITY;planearcs[i][j].stata[k].begintime[0]=0;planearcs[i][j].stata[k].begintime[1]=0;planearcs[i][j].stata[k].arrivetime[0]=INFINITY;planearcs[i][j].stata[k].arrivetime[1]=INFINITY;planearcs[i][j].last=-1;trainarcs[i][j].stata[k].expenditure=INFINITY;trainarcs[i][j].stata[k].begintime[0]=0;trainarcs[i][j].stata[k].begintime[1]=0;trainarcs[i][j].stata[k].arrivetime[0]=INFINITY;trainarcs[i][j].stata[k].arrivetime[1]=INFINITY;trainarcs[i][j].last=-1;}for(i=0;i<G.vexnum;i++){plane=G.vertices[i].planefirstarc;train=G.vertices[i].trainfirstarc;while(plane!=NULL){planearcs[i][plane->adjvex]=plane->info;plane=plane->nextarc;}while(train!=NULL){trainarcs[i][train->adjvex]=train->info;train=train->nextarc;}}printf("\n请选择旅行起始城市:\n");for(k=0;k<G.vexnum;k++)printf("%d=%s\n",k,G.vertices[k].cityname);printf("选择?");scanf("%d",&i);printf("\n请选择旅行到达城市:\n");for(k=0;k<G.vexnum;k++)printf("%d=%s\n",k,G.vertices[k].cityname);printf("选择?");scanf("%d",&j);printf("\n请选择交通工具:\n");printf("1=列车\n2=飞机\n");printf("选择?");scanf("%d",&k);printf("\n确认? (Y/n)");scanf("%c",&q);scanf("%c",&q);if(q=='Y'||q=='y'){if(k==1&&n==1)ExpenditureDispose(1,trainarcs,G,i,j,M,final); //费用else if(k==1&&n==2)TimeDispose(1,trainarcs,G,i,j,T,final); //时间else if(k==1&&n==3)TransferDispose(1,trainarcs,G,i,j); //中转次数else if(k==2&&n==1)ExpenditureDispose(2,planearcs,G,i,j,M,final);else if(k==2&&n==2)TimeDispose(2,planearcs,G,i,j,T,final);else if(k==2&&n==3)TransferDispose(2,planearcs,G,i,j);}else if(q=='N'||q=='n')UserDemand(G);else{printf("\n选择错误\n");DemandDispose(k,G);}return ;}void InitQueue(LinkQueue *Q){Q->front=(QNode *)malloc(sizeof(QNode));Q->rear=Q->front;Q->front->next=NULL;}void EnterQueue(LinkQueue *Q,int x){QNode *newnode;newnode=(QNode *)malloc(sizeof(QNode));newnode->adjvex=x;newnode->next=NULL;Q->rear->next=newnode;Q->rear=newnode;}void DeleteQueue(LinkQueue *Q,int *x)/*出队操作*/{QNode *p;p=Q->front->next;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;*x=p->adjvex;free(p);}int IsEmpty(LinkQueue *Q)/*队列判空操作*/{if(Q->front==Q->rear)return(1);elsereturn(0);}///void TransferDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1)/*最少旅行中转次数处理*/{int visited[MAX_VERTEX_NUM],v,w,n=1;LinkQueue Q;ArcNode *t;Node *p,*q,*r,*s;p=(Node *)malloc(G.vexnum*sizeof(Node));for(v=0;v<G.vexnum;v++){visited[v]=0;p[v].next=NULL;}InitQueue(&Q);visited[v0]=1;q=(Node *)malloc(sizeof(Node));q->adjvex=v0;q->next=NULL;p[v0].next=q;EnterQueue(&Q,v0);while(!IsEmpty(&Q))//队列不空{DeleteQueue(&Q,&v);if(k==1)t=G.vertices[v].trainfirstarc;elset=G.vertices[v].planefirstarc;while(t!=NULL){w=t->adjvex; //w为与城市v相连的第一个城市if(!visited[w]) //城市w未访问{visited[w]=1; //将城市w设为已访问q=&p[w];s=p[v].next;while(s!=NULL){r=(Node *)malloc(sizeof(Node));r->adjvex=s->adjvex;q->next=r;q=r;s=s->next;}r=(Node *)malloc(sizeof(Node));r->adjvex=w;r->next=NULL;q->next=r;if(w==v1)//w等于v1{q=p[w].next;r=q->next;printf("\n旅行路线是:\n");while(r!=NULL){if(k==1)printf("乘坐No.%d列车车次在%02d:%02d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);elseprintf("乘坐No.%d飞机航班在%02d:%02d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);q=r;r=r->next;n++;}printf("最少中转次数是%d次\n",n-2);for(v=0;v<G.vexnum;v++){q=p[v].next;while(q!=NULL){s=q;q=q->next;free(s);}p[v].next=NULL;}free(p);return;}EnterQueue(&Q,w); // 将城市w入队}t=t->nextarc; //w等于城市v相连的下一个城市}}for(v=0;v<G.vexnum;v++){q=p[v].next;while(q!=NULL){s=q;q=q->next;free(s);}p[v].next=NULL;}free(p);if(k==1)printf("\n不存在列车车次从%s到%s\n",G.vertices[v0].cityname,G.vertices[v1].cityname);elseprintf("\n不存在飞机航班从%s到%s\n",G.vertices[v0].cityname,G.vertices[v1].cityname);}void MinExpenditure(infolist arcs,float *expenditure,int *route)/*两直达城市之间最少旅行费用和相应路径*/{int i;*expenditure=arcs.stata[0].expenditure;if(*expenditure<INFINITY)*route=0;else*route=-1;for(i=1;i<=arcs.last;i++)if(arcs.stata[i].expenditure<*expenditure){*expenditure=arcs.stata[i].expenditure;*route=i;}}void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final)/*最少旅行费用处理*/{int v=-1,w,i,route;float m,expenditure;Node *p,*q,*r,*s;p=(Node *)malloc(G.vexnum*sizeof(Node));for(v=0;v<G.vexnum;v++){*(final+v)=False; //城市v还未求得最少费用MinExpenditure(*(*(arcs+v0)+v),M+v,&route); // *(D+v)=城市v0到v的最少费用;p[v].next=NULL;//将城市v的路径设置为空if(*(M+v)<INFINITY){q=(Node *)malloc(sizeof(Node)); //将城市v0和v加入到城市v的路径中s=(Node *)malloc(sizeof(Node));q->adjvex=v0;s->adjvex=v;s->route=route;p[v].next=q;q->next=s;s->next=NULL;}}*(M+v0)=0; // 城市v0到城市v0的最少费用为0*(final+v0)=True; //城市v0设为已求得最少费用for(i=1;i<G.vexnum;i++){m=INFINITY;v=-1;for(w=0;w<G.vexnum;w++)if(*(final+w)==False) //城市w未求得最少费用if(*(M+w)<m){v=w;m=*(M+w);}if(v==v1)//v等于v1{q=p[v].next;r=q->next;printf("\n旅行路线是:\n");while(r!=NULL){if(k==1)printf("乘坐No.%d列车车次在%02d:%02d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);elseprintf("乘坐No.%d飞机航班在%02d:%02d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);q=r;r=r->next;}printf("最少旅行费用是%f元\n",m);for(v=0;v<G.vexnum;v++){q=p[v].next;while(q!=NULL){s=q;q=q->next;free(s);}p[v].next=NULL;}free(p);return;}else if(v!=-1){*(final+v)=True; //将城市v设为已求得最少费用for(w=0;w<G.vexnum;w++)if(*(final+w)==False&&(*(*(arcs+v)+w)).last>-1){MinExpenditure(*(*(arcs+v)+w),&expenditure,&route);if(*(M+w)>m+expenditure){*(M+w)=m+expenditure;q=p[w].next;while(q!=NULL){s=q;q=q->next;free(s);}q=&p[w];s=p[v].next;while(s!=NULL){r=(Node *)malloc(sizeof(Node));r->adjvex=s->adjvex;r->route=s->route;q->next=r;q=r;s=s->next;}r=(Node *)malloc(sizeof(Node));r->adjvex=w;r->route=route;r->next=NULL;q->next=r;}}}}for(v=0;v<G.vexnum;v++){q=p[v].next;while(q!=NULL){s=q;q=q->next;free(s);}p[v].next=NULL;}free(p);if(k==1)printf("\n不存在列车车次从%s到%s\n",G.vertices[v0].cityname,G.vertices[v1].cityname);elseprintf("\n不存在飞机航班从%s到%s\n",G.vertices[v0].cityname,G.vertices[v1].cityname);}void MinTime(infolist arcs,int *time,int *route)/*两直达城市之间最少旅行时间和相应路径*/{int i,t[2];time[0]=arcs.stata[0].arrivetime[0]-arcs.stata[0].begintime[0];time[1]=arcs.stata[0].arrivetime[1]-arcs.stata[0].begintime[1];if(time[0]<0)time[0]=time[0]+24;if(time[1]<0){time[0]--;time[1]=time[1]+60;}*route=0;for(i=1;i<=arcs.last;i++){t[0]=arcs.stata[i].arrivetime[0]-arcs.stata[i].begintime[0]; t[1]=arcs.stata[i].arrivetime[1]-arcs.stata[i].begintime[1]; if(t[0]<0)t[0]=t[0]+24;if(t[1]<0){t[0]--;t[1]=t[1]+60;}if(t[0]<time[0]||(t[0]==time[0]&&t[1]<time[1])){time[0]=t[0];time[1]=t[1];*route=i;}}}void TimeTreeDispose(Node *head,infolist (*arcs)[MAX_VERTEX_NUM])/*时间树处理*/{int n,i,j;Node *p;LinkQueue Q;TimeTree root;root=(TimeNode *)malloc(sizeof(TimeNode));InitQueue(&Q);TTime[0]=INFINITY;TTime[1]=INFINITY;p=head->next;while(p!=NULL){EnterQueue(&Q,p->adjvex);p=p->next;}DeleteQueue(&Q,&i);root->adjvex=i;DeleteQueue(&Q,&j);CreateTimeTree(root,i,j,&Q,arcs);for(n=0;n<=(*(*(arcs+i)+j)).last;n++){time1[0]=0;time1[1]=0;time2[0]=root->child[n]->begintime[0];time2[1]=root->child[n]->begintime[1];time[0]=INFINITY;time[1]=INFINITY;VisitTimeTree(root->child[n]);if(time[0]<TTime[0]||(time[0]==TTime[0]&&time[1]<TTime[1])){TTime[0]=time[0];TTime[1]=time[1];p=head->next;while(p!=NULL){p->route=d[p->adjvex];p=p->next;}}}DestoryTimeTree(root);}void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM])/*创建时间树*/{int n,x,y;TimeTree q;q=(TimeNode *)malloc(sizeof(TimeNode));q->adjvex=j;q->begintime[0]=(*(*(arcs+i)+j)).stata[0].begintime[0];q->begintime[1]=(*(*(arcs+i)+j)).stata[0].begintime[1];q->arrivetime[0]=(*(*(arcs+i)+j)).stata[0].arrivetime[0];q->arrivetime[1]=(*(*(arcs+i)+j)).stata[0].arrivetime[1];q->route=0;p->child[0]=q;for(n=1;n<=(*(*(arcs+i)+j)).last;n++){q=(TimeNode *)malloc(sizeof(TimeNode));q->adjvex=j;q->begintime[0]=(*(*(arcs+i)+j)).stata[n].begintime[0];q->begintime[1]=(*(*(arcs+i)+j)).stata[n].begintime[1];q->arrivetime[0]=(*(*(arcs+i)+j)).stata[n].arrivetime[0];q->arrivetime[1]=(*(*(arcs+i)+j)).stata[n].arrivetime[1];q->route=n;p->child[n]=q;}while(n<MAX_ROUTE_NUM){p->child[n]=NULL;n++;}x=j;if(!IsEmpty(Q)){DeleteQueue(Q,&y);CreateTimeTree(p->child[0],x,y,Q,arcs);for(n=1;n<=(*(*(arcs+i)+j)).last;n++)CopyTimeTree(p->child[n],p->child[0]);}else{for(n=0;n<MAX_ROUTE_NUM;n++)p->child[0]->child[n]=NULL;for(n=1;n<=(*(*(arcs+i)+j)).last;n++)CopyTimeTree(p->child[n],p->child[0]);}return ;}void CopyTimeTree(TimeTree p,TimeTree q)/*复制时间树*/{TimeTree r;int n=0;while(q->child[n]!=NULL){r=(TimeNode *)malloc(sizeof(TimeNode));r->adjvex=q->child[n]->adjvex;r->begintime[0]=q->child[n]->begintime[0];r->begintime[1]=q->child[n]->begintime[1];r->arrivetime[0]=q->child[n]->arrivetime[0];r->arrivetime[1]=q->child[n]->arrivetime[1];r->route=q->child[n]->route;p->child[n]=r;CopyTimeTree(p->child[n],q->child[n]);n++;}while(n<MAX_ROUTE_NUM){p->child[n]=NULL;n++;}return ;}void VisitTimeTree(TimeTree p)/*访问时间树界面*/{int n,x[2],y[2];//TimeTree q;x[0]=time1[0];x[1]=time1[1];y[0]=time2[0];y[1]=time2[1];if(p->begintime[0]>time2[0]||(p->begintime[0]==time2[0]&&p->begintime[1]>=time2[1])){time1[0]=time1[0]+p->begintime[0]-time2[0];time1[1]=time1[1]+p->begintime[1]-time2[1];if(time1[1]<0){time1[1]=time1[1]+60;time1[0]--;}if(time1[1]>=60){time1[1]=time1[1]-60;time1[0]++;}}else if(p->begintime[0]<time2[0]||(p->begintime[0]==time2[0]&&p->begintime[1]<time2[1])){time1[0]=time1[0]+p->begintime[0]-time2[0]+24;time1[1]=time1[1]+p->begintime[1]-time2[1];if(time1[1]<0){time1[1]=time1[1]+60;time1[0]--;}if(time1[1]>=60){time1[1]=time1[1]-60;time1[0]++;}}if(p->arrivetime[0]>p->begintime[0]||(p->arrivetime[0]==p->begintime[0]&&p->arrivetime[1]>=p->begintime[1])){time1[0]=time1[0]+p->arrivetime[0]-p->begintime[0];time1[1]=time1[1]+p->arrivetime[1]-p->begintime[1];if(time1[1]<0){time1[1]=time1[1]+60;time1[0]--;}if(time1[1]>=60){time1[1]=time1[1]-60;time1[0]++;}}else if(p->arrivetime[0]<p->begintime[0]||(p->arrivetime[0]==p->begintime[0]&&p->arrivetime[1]<p->begintime[1])){time1[0]=time1[0]+p->arrivetime[0]-p->begintime[0]+24;time1[1]=time1[1]+p->arrivetime[1]-p->begintime[1];if(time1[1]<0){time1[1]=time1[1]+60;time1[0]--;}if(time1[1]>=60){time1[1]=time1[1]-60;time1[0]++;}}time2[0]=p->arrivetime[0];time2[1]=p->arrivetime[1];c[p->adjvex]=p->route;if(p->child[0]==NULL){if(time1[0]<time[0]||(time1[0]==time[0]&&time1[1]<time[1])){time[0]=time1[0];time[1]=time1[1];for(n=0;n<MAX_VERTEX_NUM;n++)d[n]=c[n];}}else{n=0;while(p->child[n]!=NULL){VisitTimeTree(p->child[n]);n++;}}time1[0]=x[0];time1[1]=x[1];time2[0]=y[0];time2[1]=y[1];}void DestoryTimeTree(TimeTree p)/*销毁时间树*/{if(p!=NULL){DestoryTimeTree(p->child[0]);DestoryTimeTree(p->child[1]);DestoryTimeTree(p->child[2]);DestoryTimeTree(p->child[3]);DestoryTimeTree(p->child[4]);p->child[0]=NULL;p->child[1]=NULL;p->child[2]=NULL;p->child[3]=NULL;p->child[4]=NULL;free(p);}return ;}void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final)/*最少旅行时间处理*/{int v,w,i,route,m[2];Node *p,*q,*r,*s,*t;p=(Node *)malloc(G.vexnum*sizeof(Node));for(v=0;v<G.vexnum;v++){*(final+v)=False; //城市v还未求得最少时间MinTime(*(*(arcs+v0)+v),*(T+v),&route); //*(D+v)=城市v0到v的最少时间p[v].next=NULL; //将城市v的路径设置为空if(*(*(T+v)+0)<INFINITY&&*(*(T+v)+1)<INFINITY){q=(Node *)malloc(sizeof(Node));s=(Node *)malloc(sizeof(Node));q->adjvex=v0;s->adjvex=v;s->route=route;p[v].next=q;q->next=s;s->next=NULL;}}*(*(T+v0)+0)=0; // 城市v0到城市v0的最少时间为0*(*(T+v0)+1)=0; *(final+v0)=True; //城市v0设为已求得最少时间for(i=1;i<G.vexnum;i++){m[0]=INFINITY;m[1]=INFINITY;v=-1;for(w=0;w<G.vexnum;w++)if(*(final+w)==False) //城市w未求得最少时间if(*(*(T+w)+0)<m[0]||(*(*(T+w)+0)==m[0]&&*(*(T+w)+1)<m[1])){v=w;m[0]=*(*(T+w)+0);m[1]=*(*(T+w)+1);}if(v==v1){q=p[v].next;r=q->next;printf("\n旅行路线是:\n");while(r!=NULL){if(k==1)printf("乘坐No.%d列车车次在%02d:%02d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);elseprintf("乘坐No.%d飞机航班在%02d:%02d从%s到%s\n",(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number,(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0],(*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1],G.vertices[q->adjvex].cityname,G.vertices[r->adjvex].cityname);q=r;r=r->next;}printf("最少旅行时间是%02d:%02d\n",m[0],m[1]);for(v=0;v<G.vexnum;v++){q=p[v].next;while(q!=NULL){s=q;q=q->next;free(s);}p[v].next=NULL;}free(p);return ;}else if(v!=-1){*(final+v)=True;for(w=0;w<G.vexnum;w++)if(*(final+w)==False&&(*(*(arcs+v)+w)).last>-1){t=p[w].next;q=&p[w];s=p[v].next;while(s!=NULL){r=(Node *)malloc(sizeof(Node));r->adjvex=s->adjvex;r->route=s->route;q->next=r;q=r;s=s->next;}r=(Node *)malloc(sizeof(Node));r->adjvex=w;r->route=route;r->next=NULL;q->next=r;TimeTreeDispose(&p[w],arcs);if(*(*(T+w)+0)>TTime[0]||(*(*(T+w)+0)==TTime[0]&&*(*(T+w)+1)>TTime[1])){*(*(T+w)+0)=TTime[0];*(*(T+w)+1)=TTime[1];while(t!=NULL){q=t;t=t->next;free(q);}}else{q=p[w].next;while(q!=NULL){r=q;q=q->next;free(r);}p[w].next=t;}}}}for(v=0;v<G.vexnum;v++){q=p[v].next;while(q!=NULL){s=q;q=q->next;free(s);}p[v].next=NULL;}free(p);if(k==1)printf("\n不存在列车车次从%s到%s\n",G.vertices[v0].cityname,G.vertices[v1].cityname);elseprintf("\n不存在飞机航班从%s到%s\n",G.vertices[v0].cityname,G.vertices[v1].cityname);}void PrintGraph(ALGraph *G)/*显示城市交通系统*/{int i,j,k;ArcNode *q;printf("\n请选择显示项目:\n");printf("0=显示城市\n1=显示飞机航班\n2=显示列车车次\n3=返回上一级菜单\n");printf("选择?");scanf("%d",&i);getchar();while(i!=3){switch(i){case 0:printf("\n城市:\n");for(j=0;j<G->vexnum;j++)printf("%s ",G->vertices[j].cityname);printf("\n");break;case 1:printf("\n飞机航班:\n");for(j=0;j<G->vexnum;j++){q=G->vertices[j].planefirstarc;while(q!=NULL){printf("%s---->%s\n",G->vertices[j].cityname,G->vertices[q->adjvex].cityname);for(k=0;k<=q->info.last;k++)printf("number:%d expenditure:%5.2f begintime:%02d:%02d arrivetime:%02d:%02d\n",q->info.stata[k].number,q->info.stata[k].expenditure,q->info.stata[k].begintime[0],q->info.stata[k].begintime[1],q->info.stata[k].arrivetime[0],q->info.stata[k].arrivetime[1]);q=q->nextarc;}}break;case 2:printf("\n列车车次:\n");for(j=0;j<G->vexnum;j++){q=G->vertices[j].trainfirstarc;while(q!=NULL){printf("%s---->%s\n",G->vertices[j].cityname,G->vertices[q->adjvex].cityname);for(k=0;k<=q->info.last;k++)printf(" number:%d expenditure:%5.2f begintime:%02d:%02d arrivetime:%02d:%02d\n",q->info.stata[k].number,q->info.stata[k].expenditure,q->info.stata[k].begintime[0],q->info.stata[k].begintime[1],q->info.stata[k].arrivetime[0],q->info.stata[k].arrivetime[1]);q=q->nextarc;}}break;}printf("\n请选择显示项目:\n");printf("0=显示城市\n1=显示飞机航班\n2=显示列车车次\n3=返回上一级菜单\n");printf("选择?");scanf("%d",&i);getchar();}}
如果觉得《C语言实现数据结构-交通咨询系统》对你有帮助,请点赞、收藏,并留下你的观点哦!