ch3_9.c

数据结构的一些小算法

#include <stdio.h>
#define N 9
void  division(int r[][N],int n,int cq[],
               int newr[],int result[])
{  int k,i,pre,group,front,rear;
   for(k=0;k<n;k++)
      cq[k]=k+1;
   front=n-1;
   rear=n-1;
   for(k=0;k<n;k++)
     newr[k]=0;
   group=1;
   pre=0;

   do{   front=(front+1)%n;
         i=cq[front];
         if(i<pre)
         {   group++;
             result[i-1]=group;
             for(k=0;k<n;k++)
                newr[k]=r[i-1][k];
         }
         else if(newr[i-1]!=0)
         {   rear=(rear+1)%n;
             cq[rear]=i;
         }
         else
         {   result[i-1]=group;
             for(k=0;k<n;k++)
                newr[k]=newr[k]+r[i-1][k];
         }
         pre=i;
     }while(rear!=front);
}

void main()
{    static int r[N][N]={{0,1,0,0,0,0,0,0,0},
			 {1,0,0,0,1,1,0,1,1},
			 {0,0,0,0,0,1,1,0,0},
			 {0,0,0,0,1,0,0,0,1},
			 {0,1,0,1,0,1,1,0,1},
			 {0,0,1,0,1,1,0,0,0},
			 {0,1,0,0,0,0,0,0,0},
			 {0,1,0,1,1,0,0,0,0}};
     static int cq[N],result[N],newr[N];
     int i,n=9;
     division(r,n,cq,newr,result);
     for(i=0;i<9;i++)
	printf("%d  ",result[i]);
}