C++实现关系的闭包运算（离散数学）

目录

一、问题描述

二、相关知识

三、算法描述

四、完整代码

五、测试用例

六、补充内容

七、总结

---

一、问题描述

        编写一个程序，按照用户的输入，构建N×N的矩阵，并通过矩阵运算实现关系的闭包运算（自反闭包、对称闭包和传递闭包）。此处用户输入的关系数据以及运算后结果的输出均为关系矩阵形式，用二维数组存取。

---

二、相关知识

https://www.csdn.net/tags/MtTaIgwsMzA3NDctYmxvZwO0O0OO0O0O.html

对于关系的闭包运算相关知识，大家可以看上面这篇博客，帮助大家理解，此处不做详细介绍。

---

三、算法描述

1. 构建checkR函数，将用户输入的关系矩阵呈现出来；
2. 构建zifanbibao函数，进行矩阵运算，求出关系R的自反闭包r(R);
3. 构建duichenbibao函数，进行矩阵运算，求出关系R的对称闭包s(R);
4. 构建chuandibibao函数，进行矩阵运算，求出关系R的传递闭包t(R);
5. 构建destroy函数，释放内存空间。

---

四、完整代码

#include 
using namespace std;
void checkR(int** R, int N)
{
	cout << "R:" << endl;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << R[i][j];
			if (j != N - 1) cout << " ";
		}
		cout << endl;
	}
}
void zifanbibao(int** R, int N)
{
	for (int i = 0; i < N; i++) R[i][i] = 1;
	cout << "自反闭包:"<= 1) for (int k = 0; k < N; k++) R[i][k] = R[i][k] + R[j][k];
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (R[i][j] >= 1) R[i][j] = 1;   //布尔加法大1为1
	cout << "传递闭包:" << endl;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << R[i][j];
			if (j != N - 1) cout << " ";
		}
		if (i != N - 1) cout << endl;
	}
}
void destroy(int** R, int** r, int N)
{
	for (int i = 0; i < N; i++) delete R[i], delete r[i];
	delete R;
	delete r;
}
int main()
{
	int N, pattern;
	cout << "请输入矩阵行列值N：";
	cin >> N;
	int** R = new int* [N], ** r = new int* [N];   //地址传递会改值，需另设r传值
	for (int i = 0; i < N; i++) R[i] = new int[N], r[i] = new int[N];   //请求N×N矩阵空间
	cout << "1.单行输入，数据之间用空格分隔；" << endl;
	cout << "2.N×N规范输入矩阵R；" << endl;
	cout << "请选择输入模式：";
	cin >> pattern;
	if (pattern == 1)
	{
		cout << "请输入：";
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> R[i][j];   //根据用户输入构建N×N矩阵
	}
	else if(pattern == 2)
	{
		cout << "请输入：" << endl;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> R[i][j];
			}
			cin.get();
		}
	}
	else cout << "wrong pattern!!!";
	cout << endl;
	checkR(R, N);
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) r[i][j] = R[i][j];
	zifanbibao(r, N);   //自反闭包运算
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) r[i][j] = R[i][j];
	duichenbibao(r, N);   //对称闭包运算
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) r[i][j] = R[i][j];
	chuandibibao(r, N);   //传递闭包运算
	destroy(R, r, N);   //释放空间
	return 0;
}

---

五、测试用例

①4
输入模式1：0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0
输入模式2：
0 1 0 0
1 0 1 0
0 0 0 1
0 0 0 0

②7
输入模式1：1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
输入模式2：
1 1 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

---

六、补充内容

①函数调用时传递的参数是数组名时为地址传递，此时函数内部的 *** 作会影响原数组的值，此处增设了一个二维数组r代替R作为传递的参数，并在每次传递之前复制R的值给r；

②传递闭包通过Warshall算法实现，详情可看下面这篇博客

https://blog.csdn.net/weixin_55267022/article/details/118067024

---

七、总结

代码并不复杂，关键是要理解关系是如何进行闭包运算的。如有错误之处，还请指正。