★ FEATURED ARTICLE 简介这份离散数学实验资料包面向高校计算机及相关专业学生聚焦集合运算的编程实现帮助读者用C/C完成交、并、差、补四类基本运算的算法练习。资源包含1个C源码文件与1份docx实验文档压缩包约51KB源码可直接编译运行文档则记录实验目的、原理与实现方法便于对照理解。实验以数组A、B、C、E模拟集合要求输入时检查元素重复并保证A、B为全集E的子集每次运算前将C置空交运算通过逐一比较取相同元素并运算先复制A再追加B中不重复元素差运算从A中删除与B相同的元素补运算则用E中不属于A的元素构成结果其中补集被视为特殊的集合差。目前已有2152人学习下载适合需要完成课程实验、巩固集合运算与数组操作基础的学习者参考也可作为实验报告撰写的辅助材料。1. 离散数学实验里的集合运算一个 zip 包能跑出什么名堂很多同学拿到「大学离散数学实验集合运算.zip」的第一反应是解压打开找报告模板抄一抄交差。但如果你真打算把这门课的实验分拿满甚至想借它把编程基本功顺一遍那这个 zip 包的价值远不止一份作业。集合运算实验通常要求实现并集、交集、差集、补集、对称差还要处理子集判定、幂集生成、笛卡尔积这些操作。它表面是离散数学底层考的是数据结构选型、去重逻辑、边界条件处理。适合两类人正在上离散数学课、需要交实验报告的学生以及想用一个小项目练手、把集合抽象落到代码里的自学者。zip 解压之后怎么读、怎么写、怎么验证才是真正拉开差距的地方。2. 先想清楚集合在代码里到底用什么存2.1 列表、哈希集、位向量三种存储的取舍集合运算实验最容易翻车的地方不是算法本身而是存储结构选错了。用 Python 列表存集合写并集就是两层循环时间复杂度 O(n×m)元素一多就肉眼可见地卡。用set存底层是哈希表增删查平均 O(1)但元素必须可哈希遇到自定义对象就得自己实现__hash__和__eq__。用位向量存适合全集规模固定且不大的场景比如全班 60 个学号的选课集合一个 64 位整数就能表示交并差全是位运算快得离谱但元素必须是 0 到 N-1 的连续整数。我一般会这样选如果实验要求里元素是字符串或任意整数直接用语言自带的哈希集合如果明确是「1 到 n 的整数全集」位向量是加分项老师一看就知道你动了脑子。下面这张表是我做实验时对比过的存储方式并集复杂度去重适用场景坑有序列表O(n×m)手动元素少且需保序重复元素混入哈希集合O(nm)自动通用场景不可哈希元素报错位向量O(n/word)天然连续整数全集全集范围固定2.2 用 Python 的 set 跑通五个基本运算先别急着写类用内置set把五个运算验证一遍确认你理解对了定义。下面这段代码可以直接复制运行# 用内置 set 验证五个基本集合运算 A {1, 2, 3, 4} B {3, 4, 5, 6} union A | B # 并集 {1,2,3,4,5,6} intersection A B # 交集 {3,4} difference A - B # 差集 {1,2} sym_diff A ^ B # 对称差 {1,2,5,6} # 补集需要先定义全集 U {1, 2, 3, 4, 5, 6, 7, 8} complement U - A # 补集 {5,6,7,8} print(union, intersection, difference, sym_diff, complement)逻辑说明|、、-、^分别对应并、交、差、对称差补集用全集减去自身。参数说明A和B是任意可哈希元素构成的集合U必须包含A的所有元素否则补集结果不完整。这段代码的意义是给你一个「标准答案」后面自己实现时拿它做对照。2.3 手写一个集合类从 add 到 is_subset内置set虽然好用但实验往往要求你手写。手写时核心是去重和成员判断。下面是一个最小可用的 Python 集合类class MySet: def __init__(self, elementsNone): self._data [] if elements: for e in elements: self.add(e) def add(self, element): # 去重只有不存在才加入 if element not in self._data: self._data.append(element) def union(self, other): result MySet(self._data) for e in other._data: result.add(e) return result def intersection(self, other): result MySet() for e in self._data: if e in other._data: result.add(e) return result def is_subset(self, other): # self 是否为 other 的子集 for e in self._data: if e not in other._data: return False return True逻辑说明add用in做线性查找去重union先复制自身再逐个加入对方元素intersection遍历自身保留对方也有的元素is_subset逐个检查。参数说明elements是可选的可迭代对象other必须是MySet实例。这个实现的时间复杂度是 O(n×m)适合实验规模但你要清楚它的瓶颈在哪。3. 幂集、笛卡尔积、对称差三个最容易写错的运算3.1 幂集生成的递归与位运算两种写法幂集是集合所有子集构成的集合元素个数为 n 时结果有 2^n 个。递归写法直观def power_set(s): # 递归生成幂集 if len(s) 0: return [set()] element s[0] rest s[1:] subsets power_set(rest) # 每个子集要么不含 element要么含 element return subsets [subset | {element} for subset in subsets] print(power_set([1, 2, 3]))逻辑说明取出第一个元素递归求剩余元素的幂集然后对每个子集分别做「不含该元素」和「含该元素」两个分支。参数说明s是列表或可切片序列返回列表套集合。位运算写法更适合全集是连续整数的情况用 0 到 2^n-1 的二进制位表示每个元素选不选这里不展开但你要知道递归深度受 Python 默认递归限制影响n 超过 20 左右就会很慢。3.2 笛卡尔积的顺序陷阱笛卡尔积 A×B 是所有有序对 (a,b) 的集合顺序不能反。下面代码演示def cartesian_product(A, B): result [] for a in A: for b in B: result.append((a, b)) return result print(cartesian_product([1, 2], [x, y])) # [(1,x), (1,y), (2,x), (2,y)]逻辑说明外层遍历 A内层遍历 B保证每个 a 和每个 b 都配对一次。参数说明A和B是任意可迭代对象返回列表。注意如果 A 和 B 都是集合结果里有序对本身不可哈希不能直接塞进set需要转成元组再处理。3.3 对称差的两种等价写法与验证对称差 A⊕B 等于 (A-B)∪(B-A)也等于 (A∪B)-(A∩B)。两种写法结果一样但性能不同。第一种要遍历两次第二种要算并集和交集再相减。我一般用第一种逻辑更直白def symmetric_difference(A, B): # (A - B) ∪ (B - A) left A - B right B - A return left | right A {1, 2, 3} B {3, 4, 5} print(symmetric_difference(A, B)) # {1, 2, 4, 5}逻辑说明先算两个方向的差集再取并集。参数说明A和B是set实例。验证时拿A ^ B对照结果必须一致。如果实验要求手写记得在报告里写清楚你用的是哪种等价形式以及为什么。4. 避坑与排查集合运算实验里最常见的五个翻车点4.1 现象并集结果里出现重复元素原因用列表存集合add时没做去重或者从外部读入数据时直接append。解决所有插入操作统一走add方法内部用in或哈希判断。如果数据量大改用set做中间容器最后再转回列表。4.2 现象补集算出来是空集原因全集定义错了或者全集没有包含原集合的所有元素。解决补集运算前先断言A.is_subset(U)不满足就报错或提示。很多实验报告里补集出错都是因为全集只写了「1 到 10」但原集合里有 11。4.3 现象幂集结果数量不对少了或多了原因递归边界写错或者空集处理遗漏。解决n 个元素的幂集大小必须是 2^n写完先拿 n0、n1、n2 验证。n0 时结果应包含空集n1 时结果应有两个子集。4.4 现象笛卡尔积结果顺序和预期不一致原因集合本身无序遍历顺序不确定。解决如果实验要求有序输出先把集合转成排序后的列表再算。Python 的set遍历顺序和插入顺序无关别依赖它。4.5 现象自定义对象放进 set 后去重失效原因没实现__hash__和__eq__或者只实现了一个。解决两个必须同时实现且参与哈希的字段和参与相等判断的字段保持一致。否则会出现「看起来一样但 set 认为不同」的玄学问题。5. 把实验代码变成可复用的验证脚本5.1 用断言做自动化验证写完集合类之后别靠肉眼比对。写一组断言每次改代码跑一遍def test_my_set(): A MySet([1, 2, 3]) B MySet([3, 4, 5]) assert A.union(B)._data.sort() [1, 2, 3, 4, 5].sort() assert A.intersection(B)._data [3] assert MySet([1, 2]).is_subset(A) is True assert MySet([1, 9]).is_subset(A) is False print(all tests passed) test_my_set()逻辑说明用assert对每个运算的结果做精确比对sort()用于消除顺序影响。参数说明断言里的期望值根据定义手算不要从代码输出反推。这套测试跑通实验基本分就稳了。5.2 用随机数据做交叉验证手写实现和内置set对拍是发现边界 bug 最快的方法import random def cross_check(trials1000): for _ in range(trials): a [random.randint(1, 20) for _ in range(random.randint(0, 10))] b [random.randint(1, 20) for _ in range(random.randint(0, 10))] A, B MySet(a), MySet(b) assert set(A.union(B)._data) set(a) | set(b) assert set(A.intersection(B)._data) set(a) set(b) print(cross check passed) cross_check()逻辑说明随机生成两个列表分别用MySet和内置set算并集交集结果必须一致。参数说明trials是测试轮数建议至少 1000 轮。这个脚本能帮你抓到空集、重复元素、边界长度等隐藏问题。5.3 实验报告里该写什么、不该写什么报告不是代码堆砌。该写的是存储结构选型理由、每个运算的时间复杂度、测试用例设计、遇到的 bug 和修复过程。不该写的是大段无注释代码、从网上抄的定义、和实验无关的扩展。老师看的是你有没有真正跑过、错过、改过。把交叉验证的通过截图和失败时的报错信息一起放进去比任何漂亮排版都有说服力。5.4 一个我踩过的坑递归深度与性能第一次写幂集时我用递归处理 25 个元素的集合结果直接触发递归深度限制。后来改成迭代生成用位运算从 0 循环到 2^n-1每个数对应一个子集。这个教训让我明白实验代码也要考虑规模边界不能只在小数据上跑通就交差。现在我做任何集合运算实验都会先问一句元素最多多少个超过 20 就用迭代超过 1000 就换位向量或分块。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
