datastructure.c

编写了一个关于图的操作的应用程序

  gotoxy(3,cap+2);
  printf("If there is any arcvalue?(y/n)");   /*  输入弧的具体信息（包括起点和终点）*/
  key=getkey();
  if(key==21)
    t=1;
  qinping();
  for(i=0,cap=2;i<(*g2).arcnum;i++,cap+=2)
  {
      if(cap==19||cap==18)
     {
         gettext(2,5,79,22,buf);
         puttext(2,3,79,20,buf);
         cap-=2;
     }
     p1=(struct arcbox *)malloc(sizeof(struct arcbox));
     q=(struct arcnode2 *)malloc(sizeof(struct arcnode2));
     p=(struct arcnode2 *)malloc(sizeof(struct arcnode2));
     gotoxy(2,cap);
     printf("The arc%d starts from vertex:",i);
     shezhi(32,cap+2,37,cap+2,1,7,ding1);
     check(ding1,32,cap+2,37,cap+2);
     j=getlocate2(ding1);
     (*g2).verlist[j].gradeout++;
     (*p).position=j;
     (*p1).headvex=j;
     gotoxy(40,cap);
     printf("Ends by vertex:",i);
     shezhi(56,cap+2,61,cap+2,1,7,ding1);
     check(ding1,56,cap+2,61,cap+2);
     k=getlocate2(ding1);
     (*g2).verlist[k].gradein++;
     (*q).position=k;
     (*p1).tailvex=k;
     (*p).nextarc=(*g2).verlist[k].firstarc;
     (*q).nextarc=(*g2).verlist[j].firstarc;
     (*g2).verlist[j].firstarc=q;
     (*g2).verlist[k].firstarc=p;
     (*p1).hlink=(*g).vexlist[j].firstin;
     (*p1).tlink=(*g).vexlist[k].firstout;
     (*g).vexlist[j].firstin=(*g).vexlist[k].firstout=p1;
     if(t==1)
       gets((*p).info);
   }
}



void  check(char *string,int x1,int y1,int x2,int y2)              /*   检查顶点数组中是否存在输入的顶点值*/
{
  int flag1,flag=1;
  while(flag)
  {
    for(flag1=0;flag1<(*g2).vernum;flag1++)
    {
       if((strcmp((*g2).verlist[flag1].value,string)==0))
       {
         flag=0;                       /*  找到则停止查找 */
         break;
       }
    }
    if(flag1==(*g2).vernum)                /*  未找到则输出提示信息  */
    {
       gotoxy(x1-1,y1-2);
       printf("ERROR");
       getch();
       shezhi(x1,y1,x2,y2,1,7,string);
    }
   }
}


/****************十字链表存储形式的操作***********************/

int  gradenum(char * string)      /*  求顶点的入度和出度返回顶点的度数 */
{
   int i, gradein,gradeout,grade;
   struct  arcbox  *m,*n;
   for(i=0;i<(*g).vexnum;i++)
   {
     if(strcmp((*g).vexlist[i].vex,string)==0)
        break;
   }
   m=(*g).vexlist[i].firstout;
   n=(*g).vexlist[i].firstin;
   for(gradein=0;m!=NULL;m=(*m).tlink)
      gradein++;
   for(gradeout=0;n!=NULL;n=(*n).hlink)
      gradeout++;
   window(2,3,79,22);
   gotoxy(3,8);
   printf("The ingrade is:%d   The outgrade is:%d",gradein,gradeout);
   grade=gradein+gradeout;
   return(grade);
}


void getsgrade()                   /*  输入要查找度数的顶点并输出该顶点的度数*/
{
   int key;
   char ding1[5];
   qinping();
   gotoxy(3,3);
   printf("Input the vertex you want to search its grade:");
   shezhi(50,5,56,5,1,7,ding1);
   check(ding1,50,5,56,5);
   window(2,3,79,22);
   gotoxy(3,10);
   printf("    The grade of the vertex is %d.",gradenum(ding1));
   while(1)
   {
     gotoxy(20,11);                               /* 循环查找 */
     printf("continue?(y/n)");
     key=getkey();
     if(key==21)
       getsgrade();
     else
       break;
   }
}


int getlocate(struct gra *p,char *string)    /*获得顶点的位置*/
{
   int j;
   for(j=0;j<(*p).vexnum;j++)
     {
       if((strcmp((*p).vexlist[j].vex,string)==0))
       break;
      }
   return(j);
 }


void visit1(struct vexnode *p)     /*  用十字链表访问  */
{
  int local;
  (*p).seamark=1;
  local=getlocate(g,(*p).vex);
  shunxu[shunxu1++]=local;

}

void dfssearch(struct vexnode *p)           /*十字链表中进行深度遍历*/
{
   struct arcbox *q,*w;
   visit1(p);
   q=(*p).firstin;
   w=(*p).firstout;
   while(q||w)
   {
     if(q)
     {
        if(!(*g).vexlist[(*q).tailvex].seamark)
           dfssearch(&((*g).vexlist[(*q).tailvex]));
        q=(*q).hlink;
     }
     else
     {
        if(w)
        {
          if(!(*g).vexlist[(*w).headvex].seamark)
           dfssearch(&((*g).vexlist[(*w).headvex]));
           w=(*w).tlink;
        }
     }
   }
 }

void dfstraverse()
{
   int i,j,key;
   char fe[5];
   qinping();
   for(i=0;i<(*g).vexnum;i++)
     (*g).vexlist[i].seamark=0;
   gotoxy(3,3);
   printf("Input the vertex you want to begein to patrol(DFS):");
   shezhi(55,5,60,5,1,7,fe);
   check(fe,55,5,60,5);
   j=getlocate(g,fe);                         /*输入遍历的起始顶点并检测*/
   for(i=j;i<(*g).vexnum;i++)
   {                                           /*获得顶点位置进行深度遍历*/
      if(!(*g).vexlist[i].seamark)
        dfssearch(&(*g).vexlist[i]);
   }
   for(i=0;i<j;i++)
   {
      if(!(*g).vexlist[i].seamark)
        dfssearch(&(*g).vexlist[i]);
   }
   qinping();
   for(i=0;i<(*g).vexnum;i++)
   {

      gotoxy(3,7);
      printf("The order is:");
      gotoxy(18+4*i,7);
      puts((*g).vexlist[shunxu[i]].vex);
   }
   shunxu1=0;
    while(1)
   {
    gotoxy(3,9);
    printf("continue?(y/n)");
    key=getkey();
    if(key==21)
     {
        for(i=0;i<(*g).vexnum;i++)
         (*g).vexlist[i].seamark=0;
       dfstraverse();
     }
    else
      break;
   }
}



void  bfstraverse()                  /*  广度遍历（十字链表中遍历）*/
{
   int t,i,j,sign,key;
   char seach[5];
   Vexposition *q;
   ARCBOX *w,*z;
   que=(struct vexqueue *)malloc(sizeof(struct vexqueue));
   initque(que);
   for(i=0;i<(*g).vexnum;i++)
     (*g).vexlist[i].seamark=0;
   qinping();
   gotoxy(3,3);
   printf("Input the vertex you want to begein to partrol(BFS):");
   shezhi(55,5,60,5,1,7,seach);
   check(seach,55,5,60,5);
   t=getlocate(g,seach);                /*  输入深度遍历的起始点 */
   visit1(&(*g).vexlist[t]);
   enqueue(que,t);
   do
   {
     sign=0;
     while(!empty(que))              /*  队列非空则访问出队列的顶点的邻接点 */
     {
      i=dequeue(que);
      w=(*g).vexlist[i].firstin;
      z=(*g).vexlist[i].firstout;
      for(;w!=NULL;w=w->hlink)           /*  依次将访问过的顶点的邻接顶点入队列 */
      {
        if(!(*g).vexlist[(*w).tailvex].seamark)
        {
           visit1(&(*g).vexlist[(*w).tailvex]);
           enqueue(que,(*w).tailvex);
        }
      }
      for(;z!=NULL;z=z->tlink)
      {
        if(!(*g).vexlist[(*z).headvex].seamark)
        {
           visit1(&(*g).vexlist[(*z).headvex]);
           enqueue(que,(*z).headvex);
        }
      }
     }
     for(j=0;j<(*g).vexnum;j++)
     {
        if(!(*g).vexlist[j].seamark)
        {
         visit1(&(*g).vexlist[j]);
         enqueue(que,j);
         sign=1;
         liantong=1;    /*  标志该图是否是连通图（是连通图（1），否（0）） */
         break;
        }
     }
   }while(sign);
   qinping();
    for(i=0;i<(*g).vexnum;i++)
   {
      gotoxy(3,7);
      printf("The order is:");
      gotoxy(18+4*i,7);
      puts((*g).vexlist[shunxu[i]].vex);
   }
   shunxu1=0;
   while(1)
   {
    gotoxy(3,9);
    printf("continue?(y/n)");
    key=getkey();
    if(key==21)
     {
        for(i=0;i<(*g).vexnum;i++)
         (*g).vexlist[i].seamark=0;
       bfstraverse();
     }
    else
      break;
   }
   gotoxy(3,11);
   printf("The graphic is a connexted-graph?");
   if(liantong)
     printf("   NO!");      /*  输出连通图的判断信息（是（ok），否（no）） */
   else
     printf("   OK!");
   getch();
 }




/*##########################邻接表存储操作##################*/


int getlocate2(char * string)           /*  获得输入的顶点值在顶点数组中的位置 */
{
   int locate;
   for(locate=0;locate<(*g2).vernum;locate++)
      if((strcmp((*g2).verlist[locate].value,string)==0))
         return(locate);
   return(locate);
}


void visit2(struct vernode2 *p)       /*  用邻接表访问  */
{
  int  local;
  (*p).vermark=1;
  local=getlocate2((*p).value);
  shunxu[shunxu1++]=local;

}


void dfssearch2(struct vernode2 *p)
{
  struct arcnode2 *q,*w;
  visit2(p);
  q=(*p).firstarc;
  while(q)
  {
    if(!(*g2).verlist[(*q).position].vermark)
       dfssearch2(&(*g2).verlist[(*q).position]);   /* 递规遍历 */
    q=q->nextarc;
  }
}


void  dfstraverse2()                /*  深度遍历（邻接链表中递规遍历 */
{
   int i,j,key;
   char fe[5];
   struct arcnode2 *q;
   for(i=0;i<(*g2).vernum;i++)
     (*g2).verlist[i].vermark=0;
   qinping();
   gotoxy(3,3);
   printf("Input the vertex you want to begein to patrol(DFS):");
   shezhi(55,5,60,5,1,7,fe);                        /*  输入深度遍历的起始点 */
   check(fe,55,5,60,5);
   for(j=0;j<(*g2).vernum;j++)
   {
       if((strcmp((*g2).verlist[j].value,fe)==0))
         break;
   }
    for(i=j;i<(*g2).vernum;i++)         /*  获得位置开始深度遍历，输出遍历的过程*/
   {
      if(!(*g2).verlist[i].vermark)
        dfssearch2(&(*g2).verlist[i]);
   }
   for(i=0;i<j;i++)
   {
      if(!(*g2).verlist[i].vermark)
        dfssearch2(&(*g2).verlist[i]);
   }
    qinping();
   for(i=0;i<(*g2).vernum;i++)
   {

      gotoxy(3,7);
      printf("The order is:");
      gotoxy(18+4*i,7);
      puts((*g2).verlist[shunxu[i]].value);
   }
   shunxu1=0;
    while(1)
   {
    gotoxy(3,9);
    printf("continue?(y/n)");
    key=getkey();
    if(key==21)
     {
        for(i=0;i<(*g2).vernum;i++)
         (*g2).verlist[i].vermark=0;
       dfstraverse2();
     }
    else
      break;
   }
}


void deletev()             /*  删除顶点和其相关联的边 */
{
   int i,k,j;
   char del[5];
   struct arcnode2 *first,*head=NULL,*q,*buf;
   struct vernode2 deletnode;
   qinping();
   gotoxy(3,3);
   printf("Input the vertex you want to delet:"); /* 输入要删除的顶点*/
   shezhi(55,5,60,5,1,7,del);
   check(del,55,5,60,5);
    for(k=0;k<(*g2).vernum;k++)
   {
       if((strcmp((*g2).verlist[k].value,del)==0))
         break;
   }
   for(i=0;i<(*g2).vernum;i++)
   {
      buf=(struct arcnode2 *)malloc(sizeof(struct arcnode2));
      (*g2).verlist[i].firstarc=buf;              /*  依次访问各顶点，若其邻接点是要删除的点 */
      if(i==k)
      {
         first=(*g2).verlist[i].firstarc;
         while(first)
        {
          q=first;
          first=first->nextarc;
          free(q);
        }
        (*g2).vernum--;
        for(j=k;j<(*g2).vernum-1;j++)
          (*g2).verlist[i]=(*g2).verlist[i+1];
      }
      else
      {
            first=(*g2).verlist[i].firstarc;
            while(first)                                /*  则删除该顶点，否则存放到新的链表中，然后 */
           {                                           /*  从新和顶点获得联系   */
               if((*first).position==k)    /* 其邻接点是要删除的点 */
               {
                   q=first;
                   first=first->nextarc;
                   free(q);
                   (*g2).arcnum--;          /*  删除后边数减一  */
               }
               else
              {                           /*  其邻接点不是要删除的点 */
                   if((*first).position>k)
                      (*first).position--;
                   q=first;
                   first=first->nextarc;
                   q->nextarc=head;
                   head =q;
              }
           }
          (*g2).verlist[i].firstarc=head;
          free(buf);
       }
   }
  /* for(i=0;i<(*g2).vernum-1;i++)
   {
     if(i>=k)
        (*g2).verlist[i]=(*g2).verlist[i+1];
   }
   (*g2).vernum--;  */
   gotoxy(3,7);                   /*  定点数减一 */
   printf("vernum:%d    arcnum:%d",(*g2).vernum,(*g2).arcnum);
   getch();
   dfstraverse2();
    while(1)
   {
    gotoxy(3,9);
    printf("continue?(y/n)");
    key=getkey();
    if(key==21)
     {
        for(i=0;i<(*g2).vernum;i++)
         (*g2).verlist[i].vermark=0;
       deletev();
     }
    else
      break;
   }
}


void  toplogicalsort()              /*   判断该图是否有环 */
{
   int i,count,key1;
   struct vernode2 *outver;
   struct arcnode2 *firstling;
   s=(struct sqstack *)malloc(sizeof(struct sqstack));
   initstack();
   for(i=0;i<(*g2).vernum;i++)       /*  找第一个入度为零的顶点 */
      if((*g2).verlist[i].gradein==0)
         push(&(*g2).verlist[i]);    /*  入度为零的顶点进堆栈  */
   count=0;                          /*  记录已访问过的定点数  */
   while(!stackempty())
   {
      outver=pop();
      visit2(outver);
      count++;
      for(firstling=(*outver).firstarc;firstling;firstling=firstling->nextarc)
      {
         (*g2).verlist[(*firstling).position].gradein--;    /* 和刚访问过的顶点相邻的顶点的入度减一 */
         if(!(*g2).verlist[(*firstling).position].gradein)
            push(&(*g2).verlist[(*firstling).position]);    /* 入度为零的顶点进堆栈*/
      }
   }
   qinping();
   for(i=0;i<count;i++)
   {
      gotoxy(3,7);
      printf("The order is:");
      gotoxy(18+4*i,7);
      puts((*g2).verlist[shunxu[i]].value);
   }
   getch();
   shunxu1=0;
   if(count<(*g2).vernum)
   {
     gotoxy(3,9);
     printf("The graph has a circle.");
   }                      /* 根据记录的定点数判断该图是否有环（有（顶点*/
   else
   {
     gotoxy(3,9);
     printf("The graph has no circle.");
   }
   getch();                  /*  数小于顶点总数），没有（顶点数等于顶点总数））*/
}


void  main()
{
    welcome ( );
    initscreen ( );
    wmainmenu ( );
    init ( );
    selectmenu ( );
    quit ( );
 }