一个数据结构的课程设计文件,VC++编写.内容为:交通咨询

{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);
  }
  else
   return;
 }
}
DeleteVertex(ALGraph *G)
//删除城市
{int i,j,k,n;
 char v[10],c;
 ArcNode *p,*q,*m;
 printf("\n请输入删除的城市:");
 gets(v);
 printf("\n确认?(Y/N)");
 c=getchar();
 getchar();
 if(c=='Y'||c=='y')
 {n=0;
  while(n<G->vexnum&&strcmp(G->vertices[n].cityname,v)!=0)
   n++;
  if(n==G->vexnum)
   printf("\n错误！无法找到此城市!\n");
  else
  {i=LocateVertex(G,v);
   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->vertices[j].planefirstarc=G->vertices[j+1].planefirstarc;
    G->vertices[j].trainfirstarc=G->vertices[j+1].trainfirstarc;
   }
   G->vertices[j].planefirstarc=NULL;
   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;
     }
     else if(p->adjvex==i)
     {if(p==G->vertices[k].planefirstarc)
      {m=p;
       G->vertices[k].planefirstarc=p->nextarc;
       p=p->nextarc;
       free(m);
      }
      else
      {q->nextarc=p->nextarc;
       m=p;
       p=p->nextarc;
       free(q);
      }
     }
     else
     {q=p;
      p=p->nextarc;
     }
    }
   }
   for(k=0;k<G->vexnum-1;k++)
   {p=G->vertices[k].trainfirstarc;
    while(p!=NULL)
    {if(p->adjvex>i)
     {p->adjvex=p->adjvex-1;
      q=p;
      p=p->nextarc;
     }
     else if(p->adjvex==i)
     {if(p==G->vertices[k].trainfirstarc)
      {m=p;
       G->vertices[k].trainfirstarc=p->nextarc;
       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);
 }
 else
  return;
}
UserDemand(ALGraph G)
//用户咨询项目选择界面
{int i;
 char q;
 printf("\n本系统只能给出费用咨询,请选择操作:\n");
 printf("\t\t\t\t1=最少旅行费用\t\t2=返回上一级菜单\n");
 printf("请选择:");
 scanf("%d",&i);
 getchar();
 while(i!=2)
 {switch(i)
  {case 1:DemandDispose(1,G);break;
  }
  printf("按回车继续\n");
  scanf("%c",&q);
  scanf("%c",&q);
  printf("\n本系统只能给出费用咨询,请选择操作:\n");
  printf("\t\t\t\t1=最少旅行费用\t\t2=返回上一级菜单\n");
  printf("请选择:");
  scanf("%d",&i);
  getchar();
 }
}
DemandDispose(int n,ALGraph G)
//用户咨询选择信息输入界面
{char name[10],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++)
   {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++)
 {
  train=G.vertices[i].trainfirstarc;
  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");
 k=1;
 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(q=='N'||q=='n')
  UserDemand(G);
 else
 {printf("\n选择错误\n\n");
  DemandDispose(k,G);
 }
}
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;
  }
}
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;
  MinExpenditure(*(*(arcs+v0)+v),M+v,&route);
  p[v].next=NULL;
  if(*(M+v)<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;
  }
 }
 *(M+v0)=0;
 *(final+v0)=True;
 for(i=1;i<G.vexnum;i++)
 {m=INFINITY;
  v=-1;
  for(w=0;w<G.vexnum;w++)
   if(*(final+w)==False)
    if(*(M+w)<m)
    {v=w;
     m=*(M+w);
    }
  if(v==v1)
  {q=p[v].next;
   r=q->next;
   printf("\n旅行路线是:\n");
   while(r!=NULL)
   {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);
   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;
   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\n",G.vertices[v0].cityname,G.vertices[v1].cityname);
 else
  ;
}
PrintGraph(ALGraph *G)
//显示城市交通系统
{int i,j,k;
 ArcNode *q;
 printf("\n请选择显示项目:\n");
 printf("\t\t1=显示城市\t  2=显示列车车次\t3=返回上一级菜单\n");
 printf("请选择:");
 scanf("%d",&i);
 getchar();
 while(i!=3)
 {switch(i)
  {case 1:printf("\n城市:\n");
          for(j=0;j<G->vexnum;j++)
           printf("%s  ",G->vertices[j].cityname);
          printf("\n");
          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("\t\t1=显示城市\t  2=显示列车车次\t3=返回上一级菜单\n");
  printf("请选择:");
  scanf("%d",&i);
  getchar();
 }
}