bibaosuanfa.cpp

该程序为经典的闭包算法

// Bibaosuanfa.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#define max 100
void zifan(int B[][max],char A[max],int n);
void duichen(int B[][max],char A[max],int n);
void Warshall(int B[][max],char A[max],int n);
void chuandibibao(int B[][max],int n);
void mul(int B1[][max],int B2[][max],int n);
void print(int B[][max],int n);
int luojicheng(int m,int n);
int luojijia(int m,int n);
int W[max][max];

int main(int argc, char* argv[])
{
	char ch,A[max];
	int B[max][max],num,i,j,head,tail,R[max][max];
	cout <<"请输入集合A的元素个数：";
	cin >>num;
	cout <<"请输入集合A的元素：";
    for(i=1;i<=num;i++)
	{
		cin >>ch;
		A[i]=ch;
	}
	cout <<endl;
	cout <<"输出集合A的元素：";
	for(i=1;i<=num;i++)
	{
		cout <<i<<A[i]<<" ";
	}
	cout <<endl;
    
	
	for(i=0;i<=num;i++)//初始化矩阵全为0
	{
		for(j=0;j<=num;j++)
		{
			B[i][j]=0;
		    R[i][j]=0;
		}
	}
    cout <<"请输入集合A上的关系R："<<endl;
	cout <<"请输入弧尾和弧头："<<endl;
	while(1)
	{
		cin >>tail>>head;
		if(tail==-10000 || head==-10000)
			break;
		else 
			B[tail][head]=1;

	}
    cout <<"关系R的矩阵："<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout <<B[i][j]<<" ";
		cout <<endl;
	}
    cout <<"关系R的序偶"<<endl;
	for(i=1;i<=num;i++)
	{	for(j=1;j<=num;j++)
		{
			if(B[i][j]==1)
				cout <<A[i]<<"->"<<A[j]<<" ";			
		}
		cout <<endl;
	}   
   
   zifan(B,A,num);
   duichen(B,A,num);
   chuandibibao(B,num);
   Warshall(B,A,num);
  /* mul(B,B,num);
  for(i=2;i<=num;i++)
  {
	  mul(W,B,num);
      
  }*/
  
	return 0;
}


void zifan(int B[][max],char A[max],int n)
{
	int i,j;
	int C[max][max];
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
			C[i][j]=B[i][j];
	}
	for(i=0;i<=n;i++)
		C[i][i]+=1;
	cout <<"集合A上关系R的自反闭包"<<endl;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			if(C[i][j]==0)
				cout <<"0"<<" ";
			else
				cout <<"1"<<" ";
		}
		cout <<endl;
	}

	cout <<"集合A上关系R的自反闭包关系序偶"<<endl;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			if(C[i][j]!=0)
				cout <<A[i]<<"->"<<A[j]<<" ";
			
		}
		cout <<endl;
	}

}


void duichen(int B[][max],char A[max],int n)
{
	int i,j;
	int C[max][max],D[max][max],E[max][max];
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
			C[i][j]=B[i][j];
	}
	for(i=0;i<=n;i++)
		for(j=0;j<=n;j++)
			D[j][i]=C[i][j];
    for(i=0;i<=n;i++)
		for(j=0;j<=n;j++)
			E[i][j]=C[i][j]+D[i][j];
	
	cout <<"集合A上关系R的对称闭包"<<endl;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			if(E[i][j]==0)
				cout <<"0"<<" ";
			else
				cout <<"1"<<" ";
			
		}
		cout <<endl;
	}

	cout <<"集合A上关系R的对称闭包关系序偶"<<endl;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			if(E[i][j]!=0)
				cout <<A[i]<<"->"<<A[j]<<" ";
			
		}
		cout <<endl;
	}

}

void Warshall(int B[][max],char A[max],int n)
{
	int i,j,k;
	int C[max][max];
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
			C[i][j]=B[i][j];
	}
	for(i=0;i<=n;i++)
		for(j=0;j<=n;j++)
		{
			if(C[j][i]==1)
			{
				int a=j;
			    for(k=0;k<=n;k++)
				C[a][k]+=C[i][k];
			}
		}
		
	cout <<"集合A上关系R的Warshall传递闭包"<<endl;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			if(C[i][j]==0)
				cout <<"0"<<" ";
			else
				cout <<"1"<<" ";
		}
		cout <<endl;
	}

	cout <<"集合A上关系R的Warshall传递闭包关系序偶"<<endl;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			if(C[i][j]!=0)
				cout <<A[i]<<"->"<<A[j]<<" ";
			
		}
		cout <<endl;
	}
}

int luojicheng(int m,int n)
{
	if(n==1&&m==1)
		return 1;
	else 
		return 0;
}

int luojijia(int m,int n)
{
	if(m==0&&n==0)
		return 0;
	else 
		return 1;
}
void chuandibibao(int B[][max],int n)
{
	int D[max][max];
	int C[max][max];
	int S[max][max];
	int a=1,b=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			D[i][j]=B[i][j];
			S[i][j]=B[i][j];
		}
	for(int r=1;r<n;r++)
	{
		for(i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				C[i][j]=S[i][j];
		for(i=1;i<=n;i++)
			for(int j =1;j<=n;j++)
			{
				b=0;
				for(int k=1;k<=n;k++)
				{
					a = luojicheng(C[i][k],B[k][j]);
					b = luojijia(a,b);
				}
				S[i][j] = b;
			}

		for(i =1;i<=n;i++)
			for(int j=1;j<=n;j++)
				D[i][j] = luojijia(D[i][j],S[i][j]);
	}
	cout<<"用距阵乘法求";
	cout<<"关系R的传递闭包t(R)为："<<endl;
	
	print(D, n);

}


void  mul(int B1[][max],int B2[][max],int n)
{
	int i,j,k;
	int C[max][max],D[max][max],E[max][max];
	
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			C[i][j]=B1[i][j];
			D[i][j]=B1[i][j];
		}

	}
	for(i=0;i<=n;i++)//初始化矩阵全为0
	{
		for(j=0;j<=n;j++)
			E[i][j]=0;
	}
	

	for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		{
			for(k=1;k<=n;k++)
			E[i][j]+=C[i][k]*D[k][j];
		}
	}
    
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
			W[i][j]=E[i][j];
			
	}
    
		cout <<"aaaaa"<<endl;
        print(E, n);
	
   
    
		
}
void print(int B[][max],int n)
{
	int i,j;
    for(i=1;i<=n;i++)
	{	for(j=1;j<=n;j++)
		    cout <<B[i][j]<<" ";
		cout <<endl;	
			
			
	} 
}