简介离散数学集合运算C或C语言实验报告以PDF格式呈现面向计算机专业需完成集合运算编程实验的学生。报告包含完整的实验目的、实验内容与算法描述用数组A、B、C、E表示集合针对交、并、差、补四种运算分别给出清晰的C语言实现思路和核心代码源程序部分提供可直接运行的完整代码包含输入元素时的重复性检查、集合置空、结果输出等环节便于读者对照调试或移植到自己的项目中。资源仅有1个PDF文件压缩包大小376KB内容紧凑、标注清晰。该实验报告已有977人学习下载适合作为离散数学课程上机实验、课程设计或期末复习的参考资料。通读后可快速掌握用C/C实现有限集合运算的方法也能理解在全集E下求补集等运算的编程细节。1. 集合运算实验为什么值得用 C/C 重写一遍网上的集合运算实验报告不少真正能换一组数据还跑对的不多。离散数学里的并、交、差、对称差看起来就是几个符号一旦把全集规模放大、输入里混进重复元素、或者要求做补集用数组硬算的演示代码立刻露馅。这篇博客围绕“离散数学集合运算”这个实验题从数据结构选型讲到 C/C 落地最后落到能写进实验报告的输出格式和自动验证。核心结论先放在前面全集有限用位图全集不明用哈希集合在这条主线上展开后面每一步都不会白写。适合正在写离散数学实验的学生也适合想找个小题目练 C/C 基本功的读者。2. 集合的三种表示数组、位图与哈希表怎么选离散数学的定义强调集合是无序且互异的对象整体。无序意味着数组下标顺序不表达集合语义互异意味着插入必须去重处理不好{1,2} 和 {2,1,2} 会被当成不同集合实验结论全错。程序里选哪种数据结构本质上是对“全集规模”和“元素类型”这两个问题预先作答。2.1 数组表示适合讲课演示不适合运运算量数组是最容易想到的方案int a[N] 存元素并集是把数组 b 里不在 a 中的元素追加进去判断元素是否在集合里要双重循环。用 C 语言写查询和去重复杂度是 O(n*m)集合量到 1000 就已经是百万级别判断实验数据再放大一些程序慢到肉眼可见。我平时写这类遍历更喜欢用指针而不是下标。对数组 a 的前 n 个元素for (p a; p ! a n; p)和for (i 0; i n; i)完全等价指针版本把终止地址 an 写在一处越界风险更直观。报告里想体现 C 语言基础用几行指针遍历比贴整段双重循环更有信息量。数组版的意义在于算法描述简单适合画流程图真正提交的代码我会选下一节的方式。如果实验强制要求“必须用 C 语言且不能借助标准库容器”数组也确实能完成全部运算只是要把去重和查询逻辑写得非常小心。2.2 位图表示全集有限时的最优解位图把全集 U 中的元素映射到 0..N-1每个元素对应一个二进制位。集合 {1,3,5} 在全集 0..7 下对应位图 0b00101010位 0 在最低位位 7 在最高位。并、交、差、对称差一次按位运算处理 64 个元素性能比数组版本高一个数量级。位图的空间随全集 N 增长N10000 时约 1250 字节N100 万时约 125 KB。离散数学实验题的全集规模通常落在这个范围内位图几乎无脑可用。超过亿级时建议换哈希因为位图变成稀疏的全 0 大数组空间浪费严重。C 里有两个位图选择std::bitset 的 N 必须编译期常量全集大小若从输入文件读入就没法用vector 自己管理则可以在运行期决定长度这是我在大多数情况下的选择。C 语言没有标准 bitset用 unsigned long 数组也能实现同样逻辑只是封装要自己写。2.3 哈希集合全集不明或元素非整数时的兜底当全集规模不确定、元素是字符串、或者全集范围大而元素很稀疏时连续编号假设不成立此时用 std::set 或 std::unordered_set 最省事。前者基于红黑树保证有序并交差可以线性归并后者基于哈希表单个成员判断平均 O(1)。纯 C 语言没有标准库哈希表如果实验强制 C我会退回到“数组 排序去重”先读入全部元素快排后把相邻重复项去掉再用排序后的数组归并求交并差。这个思路在第 4 章解析输入时还会用到它比插入时逐个查重稳定得多。2.4 选型对照表表示方案存储结构并/交/差的代价空间适用条件数组int 数组O(n*m)紧凑数量小于 100教学演示位图vectorunsigned longO(N/64)随全集 N 线性全集连续且有限本实验首选哈希集合set / unordered_setO(n log m) 或均摊 O(nm)随元素个数增长元素非整数或全集不明这张表可以直接搬进实验报告“数据结构的选择”一节评审看到的是决策过程不只是最终代码。第三行和第一行的差别在于数组方案在元素很多时仍要逐个比较哈希或排序方案把代价压到线性或对数级别。3. 用 C 位图实现并、交、差、对称差与补集实验题允许选 C 或 C我通常建议选 C理由是位图可以用 vector 自动管理内存还有 std::set 兜底元素不连续的情况。这章先给一个能直接编译的位图集合类再给一个 std::set 版本覆盖两种最常见的题目设定。3.1 位图集合类用 vectorunsigned long 代替 vectorboolstd::vectorbool 是标准库特化元素不是真正的 bool而是代理对象直接取地址或引用会出问题。我一般用 vectorunsigned long每个元素管 64 个位语义清晰也没有代理坑。#include cstdint #include vector class BitSet { public: explicit BitSet(uint64_t universeSize) : size_(universeSize), bits_((universeSize 63) / 64, 0) {} void insert(uint64_t x) { if (x size_) return; // 全集外元素直接忽略 bits_[x / 64] | (1ULL (x % 64)); } void remove(uint64_t x) { if (x size_) return; bits_[x / 64] ~(1ULL (x % 64)); } bool contains(uint64_t x) const { if (x size_) return false; return (bits_[x / 64] (x % 64)) 1ULL; } private: uint64_t size_; std::vectoruint64_t bits_; };代码说明构造函数的参数 universeSize 是全集元素个数不是分配的字数。bits_ 所需字数是 (universeSize 63) / 64全集大小 64 时只需要 1 个字。insert 和 remove 都要先做 x size_ 的边界判断位图越界写会直接破坏 vector 的内存布局这个检查不能省。contains 的返回值只有 0 或 1可以直接当 bool 用。参数说明1ULL (x % 64)是 unsigned long long 的左移x % 64 在 0..63 之间不会发生位移越界。全集大小与字数的关系容易写反提交前最好在这里打印一遍 bits_.size() 确认符合预期。3.2 四个运算的位运算映射位图上并、交、差、对称差分别对应或、与、与非、异或。先把映射表列出来后面代码逐行对应。集合运算位运算表达式说明A∪Ba | b任一集合中出现即成立A∩Ba b两个集合都出现A−Ba ~bA 出现且 B 不出现AΔBa ^ b恰好出现在一个集合中~A补集~a尾字要掩码全集 U 减去 ABitSet setUnion(const BitSet other) const { BitSet r(size_); for (size_t i 0; i bits_.size(); i) r.bits_[i] bits_[i] | other.bits_[i]; return r; } BitSet setIntersect(const BitSet other) const { BitSet r(size_); for (size_t i 0; i bits_.size(); i) r.bits_[i] bits_[i] other.bits_[i]; return r; } BitSet setDifference(const BitSet other) const { BitSet r(size_); for (size_t i 0; i bits_.size(); i) r.bits_[i] bits_[i] ~other.bits_[i]; return r; } BitSet setSymmetricDifference(const BitSet other) const { BitSet r(size_); for (size_t i 0; i bits_.size(); i) r.bits_[i] bits_[i] ^ other.bits_[i]; return r; }四个函数都按字遍历每一行处理 64 个元素循环次数最多是全集大小除以 64。差集的表达式 a ~b 要注意优先级~ 的优先级高于 所以是先取反再与符合集合差的定义。对称差的名字容易和交集混淆异或的结果是两边都为 1 的位置清零恰好是“一个在 A 一个在 B”。四个函数都假设 this 和 other 的全集一致我会在函数入口加一行断言assert(size_ other.size_)不一致时最快暴露问题。3.3 补集必须处理尾字掩码补集是离散数学实验里错误率最高的操作。A 的补集定义为 U−A位图上就是每个字按位取反但要处理最后一个字多出来的高位。BitSet complement() const { BitSet r(size_); for (size_t i 0; i bits_.size(); i) r.bits_[i] ~bits_[i]; int tailBits size_ % 64; if (tailBits ! 0) r.bits_.back() (1ULL tailBits) - 1; return r; }当全集大小不是 64 的倍数时最后一个 unsigned long 的高位不属于全集范围直接取反后会被错误当成集合元素。掩码计算方式tailBits 表示最后一个字还有多少个有效位(1ULL tailBits) - 1生成 tailBits 个连续的 1。例如全集大小 100tailBits 为 36掩码就是低 36 位为 1。这一步漏掉补集会凭空多出全集之外的元素验证环节必然报错。3.4 元素不连续时改用 std::set 的版本若实验题不允许“元素必须是连续整数”的假设用 std::set 写并交差更直观。std::set 默认有序标准库 algorithm 提供 set_union 等泛型算法五个参数分别是两个有序序列的首尾和输出迭代器。#include set #include algorithm #include iterator using IntSet std::setint; IntSet setUnion(const IntSet a, const IntSet b) { IntSet r; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(r, r.begin())); return r; } IntSet setIntersect(const IntSet a, const IntSet b) { IntSet r; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(r, r.begin())); return r; }std::inserter 每次插入都走红黑树总代价 O((nm) log(nm))。离散数学实验的数据量下不必再优化。这个版本的最大优点是不需要全集参数缺点是补集没法单独定义只能靠外部传入全集 U 后调用 setDifference。报告里选这个方案时要把全集 U 单独保存在一个变量里并解释补集依赖全集这件事。4. 实验报告落地的输入输出、文件读写与边界排错程序能跑只是第一步实验报告要贴测试数据和结果截图输出格式必须稳定。这章讲怎么设计输入输出怎么用文件重定向做批量验证再集中说三处最容易扣分的地方。4.1 输入解析命令行参数加文件读入两套方案小数据集用命令行参数最直观程序启动参数就是输入截图时一眼能对上是哪一组数据。例如./setops 1,2,3 2,3,4两个集合各占一个参数。分隔符统一用逗号因为逗号不会出现在数字里避免空格在 shell 中被拆开。C 语言解析逗号分隔字符串常用 strtok注意它会修改原字符串需要先复制一份再切。void parseSet(const char* text, int* set, int* len) { char buf[1024]; strcpy(buf, text); char* token strtok(buf, , ); *len 0; while (token *len 1024) { set[(*len)] atoi(token); token strtok(NULL, , ); } }strtok 的分隔符写成 , 会同时按逗号和空格切分容错更好。atoi 对非数字返回 0输入混入字母时要先人工检查测试数据。解析后的数组可能有重复元素我倾向于统一排序去重而不是插入时逐个查重后者在数组版本里会退化成双重循环前者一次快排就解决。数据量大时换 C 的 ifstream 和 stringstream逻辑一样。若实验明确要求展示文件读写操作输入文件用 fopen/fscanf 或 ifstream 读取报告截图里能看到完整流程。4.2 输出格式对齐实验报告的“运算结果”一栏输出至少包含集合 A、B、并、交、差、对称差和补集字段名用纯英文单词避免终端编码不一致导致报告截图乱码。空集合必须打印{ }而不是空行否则报告里看不出是空集还是漏输出。U { 0 1 2 3 4 5 } A { 1 3 5 } B { 0 2 4 } union { 0 1 2 3 4 5 } intersection { } A-B { 1 3 5 } B-A { 0 2 4 } xor { 0 1 2 3 4 5 } complement(A) { 0 2 4 }输出字段对应集合运算注意事项unionA∪B单词避免终端编码问题intersectionA∩B空集打印 { }A-B差集 A−B明确方向A-B 与 B-A 不同xor对称差 AΔB报告中说明 xor 表示 Δcomplement(A)补集 ~A依赖全集 U实验报告要求写“对称差”时建议输出字段用 xor并在正文说明其含义是 Δ这样不会因为 Unicode 符号在不同平台渲染不一致而出现问题。输出时按自然升序遍历集合位图版本从小到大扫描 contains 即可保证顺序稳定评审对照起来更舒服。4.3 文件重定向一键回归验证不管程序用 scanf 还是 cin最省事的测试方式都是文件重定向不改代码就能批量跑。gcc setops.c -o setops ./setops test1.txt result1.txttest1.txt 按行组织测试用例第一行全集大小之后每行一个集合。重定向的好处是提交实验代码时不必带测试数据程序源文件保持干净测试脚本单独留给评审。改动算法后重跑一遍命令再用 diff 对比新旧结果就能发现回归。用 vscode 调试时直接在 bits_ 数组上下断点位图按位运算的结果可以逐字查看比打印中间变量更直观。4.4 三个边界坑实验报告这里最容易被扣分4.4.1 全集未定义补集无从谈起很多学生会把全集写死在 main 函数里。评审换一组数据时程序要么越界要么补集结果错。我一般会把全集大小作为第一个输入参数或者放在输入文件首行避免“全集成为了代码的一部分”。报告中要单独写一句“本实验全集 U 默认为 {0,1,…,N−1}”这是离散数学期末复习时也会反复强调的前提。4.4.2 输入元素越界输入出现大于等于全集大小的数字属于测试数据错误。直接报错会中断整个实验流程忽略会产生静默错误。我更倾向丢弃并打印警告提示“x 不在全集范围内”让剩余测试继续跑。位图 insert 里已经把越界 return 掉了解析层再加一层警告即可。4.4.3 空集与重复元素空集与任何集合的交是空集并是对方本身差保持自身。位图版本循环自动处理不需要特判但报告里建议把空集单独列一个测试用例。重复元素由解析去重解决小数据集用冒泡排序不影响性能代码还短放在实验报告里反而好讲清楚“集合元素互异”是怎么落到代码里的。5. 幂集、笛卡尔积与德摩根律的自动验证只交并差报告内容显得单薄。加两个扩展点即可提高完成度幂集枚举和德摩根律自动验证。5.1 用位向量枚举幂集n 个元素的集合子集总数 2^n。每个子集用 n 位掩码表示第 i 位为 1 表示元素被选中。掩码从 0 遍历到 2^n−1就枚举完全部子集。void printPowerSet(const IntSet s) { std::vectorint elems(s.begin(), s.end()); size_t n elems.size(); for (size_t mask 0; mask (1ULL n); mask) { std::cout { ; for (size_t i 0; i n; i) if (mask (1ULL i)) std::cout elems[i] ; std::cout }\n; } }elems 把 set 转成带下标的数组mask 是外层循环变量。(1ULL n)在 n 不小于 64 时行为未定义所以集合元素个数要控制在 60 以内2^60 个输出也不现实。报告里计算 2^n 建议单独写循环或函数避免直接调用 pow 带来的浮点精度问题。掩码枚举和位图集合是同一套思想用二进制位表示元素是否存在。写报告时把这两处“位向量”用法放在一起讲比单独贴代码更有说服力。5.2 用德摩根律做自动验证结果分析部分与其写“经检验正确”不如让程序自己证明一次。德摩根律的一种形式是 ~(A∪B) 与 ~A∩~B 相等。需要给 BitSet 重载 operator。// 加在 BitSet 类内 bool operator(const BitSet other) const { return size_ other.size_ bits_ other.bits_; } bool checkDeMorgan(const BitSet A, const BitSet B) { BitSet lhs A.setUnion(B).complement(); BitSet rhs A.complement().setIntersect(B.complement()); return lhs rhs; }这里用链式调用组合前面的运算。如果返回 false排查顺序分三步先确认两个 BitSet 的 size_ 完全一致再看 complement 里的尾字掩码是否写对多出来的高位会把两个集合的某些位同时改成 1比较永远不相等最后确认 A 和 B 的元素都在全集内。整个验证放在测试主函数里循环跑完全部用例后输出一行 “de morgan: ok”实验报告直接引用这个结论。若题目还要求笛卡尔积最基础就是双层循环生成有序对注意 A×B 与 B×A 一般不相等输出顺序对的方向要和教材定义保持一致。本文还有配套的精品资源点击获取