简介这份压缩包围绕数据结构中的集合交、并、差运算实验展开面向正在学习C与算法基础的高校学生及自学者帮助其在Visual Studio环境中完成集合抽象、运算实现与结果验证。包内共8个文件包含3个cpp源文件、3个头文件、1份pptx演示文稿和1份docx实验文档压缩包约8.74MB既有可参考的代码实现也有用于讲解思路与记录实验过程的配套材料。资源覆盖集合初始化、交并差逻辑、基于数组/链表/哈希表的实现取舍以及复杂度分析等要点并提供两套代码组织的参考便于读者对照调试、理解模块划分和整理实验报告。目前已有314人学习适合用作数据结构课程实验参考或课设起步模板。1. 集合交并差到底是什么从两筐水果说起想象桌上摆着两个筐。第一筐是你这周买回家的水果第二筐是家里孩子愿意吃的品种。你可能会顺口问三个问题哪些是我买了、孩子也肯吃的合起来家里到底碰过哪些品种我买的里面有哪些是买回来没人动、最后放坏的这三个问题分别就是交集、并集和差集。集合的交、并、差说的不是三种新东西而是同一批对象之间三种固定的提问方式。它把「谁在谁不在」这种每天都要问的口语问题压缩成了三个可以一遍算清的符号。值得花时间搞懂的地方在于计算机里绝大多数名单比对、去重、权限判断、版本差异最后都会落到这三个动作上认出来就等于少绕一大圈。2. 为什么值得单独学把「谁在谁不在」变成一套固定动作2.1 集合自带的三条规矩决定了它能干什么在动手算之前得先接受集合的三条默认设定这三条不是数学家的洁癖而是后面所有运算能成立的地基。第一条叫确定性随便拿一个东西过来它要么在集合里要么不在不允许出现「大概算在吧」这种状态。第二条叫互异性同一个东西写十遍在集合里也只算一个。第三条叫无序性{1, 2, 3} 和 {3, 1, 2} 是同一个集合先后顺序不影响它是谁。这三条合在一起产生了一个非常关键的性格集合只关心「在不在」完全不关心「有几个」和「排第几」。所以你让它回答「有没有」「在哪些」「哪些不在」它又快又准你让它回答「买了几次」「第三个是谁」它答不上来因为它从一开始就没记这些。顺带一提互异性这条规矩让集合天生就是一台去重机。你把一列带重复的名单塞进去它自动只留一份这不是巧合是定义本身带来的副产品。很多数据处理里所谓的「去重」本质上就是把普通列表升级成集合。2.2 从两张表格说起为什么非要把问题塞进集合设想某个团队里负责客户维护的同学手上拿到两份表。一份是长期合作的客户名单八千来号人另一份是本季度下过单的人一千两百来号人。负责人顺口问了三句话这一千两百人里有多少本来就是老客户两份名单合起来一共涉及多少个不同的人那八千个老客户里有多少本季度完全没动静如果不用集合的思路常见做法是把两张表并排打开手工标颜色或者套一层查找函数一个个比对。名单小的时候还行上了几千行就开始出问题颜色标串行、公式下拉少了一格、名字里多了一个空格导致匹配不上。这类活儿翻车的概率跟数据量基本成正比。换成集合的说法三句话就是三个动作。第一句问的是「两边都有的」第二句问的是「合起来有哪些不同的」第三句问的是「在左边但不在右边的」。问题一旦被这样描述剩下的就只是把数据整理成两个集合然后套三个动作跟名单里具体是人名、商品编号还是标签没有关系。2.3 三个动作分别对应哪类问法把常见的问法归一下类大致是这样一张对照你想问的对应运算常见写法结果规模两边都满足的交集A ∩ B不会超过任何一边至少满足一边的并集A ∪ B不会小于任何一边满足 A 但不满足 B 的差集A − B不会超过 A这张表最有用的是最后一列。交集算出来的结果比两边都大或者差集算出来比被减的那一边还多那基本可以断定中间哪里写错了不用等跑完再看。这种不用看具体数据、只看规模就能判断对错的检查方式是集合运算在工程上特别讨喜的一点。再往深一层看集合运算之所以能被反复复用是因为它把「元素到底是什么」这件事彻底抹掉了。只要两个集合里的东西属于同一个讨论范围人名、编号、标签、地址全都能套同一套动作。这种「只留存在性、丢掉其他一切」的抽象才是它值得单独拿出来学的理由。3. 交集、并集、差集各自在做什么三种运算的脾气3.1 交集条件叠在一起只会越筛越少交集是最符合直觉的一个。A 是「会写 Python 的人」B 是「会写 SQL 的人」A ∩ B 就是两样都会的人。生活里叠筛子就是这个感觉一个筛子筛一遍再叠一个筛一遍能通过的总量只会更少不会更多。它有几个很好用的性质。交换律成立A ∩ B 和 B ∩ A 是同一个东西因为「两边都满足」这句话本身不分先后。结合律也成立三个集合一起交先算哪两个都一样。跟空集交结果一定是空集因为空集里没有任何东西能满足条件。自己跟自己交还是自己这叫幂等。放到实际场景里交集对应的是「多条件同时成立」。数据库查询里连写好几个 AND表格软件里叠加好几层筛选推荐系统里同时命中好几个标签才推给你做的都是交集。理解这一点之后你会发现自己平时说的「再筛一下」其实一直在做集合交。3.2 并集范围合并顺便把重复的吃掉还是那两拨人A ∪ B 指的是「至少会其中一样的人」只写 Python 的算只写 SQL 的算两样都会的也算但只算一次。这里藏着并集最容易被忽略的动作去重。很多人第一反应是把两边的数量直接相加得到的结果往往偏大因为两样都会的那部分人被数了两遍。数学上用容斥原理解释得很清楚|A ∪ B| |A| |B| - |A ∩ B|减掉的那一项正是被重复计算的部分。三个集合的时候规律会更花哨一点|A ∪ B ∪ C| |A| |B| |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| |A ∩ B ∩ C|加加减减的规律是参与相交的集合个数为奇数时加偶数时减。这个式子在实际工作里出现频率高得惊人凡是需要「统计不重复总数」的场合它都会冒出来。手工统计时最常见的出错方式就是只减了成对相交的部分忘了把三边都重合的那一小撮加回去导致结果偏小。3.3 差集有方向谁减谁完全不是一回事差集是三种运算里唯一带方向感的。A − B 的意思是「在 A 里、但不在 B 里」换过来 B − A 是另一件事。打个比方会更清楚。A 是班级花名册B 是本周交了作业的名单。A − B 是「名册上有、但没交作业」的人这是老师真正想看的东西。反过来 B − A 是「交了作业、但花名册上没这个人」可能是刚转来的、可能是名单漏登了。两个结果都可能有内容含义却完全相反写反了还照样能算出东西来不会报错这才是最麻烦的地方。差集有个很实用的等价变形A − B A − (A ∩ B)道理是A 里面那些同时也在 B 里的元素才需要被剔除所以先求出交集再从 A 里减掉结果一样。这个写法在实现上经常更好用因为求交集往往比直接做差集更容易优化。还有个规模上的直觉|A − B| |A| − |A ∩ B|也就是差集的结果不会超过被减的那一边。如果算出来比 A 还大那肯定是把方向或者符号弄反了。3.4 补集和对称差全集是个隐形的第三方补集看起来简单其实是三种运算里最容易出问题的。补集的意思是「在讨论范围里、但不在 A 里」这里的「讨论范围」就是全集记作 U补集写成 ∁_U A本质上是 U − A。关键在于全集必须先说清楚。有人问「不在 A 里的人有多少」这句话本身是不完整的不在 A 里的谁全班范围内全公司范围内还是所有出现过的人里范围不同答案能差出好几个数量级。所以补集永远不是单独存在的运算它必须挂在一个已经定好的全集上。对称差是另一个容易被忽略的角色写作 A ⊕ B含义是「恰好只在一遍出现的元素」A ⊕ B (A − B) ∪ (B − A) (A ∪ B) − (A ∩ B)两种写法说的是同一件事把两边各自独有的部分拼起来或者把合并后的结果里挖掉共同的部分。它在找「不一致」的场合特别顺手比如对比两个版本的配置文件有哪些条目对不上或者两份名单里哪些人是单方面出现的。注意它把两个方向的结果合在了一起所以看不出是谁多谁少如果业务上需要区分方向还是得老老实实分开算两次差集。4. 常见误区与易混概念空集、差集、补集到底差在哪4.1 算出空集不等于程序出错了易混点结果为空集很多人第一反应是「哪里写错了」而不是「确实没有」。为什么混空集在视觉上就是「什么都没有」和「没算出来」「报错了」看起来太像。尤其在一堆日志里一个空空的结果集和一次失败的查询呈现形式几乎一致。怎么区分空集是一个合法的答案含义是「这个条件下确实一个都没有」。判断标准不在结果长什么样而在运算有没有走完交集为空说明两边完全没有重合差集为空说明 A 完全被 B 包住了。这两个结论都是有信息量的甚至比非空结果更有信息量。真正需要警惕的是另一种情况本来应该有结果却算出空集那大概率是元素的表示方式不一致比如一边带空格一边不带一边是大写一边是小写集合认的是「完全一样」差一个字符就是不相等。4.2 差集和对称差看着都在找不同易混点两个都跟「不同」有关容易当成一回事。为什么混名字里都带着「差」的意思实际用起来又常常能得出相近的结果尤其在两边重合度很高的时候。怎么区分记住方向性。差集 A − B 是单向的只关心 A 里有哪些是 B 没有的B 里多出来的东西它完全不看。对称差 A ⊕ B 是双向的两边各自独有的部分全都要。判断方法很简单如果业务问题是「我这边缺什么」用差集如果是「两边哪里对不上」用对称差。前者只需要问一次后者往往要问两次再合并合并完就分不清方向了。4.3 交集非空不代表两个集合有关系易混点只要 A ∩ B 不是空的就以为 A 和 B 之间存在包含关系。为什么混日常语言里「有交集」常常被引申成「有共同点、沾边」语义被放大了。怎么区分交集非空只说明至少有一个元素同时属于两边仅此而已。包含关系是另一个概念A ⊆ B 要求 A 里面的每一个元素都在 B 里一个不落。两个集合完全可以只共享一个元素同时各自还有几百个对方没有的东西这时候它们既不是子集关系交集又非空。真子集还要更严格一点要求 A ⊆ B 且 A ≠ B。判断包含关系看的是「全部」判断交集看的是「至少一个」这两个量词不一样结论就不能混着用。4.4 差集和补集都写作「减」易混点A − B 和 ∁_U A 都带着减的味道有人直接把差集当补集用。为什么混补集的定义式就是 U − A看起来只是把 B 换成了 U形式上高度相似。怎么区分补集一定要有全集差集不需要。差集是两个平等的集合之间的操作减数是谁都行补集是把某个集合放到一个已经划定好的大范围里去看「剩下的部分」。如果代码里出现了一个「减」操作但减数是个临时凑出来的集合那它只能是差集不能叫补集如果减数是那个固定的讨论范围才轮得到补集。实践中最常见的错误是省掉了全集的声明直接对某个集合求补结果拿到的是「所有能想到的东西减去它」范围失控。4.5 集合去重和「统计次数」是两码事易混点把数据塞进集合处理完顺手用集合的大小当作总数。为什么混集合确实能去掉重复看起来像是把数据「整理干净」了于是很容易顺手拿它来计数。怎么区分集合的大小是「有多少种不同的元素」不是「一共出现了多少次」。一份订单表里同一个客户下了五单放进集合之后只剩一个人你去问「本季度订单量」答案必然错得离谱。判断标准是看问题问的是「种类」还是「次数」问种类集合正合适问次数就得用能保留重复的结构比如列表或者带计数的映射。这也是集合运算最本质的取舍它在扔掉重复和顺序的同时换来了判断「在不在」的极高效率用之前先想清楚扔掉的东西还要不要。5. 落到代码里长什么样哈希集合、位图与 SQL 三种写法5.1 哈希集合把两层循环换成一次遍历概念讲完落到具体语言里Python 的集合类型是最贴近前面那套符号的。下面这段用编号代替具体人名避免把真实信息写进示例# 用编号代表名单里的个体集合会自动丢掉重复项 roster {1001, 1002, 1003, 1004} # 长期合作的客户 orders {1003, 1004, 1005} # 本季度下过单的客户 both roster orders # 交集既是老客户又下过单 either roster | orders # 并集两边出现过的人都算一次 only_roster roster - orders # 差集老客户但本季度没动静 only_orders orders - roster # 差集下过单但不在老名单里 symmetric roster ^ orders # 对称差只在一边出现的人 print(len(both), len(either), len(only_roster))、|、-、^分别对应交、并、差、对称差和前面的符号一一对得上不需要额外记。关键在于复杂度把两个集合都建成哈希结构之后每次判断「某个元素在不在」平均是常数时间整体做一次交并差大约是 O(n m)也就是两边元素数量之和的量级。如果换成最朴素的双层循环对 A 里每个元素都去 B 里从头找一遍复杂度会变成 O(n × m)。八千人乘一千二百人接近一千万次比较在数据量再大一点的时候就会明显卡住这也是很多「Excel 卡死」场景背后的真实原因。哈希集合不是让机器变快了是让比较次数从相乘变成了相加。参数和边界上有两点要注意能放进集合的元素必须是可哈希的列表、字典这类可变结构不行得先转成元组或者字符串另外集合不保留顺序如果你后面还要按原始顺序输出就得另外维护一份列表别指望从集合里取回来。5.2 位图元素是连续小整数时一个数字就是一个集合当元素都是 0 到几十之间的小整数时还有种更省的做法用整数的每一位代表一个元素在不在。第 n 位是 1就表示编号 n 在集合里。def to_bits(nums): mask 0 for n in nums: mask | (1 n) # 把第 n 位置为 1其他位不动 return mask def to_list(mask, size): # 从低位往高位扫把值为 1 的位置还原成元素编号 return [i for i in range(size) if (mask i) 1] a to_bits([1, 3, 5]) # 二进制 101010 b to_bits([3, 4, 5]) # 二进制 111000 print(to_list(a b, 8)) # 交集 - [3, 5] print(to_list(a | b, 8)) # 并集 - [1, 3, 4, 5] print(to_list(a ~b, 8)) # 差集 - [1]位运算和集合运算的对应关系非常整齐按位与就是交集按位或|就是并集a ~b就是差集按位异或^就是对称差。一次位运算就能处理几十个元素的判断速度快得不像话内存占用也小到可以忽略。代价同样明显。元素必须能映射到一段连续的小整数上编号跨度一大比如 ID 是几百万的随机数整数位数就不够用了。另外这种写法可读性差调试的时候看到的是一串二进制排查问题基本靠打印。还有一个语言细节Python 里的整数是任意精度的~b会得到负数a ~b在这种语境下结果仍然正确但在位宽固定的语言里得先跟一个掩码相与把高位清掉否则会算出一堆意料之外的位。5.3 SQL 里的三种写法和 JOIN 不是一回事数据已经躺在数据库里的时候用 SQL 表达集合运算最直接-- 交集两张表里都出现过的编号 SELECT id FROM roster INTERSECT SELECT id FROM orders; -- 并集两边出现过的编号UNION 自带去重 SELECT id FROM roster UNION SELECT id FROM orders; -- 差集在 roster 里但不在 orders 里注意方向 SELECT id FROM roster EXCEPT SELECT id FROM orders;UNION默认会去重如果业务上需要保留两边的全部行比如要统计总条数得写成UNION ALL。INTERSECT和EXCEPT在部分数据库里支持得比较晚遇到不支持的方言可以用JOIN或NOT EXISTS改写-- 用 NOT EXISTS 表达 roster EXCEPT orders SELECT r.id FROM roster r WHERE NOT EXISTS ( SELECT 1 FROM orders o WHERE o.id r.id );这里要特别说清一个高频混淆点JOIN 和集合运算看着都能把两张表凑到一起实际逻辑完全不同。JOIN 是按关联条件把行做组合一对多的时候行数会翻倍结果是「拼接」集合运算是对整行判断在不在结果的行数只会小于等于输入之和是「筛选」。同样两张表用 JOIN 可能得到一万行用 INTERSECT 可能只剩三行这不是谁对谁错是问的问题不一样。判断标准是你需要把两边的字段并排放在一行里看用 JOIN你只关心某个键在不在另一张表里用集合运算。5.4 集合运算会悄悄吃掉的那部分信息前面反复提到集合会丢掉重复和顺序这里值得单独说清楚代价。一旦把数据塞进集合你就永久失去了「出现了几次」和「先后顺序」这两条信息而且是不可逆的事后想找回来只能回到原始数据重来。所以顺序应该是先想清楚问题再决定要不要转成集合。如果只是判断某个编号在不在名单里转集合是纯粹的收益如果后面还要按时间排序、还要统计每个客户下了几单那就该在集合运算之外另存一份原始数据或者干脆用带计数的结构。很多数据处理流程出问题不是因为集合运算写错了而是因为在某一步顺手转了集合把后面需要的信息提前弄丢了等发现的时候已经无从追溯。6. 什么时候该用集合运算什么时候别用判断标准其实不复杂主要看你问的是「在不在」还是「有多少、第几个」。适合用的场景基本都围绕「存在性判断」展开场景用哪种运算为什么合适两份名单找共同的人交集只关心两边都满足不需要次数合并多个来源的标签并集天然去重避免重复计数找出沉默用户差集单向判断「有但没做」对比两个版本配置对称差只想知道哪里对不上权限校验交集非空一次判断是否命中任一权限数据清洗去重转集合互异性直接生效不适合的场景往往是被集合的特性反咬一口需要计数的别用。问「这个客户下了几单」集合只会告诉你「他下过」具体几次它不知道也不会记。需要顺序的别用。集合无序取不出「第一个」和「最后一个」凡是涉及时间线、排名、先后关系的都得用别的东西。元素不可哈希的别用。列表、字典这类可变结构直接塞进集合会报错得先转成元组或者序列化字符串转换过程本身就可能引入新的不一致。数据量大到装不进内存的别用。哈希集合快是快但它要求把数据整个放进内存建表几千万条以上就得考虑排序后归并或者干脆交给数据库处理。需要模糊匹配的别用。集合判断的是完全相等差一个字符就是不在姓名里多个空格、大小写不一致、全角半角混用都会让本该命中的元素被判为不存在。这类问题不报错只是结果默默偏小属于最难查的一类。我自己的习惯是这样来的早些年做一次名单比对图省事直接拿差集算「没交作业的人」结果对着名单核了半天发现人数对不上最后查到是其中一份数据里编号前面多了个零字符串比较之下全军覆没。集合运算不会告诉你哪条数据格式有问题它只会安静地把不相等的东西排除掉然后给你一个看起来很整齐、实际上有偏差的答案。从那以后我每次做名单比对都强制先把两边各抽十条出来肉眼对一遍格式再跑运算多花的那两分钟比事后翻日志省心得多。这份《实验一集合交并差》的资料把三种运算的推演过程、边界情况和典型用例完整走了一遍包括空集、方向写反、格式不一致这些真实会踩到的点。如果你想把前面这些概念按顺序过一遍手可以从资料包里取用边看边在纸上画几个圈比自己凭空想快得多。希望帮到你。本文还有配套的精品资源点击获取