xrdj.cpp

该程序为经典的算法

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

#include "stdafx.h"
#include "iostream.h"
#define max 100
bool zifan(int B[][max],int n);
bool chuandi(int B[][max],int n);
bool duichen(int B[][max],int n);
int luojijia(int m,int n);
void dengjialei(char A[],int B[][max],int n);
void xiangronglei(char A[],int B[][max],int n);


struct node {
	int id;
	char text;
	node * next;
};
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;
	}
	

	if(zifan(B,num)&&duichen(B, num)&&chuandi(B,num))
	{
		cout<<"关系R 是等价关系！"<<endl;
		
		dengjialei(A,B,num);
	}
	else 
		cout<<"关系R 不是等价关系！"<<endl;
   
   if(zifan(B,num)&&duichen(B, num))
	{
		cout<<"关系R 是相容关系！"<<endl;
		xiangronglei(A,B,num);
	}
	else 
		cout<<"关系R 不是相容关系！"<<endl;
	return 0;
}

bool zifan(int B[][max],int n)
{
	int i;
	if(n==0)
		return false;
	for(i=1;i<=n;i++)
	{
		if(B[i][i]!=1)
			return false;
	}
		return true;
}

bool duichen(int B[][max],int n)
{
	int i,j;
	if(n==0)
		return true;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(B[i][j]!=B[j][i])
			return false;
		}
	return true;
}

bool chuandi(int B[][max],int n)
{
	int i,j,k,C[max][max];
	for(i =1;i<=n;i++)
		for(j=1;j<=n;j++)
			C[i][j]=B[i][j];
	for( i =1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				if(C[j][i]==1)
					C[j][k]=luojijia(C[j][k],C[i][k]);
	for(i =1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(C[i][j]!=B[i][j])
			return false;
			return true;

}
int luojijia(int m,int n)
{
	if(m==0&&n==0)
		return 0;
	else 
		return 1;
}
void dengjialei(char A[],int B[][max],int n)
{
	//用链表实现等价类
	int i,j,m=0;
	char D[max];
	for(i =1;i<=n;i++)
		D[i]=A[i];
	node *head = new node;
	head->id = 0;
	head->text = 0;
	head->next = NULL;
	for(i =1;i<=n-m;i++)
	{
		{
			head->id = i;
			head->text = D[i];
			head->next = NULL;
		}
		for(j=1;j<=n;j++)
			if(B[i][j]==1&&D[i]!=D[j])
			{
				node *q = new node;
				q->id = j;
				q->text = A[j];
				q->next = head ->next;
				head->next = q;
				for(int r=j;r<n;r++)
					D[r]=D[r+1];
				++m;
			}
		node *p = head;
		cout<<"["<<head->text<<"]={";
		while(p)
		{
			cout<<p->text<<" ";
			p=p->next;
		}
		cout<<"}"<<endl;
	}

}
void xiangronglei(char A[],int B[][max],int n)
{
	//用链表实现相容类
	int i,j;
	char D[max];
	for(i =1;i<=n;i++)
		D[i]=A[i];
	node *head = new node;
	head->id = 0;
	head->text = 0;
	head->next = NULL;
	for(i =1;i<=n;i++)
	{
		{
			head->id = i;
			head->text = D[i];
			head->next = NULL;
		}
		node *t=head;
		for(j=1;j<=n;j++)
			if(B[i][j]==1&&D[i]!=D[j])
			{
				node *q = new node;
				q->id = j;
				q->text = D[j];
				q->next = t ->next;
				t->next = q;
				t = t->next;
			}
		if(head->next==NULL)
			cout<<"{"<<head->text<<"}"<<" "<<endl;
		else
		{
			node *t =head;
			node *p = head->next;
			node *q = p->next;
			while(q)
			{
A:				for(q;;q=q->next )
				{
					if(B[q->id][p->id]==1||B[p->id][q->id]==1)
						q = q->next;
					else 
					{
						p = p->next ;
						t->next = p;
						q = p->next;
						goto A;
					}

				}
			     
					p=p->next;
					q=p->next;
			}
		
			p = head;
			cout<<"相容类为：{";
			while(p)
			{
				cout<<p->text<<" ";
				p=p->next;
			}
			cout<<"}"<<endl;
			head->next=NULL;
		}
	}

}