简介集合的交、并、差运算是数据结构与算法学习中的重要基础。围绕实验一集合交并差这份资源提供了完整的编码实现与配套讲解适合正在学习数据结构、需要完成课程实验或准备考试的软件工程及相关专业高校学生。压缩包共8个文件包括3个C源程序、3个头文件、1份PPT课件和1份Word实验报告整体大小8.74MB已有314人学习下载。源码定义了集合类型与初始化、添加、判断等辅助操作并实现了交集、并集、差集核心函数通过数组、链表或哈希表等不同存储方式完成集合运算同时配有结果验证与输出便于比较不同实现下的时间复杂度差异。PPT从集合基本概念、伪代码到运行截图逐步展开实验报告则提供详细操作记录与结果分析可作为报告撰写参考。1. 集合交并差实验三个运算背后是容器选型与边界意识两份名单一份是本月活跃用户一份是 VIP 用户。找“又活跃又是 VIP”的人是交集找“活跃但不是 VIP”的人是差集把两份名单合并去重是并集。“实验一集合交并差”这个资源包就是把这三件事做成一个正经的数据结构实验你的任务不只是让结果算对还要把容器选对、把重复元素处理掉、把空集和边界用例稳住。适合正在跟课程实验的初学者也适合工作中要维护标签系统、权限合并、数据去重逻辑的开发者。这一篇按我习惯的做法来写先定数据结构再写三个运算最后讲怎么验证和踩坑。2. 先选好数据容器四种方案的复杂度账与接口设计集合运算的定义不用多说真正决定代码量和运行效率的是“集合怎么存”。选错容器等数据量一大本来三行能写完的运算会慢到让人怀疑是机器问题。这一章先把复杂度账算清楚再给选型建议最后把接口固定下来。2.1 三个运算的时间复杂度由查找决定集合的语义有两条硬要求元素互异、无序。落到代码上所有运算都依赖一个底层操作——判断“某个元素是否在集合里”。顺序表和链表的查找都是 O(n)所以并集把 A 全部放入结果再逐个把 B 的元素放进结果放进前先查重。A、B 长度分别为 m、n整体 O(m*n)。交集遍历较短集合的每个元素去较长的集合里查存在性。最坏仍是 O(m*n)。差集遍历 A 的每个元素去 B 里查不存在才加入。O(m*n)。当 m、n 到一万这个量级O(m*n) 就是一亿次比较课程实验规模下机器还能扛换成十万量级就明显卡顿。这也是为什么实验报告里必须写清楚复杂度老师看的不是你能不能跑而是你有没有意识到这个差异。另一个思路是先排序再双指针。两个集合各自排序后并、交、差都能用双指针一趟做完降到 O(mn)代价是排序的 O(n log n)。这个优化方向适合做完整后加分但对实验课来说“顺序表 线性查找”是更容易和复杂度分析对应的版本。先把基础版写对再谈优化。2.2 四种容器对比从“能跑”到“优雅”容器方案查找插入并集交集差集适用场景顺序表O(n)末尾 O(1)O(m*n)O(m*n)O(m*n)数据量小实验课首选链表O(n)头插 O(1)O(m*n)O(m*n)O(m*n)需要频繁删除、不要求随机访问位图O(1)O(1)按位或按位与按位与非整数且取值区间有限哈希表平均 O(1)平均 O(1)O(mn) 平均O(mn) 平均O(mn) 平均通用场景、字符串元素顺序表的优势是直观一个数组加一个长度插入时线性查重代码十几行就能写完复杂度分析也最好写。链表看起来灵活但“查重”本质还是 O(n)还会把代码写长对这三个运算没有收益。位图是个容易被忽略的亮点方案。假设元素都是 0~1023 的整数开一个 1024 位的数组判断存在就是读一个 bit三个运算直接变成位运算// 假设 a、b、r 都是 16 个 unsigned long 组成的位图数组 // 每个 unsigned long 恰好覆盖 64 个整数 // 并集 for (int i 0; i 16; i) r[i] a[i] | b[i]; // 交集 for (int i 0; i 16; i) r[i] a[i] b[i]; // 差集 for (int i 0; i 16; i) r[i] a[i] ~b[i];位图三个运算都是严格 O(mn)而且这个“mn”其实是遍历整个取值区间的固定开销与集合实际元素个数无关。代价是空间随取值区间线性增长元素是 0~1 亿的整数就得开约 12.5MB 的位图内存立刻紧张。所以位图只适合区间小、已知、密集的整数集合。哈希表是通用场景的最优解平均 O(1) 的查找让三个运算都做到线性。课程实验里如果用 C 手写哈希表代码量会明显超出“实验一”的体量但如果你用的是自带哈希集合的语言直接拿来用就好不要在实验里重复造轮子。我的选型建议很直接课程实验数据量小顺序表够用代码量少复杂度好写想在报告里加分就额外做一组数据量稍大的测试对比顺序表和位图的耗时说明你理解差异在哪里。工作场景则直接上哈希集合没有第二个选择。2.3 先定接口再定实现不管选哪种容器三个运算的对外接口应该一致。我习惯先把接口写在头文件里实现细节全部关在函数内部#ifndef SET_H #define SET_H typedef struct { int *data; int length; int capacity; } Set; Set *set_create(int capacity); void set_destroy(Set *s); int set_contains(const Set *s, int value); int set_insert(Set *s, int value); void set_print(const Set *s, const char *name); Set *set_union(const Set *a, const Set *b); Set *set_intersect(const Set *a, const Set *b); Set *set_difference(const Set *a, const Set *b); #endif接口定下来之后主函数无论怎么换实现都不用改。这也是一个工程习惯把“操作”和“容器”解耦。实验报告里写一句“接口与实现分离便于替换底层数据结构”通常能加分。三个运算函数的参数顺序也有讲究。先 a 后 b差集固定表达 A-B这样调用时不会把方向写反。第 4 章的避坑记录里有一条专门讲这个先记下。3. 用顺序表实现交并差C 语言核心代码与参数说明顺序表方案里集合就是一个动态数组加一个长度计数器。这一章把完整可编译的代码拆成四段讲基础操作、并集、交集差集、主函数与验证脚本。每一段都写清楚参数含义和改参数的影响。3.1 结构体与基础操作扩容、插入、查找#include stdio.h #include stdlib.h #include set.h Set *set_create(int capacity) { Set *s (Set *)malloc(sizeof(Set)); if (capacity 0) capacity 1; s-data (int *)malloc(sizeof(int) * capacity); s-length 0; s-capacity capacity; return s; } void set_destroy(Set *s) { if (s) { free(s-data); free(s); } } int set_contains(const Set *s, int value) { for (int i 0; i s-length; i) { if (s-data[i] value) return 1; } return 0; } int set_insert(Set *s, int value) { if (set_contains(s, value)) return 0; if (s-length s-capacity) { int new_capacity s-capacity * 2; int *new_data (int *)realloc(s-data, sizeof(int) * new_capacity); if (new_data NULL) return -1; s-data new_data; s-capacity new_capacity; } s-data[s-length] value; return 1; } void set_print(const Set *s, const char *name) { printf(%s:, name); for (int i 0; i s-length; i) { printf( %d, s-data[i]); } printf(\n); }几个参数和边界条件单独说。capacity 是初始容量传入 0 或负数会被修正为 1。原因是 C 标准里 malloc(0) 的行为是实现相关的有的平台返回 NULL 导致后续插入直接失败这两行修正就能把不确定因素消掉。初始容量给 4 还是给 100 都不影响正确性只影响扩容次数实验数据量下看不出差别。扩容倍数选 2 是个惯例每次装满就把容量翻倍n 次插入的总代价是 O(n)单次插入均摊 O(1)。如果改成固定增量比如每次只加 10插入 n 个元素的代价会退化到 O(n^2)数据量大时会突然卡死。set_insert 的返回值约定0 表示元素已存在、未插入1 表示插入成功-1 表示 realloc 失败。调用方不检查这个返回值在正常情况下没问题但你要知道它有这层含义。注意 realloc 的用法返回值必须先用临时变量接住判空之后再赋给 s-data。如果直接s-data realloc(...)一旦内存分配失败原来的指针就丢了后续 free 会变成对非法地址的操作。set_create 里的两次 malloc 也没有判空实验代码可以接受真实项目里至少应该返回 NULL 并让调用方处理。还有一个常见误用有人把 Set 当普通数组用插入前不查重最后并集里全是重复值。set_contains 这一步看起来多余但它才是“集合”语义的保证。课程实验的数据往往恰好没有重复掩盖了这个问题换成随机数据立刻暴露。3.2 并集实现把查重交给 set_insertSet *set_union(const Set *a, const Set *b) { Set *r set_create(a-length b-length); for (int i 0; i a-length; i) { set_insert(r, a-data[i]); } for (int i 0; i b-length; i) { set_insert(r, b-data[i]); } return r; }这段代码的要点是结果集初始容量给a-length b-length。这是并集元素数量的最大值给满之后整个并集过程不会触发扩容省掉不必要的 realloc。逻辑上先放 A 的全部元素再逐个放 B 的元素B 里跟 A 重复的元素会被 set_insert 里的 set_contains 拦住返回 0 但不影响结果。输出顺序是插入顺序不是排序后的顺序。实验讲义如果要求结果按升序输出就在返回前对 data[0..length-1] 做一次排序常见做法是 qsort。排序不改变集合本身只改变打印顺序很多同学在这里纠结其实一行 qsort 就能解决。提示qsort 需要自己写比较函数。比较 int 的最稳写法是判断大小后返回 -1/0/1不要用*(int *)a - *(int *)b当返回值两个大整数相减可能溢出边界数据下会出奇怪结果。3.3 交集与差集实现遍历次序影响常数交集的小优化是遍历短的集合。两个集合长度 m、n外层循环次数取 min(m,n)每次内层查找 O(max(m,n))。最坏复杂度还是 O(m*n)但常数项小一圈尤其在一个集合远小于另一个时效果明显。Set *set_intersect(const Set *a, const Set *b) { const Set *small a-length b-length ? a : b; const Set *large a-length b-length ? b : a; Set *r set_create(small-length); for (int i 0; i small-length; i) { if (set_contains(large, small-data[i])) { set_insert(r, small-data[i]); } } return r; }结果集容量给 small-length因为交集元素不可能超过更小的那个集合这个上界比a-length b-length更紧同样是为了避免扩容。代码里 small 和 large 加了 const 修饰表示这里只读不写养成这个习惯能避免不少误操作。差集的实现思路完全对称但方向要盯死Set *set_difference(const Set *a, const Set *b) { Set *r set_create(a-length); for (int i 0; i a-length; i) { if (!set_contains(b, a-data[i])) { set_insert(r, a-data[i]); } } return r; }set_difference(a, b) 表达的是“A 有而 B 没有”。想表达相反方向就调用 set_difference(b, a)。差集不对称测试时如果发现结果集合里全是 B 的元素基本就是调用时把参数顺序写反了。3.4 主函数与差分验证脚本主函数从 stdin 读入两个集合输出三个结果这样方便后面的 Python 脚本做自动化验证int main(void) { int n, m; scanf(%d, n); Set *a set_create(n); for (int i 0; i n; i) { int v; scanf(%d, v); set_insert(a, v); } scanf(%d, m); Set *b set_create(m); for (int i 0; i m; i) { int v; scanf(%d, v); set_insert(b, v); } Set *u set_union(a, b); Set *it set_intersect(a, b); Set *d set_difference(a, b); set_print(u, U); set_print(it, I); set_print(d, D); set_destroy(a); set_destroy(b); set_destroy(u); set_destroy(it); set_destroy(d); return 0; }输入格式是第一行一个整数表示 A 的元素个数第二行 A 的元素第三行一个整数表示 B 的元素个数第四行 B 的元素。这种格式比命令行参数更灵活数据量大了也不会撞系统的参数长度限制。scanf 的返回值这里没有检查实验代码从简真实代码里至少应该判断是不是读到了 1 个整数。差集方向在 main 里产生的输出 D 就是 A-B。如果你把最后一个调用改成 set_difference(b, a)打印名字不变程序输出就变成了反方向人工看不出来但差分验证立刻能抓出来。这就是自动化的价值。Python 脚本负责生成随机数据、调用程序、比对结果import random import subprocess import sys def build_input(a, b): lines [ str(len(a)), .join(map(str, a)), str(len(b)), .join(map(str, b)), ] return \n.join(lines) def run_c(a, b): p subprocess.run( [./set_demo], inputbuild_input(a, b), capture_outputTrue, textTrue, timeout5 ) if p.returncode ! 0: raise RuntimeError(p.stderr) out {} for line in p.stdout.strip().splitlines(): name, _, values line.partition(:) out[name] set(int(x) for x in values.split()) return out def main(): random.seed(2024) for t in range(500): a set(random.sample(range(0, 100), random.randint(0, 40))) b set(random.sample(range(0, 100), random.randint(0, 40))) got run_c(a, b) expected {U: a | b, I: a b, D: a - b} for key in expected: if got[key] ! expected[key]: print(f第 {t} 组不一致键 {key}) print(A , sorted(a)) print(B , sorted(b)) print(期望 , sorted(expected[key])) print(实际 , sorted(got[key])) sys.exit(1) print(500 组随机数据全部通过) if __name__ __main__: main()脚本里的 random.seed(2024) 固定随机种子每次跑出来的测试集完全一样这保证了“改了一行代码后重跑”是在同一批数据上对比。集合规模从 0 到 40、元素取值范围 0 到 99覆盖了空集、单元素、满集、大重叠、互斥各种情况。比较前把 C 程序输出转成 set绕开元素顺序问题——C 输出顺序是插入序不是升序直接比较两个字符串会误报。4. 实验常见问题与避坑记录五个让集合结果翻车的细节这一章按现象、原因、解决三个方面写。这些坑我都见过有一个还是我自己调了一晚上才定位的玄学问题最后发现和代码逻辑没关系纯粹是边界数据没测。4.1 并集结果出现重复元素现象A{1,2,3}B{2,3,4}并集输出的顺序是 1 2 3 2 3 4而不是 1 2 3 4。原因set_insert 没做唯一性检查或者写并集时直接循环把 b-data 全部写进结果没有经过 set_insert。这种情况多发生在“先写一个 append 函数再套到并集里”的代码结构上append 只管追加不管查重。解决插入必须走 set_insert。如果已经写了一个“追加”函数把它改成调用 set_insert或者在 append 里先 set_contains 再追加。并集里不要手写“把 B 的元素拼进结果”的循环查重逻辑和插入逻辑合在一起才可靠。4.2 差集方向被搞反现象A{1,2,3}、B{3,4,5}想求“A 有而 B 没有”程序却输出 4 5一看就是 B-A 的结果。原因调用时把参数顺序写反了或者函数的代码里外层循环遍历的是 b 而不是 a。解决先在 main 里明确打印标签差集输出行写成 D并注释“D A - B”。测试数据要故意选 A、B 各有独有元素的非对称案例比如 A 独有 {1,2}、B 独有 {4,5}这种数据一旦方向反了立刻看得出来。对称数据比如两个集合长度相等、各有一半重叠反而会掩盖方向错误。4.3 扩容后没更新 capacity 导致越界现象小数据量时一切正常数据量一大程序在插入某个值后崩溃或者 valgrind 报 invalid write。原因realloc 之后只更新了 s-data忘记更新 s-capacity。下次插入时 length 和 capacity 的关系不变继续触发扩容但 data 指向的新内存块容量记录已经过时后续写入越过了分配边界。解决扩容函数里 data 和 capacity 必须同时更新。顺序是先算 new_capacity再 realloc判空后一起赋值。写完后自查一遍代码里凡是出现s-data 的地方后面一定跟着s-capacity 的更新。4.4 只测“正常”数据边界用例全挂现象讲义给的测试数据能过自己造几组空集交空集、空集与任意集合、两个完全相同的集合、含负数和 0 的集合结果不对或程序直接崩。原因覆盖不足。空集场景会暴露出 set_create 对零容量的处理负数场景在检查下标或位图方案里会变成负数下标越界两个完全相同集合的交集应该等于集合本身差集应该是空集这条很多实现会栽跟头。解决不管实验讲义有没有要求至少准备五组边界用例A∅、B∅A∅、B 非空A 与 B 完全一致A 与 B 互斥元素含 0 和负数。把五组跑过再跑随机差分基本稳。4.5 全局变量导致多组测试相互污染现象第一个用例输出正确第二个用例的结果里混进第一个用例的残留元素。原因集合用全局变量声明每次测试前只清了一部分字段或者创建新集合时没有初始化 lengthlength 残留上一个用例的值后续插入写到数组末尾打印时把旧数据也带了出来。解决集合结构体在创建时把 length 置 0、capacity 按参数赋值。每个测试用例用 set_create 新建、用完 set_destroy保持成对。不要写一个全局 Set 反复用除非测试数据确实只有一组。5. 把差分验证养成习惯随机数据黑盒测试你的集合实现差分验证的思路是用一个绝对可信的参考实现Python 内置 set和被测实现C 程序在同一批随机输入上对跑输出不一致就说明被测实现有 bug。这个思路不限于集合实验任何有标准库可对照的算法题都适用。我现在的习惯是改完代码先跑一遍第 3 章的 Python 脚本500 组数据全过再交。这个习惯救过我一次。某次我把差集写成了“对称差”就是两边独有的元素都输出。用讲义上的用例测结果看起来完全正常——那组数据恰好 A、B 各有相同数量的独有元素且没有公共元素时对称差和差集输出长得一样。随机差分一跑500 组里崩了 12 组每条都明确打印出输入、期望、实际定位只花了十分钟。如果没有差分脚本这种 bug 靠肉眼几乎不可能发现因为人工能看的样例太少了。参数上有几个值得注意的点。随机种子必须固定它保证可复现今天跑挂了第 37 组明天修完代码重跑挂的还是第 37 组可以直接对比。集合规模和元素取值范围要留成变量range(0, 100) 加随机长度 0~40让 A、B 之间大概率有重叠但也会出现空集、单元素、完全互斥的情况覆盖面比手写测试数据好得多。想加强边界覆盖把取值范围改成 0~10 再跑一轮重复率会显著上升重叠和完全一致的样本更多。这套东西放进实验包后提交前跑一遍比肉眼检查可靠得多。它同时也是一种通用工程习惯凡是手工验证只能覆盖个位数例子的逻辑都值得配一个差分脚本。希望帮到你。本文还有配套的精品资源点击获取