atrain8.c

数据结构中的

#include<stdio.h>
#define MAX_VERTEX_NUM 30
#define MAX_TREE_SIZE 20
#define STACKINCREMENT 10
#define STACK_INIT_SIZE 20



typedef struct ArcNode{
  int adjvex;              /*该弧所指向顶点的位置*/
  int fadjvex;             /*该弧弧尾所指向定点的位置*/
  struct ArcNode *nextarc;  /*指向下一条弧的指针*/
  int info;      /*该弧相关信息的指针*/
   int see; 

 }ArcNode;

typedef struct VNode{
  char data;     /*顶点指向的信息*/
  int level;
   int called; 
   int addinfo;
  ArcNode *firstarc;  /*指向第一条依附于该点的弧的信息*/
 }VNode,Adjlist[MAX_VERTEX_NUM];

typedef struct{
  Adjlist vertices;
  int vexnum; /*图的当前顶点数和弧数*/
                  /*图的种类标志 */
 }ALGraph;



 typedef struct QNode{
   int data1;
   struct QNode *next;
 }QNode,*QueuePtr;

typedef struct{
   QNode *front;
   QNode *rear;
}LinkQueue;



typedef struct{
  int *base;
  int *top;
  int stacksize;
  }SqStack;


 int visited[30];
 ALGraph G,G1;

  void Creategraph(ALGraph *G){
  FILE *pf;
   int i;
   int u,v,n,w;
   char c,m,name[10];
   ArcNode *s;

   /* VNode *p;*/
     ArcNode *q,*h;
     int j;

      scanf("%s",name);

    if((pf=fopen(name,"r"))==NULL)
     {printf("can't open file");
       exit(0);}


     fscanf(pf,"n=%d ",&n);


      printf("%d",n);
    G->vexnum=n;

    /* fscanf(pf,"\n",&m);*/

   for(i=1;i<=n;i++){

      fscanf(pf,"%c ",&(G->vertices[i].data));

     printf("%c   ",G->vertices[i].data);


     G->vertices[i].firstarc=NULL;

    }
   printf("\nover");

  /* fscanf(pf,"\n",&m);  */


   while(!feof(pf)){
       getch();
     fscanf(pf,"(%d %d) %d ",&u,&v,&w);
     printf("(%d %d) %d, ",u,v,w);

     if((u==0)||(v==0)||(w==0))
       break;
     s=(ArcNode *)malloc(sizeof(ArcNode));
     s->adjvex=v;
     s->info=w;
     s->nextarc=G->vertices[u].firstarc;
     G->vertices[u].firstarc=s;



    }

    fclose(pf);}


     display(ALGraph G) {
     ArcNode *p;
     int j;
     for(j=1;j<=G.vexnum;j++){

       printf("\n");
       printf("%d ",j);
       printf("%c  ",G.vertices[j].data);
      p=G.vertices[j].firstarc;
       while(p)
       {
          /*  printf("  %c  (%d)  ",G->vertices[p->adjvex].data,p->info->dis);*/
            printf(" %c",G.vertices[p->adjvex].data);
         printf("(%d)  ",p->info);
         p=p->nextarc;
       

         }     }


      }






int FirstAdjVex(ALGraph G,int v){
   
    int c;
    
    
    if(G.vertices[v].firstarc==NULL)
      return 0;
      
    else 
       { c=G.vertices[v].firstarc->adjvex;
         return c;
       }
    
  }


   
int NextAdjVex(ALGraph G,int v,int w){
  ArcNode *p;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc){
    if(p->adjvex==w)
     {if(p->nextarc!=NULL)
        return p->nextarc->adjvex;
       else return 0;
      } 
    }

}

int FirstFAdjVex(ALGraph G,int v){
   
    int c;
    
    
    if(G.vertices[v].firstarc==NULL)
      return 0;
      
    else 
       { c=G.vertices[v].firstarc->fadjvex;
         return c;
       }
    
  }


   
int NextFAdjVex(ALGraph G,int v,int w){
  ArcNode *p;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc){
    if(p->fadjvex==w)
     {if(p->nextarc!=NULL)
        return p->nextarc->fadjvex;
       else return 0;
      } 
    }

}






 int InitStack(SqStack *s){                /*  构造一个空栈*/
   s->base=(int * )malloc(20*sizeof(int));
   if(!s->base) exit(0);

   s->top=s->base;
   s->stacksize=STACK_INIT_SIZE;
   return 1;}


/* int Gettop(SqStack *s,int *e){
   if(s->top==s->base) exit(0);
   *e=*(s->top-1);
   return 1;} */

 int Push(SqStack *s,int e){               /*插入元素E为新的栈顶元素*/
   if(s->top-s->base>=s->stacksize){
        s->base=(int *)realloc(s->base,(s->stacksize+10)*sizeof(int));
        if(!s->base) exit(0);
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
        }
        *s->top++=e;
        return 1;
    }


 int Pop(SqStack *s,int *e){              /*若栈非空则删除栈顶元素,用E返回其值*/
   if(s->top==s->base) printf(" the stack is empty");
   *e=*(--s->top);
   return 1;
  }

 int StackEmpty(SqStack *s){
    if(s->top==s->base)
      return 1;
    else
      return 0;
  }




int InitQueue(LinkQueue *Q){ /*构造一个空队列*/
   Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
   if(!Q->front)
     exit(0);
   Q->front->next=NULL;
   
   return 1;
}

int EnQueue(LinkQueue *Q,int v){ /* 插入元素e为Q的新的队尾元素*/
      QNode *p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)
     exit(0);
    p->data1=v;
    p->next=NULL;
    Q->rear->next=p;
    Q->rear=p;
    return 1;
}

int DeQueue(LinkQueue *Q,int *v){
    QNode *p;
     p=(QNode*)malloc(sizeof(QNode));
    if(Q->front==Q->rear)
      return 0;
    p=Q->front->next;
    (*v)=p->data1;
    Q->front->next=p->next;
    if(Q->rear==p)
       Q->rear=Q->front;
    free(p);
    return 1;
}

int QueueEmpty(LinkQueue *Q){
    if(Q->front==Q->rear)
      return 1;
    else
      return 0;
  }


  void BFSTraverse1(ALGraph *G,int v,int x){
   int w,m,i,f,a1,a2,a,b;
   int *u;
   LinkQueue *Q;
   ArcNode p,*s;
   VNode t;
    SqStack *r;
   u=NULL;
   Q=(LinkQueue *)malloc(sizeof(LinkQueue));

   for(m=1;m<=G->vexnum;++m)
     {visited[m]=0;
      G->vertices[m].level=0;}
     InitQueue(Q);
   /* printf("\n"); */

   for(m=1;m<=G->vexnum;++m){
      if(!visited[v])
     { G->vertices[v].level=0;
       visited[v]=1;

       printf("\nLevel:  ");
       printf("%c",G->vertices[v].data);
       printf("(%d) ",G->vertices[v].level);
       EnQueue(Q,v);

      while(!QueueEmpty(Q)){
        DeQueue(Q,u);


        for(w=FirstAdjVex((*G),(*u));w>0;w=NextAdjVex((*G),(*u),w))
           if(!visited[w]){
             visited[w]=1;



            G->vertices[w].level=(G->vertices[(*u)].level)+1;


              if(w==x){
                printf("%c",G->vertices[w].data);
                printf("(%d) ",G->vertices[w].level);
                printf("finding!!!\n");
                for(m=1;m<=G->vexnum;++m){
                 if(visited[m]==0)
                  { G->vertices[m].level=G->vertices[x].level+1;
                    /* printf("%d ",G->vertices[m].level);*/
                   }

                 }

                return;}
             printf("%c",G->vertices[w].data);
              printf("(%d) ",G->vertices[w].level);
             EnQueue(Q,w);
            }
       }

     } 
   }




  }



 void BFSTraverse2(ALGraph G,int v,int x){

   int w,m,i,f,*e,n,a,f1,j1,f2,j2;
   int *u;
   LinkQueue *Q;
   SqStack *r;
   ArcNode p,q,*s,*z,*h,*c;
   VNode t;
   i=1;
   u=NULL;  
   e=NULL;
  Q=(LinkQueue *)malloc(sizeof(LinkQueue));
   for(m=1;m<=G.vexnum;++m)
     {G1.vertices[m].called=0;
       c=G1.vertices[m].firstarc;                         /*初始化*/



     G1.vertices[m].addinfo=0;}


     InitQueue(Q);


       EnQueue(Q,v);
       
      while(!QueueEmpty(Q)){



        DeQueue(Q,u);
        if((i>1)&&(G1.vertices[(*u)].called==1))
         {i=i-1;}


         if((i==1)&&(G1.vertices[1].called==0)){
           p.adjvex=(*u);
           G1.vertices[1].data=G.vertices[(*u)].data;

           G1.vertices[1].firstarc=NULL;

          G1.vertices[(*u)].called=1;


           }


       if((i>1)&&(G1.vertices[(*u)].called==0)){

        p.adjvex=(*u);
        G1.vertices[i].data=G.vertices[(*u)].data;

        G1.vertices[i].firstarc=NULL;
        G1.vertices[(*u)].called=1;



        }



             
             for(m=1;(i>1)&&(m<=G.vexnum);m++){

                 if(FirstAdjVex((G),m))
                 { for(h=G.vertices[m].firstarc;h;h=h->nextarc)
                   { n=h->adjvex;


                    if(G.vertices[n].level<=G.vertices[x].level){
                      if(G.vertices[n].level>G.vertices[m].level){

                        if(n==(*u))
                       {
                             a=find(G.vertices[m].data,(G));

                          if((G1.vertices[i].firstarc==NULL))
                          {




                             s=(ArcNode*)malloc(sizeof(ArcNode));
                             s->fadjvex=m;
                             s->info=h->info;
                             s->nextarc=G1.vertices[i].firstarc;
                             G1.vertices[i].firstarc=s;
                             G1.vertices[i].addinfo=G1.vertices[a].addinfo+h->info;
                             G1.vertices[i].firstarc->see=0;

                           }


                          if((G1.vertices[i].firstarc)&&((G1.vertices[a].addinfo+h->info)<G1.vertices[i].addinfo))
                          {


                             s=(ArcNode*)malloc(sizeof(ArcNode));
                             s->fadjvex=m;
                             s->info=h->info;
                             s->nextarc=G1.vertices[i].firstarc;
                             G1.vertices[i].firstarc=s;
                             G1.vertices[i].addinfo=G1.vertices[a].addinfo+h->info;
                              G1.vertices[i].firstarc->see=0;
                             G1.vertices[i].firstarc->nextarc=NULL;
                           }


                          if((G1.vertices[a].addinfo+h->info)==G1.vertices[i].addinfo)
                          {   s=(ArcNode*)malloc(sizeof(ArcNode));
                              s->fadjvex=m;
                              s->info=h->info;
                              s->nextarc=G.vertices[i].firstarc;
                              G1.vertices[i].firstarc=s;
                              G1.vertices[i].addinfo=G1.vertices[a].addinfo+h->info;
                              G1.vertices[i].firstarc->nextarc=NULL;
                               c=G1.vertices[i].firstarc;
                              while(c){
                                   c->see=0;
                                   c=c->nextarc;
                                  }



                           }

                         }

                      }
                     }

                  }

                 }


              }


            i=i+1;



              for(w=FirstAdjVex((G),(*u));w>0;w=NextAdjVex((G),(*u),w))
              {
                 EnQueue(Q,w);

                if((*u)==x){


                break;}
               }


  /*if((*u)==x){
           printf("444444444");
           for(i=1;i<=20;i++){

              printf("\n");
              printf("%c  ",G1.vertices[i].data);
              z=G1.vertices[i].firstarc;

             printf("(%d)",G1.vertices[i].addinfo);
              while(z)
             {

              printf(" %c",G.vertices[z->fadjvex].data);
             printf("(%d)  ",z->info);
               printf("(%d)  ",G1.vertices[i].addinfo);
              z=z->nextarc;
       

              }


              }

            break;
             }   */


   if((*u)==x){
                printf("\nthe path:");
              f1=find(G.vertices[x].data,G);


                printf("&&&&%df1****",f1);

              while(f1!=find(G.vertices[v].data,G))

               {

                  printf("%c<------",G1.vertices[f1].data);

                 f2=G1.vertices[f1].firstarc->fadjvex;

                 f1=find1(G1.vertices[f1].data,G1);

                 f1=find(G.vertices[f2].data,G);


                   }

                printf("%c ",G1.vertices[find(G.vertices[v].data,G)].data);

               break;
              }

/* if((*u)==x){
             printf("%c",G.vertices[x].data);



              InitStack(r);

                f1=find(G.vertices[x].data,G);

                printf("(((%d",f1);

            if(G1.vertices[f1].firstarc->see==0)

                {
                 Push(r,f1);




              }     printf("UUU%d   ",G1.vertices[f1].firstarc->fadjvex);

               while((G1.vertices[f1].firstarc->fadjvex!=v)&&(G1.vertices[f1].firstarc->see==0))
                {
                    f1=find(G.vertices[f1].data,G);
                    printf("YYYY%d  ",f1);
                      printf(":::%c:::    ",G1.vertices[f1].data,G);

                  Push(r,f1);


                if((G1.vertices[f1].firstarc->nextarc))
                 { G1.vertices[f1].firstarc->see=1;
                   G1.vertices[f1].firstarc=G1.vertices[f1].firstarc->nextarc;
                  }
                 f1=G1.vertices[f1].firstarc->fadjvex;

                }
                    f1= G1.vertices[f1].firstarc->fadjvex;
                if(G1.vertices[f1].firstarc->fadjvex==v){

                      f1=find(G.vertices[f1].data,G);
                      printf("&&&%d  ",f1);
                      Push(r,f1);


                  }


                    while(!StackEmpty(r))
                   {
                      printf("    %d::::: ",(*e));
                      Pop(r,e);



                  printf("%c",G1.vertices[(*e)].data);

                    }


               break;

               }   */

            }
          if(QueueEmpty(Q)){
           printf("find no way!");
           }


  }



 int find1(char c,ALGraph G1){
  int i;
  for(i=1;i<=27;i++){
    if(c==G.vertices[i].data)
     { return i;}

   }
    return 0;
  }



int find(char c,ALGraph G){
  int i;
  for(i=1;i<=27;i++){
    if(c==G1.vertices[i].data)
     { return i;}

   }
    return 0;
  }
main()

{  int v,x,g;
    char key;

  clrscr();
 printf("\n     1. Creategraph\n");
  printf("     2.display the ALGraph\n");
  printf("     3. Traverse Level\n");
  printf("     4. display the path\n");
  printf("     5.exit\n");
  printf("\n\n\n     input your choice:");

key=getch();
 while(key!='5'){
switch(key)
  { case '1':printf("1");
             printf("\ninput the name of the FILE:");
               Creategraph(&G);



             break;
   
    case '2':
            printf("\ndisplay the ALGraph:\n");

            display(G);


        break;

    case '3':printf("\ndisplay the Traverse Level:");
               BFSTraverse1(&G,v,x);
         break;


    case '4': printf("\ninput the station:");
              printf("input the first and final station:");
              scanf("%d %d",&v,&x);

              printf("\ndisplay the short path:");
               BFSTraverse1(&G,v,x);
               BFSTraverse2(G,v,x);

               break;
    default :break;
   }
  key=getch();}


  }