集合交并差实验：C语言数据结构选型与复杂度分析

简介：集合的交、并、差运算是数据结构与算法学习中的重要基础。围绕'实验一集合交并差'，这份资源提供了完整的编码实现与配套讲解，适合正在学习数据结构、需要完成课程实验或准备考试的软件工程及相关专业高校学生。压缩包共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(m+n)，代价是排序的 O(n log n)。这个优化方向适合做完整后加分，但对实验课来说，“顺序表 + 线性查找”是更容易和复杂度分析对应的版本。先把基础版写对，再谈优化。

2.2 四种容器对比：从“能跑”到“优雅”

顺序表的优势是直观：一个数组加一个长度，插入时线性查重，代码十几行就能写完，复杂度分析也最好写。链表看起来灵活，但“查重”本质还是 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(m+n)，而且这个“m+n”其实是遍历整个取值区间的固定开销，与集合实际元素个数无关。代价是空间随取值区间线性增长：元素是 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_insert

Set *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"], input=build_input(a, b), capture_output=True, text=True, timeout=5 ) 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 全局变量导致多组测试相互污染

现象：第一个用例输出正确，第二个用例的结果里混进第一个用例的残留元素。

原因：集合用全局变量声明，每次测试前只清了一部分字段，或者创建新集合时没有初始化 length，length 残留上一个用例的值，后续插入写到数组末尾，打印时把旧数据也带了出来。

解决：集合结构体在创建时把 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 再跑一轮，重复率会显著上升，重叠和完全一致的样本更多。

这套东西放进实验包后，提交前跑一遍，比肉眼检查可靠得多。它同时也是一种通用工程习惯：凡是手工验证只能覆盖个位数例子的逻辑，都值得配一个差分脚本。希望帮到你。

本文还有配套的精品资源，点击获取