离散数学实验——集合的运算

实验一集合的运算

1.1实验目的

集合论是一切数学的基础，也是计算机科学不可或缺的，在数据结构、数据库理论、开关理论、自动机理论和可计算理论等领域都有广泛的应用。集合的运算规则是集合论中的重要内容。通过该组实验，目的是让学生更加深刻地理解集合的概念和性质，并掌握集合的运算规则等。

1.2实验内容

1、选用恰当的数据结构实现集合的存储；（数组、向量）

2、实现集合的基本操作：查找、插入、删除、输出；

3、判断某个元素是否属于集合；

4、实现集合的基本运算：并、交、差、对称差运算；

5、判断两集合之间的关系：包含、相等；

6、求集合的幂集并输出。

1.3主要算法思想

　　集合的交：

　　 ① 把需要求交集的集合中的元素全部放在一个新的字符串allElem中，比如A{a,b,c,d}、B{a,d,e,f,g},则allElem=“abcdadefg”。

② 然后利用两次循环计算allElem中的每个字符出现的个数，用InNum记录。计算完一个字符后，InNum归零。

③ 如果InNum=集合的个数，则说明当前元素在所有的集合里，所以输出当前元素。

//计算交集(多个集合进行计算)
string ListIntersect(string &SelectedList) {
	string NewList="";
	ListAllOutput();
	cout << endl << "请选择需要求交集的集合：";
	cin >> SelectedList;
	//把所有集合放在一个字符穿里  
	string allElem="";
	for (int i = 0; i < SelectedList.length(); i++) {
		allElem += List[int(SelectedList[i]) - 65];
	}

	//判断allElem出现了选中集合数量的次数
	for (int i = 0; i < allElem.length(); i++) {
		int InNum = 0;
		for (int j =i; j < allElem.length(); j++) {
			if (allElem[i] == allElem[j])
				InNum++;
		}
		if (InNum == SelectedList.length())
		{
			NewList += allElem[i];
		}
	}
	cout << "交集为";
	return NewList;
}

集合的并：

① 把需要求并集的集合中的元素全部放在一个新的字符串allElem中，比如A{a,b,c,d}、B{a,d,e,f,g},则allElem=“abcdadefg”。

② 然后先利用InNum求出元素在allElem出现的次数，然后依次输出allElem的元素，如果出现两次，则只输出一次。

//计算并集(多个集合进行计算)
string ListUnion(string &SelectedList) {
	string NewList="";
	ListAllOutput();
	cout << endl << "请选择需要求并集的集合：";
	cin >> SelectedList;
	bool flag;
	//把所有集合放在一个字符穿里  
	string allElem = "";
	for (int i = 0; i < SelectedList.length(); i++) {
		allElem += List[int(SelectedList[i]) - 65];
	}
	//cout << "集合" << SelectedList << "的并集为：{";
	//排除allElem的重复元素就是并集
	for (int i = 0; i < allElem.length(); i++) {
		int InNum = 0;
		flag = true;
		for (int j = i; j < allElem.length(); j++) {
			if (allElem[i] == allElem[j])
				InNum++;
		}
		if (InNum <= 1)
		{
			NewList += allElem[i];
		}
			
	}
	cout << "并集为";
	return NewList;
}

　　集合的差：

　　① 输入：集合名1-集合名2。

② 利用两层循环，第一层遍历集合名1的元素，第二层遍历集合名2的元素，并判断集合名1中的元素是否在集合名2中，如果在则不输出。

//计算差集(也就是相对补集，,两个集合进行计算)
string ListSubtract(string &SelectedList) {
	while (true) {
		ListAllOutput();
		cout << endl << "注意：求差集集合名顺序不能改变"<<endl<<"例如：集合A:{a,b,c,d} B:{c,d,e,f}"<<endl<<"	则A-B={a,b}    B-A={e,f}";
		cout << endl << "请按照 ‘集合名1-集合名2’输入：";
		cin >> SelectedList;
		if (SelectedList.length() > 3)
			cout << "输入有误！请重新输入！" << endl;
		else
			break;
	}
	int List1Length = List[int(SelectedList[0]) - 65].length();
	int List2Length = List[int(SelectedList[2]) - 65].length();
	string NewList="";//保存
	bool flag;
	//cout << "" << SelectedList << "的集合为：{";
	for (int i = 0; i < List1Length; i++)//循环集合名1的长度
	{
		flag = true;
		for (int j = 0; j < List2Length; j++)//循环集合名2的长度   冒泡遍历  依次用集合名1的元素跟所有集合名2中的元素比较  有相同则除去
		{
			if (List[int(SelectedList[0]) - 65][i] == List[int(SelectedList[2]) - 65][j])//集合名1中的第i个元素等于集合名2中的第j个元素
			{
				flag = false;
				break;
			}
		}
		if(flag)
			NewList += List[int(SelectedList[0]) - 65][i];

	}
	cout << "差集为";
	return NewList;

}

集合的对称差：

① 将求对称差的集合中的元素全部放在一个新的字符串allElem中。

② 定义一个flag，利用两层循环将allElem中的每个元素于其他元素比较，若相等则是交集就不输出，若没有相等的则说明不是交集就输出。

//计算对称差(可以多个集合计算)
string ListSymDifference(string& SelectedList) {
	string NewList = "";
	ListAllOutput();
	cout << endl << "请选择需要求对称差的集合：";
	cin >> SelectedList;
	bool flag;
	//把所有集合放在一个字符穿里  
	string allElem = "";
	for (int i = 0; i < SelectedList.length(); i++) {
		allElem += List[int(SelectedList[i]) - 65];
	}
	for (int i = 0; i < allElem.length(); i++) {
		flag = true;
		for (int j = 0; j < allElem.length(); j++) {
			if (i == j)
				continue;
			if (allElem[i] == allElem[j])
			{
				flag = false;
				break;
			}
		}
		if (flag) {
			NewList += allElem[i];
		}
	}
	cout << "对称差为";
	return NewList;
}

集合求幂集：

① 利用三层循环，第一层循环是计算i元子集。

② 第二层循环是计算包含第j个元素的所有i元子集

③ 第三层循环则是第j个元素的i元子集的所有组合。

//求幂集
void PowerSet() {
	char ListName;//需要求幂集的集合名
	ListAllOutput();
	cout << endl << "请选择要求幂集的集合：";
	cin >> ListName;
	string PowerSet;//幂集字符串
	int ListLength = List[int(ListName) - 65].length();
	cout << "{{},";//首先输出空集
	for (int i = 1; i <= ListLength; i++) {//第一层循环是计算几元子集
		/// <summary>
		/// 第二层循环是计算包含第j+1个元素的所有i元子集
		/// 例如：A{a,b,c,d}  
		/// 当j=0 i=1，则有{a}
		/// 当j=0 i=2，则有{a,b} {a,c} {a,d}
		/// </summary>
		for (int j = 0; j < ListLength; j++) {
			if (j + i > ListLength)
				break;
			//求一元子集直接求
			if (i == 1) {
				cout << "{" << List[int(ListName) - 65][j] << "},";
			}
			else
			{
				//其他元子集利用循环求
				int n = 0;
				for (int k = j + 1; k < ListLength; k++) {
					if (n == 0)
					{
						cout << "{";
						cout << List[int(ListName) - 65][j];
					}
					n++;
					if (n == i)
					{
						k=k-i+1;
						n = 0;
						cout << "},";
						continue;
					}
					else
					{
						cout << "," << List[int(ListName) - 65][k];
					}
				}
				if (i == ListLength)
					cout << "}";
				else
					cout << "},";
			}
		}
	}
	cout << "}";
}

完整代码：