交通咨询.txt

交通管理系统

      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\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 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];
  time0[0]=INFINITY;
  time0[1]=INFINITY;
  VisitTimeTree(root->child[n]);
  if(time0[0]<TTime[0]||(time0[0]==TTime[0]&&time0[1]<TTime[1]))
  {
   TTime[0]=time0[0];
   TTime[1]=time0[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]<time0[0]||(time1[0]==time0[0]&&time1[1]<time0[1]))
  {
   time0[0]=time1[0];
   time0[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列车车次在%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("最少旅行时间是%d:%d\n\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\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 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:%5.2f  arrivetime:%5.2f\n",q->info.stata[k].number,q->info.stata[k].expenditure,q->info.stata[k].begintime,q->info.stata[k].arrivetime);
            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:%5.2f  arrivetime:%5.2f\n",q->info.stata[k].number,q->info.stata[k].expenditure,q->info.stata[k].begintime,q->info.stata[k].arrivetime);
            q=q->nextarc;
           }
          }
          break;
  }
  printf("\n请选择显示项目:\n");
  printf("0=显示城市\n1=显示飞机航班\n2=显示列车车次\n3=返回上一级菜单\n");
  printf("选择?");
  scanf("%d",&i);
  getchar();
 }
}