#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define MAX_VERTEX_NUM 18
#define NULL 0
#define MAX_ARC_SIZE 100
#define MAX_ROUTE_NUM 5
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define False 0
#define True 1
#define INFINITY 10000
typedef 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","wb"))==NULL)
 {printf("無法打開文件!\n");
  return;
 }
 for(j=0;j<i;j++)
  fprintf(fp,"%10s",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("飛機航班編號:");  //輸入航班code
  scanf("%d",&code);
  getchar();
  printf("起始城市:");   //輸入航班的出發城市vt
  gets(vt);
  printf("目的城市:");  //輸入航班的到達城市vh
  gets(vh);
  printf("航班費用:");  //輸入機票價格money
  scanf("%f",&money);
  getchar();
  printf("起飛時間:");  //輸入航班的出發時間bt
  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("到達時間:");  //輸入航班的到達時間at
  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; // 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+1
  printf("繼續輸入?(Y/N)");  //提示"是否要繼續輸入航班信息："
  scanf("%c",&flag);
  getchar();
  printf("\n");
 }
 if((fp=fopen("plane.txt","wb"))==NULL) //航班文件不能以讀寫形式打開
  printf("\n無法打開文件!\n");  //提示"無法打開文件"
 fprintf(fp,"%d",count);    //將計數值count寫入航班車文件
 for(i=0;i<count;i++)
  if(fwrite(&a[i],sizeof(struct arc),1,fp)!=1) //無法將a[i]寫入航班文件
   printf("\n文件寫入錯誤!\n");  //提示"文件無法寫入"
 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","wb"))==NULL)
  printf("\n無法打開文件!\n");
 fprintf(fp,"%d",count);
 for(i=0;i<count;i++)
  if(fwrite(&a[i],sizeof(struct arc),1,fp)!=1)
   printf("\n文件寫入錯誤!\n");
 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，plan，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","rb"))==NULL)  //打開城市文件，文件指針返回值為空
 {printf("\n無法打開文件!\n");
  return;
 }
 while(!feof(fp))  //文件不為空
 {fscanf(fp,"%10s",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","rb"))==NULL)
  printf("\n無法打開文件!\n");
 k=0;
 fscanf(fp,"%d",&count1);   //打開航班信息文件"plane.txt"
 while(k<count1)
 {if(fread(&a[k],sizeof(struct arc),1,fp)!=1)
   printf("\n文件讀入錯誤!\n");
  k++;
 }
 fclose(fp);  //關閉文件
 k=0;         //a的計數變量k=0
 arc_num=0;  //弧的計數變量 arc_num=0
 while(k<count1)
 {i=LocateVertex(G,a[k].vt); //調用函數 LocateVertex(G,a[k].vt)得到起始結點的位置 i
  j=LocateVertex(G,a[k].vh); //調用函數 LocateVertex(G,a[k].vh)得到起始結點的位置 j
  q=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","rb"))==NULL)
 {printf("\n無法打開文件!\n");
  return;
 }
 k=0;
 fscanf(fp,"%d",&count2);  //打開列車信息文件"plane.txt"
 while(k<count2)
 {if(fread(&a[k],sizeof(struct arc),1,fp)!=1)
   printf("\n文件讀入錯誤!\n");
  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)得到起始結點的位置 i
  j=LocateVertex(G,a[k].vh);  // 調用函數 LocateVertex(G,a[k].vh)得到起始結點的位置 j
  q=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];