C/C++链表实现集合交并补差运算：完整思路与代码解析

做数据结构课程设计那会儿我拿到过一个题目C/C利用链表实现集合的交、并、补、差运算。第一眼看上去就是写四个函数的事真正动手才发现里面藏着不少细节重复元素怎么去头结点要不要补集的全集是什么返回新链表还是改原链表每一个都够折腾一阵子。今天把完整的设计思路、实现代码、测试方法和踩坑记录一次性写清楚给正在跟链表和集合运算较劲的同学一个可以直接“抄作业”的参考。1. 集合运算与链表选型从题目本身想清楚设计思路1.1 先明确集合的数学规则别急着写代码集合是离散数学里的基础概念在做链表实现之前必须先把数学定义落到程序语言上。集合有三个核心特征确定性、互异性、无序性。翻译成代码的语言就是元素是否属于集合判断结果必须唯一同一个集合里不能出现两个相同的值元素之间的先后顺序不影响集合本身。基于这三个特征程序层面的约束就很明确了。读入数据时要去重插入新元素前要判断是否已经存在运算结果的集合也必须保证没有重复元素。很多人写交并差的时候只想着遍历和比较结果输出里出现一堆重复值被测试样例直接打回根源就是没有把“互异性”落实到每一步操作里。补集和另外三个运算有一点点不同。交、并、差都是二元运算输入两个集合输出一个新集合。补集在数学上的严格定义是“相对于某个全集U的补集”即 U - B。也就是说实现补集函数时不能只传入一个集合还要带上全集。题目里如果只说“补集”两个字通常默认全集是人为给定的比如限定在整数1到100范围内或者限定在某些特定数据范围内。这个前提不确认清楚补集函数写出来一定是错的。1.2 为什么选链表数组、位图、链表的对比这个题目点名要用链表但如果只是单纯完成任务其实数组可能更好写。数组天然支持随机访问判断一个元素是否存在只需要一层循环扫过去交并差都不难实现。问题是数组的大小在创建时必须确定集合元素个数如果是动态变化的就得频繁扩容插入删除需要移动大量元素。位图是另一个常见方案把每个整数映射到一个bit位判断存在与否是O(1)级别的操作性能非常抢眼。但位图的适用范围很窄元素必须是整数而且数值跨度不能太大。假如集合里既有整数又有字符串或者数值范围从0到一个很大的数位图就力不从心了。链表的好处是大小动态可变插入和删除在已知位置的情况下是O(1)底层结构简单非常适合用来理解指针操作和数据结构的动态管理。缺点同样明显查找元素必须从头遍历每次都只能一个结点一个结点走。链式存储还会产生额外的指针开销和内存碎片频繁malloc和free也会带来性能损耗。但作为教学题目链表能把“构造数据管理内存设计算法”三件事都练到选它作为实现方式是很合理的。1.3 整体架构规划带头结点还是不带头结点动手之前有一个重要的设计决策要做链表用不用头结点哨兵结点。不带头结点的单链表头指针直接指向第一个数据结点插入和删除第一个元素时需要修改头指针本身函数里通常要传入二级指针或者通过返回值更新头结点。很多初学者就是在这里翻车插入第一个数据时忘记更新头指针打印出来的链表“凭空消失”了一个元素。带头结点的链表头结点固定在表头data域闲置不用或者用来存链表长度next指向真正的第一个数据结点。插入和删除任何位置都不需要改动头结点本身代码逻辑更统一。我建议做这个题目时用带头结点的单链表虽然多了一个结点的内存开销但换来的实现稳定性非常值得。后面所有的代码示例都采用带头结点的写法。2. 链表集合的基础设施核心操作的细节决定成败2.1 结点定义与两个辅助函数的设计集合的每个元素对应链表中的一个结点。结点结构体定义如下typedef struct Node { int data; // 数据域这里以int类型为例 struct Node *next; // 指针域 } Node;数据域用int是最直观的选择方便测试和调试。题目如果不限定类型后面可以考虑泛化成字符串或结构体这个我在“常见问题”部分再展开。和结点定义配套的是两个贯穿整个项目的基础工具函数查找函数和去重插入函数。所有运算的核心判断都依赖“元素x是否在集合S中”这个基本操作。int contains(Node *head, int x) { Node *p head-next; while (p ! NULL) { if (p-data x) { return 1; } p p-next; } return 0; }contains函数的时间复杂度是O(n)在无序链表里这是不可避免的。后面的交集和差集都会循环调用它所以这个函数虽然简单但性能直接影响整个项目。去重插入函数在每次插入前先调用contains检查保证集合的互异性。void insertNoDup(Node *head, int x) { if (contains(head, x)) { return; } Node *p head; while (p-next ! NULL) { p p-next; } Node *newNode (Node *)malloc(sizeof(Node)); newNode-data x; newNode-next NULL; p-next newNode; }insertNoDup采用的是尾插法每次找到链表的最后一个结点再挂上新结点。如果输入数据量特别大尾插法每次都要遍历整个链表效率不高。另一种做法是头插法新结点直接插在头结点后面时间复杂度降到O(1)但输出顺序会跟输入顺序完全相反。对集合来说顺序无关紧要所以如果追求效率可以直接改成头插法。不过这里为了代码可读性我保留尾插法并把contains查找和去重逻辑分开方便大家理解。2.2 集合的创建、打印与销毁易被忽视的收尾工作创建空集合就是创建一个带头结点的空链表。Node *createSet() { Node *head (Node *)malloc(sizeof(Node)); head-data 0; head-next NULL; return head; }打印集合用来验证运算结果调试时几乎离不开它。打印时跳过哨兵结点元素之间用空格分隔最后换行。void printSet(Node *head) { Node *p head-next; if (p NULL) { printf({}); return; } printf({); while (p ! NULL) { printf(%d, p-data); if (p-next ! NULL) { printf(, ); } p p-next; } printf(}); }销毁链表是内存收尾的关键很多人写完交并差就忘了释放原链表和结果链表程序虽然能跑但内存泄漏严重。正确做法是逐个结点free不能只free头结点否则后面的结点全变成无法访问的悬空内存。void freeSet(Node *head) { Node *p head; Node *tmp; while (p ! NULL) { tmp p; p p-next; free(tmp); } }注意freeSet接收的是头结点指针使用后再也不对这个链表做任何访问。调用完成后建议把原指针设为NULL避免误用。2.3 三条经验为什么要做这些基础操作第一contains和insertNoDup是所有运算的公共底座写好了后面四个函数都很轻松底座写不好交集可能包含了B里没有的元素并集可能出现重复数据调试起来非常痛苦。第二哨兵结点的data域虽然闲置但代码里不要拿它来存什么“魔法值”。我在初版实现里试图给头结点的data存链表长度后来发现每次插入删除都要维护这个值多了一堆边界条件纯属给自己挖坑。第三printSet这个函数看起来微不足道但建议在一开始就写好。后面测试时每步运算后都调用它打印结果能第一时间发现指针断链、重复数据等问题比断点调试更直观。3. 四种集合运算的实现思路与边界条件3.1 交集遍历A判断元素是否在B中集合A和集合B的交集是“属于A且属于B”的元素组成的集合。做法很直接遍历A的每一个元素用contains在B中查找找到就插入结果集合。Node *intersection(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; while (pa ! NULL) { if (contains(B, pa-data)) { insertNoDup(res, pa-data); } pa pa-next; } return res; }这个方案的时间复杂度是O(m*n)m是A的长度n是B的长度。因为外层循环遍历A内层contains在B中逐个查找。如果两个集合长度都在1000左右最坏情况要跑100万次比较性能一般但可以接受如果数据量再大就要考虑有序链表或哈希表的优化方案。边界条件方面如果A或B是空集contains恒为0或循环体根本不执行结果自然是空集代码不需要额外写if判断去处理空集这是这个方法的一个优点。3.2 并集逐个插入自动去重并集是“属于A或属于B”的元素组成的集合。最容易想到的思路是把A全部复制进结果集合再把B的元素逐个插入insertNoDup会自动过滤掉已经在结果集合里的元素。Node *unionSet(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; while (pa ! NULL) { insertNoDup(res, pa-data); pa pa-next; } Node *pb B-next; while (pb ! NULL) { insertNoDup(res, pb-data); pb pb-next; } return res; }这里有个隐藏的重复判断开销insertNoDup内部先调contains检查是否已经存在。复制A的时候A本身是集合没有重复元素所以这个contains是多余的。基于这一点可以把insertNoDup拆出一个“无检查插入”的底层函数纯粹尾插或头插。考虑到代码可读性我在这里保留统一接口但真正追求性能时可以优化掉这部分冗余检查。并集的边界条件主要是两个集合完全重合的情况。比如集合A和B都含有元素{1,2,3}并集输出必须还是{1,2,3}不能输出六个元素这正是insertNoDup发挥作用的地方。3.3 补集先定义全集否则无从谈起补集是四个运算里最容易被误解的一个。集合B在全集U中的补集定义为所有属于U但不属于B的元素。也就是说补集运算需要两个输入全集U和被减集合B。Node *complement(Node *U, Node *B) { Node *res createSet(); Node *pu U-next; while (pu ! NULL) { if (!contains(B, pu-data)) { insertNoDup(res, pu-data); } pu pu-next; } return res; }这里的关键是函数的参数列表里必须包含U。我在代码评审时见过很多同学写补集函数只传一个参数然后默认“全集是系统里见过的所有元素”结果不同输入环境下返回结果完全不一样这就是对数学定义理解不到位导致的。补集的时间复杂度同样是O(m*n)m是全集的长度n是集合B的长度。为了降低开销可以先遍历U把U中不在B里的元素加入结果也可以遍历B从U中删除B的元素但自定义链表中删除结点比插入麻烦一些容易出错不如直接“筛选式构造新链表”。3.4 差集与交集互补的逻辑差集A-B是“属于A但不属于B”的元素组成的集合。这个运算和交集只差了一处逻辑判断交集是contains为真才插入差集是contains为假才插入。Node *difference(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; while (pa ! NULL) { if (!contains(B, pa-data)) { insertNoDup(res, pa-data); } pa pa-next; } return res; }差集和补集看起来很像一个是A-B一个是U-B代码结构确实同构但语义上必须区分清楚。补集是针对一个“大集合”做减法差集是针对两个平级集合做减法。如果A本身就等于全集那A-B和U-B的结果恰好相同这只是巧合不是两者能互相替代的理由。差集实现最大的坑是忘记“A中可能有重复元素”。虽然理论上A是集合不会有重复但如果你的A是通过普通数组直接构造的没有经过去重那差集函数里insertNoDup会帮你兜底结果依然正确。反过来如果没有insertNoDup这层保护差集结果里混入重复元素数学上就不再是集合了。3.5 一个值得掌握的优化有序链表的归并式实现前面四个实现都建立在无序链表的基础上最坏情况复杂度是O(m*n)。如果给链表提前排序让元素保持递增有序交、并、差都能用双指针归并的思路降到O(mn)。双指针的思路是同时遍历A和B比较当前两个指针指向的元素大小。以交集为例如果A当前元素小于B当前元素A的指针后移如果大于B的指针后移如果相等把该元素加入结果两个指针同时后移。整个过程两个链表只各遍历一次效率非常高。Node *intersectionSorted(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; Node *pb B-next; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { pa pa-next; } else if (pa-data pb-data) { pb pb-next; } else { insertNoDup(res, pa-data); pa pa-next; pb pb-next; } } return res; }这里的代价在于维护有序性。如果输入数据本身无序需要先做一次排序排序链表的常见方案是归并排序复杂度O(n log n)。排序加归并的总复杂度O(n log n)仍然远优于无序方案的O(m*n)。建议初学阶段先把无序版本跑通再回头优化成有序版本两种思路都吃透才算真正掌握这个题目。4. 完整可运行代码与测试设计4.1 完整代码串联把前面所有函数拼成一个完整的单文件程序方便直接编译运行验证。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createSet() { Node *head (Node *)malloc(sizeof(Node)); head-data 0; head-next NULL; return head; } int contains(Node *head, int x) { Node *p head-next; while (p ! NULL) { if (p-data x) { return 1; } p p-next; } return 0; } void insertNoDup(Node *head, int x) { if (contains(head, x)) { return; } Node *p head; while (p-next ! NULL) { p p-next; } Node *newNode (Node *)malloc(sizeof(Node)); newNode-data x; newNode-next NULL; p-next newNode; } void printSet(Node *head) { Node *p head-next; if (p NULL) { printf({}); return; } printf({); while (p ! NULL) { printf(%d, p-data); if (p-next ! NULL) { printf(, ); } p p-next; } printf(}); } void freeSet(Node *head) { Node *p head; Node *tmp; while (p ! NULL) { tmp p; p p-next; free(tmp); } } Node *intersection(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; while (pa ! NULL) { if (contains(B, pa-data)) { insertNoDup(res, pa-data); } pa pa-next; } return res; } Node *unionSet(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; while (pa ! NULL) { insertNoDup(res, pa-data); pa pa-next; } Node *pb B-next; while (pb ! NULL) { insertNoDup(res, pb-data); pb pb-next; } return res; } Node *complement(Node *U, Node *B) { Node *res createSet(); Node *pu U-next; while (pu ! NULL) { if (!contains(B, pu-data)) { insertNoDup(res, pu-data); } pu pu-next; } return res; } Node *difference(Node *A, Node *B) { Node *res createSet(); Node *pa A-next; while (pa ! NULL) { if (!contains(B, pa-data)) { insertNoDup(res, pa-data); } pa pa-next; } return res; } int main() { Node *A createSet(); Node *B createSet(); Node *U createSet(); insertNoDup(A, 1); insertNoDup(A, 3); insertNoDup(A, 5); insertNoDup(A, 7); insertNoDup(B, 3); insertNoDup(B, 6); insertNoDup(B, 7); insertNoDup(B, 8); for (int i 1; i 10; i) { insertNoDup(U, i); } printf(A ); printSet(A); printf(\n); printf(B ); printSet(B); printf(\n); Node *inter intersection(A, B); printf(A ∩ B ); printSet(inter); printf(\n); Node *uni unionSet(A, B); printf(A ∪ B ); printSet(uni); printf(\n); Node *comp complement(U, B); printf(U - B ); printSet(comp); printf(\n); Node *diff difference(A, B); printf(A - B ); printSet(diff); printf(\n); freeSet(A); freeSet(B); freeSet(U); freeSet(inter); freeSet(uni); freeSet(comp); freeSet(diff); return 0; }这段代码在主流C语言编译器下可以直接编译运行。输出结果如下A {1, 3, 5, 7} B {3, 6, 7, 8} A ∩ B {3, 7} A ∪ B {1, 3, 5, 7, 6, 8} U - B {1, 2, 4, 5, 9, 10} A - B {1, 5}注意并集的输出顺序是“先全部放A再逐个放B”所以B中元素6和8出现在7后面看起来有点不整齐。这符合集合的无序性特征如果要求输出有序需要额外做排序处理。4.2 测试用例怎么设计光跑通还不够代码能跑通main里的示例只是第一步设计测试用例时要覆盖各种边界情况才算真正可靠。我整理了一个常用测试矩阵测试场景AB期望结果检查重点空集与其他集合空集{1,2}交空集并{1,2}差空集链表为空时不出错两个完全相同的集合{1,2}{1,2}交{1,2}并{1,2}差空集重复元素只保留一份两个完全不同的集合{1}{2}交空集并{1,2}差{1}完全不重合时逻辑正确包含关系{1,2,3}{1,2}交{1,2}并{1,2,3}差{3}子集场景创建时输入重复元素{1,1,2}{1,3}交{1}并{1,2,3}差{2}输入阶段去重是否生效全集部分重合U{1..5}B{4,5,6}U-B{1,2,3}补集对“出现在B但不在U”的元素的处理第六个用例特别容易踩坑。当B中存在全集U里没有的元素时很多实现会在补集结果里“自动排除”这些元素这是对的但需要确认代码没有因为contains返回真而误删U里的其他元素。由于补集只遍历UB中那些“多余”元素不会参与遍历代码天然安全但如果反向遍历B从U中删除就必须小心这种情况。4.3 复杂度对照选型前心里要有数无序链表方案和有序链表归并方案在不同运算下的时间复杂度差异值得用一张表搞清楚运算无序链表实现有序链表归并实现说明交集O(m*n)O(mn)有序方案优势最大并集O(m*n m)O(mn)无序版还要额外去重补集O(m*n)O(mn)m为全集长度差集O(m*n)O(mn)与交集同构空间复杂度方面所有方案都需要为结果链表申请新的结点占O(mn)空间。如果原地修改原集合可以省掉结果链表的内存但要承担破坏原数据的风险。实际做题时建议优先返回新集合保留原集合方便多次运算和结果验证。5. 常见问题与调试实录5.1 运算时应该原地修改还是构造新集合很多初学者会把交并差实现成“直接修改传入的链表”。比如并集直接把B的结点挂到A的尾部差集直接在A里删除B中存在的元素。这样做的好处是省内存但坏处非常明显原集合被破坏了后续如果想再做一次交集或者验证中间结果数据已经不复存在。我的建议是所有运算函数都返回新链表至少把新链表作为主要接口。原链表保留测试时随时可以复用。这一点在实际开发里也成立函数设计的不变式越强调用时越不容易出错。如果确实需要原地版本单独写另一个函数命名清楚比如intersectionInPlace不要混在一起。5.2 内存泄漏排查从哪里看起单链表的内存泄漏几乎都集中在freeSet函数和运算函数里的malloc搭配。最典型的错误是只free头结点不free后面的数据结点结果程序不报错但内存占用持续上涨。判断方法很简单跑大量的测试循环之后观察进程内存占用是否稳定如果不断爬升说明有泄漏。另外一个容易被忽略的问题是结果链表的释放时机。main里连续调用四个运算函数每个返回一个新的链表头指针用完必须逐个freeSet。漏掉任何一个都是泄漏。有人图省事让结果链表借用原链表的结点结果freeSet时重复释放同一个结点直接崩溃。切记“谁malloc出来的谁负责释放别跨链表借结点”。5.3 数据域只有int吗扩展到其他类型题目示例通常用int但集合元素完全可能是字符、浮点数或者结构体。链表实现的框架不依赖具体数据类型只要把Node里的data类型替换成目标类型同时修改contains里的比较逻辑和printSet里的打印格式即可。如果元素是结构体比较两个元素是否相等就不能用“”需要写一个compare回调函数。这在C语言里可以用函数指针实现在C里可以直接重载运算符或者使用模板类。这也是很多人觉得C实现比C更舒服的原因之一。不过我建议初学阶段先把int版本吃透理解链表本身的结构和控制逻辑再考虑类型泛化不然容易陷入模板和指针混合的泥潭。5.4 调试技巧先打印再断点链表调试最直观的武器就是printSet。凡是怀疑指针断链、元素顺序不对、插入位置错了先打印“当前链表长什么样”。我调试时习惯在每个关键步骤后打印一次比如插入完成后、contains查找前后、运算函数内部处理完一个元素后都能快速定位是哪一步出了问题。还有一种常见的指针错误是“修改了临时指针之后原链表结构也被破坏了”。排查办法是画图。在纸上把链表画成方框加箭头的形式手动模拟插入删除过程指针指向哪个结点一画就清楚比干看代码有效得多。5.5 一个常被忽略的细节contains的NULL判断contains函数内部是从head-next开始遍历的如果传入的head本身是NULL程序会直接段错误。我在初版代码里偷懒没有在函数入口做参数检查结果测试时不小心传了一个已销毁的链表指针进去当场崩溃。后来在每个公共工具函数里加了参数校验传入NULL时直接返回0或直接返回虽然代码多几行但整个项目的健壮性提升了一大截。写在最后几个真实体会这套链表集合运算写下来我对指针和内存管理的感觉比之前清晰了很多。交并差四个函数本身不难难的是把数学定义准确翻译成代码约束去重、头结点、全集的语义、释放时机每一步都在考察你有没有真正理解数据结构而不只是背模板。如果现在再让我从这里往后推进我会优先做两件事一是实现有序链表归并版本把复杂度从O(m*n)降下来二是把数据结构抽象成更通用的容器让字符、浮点数、自定义结构体都能参与集合运算。做数据结构题目项目本身只是个起点里面任何一个点挖深了都能再写一篇完整的设计记录。