离散数学实验二
一、算法描述,算法思想
(一)相关数据结构
typedef struct Set *S; //存放集合
struct Set
{
int size; //集合的元素个数
char *A; //存放该集合的元素
};
Set存放有限集合A,该集合的元素个数为size,size可以用来判断该集合是否为空集,然后集合中的元素就放在A数组里。
typedef struct Confirm *C; //存放关系的序偶<x, y>
struct Confirm
{
int x, y;
};
Confirm存放一个序偶<x, y>。
typedef struct Relation *R; //存放关系矩阵
struct Relation
{
int n, size; // n行 n列矩阵,序偶个数为size
int r[10][10]; //关系矩阵
C c; //存放该关系的序偶
};
Relation存放集合A的关系,r为一个n行,n列的关系矩阵,size为其中的序偶数,c即存放该关系的所有序偶。
int flagz = 1, flagfz = 1, flagd = 1, flagfd = 1, flagc = 1; // flagz判断是否为自反,flagfz判断是否为反自反,
// flagd判断是否为对称,flagfd判断是否为反对称,flagc判断是否为传递
设置全局变量,方便判断矩阵关系。
(二)相关算法实现
1、输出关系矩阵R
void PrintRelation(R re) //打印关系矩阵
{
printf("关系矩阵如下:\n");
for (int i = 0; i < re->n; i++)
{
for (int j = 0; j < re->n; j++)
printf("%d ", re->r[i][j]);
printf("\n");
}
printf("\n");
}
用户输入的为一个关系矩阵,只要将其存储下,然后直接输出即可,注意换行。
2、输出R具有的性质
void PrintCharacter(S s, R re) //判断该矩阵的性质
if (s->size == 0) //空集,关系具有所有性质
{
printf("该关系具有以下性质:\n");
printf("自反性\n");
printf("反自反性\n");
printf("对称性\n");
printf("反对称性\n");
printf("传递性\n");
return;
}
(1)首先是判断该集合是否为空,如果集合为空集,则具有所有的性质。
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j && !re->r[i][j]) //不可能为自反关系
flagz = 0;
if (i == j && re->r[i][j]) //不可能为反自反关系
flagfz = 0;
if (re->r[i][j] && !re->r[j][i] && i != j) //不可能为对称关系
flagd = 0;
if (re->r[i][j] && re->r[j][i] && i != j) //不可能为反对称关系
flagfd = 0;
}
}
(2)确定该集合不为空后,接下来先根据矩阵来判断自反性,反自反性,对称性,反对称性。
如果出现横纵坐标相同的点,但是其不为1,说明该集合存在a属于集合s,但不具有<a, a>序偶,则该矩阵不可能具有自反关系,将flagz = 0;
如果出现横纵坐标相同的点,但是其为1,说明该集合存在a属于该集合,且有<a, a>序偶,则该矩阵不可能具有反自反关系,将flagfz = 0;
如果出现横纵坐标不相同,且相反的两点,但是其为1,说明该集合存在a,b属于该集合,且有<a, b>,<b,a>序偶,则该矩阵不可能具有反对称关系,将flagfd = 0;
如果出现横纵坐标不相同,且相反的两点,但是其只有一个为1,说明该集合存在a,b属于该集合,且有<a, b>,没有<b,a>序偶,则该矩阵不可能具有对称关系,将flagd = 0;
for (int i = 1; i <= re->size; i++) //判断是否具有传递性
{
if (!flagc)
break;
int x = re->c[i].x, y = re->c[i].y; //若存在<x, y>
if (x == y)
continue;
for (int j = 0; j < n; j++) //找<y, j>
{
if (re->r[y][j] && !re->r[x][j]) //是否存在<x, j>
{
flagc = 0;
break;
}
}
}
(3)接下来是根据矩阵中为1的点,即该集合所具有的序偶来判断是否具有传递关系。
若存在<x, y>,我们去找<y, j>,看是否存在<x, j>,如果不存在则不具有传递关系,flagc = 0。
(4)最后将所有关系输出即可。
3、输出R的自反闭包,对称闭包,传递闭包
void PrintBibao(R re) //计算自反闭包,对称闭包,传递闭包矩阵
//自反闭包
int n = re->n;
R tmp = CopyRelation(re);
for (int i = 0; i < n; i++)
tmp->r[i][i] = 1;
printf("自反闭包矩阵:\n");
PrintRelation(tmp);
DestoryRelation(tmp);
(1)计算自反闭包,首先将原矩阵复制到tmp中,将所有横纵坐标相同的点都该为1,即为自反闭包。
//对称闭包
tmp = CopyRelation(re);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i != j && tmp->r[i][j])
{
tmp->r[j][i] = 1;
}
}
}
printf("对称闭包矩阵:\n");
PrintRelation(tmp);
DestoryRelation(tmp);
(2)计算对称闭包,首先将原矩阵复制到tmp中,将横纵坐标不同的的,原矩阵中存在的为1的点,将其的对称点也改为1,即为对称闭包。
//传递闭包
tmp = CopyRelation(re);
R ans = InitRelationTmp(n);
AddRelation(ans, re);
for (int i = 0; i < n-1; i++)
{
tmp = Multiply(tmp, re); //最多乘n次
AddRelation(ans, tmp);
}
printf("传递闭包矩阵:\n");
PrintRelation(ans);
DestoryRelation(tmp);
free(ans);
(3)计算传递闭包,首先将原矩阵复制到tmp中,将tmp与原矩阵乘矩阵的行(列)数次,将每次计算的大于1的数改为1,每次将矩阵相加,返回即可。
4、判断R是否为等价关系,相容关系,偏序关系
void PanRelation(R re) //判断矩阵的关系
{
printf("具有的关系为:\n");
if (flagz == 1 && flagd == 1 && flagc == 1) //如果为自反,对称,传递则为等价关系
printf("等价关系\n");
if (flagz == 1 && flagd == 1) //若为自反,对称则为相容关系
printf("相容关系\n");
if (flagz == 1 && flagfd == 1 && flagc == 1) //若为自反,反对称,传递为偏序关系
printf("偏序关系\n");
}
(1)等价关系:若R具有自反性,对称性,传递性。
(2)相容关系:若R具有自反性,对称性。
(3)偏序关系:若R具有自反性,反对称性,传递性。
(三)流程图
main()函数
void PrintRelation(R re) 打印关系矩阵
void PrintCharacter(S s, R re) 判断该关系矩阵的性质
void PrintBibao(R re) 计算自反闭包,对称闭包,传递闭包矩阵
void PanRelation(R re) 判断矩阵的关系
(四)程序运行截图与样例说明
输入:元素个数、集合的每个元素(用单个字符表示)、该集合的关系矩阵。
输出:关系矩阵、关系矩阵性质、自反闭包、对称闭包、传递闭包矩阵、关系矩阵的关系。
分析:该关系矩阵的序偶为<1,2>,<2,1>,<2,3>,<3,4>。
可以看出该关系矩阵不具有自反性,对称性,反对称性,传递性。
具有反自反性。
且计算的自反闭包,对称闭包,传递闭包与答案相同。
判断的关系也正确。
(五)代码
#include <stdio.h>
#include <stdlib.h>
typedef struct Confirm *C; //存放关系的序偶<x, y>
struct Confirm
{
int x, y;
};
typedef struct Relation *R; //存放关系矩阵
struct Relation
{
int n, size; // n行 n列矩阵,序偶个数为size
int r[10][10]; //关系矩阵
C c; //存放该关系的序偶
};
typedef struct Set *S; //存放集合
struct Set
{
int size; //集合的元素个数
char *A; //存放该集合的元素
};
int flagz = 1, flagfz = 1, flagd = 1, flagfd = 1, flagc = 1; // flagz判断是否为自反,flagfz判断是否为反自反,
// flagd判断是否为对称,flagfd判断是否为反对称,flagc判断是否为传递
S InitSet(int size) //创建集合
{
S s = (S)malloc(sizeof(struct Set));
s->A = (char *)malloc(sizeof(char) * size);
s->size = size;
printf("注意:集合的每个元素用单个字符来表示\n");
for (int i = 0; i < size; i++)
scanf("%d", &s->A[i]);
return s;
}
R InitRelation(int n) //创建关系矩阵
{
int now = 0;
R re = (R)malloc(sizeof(struct Relation));
re->n = n;
re->c = (C)malloc(sizeof(struct Confirm) * n);
printf("请输入该集合的关系矩阵(n*n):\n");
for (int i = 0; i < re->n; i++)
{
for (int j = 0; j < re->n; j++)
{
scanf("%d", &re->r[i][j]);
if (re->r[i][j])
{
re->c[++now].x = i;
re->c[now].y = j;
}
}
}
re->size = now;
return re;
}
R InitRelationTmp(int n)
{
R tmp = (R)malloc(sizeof(struct Relation));
tmp->n = n;
for (int i=0; i<tmp->n; i++)
{
for (int j=0; j<tmp->n; j++)
tmp->r[i][j] = 0;
}
return tmp;
}
void DestorySet(S s) //释放集合内存
{
free(s->A);
free(s);
}
void DestoryRelation(R re) //释放关系矩阵内存
{
free(re->c);
free(re);
}
void PrintRelation(R re) //打印关系矩阵
{
printf("关系矩阵如下:\n");
for (int i = 0; i < re->n; i++)
{
for (int j = 0; j < re->n; j++)
printf("%d ", re->r[i][j]);
printf("\n");
}
printf("\n");
}
R Multiply(R re, R re2) //计算两矩阵相乘,且将相乘后的大于1的数改为1
{
int n = re->n, tmp = 0, i, j;
R ans = InitRelationTmp(n);
for (i = 0; i < n; i++) //每一行
{
for (j = 0; j < n; j++) //该行的列
{
tmp = 0;
for (int k = 0; k < n; k++)
{
tmp += re->r[i][k] * re2->r[k][j];
}
if (tmp >= 1)
{
ans->r[i][j] = 1;
}
}
}
return ans; //返回得出的矩阵
}
void AddRelation(R re1, R re2)
{
int n = re1->n;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
re1->r[i][j] += re2->r[i][j];
if (re1->r[i][j]>1)
re1->r[i][j] = 1;
}
}
}
void PrintCharacter(S s, R re) //判断该矩阵的性质
{
int n = re->n;
if (s->size == 0) //空集,关系具有所有性质
{
printf("该关系具有以下性质:\n");
printf("自反性\n");
printf("反自反性\n");
printf("对称性\n");
printf("反对称性\n");
printf("传递性\n");
return;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j && !re->r[i][j]) //不可能为自反关系
flagz = 0;
if (i == j && re->r[i][j]) //不可能为反自反关系
flagfz = 0;
if (re->r[i][j] && !re->r[j][i] && i != j) //不可能为对称关系
flagd = 0;
if (re->r[i][j] && re->r[j][i] && i != j) //不可能为反对称关系
flagfd = 0;
}
}
for (int i = 1; i <= re->size; i++) //判断是否具有传递性
{
if (!flagc)
break;
int x = re->c[i].x, y = re->c[i].y; //若存在<x, y>
if (x == y)
continue;
for (int j = 0; j < n; j++) //找<y, j>
{
if (re->r[y][j] && !re->r[x][j]) //是否存在<x, j>
{
flagc = 0;
break;
}
}
}
//输出性质
printf("该关系具有以下性质:\n");
if (flagz == 1)
printf("自反性\n");
if (flagfz == 1)
printf("反自反性\n");
if (flagd == 1)
printf("对称性\n");
if (flagfd == 1)
printf("反对称性\n");
if (flagc == 1)
printf("传递性\n");
if (!flagz&&!flagfz&&!flagd&&!flagfd&&!flagc)
printf("该关系矩阵不具有自反、反自反、对称、反对称、传递性\n");
}
R CopyRelation(R re) //复制关系矩阵,方便计算
{
R tmp = (R)malloc(sizeof(struct Relation));
tmp->n = re->n;
tmp->size = re->size;
tmp->c = (C)malloc(sizeof(struct Confirm) * tmp->size);
for (int i = 0; i < tmp->n; i++)
{
for (int j = 0; j < tmp->n; j++)
tmp->r[i][j] = re->r[i][j];
}
for (int i = 1; i <= tmp->size; i++)
{
tmp->c[i].x = re->c[i].x;
tmp->c[i].y = re->c[i].y;
}
return tmp; //返回该复制的矩阵
}
void PrintBibao(R re) //计算自反闭包,对称闭包,传递闭包矩阵
{
//自反闭包
int n = re->n;
R tmp = CopyRelation(re);
for (int i = 0; i < n; i++)
tmp->r[i][i] = 1;
printf("自反闭包矩阵:\n");
PrintRelation(tmp);
DestoryRelation(tmp);
//对称闭包
tmp = CopyRelation(re);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i != j && tmp->r[i][j])
{
tmp->r[j][i] = 1;
}
}
}
printf("对称闭包矩阵:\n");
PrintRelation(tmp);
DestoryRelation(tmp);
//传递闭包
tmp = CopyRelation(re);
R ans = InitRelationTmp(n);
AddRelation(ans, re);
for (int i = 0; i < n-1; i++)
{
tmp = Multiply(tmp, re); //最多乘n次
AddRelation(ans, tmp);
}
printf("传递闭包矩阵:\n");
PrintRelation(ans);
DestoryRelation(tmp);
free(ans);
}
void PanRelation(R re) //判断矩阵的关系
{
int flag = 0;
printf("具有的关系为:\n");
if (flagz == 1 && flagd == 1 && flagc == 1) //如果为自反,对称,传递则为等价关系
{
printf("等价关系\n");
flag = 1;
}
if (flagz == 1 && flagd == 1) //若为自反,对称则为相容关系
{
printf("相容关系\n");
flag = 1;
}
if (flagz == 1 && flagfd == 1 && flagc == 1) //若为自反,反对称,传递为偏序关系
{
printf("偏序关系\n");
flag = 1;
}
if (!flag)
printf("该关系矩阵不具有等价、相容、偏序关系\n");
}
int main()
{
int size;
printf("请输入该集合的元素个数:\n");
scanf("%d", &size);
S s = InitSet(size); //输入集合
R re = InitRelation(size); //输入关系矩阵
PrintRelation(re); //打印关系矩阵
PrintCharacter(s, re); //打印矩阵性质
PrintBibao(re); //打印闭包矩阵
PanRelation(re); //判断矩阵的关系
DestorySet(s); //释放内存
DestoryRelation(re);
return 0;
}