03081626-3.c

这是离散数学中集合与图论部分的算法实现 压缩包中有六个算法

#include<stdio.h>
#define N 10
int n;//集合A的元素的个数
int f1,f2;//存放关系R1与R2中序偶个数
char  A[N];

///////////////////////////////////////////////////////////

void input(char a[N],char b[N],int f)//输入序偶函数
{
  int i;  
  
  printf("输入序偶:");
  for(i=0;i<f;i++)
     scanf(" %c%c",&a[i],&b[i]);
	  
  printf("\n { ");	  
    for(i=0;i<f;i++)
	{ 
		printf("<");
	    printf("%c,",a[i]);
	      printf("%c,",b[i]);
		  printf("\b");
	      printf(">,");
		  
	}
   printf("\b");
   printf(" } ");
   printf("\n");
}

///////////////////////////////////////////////////////////

void print(int t[N][N])//输出矩阵函数
{
   int i,j;
   for(i=0;i<n;i++)
	{	
		for(j=0;j<n;j++)
            printf(" %d ",t[i][j]);
		    printf("\n");
	}
}		  
///////////////////////////////////////////////////////////  
   
void zhuanhua(char a[N],char a1[N],char a2[N],int b[N][N])  
{                                 //将序偶转化为关系矩阵         
	int i,j;
	int k1=0;
    int k2=0;
 for(i=0;i<N;i++)
	{ 
		for(j=0;j<N;j++)
	        if(a1[i]==a[j])
			{
				k1=j;
				break;
			}
		for(j=0;j<N;j++)	
		   if(a2[i]==a[j])
			{
			   k2=j;
			   break;
			}
		b[k1][k2]=1;
	}	
 printf("\n");   
 print(b);//调用，输出矩阵
}

///////////////////////////////////////////////////////////

void fuhe1(char a1[N],char a2[N],char b1[N],char b2[N])
{                           //关系复合运算函数
	int i,j;
	printf(" { ");
	 for(i=0;i<f1;i++)
		for(j=0;j<f2;j++)
		{
			if(a2[i]==b1[j])
			   printf("<%c,%c>,", a1[i],b2[j]);
			

		}
	printf("\b");
    printf(" }");
	printf("\n");
}		
				
///////////////////////////////////////////////////////////

void fuhe2(int b1[N][N],int b2[N][N],int t[N][N])//利用矩阵求复合
{
	int i,j,k;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			{
			for(k=0;k<n;k++)
			
				if(b1[i][k]==1&&b2[k][j]==1)
					
					t[i][j]=1;
				

			}
	

}
                
///////////////////////////////////////////////////////////
void zfbibao(int b[N][N],int t[N][N])
{
	int i,j;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
        	t[i][j]=b[i][j];
	 for(i=0;i<N;i++)
		t[i][i]=1;
	
    printf("其自反闭包的关系矩阵为：\n"); 
	print(t);
	
}

///////////////////////////////////////////////////////////

void dchbibao(int b[N][N],int t[N][N])
{
	int i,j;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
	       t[i][j]=b[i][j];  
   for(i=0;i<N;i++)
      for(j=0;j<N;j++)
	  { 
		  if(i!=j&&b[i][j]==1)
			  t[j][i]=1;
	  }
	
   printf("其对称闭包的关系矩阵为：\n"); 
      for(i=0;i<n;i++)
	 {
		 for(j=0;j<n;j++)
			 
            printf("%d ",t[i][j]);
		     printf("\n");
	 }
}

///////////////////////////////////////////////////////////

void chdbibao(int b[N][N],int t[N][N])//通过关系复合求关系传递闭包
{
	int i,j,k=1;
	int t1[N][N]={0};
    for(i=0;i<N;i++)
		for(j=0;j<N;j++)
	    {
			t1[i][j]=b[i][j];
		    t[i][j]=b[i][j];
		}
		do
		{
			fuhe2(t1,b,t1);
      
            for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					t[i][j]=t[i][j]+t1[i][j];
			k++;
			  
		}while(k<=n-1);
printf("其传递闭包的关系矩阵为\n");
    print(t);
		
		
}	

///////////////////////////////////////////////////////////

void warshall(int b[N][N],int t[N][N])//warshall算法
{
	int i,k,j;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
	       t[i][j]=b[i][j]; 
	for(i=0;i<=n;i++)
		for(j=0;j<n;j++)
		    for(k=0;k<n;k++)	
			 if(t[j][i]==1)   
				{
		        	if(t[j][k]==1)
						t[j][k]=1;
					else 
						if(t[i][k]==1)
						    t[j][k]=1;
					    else 
							t[j][k]=0;
			 }
					
  printf("其传递闭包的关系矩阵为\n");
    print(t);
}


///////////////////////////////////////////////////////////

void output(int t[N][N],char a[N])
{
	int i,j;
	printf("{ ");
	for(i=0;i<n;i++)
	   for(j=0;j<n;j++)
		  if(t[i][j]!=0)
			{
				printf("<");
		  printf("%c,",a[i]);
	      printf("%c,",a[j]);
		  printf("\b");
	      printf(">,");
			}
	printf("\b");
	printf(" }");
	printf("\n\n\n");
		
}
				
///////////////////////////////////////////////////////////

main()
{
	char a1[N],a2[N],b1[N],b2[N];
	
	int B1[N][N]={0};
	int B2[N][N]={0};
	int t[N][N]={0};
	printf("输入集合A：");
    gets(A);
	n=strlen(A);
	printf("\n请输入关系R1：\n");
    printf("输入中R1序偶个数：");
          scanf("%d",&f1);
	input(a1,a2,f1);
	
	/*printf("关系R1与R2的复合关系为：\n");
	fuhe1(a1,a2,b1,b2);*/
	printf("关系R1对应的关系矩阵为\n");
	zhuanhua(A,a1,a2,B1);
 	
	 zfbibao(B1,t);
     printf("关系R1自反闭包为：\n");
     output(t,A);
	 dchbibao(B1,t);
	 printf("关系R1的对称闭包为：\n");
	 output(t,A);
	 chdbibao(B1,t);
     printf("关系R1的传递闭包为：\n");
	 output(t,A);
	 warshall(B1,t);
     printf("关系R1传递闭包为：(warshall算法)\n");
	 output(t,A);
	 printf("\n请输入关系R2：\n");
    printf("输入R2中序偶个数：");
      scanf("%d",&f2);
	input(b1,b2,f2);
	printf("关系R2对应的关系矩阵为\n");   
	zhuanhua(A,b1,b2,B2);
    printf("关系R1与R2的复合的关系矩阵为：\n");
	fuhe2(B1,B2,t);
	print(t);
    printf("关系R1与R2的复合关系为：\n");
	
	output(t,A);
}