《离散数学》
实验报告
学院软件学院
专业软件工程
指导教师邹丽娜
学号********
姓名冯立勇
提交日期2011-12-25
实验二 关系的闭包运算
一 、实验目的
熟悉关系的闭包运算，编程实现关系闭包运算算法。

一 、实验内容
利用矩阵求解有限集上给定关系的自反、对称和传递闭包。

三. 实验过程
1. 算法分析：
在三种闭包中自反和对称闭包的求解很容易，对矩阵表示的关系，其自反闭包只要将矩阵的主对角线全部置为1就可；对称闭包则加上关系的转置矩阵（逻辑加法）；传递闭包则有两种算法（二选一即可）：
算法1：直接根据 n i i R
R t 1)(==计算，过程略。

算法2：Warshall 算法(1962)
设R 的关系矩阵为M
(1)令矩阵A=M
(2)置i=1
(3)对所有的j ，若A[j ，i]=1，则
对于 k=1，2，…，n ，令A[j ，k]=A[j ，k]+A[i ，k]
注：此处为逻辑加，可以使用运算符||
(4) i=i+l ．
(5)若i ≤n ，则转到(3)，否则结束．
流程图
2. 程序代码：
#include<stdio.h>
void output(int s[][100]);
void zifan(int s2[][100]);
void duichen(int s2[][100]);
void chuandi2(int s2[][100]);
void chuandi1(int s2[][100]);
void aa();
int s[100][100],z;
int d,n ,i,j;
int main(){aa();return 0;}
void aa()
{
printf("请输入矩阵的行数(必须小于10)\n ");
scanf("%d",&n);
printf("请输入矩阵的列数(必须小于10)\n ");
scanf("%d",&d);
printf("请输入关系矩阵\n");
for(i=0;i<n;i++)
{ printf("\n");
printf("请输入矩阵的第%d行元素",i);
for(j=0;j<d;j++)
scanf("%d",&s[i][j]);
}
printf("输入对应序号选择算法\n1:自反闭包\n2:传递闭包1\n3:传递闭包(Warhall算法)2\n4:对称闭包\n");
scanf("%d",&z);
switch(z)
{
case 1:zifan(s); break;
case 2:chuandi1(s);break;
case 3:chuandi2(s);break;
case 4:duichen(s); break;
}
}
void output(int s[][100])
{printf("所求关系矩阵为\n"); for(i=0;i<n;i++)
{for(j=0;j<d;j++)
printf("%d",s[i][j]);
printf("\n");
}
}
void zifan(int s2[][100])
{
for(i=0;i<n;i++)
s2[i][i]=1;
output(s2);aa();
}
void duichen(int s2[][100])
{int s1[100][100];
for(i=0;i<n;i++)
for(j=0;j<d;j++)
s1[j][i]=s2[i][j];
for(i=0;i<n;i++)
for(j=0;j<d;j++)
{s2[i][j]=s2[i][j]+s1[i][j];
if(s2[i][j]>1)
s2[i][j]=1;
}
output(s2);
aa();
}
void chuandi1(int s2[][100]) {int m[100][100],a[100][100],k,h; int t[100][100];
for(i=0;i<n;i++)
for(j=0;j<d;j++)
{ a[i][j]=0;
t[i][j]=s2[i][j];
m[i][j]=s2[i][j];}
for(h=0;h<n;h++)
{for(i=0;i<n;i++)
for(j=0;j<d;j++)
if(m[i][j]==1)
{for(k=0;k<n;k++)
if(s2[j][k]==1)
a[i][k]=1;
}
for(i=0;i<n;i++)
for(j=0;j<d;j++)
{ m[i][j]=a[i][j];
t[i][j]+=a[i][j];
a[i][j]=0;
if(t[i][j]>1)
t[i][j]=1;
}
}
output(t);aa();
}
void chuandi2(int s2[][100]) {int k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(s2[j][i]==1)
for(k=0;k<n;k++) s2[j][k]+=s2[i][k];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(s2[i][j]>1)
s2[i][j]=1;
output(s2);aa();
}
3.实验数据及结果分析。