交通咨询.txt

交通管理系统

 {
  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;
      else
       q->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;
     }
    else
     printf("\n在此两城市之间无法找到No.%d飞机航班\n",code);
    save(G);
    return 0;
   }
   q=p;
   p=p->nextarc;
  }
  if(p==NULL)
   printf("\n在此两城市之间无飞机航班存在\n");
 }
 else
  return 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;
      else
       q->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;
     }
    else
     printf("\n在此两城市之间无法找到No.%d列车车次\n",code);
    save(G);
    return 0;
   }
   q=p;
   p=p->nextarc;
  }
  if(p==NULL)
   printf("\n在此两城市之间无列车车次存在\n");
 }
 else
  return 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\n");
  DemandDispose(k,G);
 }
 return ;
}

////////////////////////////////////////////
void InitQueue(LinkQueue *Q)
/*
  初始化队列,链队列：队列的链式表示，见教材P62
*/
{
 Q->front=(QNode *)malloc(sizeof(QNode));
 Q->rear=Q->front;
 Q->front->next=NULL;
}

void EnterQueue(LinkQueue *Q,int x)
/*
  入队操作，插入元素x为Q的新的队列元素，见教材P62
*/
{
 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);
 else
  return(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;
  else
   t=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列车车次在%d:%d从%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);
      else
       printf("乘坐No.%d飞机航班在%d:%d从%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",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\n",G.vertices[v0].cityname,G.vertices[v1].cityname);
 else
  printf("\n不存在飞机航班从%s到%s\n\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列车车次在%d:%d从%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);
    else
     printf("乘坐No.%d飞机航班在%d:%d从%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\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;