grand.c

求图中的祖先节点(不含父亲节点) 内含说明

/*本程序通过输入指定的图中的节点，然后自动找出该节点的所有祖先节点(不包括父亲节点)*/

/*有向欧拉图的输入输出算法程序实现*/
#include<stdio.h>

int node;


int q[20][20];  /*本程序最多处理含20个结点的有向图*/

char ch[50];   /*字符数组暂存从文件读入的数据*/
long int pos;   /*记录文件位置*/
static int point_number=0;  /*图的结点数*/
static int n=0;   /*表示结点数,将由point_number赋值*/

input_file()
{
   FILE *fp=NULL;

   int i=0,j=0;  /*用于计数的变量,计数均从0开始*/
   int line=0,row=0;
   int n=0;   /*表示结点数,将由point_number赋值*/
   int js1=0,js2=0;

   char s1[50];

   fp=fopen("g:\\yxolt_io\\shuru.txt","r");

     if(fp==NULL)
       {
     printf("can not open file\n");
     getch();
            exit(1);
        }

   /*从文件中读入图的结点数*/
   while(point_number==0)
    {
       fscanf(fp,"%c",&ch[i]);

       if(ch[i]==':')
         {
         while(j<i)  /*将 : 之前(即是i之前)的字符读入字符串s1[]*/
              {
        s1[j]=ch[j];
        j++;
               }

          s1[j]='\0';  /*使字符数组成为字符串*/

          if(strcmp(s1,"points")==0)  /*如果':'之前的字符串是points则读取:后的数字*/
                 {
            fscanf(fp,"%d",&point_number); /*将':'后的结点数放入point_number*/
                    /*记下当前文件的位置,并退出当前循环*/
                      if((pos=ftell(fp))==-1L)   /*pos记下当前文件位置*/
                          {
                 printf("A file error has occurred!");
                 getch();
                             exit(1);
                            }

                        else
                          {
                           i=0;
                           fclose(fp);
                           break;
                           }
                   }
           }
       i++; /*指向下一个ch[]数组单元*/
     }

  /*由point_number提供的有向图结点数生成相关数组*/

    n=point_number;

     for(js1=0;js1<=n;js1++)
       for(js2=0;js2<=n;js2++)
        {
           q[js1][js2]=0;
          }   /*初始化相关矩阵*/

 /*从文件上次位置(读完结点数目)开始读入文件中的数据*/

    fp=fopen("g:\\yxolt_io\\shuru.txt","r"); /*第二次打开文件*/

     if(fp==NULL)
       {
     printf("can not open file\n");
     getch();
            exit(1);
        }

     fseek(fp,pos,SEEK_SET);  /*将指针指向上次文件中断的地方*/
     /*经单步调试证明上句已成功执行,将文件指针指向从文件开头后pos个字节后的位置,
      即是points:6后的位置,此技术在本程序中并无实际意义,但此举进一步完善了我的文件
      读写技术,以供今后使用.*/

     i=0;  /*ch[]从头开始存放读入的数据*/

     while(!feof(fp))
        {
           fscanf(fp,"%c",&ch[i]);

           if(ch[i]=='>'&&ch[i-1]=='-')
              {
          row=ch[i-2]-48;  /*行值*/
                 
        /*2004.7.6对本程序维护，使其真正能够处理20个顶点的有向图，原先实际只能处理编号<10的有向图*/

                  if(ch[i-3]>='0'&&ch[i-3]<='9') /*针对顶点编号是两位数的情况(10.11,12...)
                                                 由于本程序处理上限是20个顶点，故此不考虑顶点
                                                 编号是三位或三位以上的情况。*/
                    { 
                       row=(ch[i-3]-48)*10+row; /*处理顶点编号是两位数的情况*/
                     }
        /*2004.7.6对本程序维护*/

                  i++; /*指向下一个ch[]存储单元*/
                  i=check_i(i); /*一旦i>=50就进行队列管理*/

                 fscanf(fp,"%c",&ch[i]);/*将->后的列值从文件读入*/
                 line=ch[i]-48;   /*列值*/


       /*2004.7.6对本程序维护，使其真正能够处理20个顶点的有向图，原先实际只能处理编号<10的有向图*/
               i++;
               i=check_i(i); /*一旦i>=50就进行队列管理*/
               fscanf(fp,"%c",&ch[i]);/*试探性的再读入一个字符，若该字符是数字，则说明列值是两位数*/

                if(ch[i]>='0'&&ch[i]<='9')/*计算两位数的顶点编号*/
                  {
                     line=line*10+(ch[i]-48);
                     }
      /*2004.7.6对本程序维护*/

                     do{
                          i++; /*指向下一个ch[]存储单元*/
                          i=check_i(i); /*一旦i>=50就进行队列管理*/

                          fscanf(fp,"%c",&ch[i]); /*读入两点间有向边条数*/
                            if(ch[i]>='0'&&ch[i]<='9')  
                               {
                                    q[row][line]=ch[i]-48;
                                 }

            } while((ch[i]!='\n')&&(!feof(fp)));  /*以读到该行的结尾为结束,并再读下一行*/
        }

              i++;   /*指向下一个ch[]存储单元*/
              i=check_i(i); /*一旦i>=50就进行队列管理*/

      }

  fclose(fp);
}


check_i(int i)
{
  if(i>=50)    /*一旦i>=50就进行队列管理*/
    {
      queue_manage();
      i--;
     }

  return i;
}

queue_manage()/*将最早入队的数据出队，i减一。50个字符空间相当于存储有关
                信息的缓冲区，以备后用*/
{
   int j=0;

   for(j=0;j<49;j++)
      ch[j]=ch[j+1];
}

father(int fnode,int G[],int jg)
{
  int i=0;
  int F[21]; /*用来存放fnode 的父亲节点,也就是node的祖先节点，应该存入G[]数组中*/
  int jf=0; /*纪录fnode节点的父亲节点的个数*/

  for(i=0;i<=20;i++)
     {
       F[i]=0;
      }

  F[jf]=0; /*F[0]用来记录父亲节点的个数*/
 for(i=1;i<=point_number;i++)
  {
    if(q[i][fnode]==1)
      {
        F[++jf]=i; /*记下一个fnode 的父亲节点*/
        G[++jg]=i; /*同时作为node的祖先节点存入G[]*/
        }
    }/*此for循环找出fnode的所有父亲节点，并将这些节点作为NODE的祖先节点存入G[]*/

  F[0]=jf; /*F[0]用来记录父亲节点的个数*/
  G[0]=jg;/*G[0]用来记录node祖先节点的个数*/

 /*通过递归找出node节点祖先的祖先，并存入G[]*/
  if(F[0]!=0)
   {
      while(jf!=0)
        {
          if(F[jf]!=0)
            jg=father(F[jf],G,jg);

          jf--;
         }
    }

  return jg;
}


grand() /*找出M[]中的node的祖先节点，并将其从M[]中移出*/
{
  int G[21];/*用来存放node 的祖先节点，用于与M[]数组比较*/
  int jg=0; /*纪录祖先节点的个数*/
  int i=0;
  int F[21]; /*用来存放node 的父亲节点*/
  int jf=0; /*纪录父亲节点的个数*/

  for(i=0;i<=20;i++)
     {
       G[i]=0;
       F[i]=0;

      }

  F[jf]=0; /*F[0]用来记录父亲节点的个数*/
  for(i=1;i<=point_number;i++)
     {
       if(q[i][node]==1)
           {
             F[++jf]=i; /*记下一个node 的父亲节点*/
             }
       }/*此for循环找出node的所有父亲节点*/
  F[0]=jf; /*F[0]用来记录父亲节点的个数*/

  while(jf!=0)
  {
    if(F[jf]!=0)
     jg=father(F[jf],G,jg);/*通过father()函数以及node node 的父亲节点找出node所有祖先节点*/

     jf--;
    }

  /*输出G[]的内容*/
 if(jg==0)
   {
    printf("\n The node didn't have grand! \n ");
     }

  else
    {
      /*由于可能出现node节点的祖先节点重复出现在G[]中，故此对G[]做一个处理，
       将G[]中重复的节点只保留一个*/
       tidyG(G,jg);

     printf("\n %d's grands are:",node);

      jg=G[0];
      while(jg!=0)
     {
       printf("%4d",G[jg]);
       jg--;
       }

     }/*end else*/

  /*将G[]中出现的node的祖先节点，从M[]中移出*/
 }

tidyG(int G[],int jg)
{
  int temp[21];
  int jt=0;
  int cut=0;
  int i=0,j=0;

  for(i=0;i<=20;i++)
     {
        temp[i]=0;
      }


  jg=G[0];
     while(jg!=0) /*将G[]中的节点加入temp[]，节点不能重复出现在temp[]中*/
       {
         j=jt;
         cut=0;

         if(j>0) /*temp[]不空*/
           {
             while(j!=0)
               {
                 if(temp[j]==G[jg]) /*检查G[jp]是否与已经进入temp[]的节点重复
                                       若重复，则G[jp]不加入temp[]*/
                    {
                       cut=1;break;
                       }

                  j--;
                 }
             }

         if(cut==0)
           {
              temp[++jt]=G[jg];
             }

         jg--;
       } /*end while*/

     temp[0]=jt;

     for(i=0;i<=temp[0];i++)  /*得到经过整理的G[],其中没有重复的元素*/
       {
           G[i]=temp[i];
         }
}


main()
{
  clrscr();
  input_file();/*读入有向图，建立q[][]邻接矩阵*/

  printf("\nPlease input the node witch you want to find it's grands(but not include father): ");
  scanf("%d",&node);
  grand();

  getch();
}