03081626-2.c

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

#include<stdio.h>
#define N 20
int n;//集合A的元素的个数
int x,y,z;//判断自反性对称性传递性的标志

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

void input(char a[N],char r[N][N],int b[N][N])//输入序偶函数,
{                                              //并将其转化为关系矩阵
  int i,j,f;   //f为序偶个数
  int k1,k2;
   printf("输入序偶个数：");
   scanf("%d",&f);
   printf("\n输入序偶:");
  for(i=0;i<f;i++)
    for(j=0;j<2;j++)
	      scanf(" %c",&r[i][j]);
		  for(i=0;i<N;i++)
	     for(j=0;j<N;j++) 
			 b[i][j]=0;
/*for(i=0;i<n;i++)
	  for(j=0;j<2;j++)
 printf("%c",r[i][j]);*/
 for(i=0;i<N;i++)
	{ 
		for(j=0;j<N;j++)
	        if(r[i][0]==a[j])
			{
				k1=j;
				break;
			}
		for(j=0;j<N;j++)	
		   if(r[i][1]==a[j])
			{
			   k2=j;
			   break;
			}
		b[k1][k2]=1;
	}	
	 printf("对应的关系矩阵为:\n");   
   for(i=0;i<strlen(a);i++)
   {  
	   for(j=0;j<strlen(a);j++)
         printf("%d ",b[i][j]);
	      printf("\n");
   }
} 

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

zifan(int b[N][N])//判断自反函数
{
	int i;
	int k=0;
  for(i=0;i<n;i++)
  { 
	  if(b[i][i]==1)
            k++;
  }
	if(k==n)	
	{  printf("此关系具有自反性\n");
	   x=1;//置标志为1
	}
    if(k==0)
	   printf("此关系具有反自反性\n");
	if(k!=0&&k!=n)
	   printf("此关系既无自反性又无反自反性\n");
	  
     return x;//返回标志X
 }

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

duichen(int b[N][N])
 {   
	 int i,j;
     int k1=0;int k3=0;
	 int k2=0;
	  for(i=0;i<n;i++)
		 for(j=0;j<n;j++&&i!=j)
		if(b[i][j]==1)
		{       
			  k1++;
		   if(b[j][i]==1)
			k2++;
		}
		if(k1==k2)
		{
			printf("此关系具有对称性\n");
			y=1;//置标志为1
		}
	   		
	 for(i=0;i<n;i++)
	 { 
		 for(j=0;j<n;j++)
		    if(i!=j&&b[i][j]*b[j][i]==0)
			   k3++;
	 }
	   if(k3==n*(n-1))
          printf("此关系具有反对称性\n");
	   if(k1!=k2&&k3!=n*(n-1))
           printf("此关系既不具有对称性又不具有反对称性\n");
	 
     return y;//返回标志Y
 }

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

chuandi(int b[N][N])	
{
	int i,j;
    int k1,k2,k;
     
     k1=k2=0;
    for(i=0;i<n;i++)
		 for(j=0;j<n;j++)
			 if(b[i][j]==1)
			{
			 for(k=0;k<n;k++)
			   if(b[j][k]==1&&b[i][k]!=1)
				   k1=0;
			   
			   }
			 else 
				   k1++;
	if(k1!=0)
	{
		printf("此关系具有传递性\n");
		z=1;//置标志为1
	}
	else 
		printf("此关系不具有传递性\n");
    return z;//返回标志Z
 }

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

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

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

main()
{
	int B[N][N];
    char A[N];
    char R[N][N]={0};
    printf("输入集合A：");
    gets(A);n=strlen(A);
    printf("输入集合A上的关系：\n");
    input(A,R,B);
    zifan(B);
    duichen(B);
    chuandi(B);
      if(x&&y&&z)  //是否为等价关系	
	{	
		  printf("此关系为等价关系\n");
	      printf("其商集A/R为:\n");
	       shangji(B,A);
	}
	return 0;
}