刚拿到《数据结构》的第一个实验“集合的交、并、差”时不少人会觉得这是道送分题交集、并集、差集初中数学就学过的概念用 C 语言写出来还不容易但真正坐到电脑前把“从键盘输入两个集合”“去重”“排序”“输出结果”这几个环节串起来才发现事情比想象中麻烦得多。这个实验表面是在复习集合运算实际上是在逼你回答一个核心问题一个抽象的数学对象在内存里应该长成什么样这也是数据结构这门课和“会写几段 C 代码”之间的分水岭。这篇文章我按自己做实验的完整过程来写从数学定义、存储结构选型到双指针算法、边界测试再到报告写法全部拆开讲清楚适合正在做这份实验、或者在准备数据结构考试的同学直接参考。1. 这个实验到底在考什么从数学集合到内存里的数据结构1.1 数学定义和程序表达之间隔着三道坎先回到高等数学里的定义。设集合 A、B交集、并集、差集的数学描述是交集A∩B { x | x∈A 且 x∈B }并集A∪B { x | x∈A 或 x∈B }差集A−B { x | x∈A 且 x∉B }数学里“集合”是一个理想化的概念元素可以无限多元素类型可以是数、点、函数。但程序世界里没有这种“理想化”的东西键盘输入进来的一定是有限个数值而且它们的排列顺序取决于用户怎么敲键盘。于是从数学定义到程序表达中间至少隔着三道坎。第一道坎是互异性。数学上的集合天然不允许重复元素但用户输入时完全可能敲出 1、2、2、1。从数学角度看这就是集合 {1,2}但程序如果原样存储后面求交并差时会把重复元素也输出一遍结果就错了。所以程序必须自己承担“去重”的工作。第二道坎是无序性。数学里集合不讲究顺序{1,2,3} 和 {3,2,1} 是同一个集合。但 C 语言数组是有下标的程序读进来的数据天然保留“输入顺序”。如果不做任何处理两个集合的比较就只能靠两层循环暴力扫描效率很低。如何把无序变成有序是这次实验最重要的思维转变。第三道坎是规模不固定。数学里集合的规模没有上限但 C 语言里数组长度在定义时就得确定。这意味着程序最好使用动态内存分配或者至少用一个容量较大的结构体来管理集合大小而不是写死int a[100]就完事。这三道坎总结成一句话所谓数据结构实验就是让你在某个具体的物理存储结构上实现一个抽象的逻辑模型。集合是抽象模型顺序表或链表是物理实现你的任务就是把两者对齐。1.2 实验指导书没写明白的隐性要求实验指导书上通常只有一句话输入集合 A 和 B输出交集、并集、差集。但真正动手时你会遇到几个它没写明的问题。第一输入时是否要先输入元素个数还是直接输入一串数这个不约定好程序就没法判断什么时候输入结束。我建议采用“先输入个数再输入每个元素”的方式这样代码结构最清晰也方便后续测试。第二输出格式是按集合的数学书写习惯来还是按平台的输出规范来数学上一般写成 {1,2,3}但很多实验平台要求空格分隔。这些细节会影响成绩也值得在写代码前确认。第三实验报告里要求体现数据结构设计。所谓“设计”是指你要说明白为什么选顺序表而不选链表、为什么选排序加双指针而不选暴力循环而不是简单贴一段代码。这一步恰恰是许多初学者最容易忽略、也最拉分的部分。2. 存储结构选型为什么我选了有序顺序表而不是链表或位图2.1 四种候选方案的基本盘对比在处理两个整数集合的交并差时常见的物理存储方案有四种无序数组、有序顺序表、链表、位图。它们各有性格我先列个总表。存储方案内存形式求交/并/差的直观思路优点缺点适用场景无序数组连续内存两层循环逐个比较实现最简单时间复杂度 O(m*n)数据量一大就崩很小的集合、临时演示有序顺序表连续内存排序后双指针归并O(mn)逻辑清晰好调试插入和删除需要移动元素本实验首选也是多数教材前几章的标准场景链表不连续内存两个链表逐个节点比对插入删除灵活指针操作繁琐无法随机访问调试成本高元素频繁增删、作业要求用链表位图连续 bool 数组用下标直接标记元素是否存在单次查找 O(1)代码极短空间受元素取值范围限制值域大就爆元素值域小而确定比如 0~100 或 0~10002.2 选有序顺序表的三个决定性理由我最后选了“有序顺序表”也就是先用数组存下所有输入然后排序、去重让集合在内部始终维持升序。理由有三个。第一调试体验天差地别。数组带下标任何时候都可以打印出来看中间状态排序排得对不对、去重有没有出错一眼就能发现。链表就不一样了指针一旦指错就是段错误对初学者来说排查成本很高。第二能自然衔接教材内容。严蔚敏版《数据结构》最早引入的存储结构就是顺序表这个实验通常安排在链表之前。用顺序表做正好把课程里的“线性表”知识用起来也和老师课堂节奏一致。第三性能完全够用而且能体现出算法设计的价值。排序用 C 标准库的qsort是 O(n log n)之后双指针求交并差是 O(mn)。一共几万个数毫无压力。这个“排序双指针”的组合拳后面学归并排序、有序表合并、甚至刷算法题时都会反复遇到早用早受益。2.3 用结构体把“集合”立成一个独立类型我没有直接定义裸数组而是定义了一个 Set 结构体。typedef struct { int *data; // 指向动态分配的数组 int length; // 当前元素个数 int capacity; // 已分配容量 } Set;这样做的第一个好处是语义清晰。所有函数签名都写成Set *读代码的时候就是“两个集合做并集”而不是“两个数组加两个长度”可读性完全不一样。第二个好处是内存管理集中化。创建集合用createSet销毁用destroySet谁也不会忘记 free。第三个好处是抽象隔离。如果哪天你想把底层换成链表只要保持Set *这个类型不变运算函数的调用方式基本不用改。这就是抽象数据类型ADT的基本思想。3. 核心算法三类运算的统一解法是“归并式双指针”3.1 为什么“有序”是这一切的前提两个无序数组求交最笨的办法是对 A 的每个元素去 B 里查一遍这就是 O(m*n)。如果 mn10 万要执行 100 亿次比较程序基本等于卡死。但排序之后问题性质完全变了。A {1,3,5,7,9}B {2,3,5,8}我只需要让两个指针 i、j 从头开始谁小谁往前走相等就记录。整个过程每个元素最多被扫描一次复杂度降到 O(mn)。这个方法就是从归并排序里提炼出来的“归并式双指针”本质上就是合并两个有序序列的变体。交集、并集、差集三个操作都建立在这套双指针逻辑上。3.2 求并集合并两个有序序列并去重Set unionSet(Set *a, Set *b) { Set res createSet(a-length b-length); int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { res.data[res.length] a-data[i]; } else if (a-data[i] b-data[j]) { res.data[res.length] b-data[j]; } else { res.data[res.length] a-data[i]; j; } } while (i a-length) res.data[res.length] a-data[i]; while (j b-length) res.data[res.length] b-data[j]; return res; }并集的关键在于“相等只拷贝一次”。因为两个集合已经各自去重当 A[i] B[j] 时这个元素只需进结果一次然后把两个指针都往后推。否则并集里就会出现同一个元素出现两次的情况。并集的容量可以直接申请 a-length b-length因为最坏情况是两个集合完全没有交集并集刚好等于两个集合的拼接。容量多申请一点没问题反正 length 会控制在真实元素个数。3.3 求交集相等才记录不相等就推小指针Set intersectSet(Set *a, Set *b) { int cap a-length b-length ? a-length : b-length; Set res createSet(cap); int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { i; } else if (a-data[i] b-data[j]) { j; } else { res.data[res.length] a-data[i]; i; j; } } return res; }交集比并集简单因为只有两边相等时才需要记录。A[i] B[j] 说明 A[i] 比 B 当前元素小它不可能在 B 后面的更大元素里出现直接让 i 前进反过来同理。这里有个细节创建结果集合时容量可以取a-length b-length ? a-length : b-length因为交集元素个数不可能超过较短的集合。虽然 malloc 多申请一点也无所谓但写出这个细节说明你真理解了集合运算的性质这是实验报告里值得写一笔的地方。3.4 求差集A 小要带走相等要舍弃B 小直接跳过Set differenceSet(Set *a, Set *b) { Set res createSet(a-length); int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { res.data[res.length] a-data[i]; } else if (a-data[i] b-data[j]) { j; } else { i; j; } } while (i a-length) res.data[res.length] a-data[i]; return res; }差集是最容易写错的一个。逻辑拆开来看A[i] B[j]A[i] 比 B 当前元素小而 B 后面只会更大所以 A[i] 不可能出现在 B 中把它加入结果i 前进。A[i] B[j]B[j] 在 A 中没有匹配跳过它j 前进。A[i] B[j]这个元素属于交集不属于差集两边一起舍弃i、j 都前进。循环结束后别忘了把 A 中剩余元素全部拷入结果。很多人漏掉这一行原因是只盯着 while 循环里的逻辑忘了处理“B 已经走完但 A 还有剩余”的情况。想一下B 指针走到头说明 B 里再也没有能和 A 剩余元素相等的值了所以这些元素必然属于差集必须带走。3.5 排序去重实验里最容易翻车的前置步骤无论求交并差前置条件都是两个集合已经按升序排列且无重复。我用qsort排序再用相邻去重int cmpInt(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void sortAndDeduplicate(Set *s) { qsort(s-data, s-length, sizeof(int), cmpInt); int k 0; for (int i 0; i s-length; i) { if (k 0 || s-data[k - 1] ! s-data[i]) { s-data[k] s-data[i]; } } s-length k; }这里有个细节值得多说一句比较时用的是s-data[k-1]不是s-data[i-1]。因为 k 表示“已保留结果序列的末尾下标”而 i 是遍历原数组的下标。像序列 1 1 2 2 3当 i 扫到 2 的时候i-1 指向 1比较结果相等没毛病但当 i 扫到 3 时i-1 是 2比较结果也不相等看起来也行。真正会出问题的是连续多个重复项中间的情况用已保留序列的末尾元素去比较逻辑才无懈可击。这个细节我是在测试中反复输入重复数据后才注意到的属于“文档里不会写”的经典坑。4. 复杂度分析与试卷上会扣分的边界情形4.1 为什么说双指针把 O(m*n) 变成了 O(mn)按我上面的实现整个程序的复杂度分为三段输入和建表O(n)排序qsort平均 O(n log n)三种集合运算O(mn)这里的双指针复杂度值得仔细想一遍并集也好交集也好差集也好每次循环里要么 i 前进要么 j 前进要么两个都前进没有任何一个指针会回退。所以循环执行次数最多是 mn 量级。这跟两层循环的 O(m*n) 差距是数量级的不是快一倍两倍那么简单。如果 mn10 万暴力法要 100 亿次比较双指针只要 20 万次。这就是数据结构课程想让你体会的第一件重要事情物理结构和预处理方式直接决定算法能达到什么复杂度水平。4.2 必须处理的五类边界场景实验提交前我强烈建议至少测这五类输入场景A 输入B 输入正确结果普通情况1 2 3 4 53 4 5 6 7交 {3,4,5}并 {1,2,3,4,5,6,7}差 {1,2}完全不相交1 23 4交为空并 {1,2,3,4}差 {1,2}包含关系1 2 32交 {2}并 {1,2,3}差 {1,3}空集无1 2 3交为空并 {1,2,3}差为空重复且乱序1 2 2 3 13 3 2 4交 {2,3}并 {1,2,3,4}差 {1}空集尤其容易出问题程序里的length是 0打印函数要能输出{}而不是什么都不打印或者打印一个换行符。有的老师会要求空集也要输出花括号看清楚题目要求。另外一个老生常谈但每年都有人踩的坑是输出格式。如果要求集合元素之间用逗号加空格分隔就要控制好“最后一处不能有分隔符”的逻辑。评委平台常见的说法是“输出格式错误”其实不是算法错了是末尾多了一个空格或逗号。我的printSet用循环内判断if (i 0) printf(, );来解决这个问题属于既稳又简单的套路。5. 完整可运行代码与测试记录5.1 可直接编译运行的 C 语言实现把上面的函数组装起来就是一个完整的实验程序。我用gcc编译测试过运行逻辑是这样先提示输入集合元素个数然后依次读入元素程序自动排序去重最后输出 A、B、交集、并集、差集。#include stdio.h #include stdlib.h typedef struct { int *data; int length; int capacity; } Set; Set createSet(int capacity) { Set s; s.data (int *)malloc(sizeof(int) * capacity); s.length 0; s.capacity capacity; return s; } void destroySet(Set *s) { free(s-data); s-data NULL; s-length 0; s-capacity 0; } int cmpInt(const void *a, const void *b) { return (*(int *)a - *(int *)b); } void sortAndDeduplicate(Set *s) { qsort(s-data, s-length, sizeof(int), cmpInt); int k 0; for (int i 0; i s-length; i) { if (k 0 || s-data[k - 1] ! s-data[i]) { s-data[k] s-data[i]; } } s-length k; } void inputSet(Set *s) { int n; printf(请输入集合元素个数: ); scanf(%d, n); *s createSet(n); printf(请输入 %d 个元素允许重复、乱序:\n, n); for (int i 0; i n; i) { int x; scanf(%d, x); s-data[s-length] x; } sortAndDeduplicate(s); } void printSet(const char *name, Set *s) { printf(%s { , name); for (int i 0; i s-length; i) { if (i 0) printf(, ); printf(%d, s-data[i]); } printf( }\n); } Set unionSet(Set *a, Set *b) { Set res createSet(a-length b-length); int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { res.data[res.length] a-data[i]; } else if (a-data[i] b-data[j]) { res.data[res.length] b-data[j]; } else { res.data[res.length] a-data[i]; j; } } while (i a-length) res.data[res.length] a-data[i]; while (j b-length) res.data[res.length] b-data[j]; return res; } Set intersectSet(Set *a, Set *b) { int cap a-length b-length ? a-length : b-length; Set res createSet(cap); int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { i; } else if (a-data[i] b-data[j]) { j; } else { res.data[res.length] a-data[i]; i; j; } } return res; } Set differenceSet(Set *a, Set *b) { Set res createSet(a-length); int i 0, j 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { res.data[res.length] a-data[i]; } else if (a-data[i] b-data[j]) { j; } else { i; j; } } while (i a-length) res.data[res.length] a-data[i]; return res; } int main() { Set A, B, U, I, D; inputSet(A); inputSet(B); printSet(A, A); printSet(B, B); U unionSet(A, B); I intersectSet(A, B); D differenceSet(A, B); printSet(A∪B, U); printSet(A∩B, I); printSet(A-B, D); destroySet(A); destroySet(B); destroySet(U); destroySet(I); destroySet(D); return 0; }编译运行的方式很简单gcc main.c -o main ./main5.2 实测结果与中间状态检查我拿普通测试用例跑了一轮请输入集合元素个数: 5 请输入 5 个元素允许重复、乱序: 1 2 3 4 5 请输入集合元素个数: 5 请输入 5 个元素允许重复、乱序: 3 4 5 6 7 A { 1, 2, 3, 4, 5 } B { 3, 4, 5, 6, 7 } A∪B { 1, 2, 3, 4, 5, 6, 7 } A∩B { 3, 4, 5 } A-B { 1, 2 }结果完全符合预期。调试这类程序时我建议每算完一个集合就立刻打印出来检查而不是等全部算完再一块看。这样做的好处是一旦发现交集结果不对你能快速定位是排序阶段出了问题还是去重阶段出了问题又或者是双指针的某个分支写错了。6. 实验报告的写法与三个可以继续深挖的方向6.1 让老师眼前一亮的报告结构很多同学的实验报告就是贴一段代码再加几句解释这种写法拿不到高分。我建议按下面这套结构来组织需求分析明确输入是什么、输出是什么、有什么约束条件比如输入可能重复、可能乱序、可能为空集。数据结构设计说明为什么选有序顺序表、为什么不用链表和位图画出 Set 结构体的存储示意图。算法设计写清楚排序、去重、求交、求并、求差的算法思路核心是“双指针归并”。复杂度分析分别分析时间和空间并和暴力 O(m*n) 做对比强调 O(mn) 的来源。测试与结果贴出边界测试的输入输出并解释结果为什么正确。实验总结写你实际踩过的坑比如漏了差集循环后的剩余元素、输出格式多了逗号、重复输入导致结果错误等。其中数据结构设计和复杂度分析这两块最能拉开分差。招人喜欢的写法不是“我用了结构体数组”而是“我为什么用结构体数组”——体现出你对存储结构有过思考而不是碰巧能跑。6.2 进阶方向位图、链表以及 Java/Python 的对应实现这个实验做完后还可以往三个方向延伸尤其是做扩展或二次作业时会用到。第一个方向是位图。假设题目明确说明元素范围在 0 到 100 之间那可以开一个bool exist[101]输入时直接exist[x] true。两种集合的并集就是两个数组对应下标做逻辑或交集做逻辑与代码会短到不可思议单次成员判断也是 O(1)。缺点很直接取值范围一大比如元素到 2^31位图就会爆内存。第二个方向是链表。把 Set 结构体里的数组换成单链表双指针归并的思路不变但每个“指针移动”都要变成“节点指针后移”。链表的好处是插入和删除灵活结果集合不需要提前申请大容量缺点是代码里全是节点指针调试难度上去一截。这个方向适合学完链表后回头再看能把两种物理结构对同一逻辑模型的差异体会得更深。第三个方向是跨语言对照。Java 里对ListString求交集常用的做法是list1.retainAll(list2)求并集用addAll加去重求差集用removeAll。Python 更直接set(A) set(B)、set(A) | set(B)、set(A) - set(B)三行写完。不过如果实验课目的是让你理解底层的双指针归并逻辑用现成 API 交作业反而可能失去练习意义。我的建议是先用 C 语言把算法原理写透再去看 Java 和 Python 的封装那时你对它们的实现原理会有完全不同的认识。回到实验本身这个题目真正教给我的不是“集合怎么求交并差”而是“如何给一个数学概念选择合适的物理载体”。有序顺序表加双指针这套组合后面在归并排序、有序表合并、求两个有序数组的中位数、甚至很多知名算法题里都会反复出现。你要是能在这个实验里把双指针的每个分支都弄明白后面学起来会轻松很多。