简介《实验一集合交并差》压缩包面向计算机科学与软件工程相关课程的学习者聚焦数据结构中集合交集、并集与差集的概念理解与编程实现适合在Visual Studio环境下完成课程实验、对照源码复盘或作为算法入门练习。压缩包共8个文件约8.74MB包含3个cpp源文件、3个头文件、1个pptx演示文稿和1个docx实验报告分别承担核心代码实现、接口声明、思路讲解与实验过程记录结构紧凑便于按模块查阅。已有314人学习或下载说明该实验主题在数据结构入门阶段具有较稳定的参考需求。资源内容覆盖集合初始化、交并差运算、结果验证以及基于数组、链表、哈希表等结构的实现思路并涉及时间与空间复杂度分析可帮助读者把课堂概念落到可运行代码并对照演示文稿与报告梳理实验流程、检查结果正确性。1. 集合交并差从一个「谁跟谁重叠」的问题说起三个同学凑在一起核对社团名单A 说想知道哪些社团咱俩都报了B 说想知道两边的社团合起来一共涉及多少家C 说想知道自己报了而 A 没报的是哪些。这三句话其实就是集合交并差的全部日常用法交集找共同并集合并去重差集做排除。名字取自数学课本作用却是程序里最耐用的三种「比对关系」几乎每一处筛选、去重、对账的代码里都藏着它的影子。这份名为实验一的资料把集合的交、并、差整理成一个压缩包围绕定义、写法和实验过程中容易出错的地方展开。值得花几分钟搞懂它是因为往后遇到标签筛选、好友推荐、权限核对、数据对账翻来覆去都是这三种运算的组合认得它们很多需求描述会一下变得清晰。2. 为什么要有交集并集差集三种关系不是三种算法很多人第一次看到 ∩、∪、− 这三个符号第一反应是「又是一套要背的记号」。可换个角度看它们并不是三种计算技巧而是三种提问方式交集问的是「两边都有的有哪些」并集问的是「合起来一共有哪些」差集问的是「这边有、那边没有的有哪些」。同一个数据集换一种问法答案的用途就完全不同。这也是为什么这三种运算是成组出现的。只要你在处理两个集合之间的关系问题必然落在这三类里跑不出第四种。理解了这一点再看到某个需求写着「取共同标签」「合并去重」「排除已处理」你就不会急着写循环而是先判断它属于哪一种关系。2.1 交集把「同时满足」变成一次筛选交集的定义很直白同时属于 A 和 B 的所有元素组成的集合记作 A ∩ B。举个具体例子A {1, 2, 3, 4}B {3, 4, 5}那么 A ∩ B {3, 4}。只有 3 和 4 同时出现在两边。这里有一个很多人做实验时才注意到的性质交集的结果一定是两边集合的子集所以它的元素个数永远不会超过两边中较小的那个。这个性质看起来平淡实际很有用——当你在代码里想优化性能时它告诉你「以较小的集合为基准去遍历」是安全的因为答案最多也就那么大。交集最常见的用途是找共同点。两个用户都关注的账号、两台机器都安装的软件包、两个订单里都出现的商品、接口要求的权限和调用方实际拥有的权限。这类问题的共同特征是「必须同时满足」一旦有一边缺失就不该出现在结果里。用交集表达逻辑和目标是一一对应的不需要额外的判断条件。还有一个容易被新手忽略的情况交集为空。空结果不是失败它本身就是一个有信息量的答案——说明两边完全没有重叠。做数据对账时「交集为空」往往比「交集有几百条」更值得警觉因为它通常意味着某一边的数据源出了问题而不是业务上真的毫无关联。2.2 并集合起来算总数但同一个人只算一次并集是把两个集合的元素合并在一起重复的只保留一份记作 A ∪ B。还是拿 A {1, 2, 3, 4}、B {3, 4, 5} 举例A ∪ B {1, 2, 3, 4, 5}3 和 4 只出现一次。这里最关键的是「重复只算一次」这个约定。如果只是想简单地把两个列表拼起来重复元素照样保留那得到的是拼接不是并集。两者的区别在统计总数时会暴露得非常明显。假设 A 有 4 个人、B 有 3 个人其中 2 个人两边都在那么并集是 5 个人而简单拼起来会数出 7。由此可以推出一个很实用的关系式|A ∪ B| |A| |B| − |A ∩ B|。其中绝对值表示集合的元素个数。把两边人数相加重叠的那部分被算了两次所以要减掉一次。这个式子在很多「去重统计」的场景里是心算级别的工具比如两个部门联合报人数、两个渠道合并统计覆盖用户数。并集的另一个常见用途是合并多来源的数据。三份名单要合成一份完整名单、多个配置文件要合并成一份有效配置、几个分片的结果要汇总成一个结果集——只要诉求是「不漏、不重」并集就是标准答案。2.3 差集排除法的正规写法差集问的是「属于 A 但不属于 B 的元素有哪些」记作 A − B。用前面的例子A − B {1, 2}B − A {5}。这两个结果完全不同因为差集是有方向的。方向性是这个运算最容易被低估的地方。日常语言里说「去掉已处理的」听上去含糊落到代码里必须明确是「全量减去已处理」还是「已处理减去全量」。写反了不会报错只会安静地给出一个空结果或者一个莫名其妙的集合。这类 bug 没有异常、没有日志排查起来相当折磨很多人的血泪经验都来自这里。差集在实际系统里的出镜率可能比交集还高。全量用户减去已激活用户就是待激活名单白名单减去黑名单就是实际生效的名单昨天的数据减去今天的数据就是消失的记录目标状态减去当前状态就是还需要执行的动作。这些需求的共同句式是「从谁里面扣掉谁」正好对应 A − B 的结构。差集还能组合出更精细的表达。比如「只报了其中一个社团的人」可以写成 (A − B) ∪ (B − A)也就是两边各自减去对方再合并。这个组合有个专门的名字叫对称差下一章会专门讲它为什么容易和并集搞混。把三种运算放在一起看会发现它们其实共用同一套原始信息哪些元素只在左边、哪些只在右边、哪些两边都有。交集取「两边都有」差集取「只在左边」并集则把三类全收。理解了这个底层结构后面看任何实现方式都不会觉得突兀。3. 交并差在代码里怎么落地位运算、哈希与归并三条路线概念清楚之后下一个问题是怎么让机器真的算出来。这一步的选择比很多人想象的更重要同一组数据、同样三种运算换一种实现路线性能可能差几十倍。小数据上随便写都能跑通数据量一上来就出事翻车现场通常出现在实验验收或者线上压测的时候。下面三条路线各有明确的适用边界不存在「哪个最好」只有「哪个配这套数据最合适」。看的时候重点留意两件事元素长什么样以及数据是不是本来就有序。这两个条件基本决定了该走哪条路。3.1 位运算路线把集合压成一串 0 和 1如果集合里的元素都是小范围的整数比如学号 1 到 64、星期几、状态位、权限编号那么可以把整个集合压缩成一个整数的二进制位第 i 位是 1 表示元素 i 在集合里是 0 表示不在。这样一来交集、并集、差集就变成了按位与、按位或、按位与非。# 用整数的二进制位表示集合第 i 位为 1 表示元素 i 存在 a 0b1011 # 集合 {0, 1, 3} b 0b0110 # 集合 {1, 2} inter a b # 交集0b0010 - {1} union a | b # 并集0b1111 - {0, 1, 2, 3} diff a ~b # 差集 A - B0b1001 - {0, 3} sym a ^ b # 对称差0b1101 - {0, 2, 3}是按位与只有两边同一位都是 1 才保留对应交集|是按位或只要有一边是 1 就保留对应并集a ~b是先对 b 取反再与 a 相与效果就是「a 有而 b 没有」对应差集。这里要特别注意别把差集写成a ^ b异或得到的是对称差等价于 (A − B) ∪ (B − A)比 A − B 多了「只在 B 里」的那部分是个高频错误。这条路线最大的优点是快和省一次按位操作同时处理几十个元素内存占用几乎可以忽略判断「某个元素在不在」也只是(a i) 1一句话。代价是适用范围窄元素必须能映射成连续的小下标范围一大比如编号到了百万级就会浪费大量空位反而不划算。3.2 哈希集合路线通用好写但吃内存绝大多数场景下元素不是整齐的小整数而是字符串、对象、ID。这时候通用做法是用哈希集合底层是一张哈希表插入和查找平均是常数时间。Python 的set、Java 的HashSet、Go 的map[T]struct{}都属于这一类。A {1, 2, 3, 4} B {3, 4, 5} inter A B # 交集 {3, 4} union A | B # 并集 {1, 2, 3, 4, 5} diff A - B # 差集 {1, 2}方向是从 A 里扣 B sym A ^ B # 对称差 {1, 2, 5} # 数据量偏大时更省内存的写法只在较小的集合上迭代 small, big (A, B) if len(A) len(B) else (B, A) inter2 {x for x in small if x in big} # 结果与 A B 相同上面这段里、|、-、^分别对应交集、并集、差集、对称差写法已经和数学符号非常接近。最后两行展示了一个实用优化计算交集时以较小的集合为驱动方遍历次数等于较小集合的大小而不是把两个集合都过一遍。差集就不能这样随意调换顺序了。A - B必须以 A 为驱动方写成B - A得到的是另一个集合。图省事把两个操作数对调是新手最容易犯却也最难自查的错误之一因为结果依然是一个格式合法的集合不会报错。这条路线的主要风险来自哈希本身哈希函数设计得不好大量元素会挤进同一个桶查找退化成线性扫描性能瞬间滑坡此外哈希表的装载因子、扩容机制都会带来额外的内存开销处理上千万条数据时这部分开销相当可观。3.3 排序归并路线有序数据的顺势而为如果两个集合都已经排好序或者你有办法先排序那么一趟双指针扫描就能同时算出交集、并集和差集而且结果天然是有序的。这种做法在数据库、日志分析、离线批处理里非常常见。def merge_ops(a, b): 前提a、b 均为升序排列返回交集、并集、差集 A-B i j 0 inter, union, diff [], [], [] while i len(a) and j len(b): if a[i] b[j]: # a 当前元素偏小只可能进并集和 A-B union.append(a[i]); diff.append(a[i]); i 1 elif a[i] b[j]: # b 当前元素偏小只进并集 union.append(b[j]); j 1 else: # 两边相等进并集和交集 union.append(a[i]); inter.append(a[i]); i 1; j 1 # 收尾某一方剩余部分全部进并集A 的剩余部分还要进 A-B while i len(a): union.append(a[i]); diff.append(a[i]); i 1 while j len(b): union.append(b[j]); j 1 return inter, union, diff核心思路是因为两边都有序当前两个指针指向的元素谁小谁就一定是「只在这一边」的元素相等时就是「两边都有」。三种结果在一次扫描中同步产出互不干扰。函数末尾的两个收尾循环负责处理一方已经走完的情况A 剩下的元素既属于并集也属于 A − BB 剩下的元素只属于并集。这条路线的时间成本主要落在排序上通常是 O(n log n m log m)归并本身只有 O(n m)。如果数据本来就有序或者存在于一个天然有序的结构里比如数据库索引、有序集合类型那这一步就省掉了效率非常高额外空间也只需要存放结果。提示如果实验里要求结果按某种顺序输出排序归并路线顺带就解决了排序问题往往比先算再排更省事。3.4 三条路线怎么选一张对照表路线适合的数据时间成本额外空间典型翻车点位运算小范围连续整数、状态位一次按位操作处理整字几乎为 0元素范围一大就浪费空位差集误写成异或哈希集合任意可哈希元素随机访问多平均线性取决于哈希质量有哈希表开销哈希退化差集方向写反排序归并已有序或需有序输出排序主导归并线性仅结果本身忘记收尾处理剩余元素输入未排序选择时可参考这个顺序来想先看元素是不是小整数是就优先位运算再看数据是否已经有序有序可直接归并两者都不满足就用哈希集合作为默认方案。这个判断顺序不绝对但在多数情况下能省掉一次返工。4. 常见误区与易混概念差集方向、对称差、去重和子集概念本身不难真正让人懵的是几个相邻概念之间的边界。它们长得像、名字像、在某些场景下结果还恰好一样于是特别容易混。下面五条是初学者最常撞上的每一条都按「为什么混、怎么分」来说清楚。4.1 差集有方向A 减 B 不等于 B 减 A易混点在于减号在算术里是可交换的虽然减法也不可交换但整数减法结果至少是数字很多人下意识把集合差也当成对称操作。为什么混因为「去掉」这个动作在自然语言里没有主语谁去掉谁说出来都通顺。怎么区分永远把差集读成一句完整的话——「从 A 中扣掉 B 里的元素」。写代码时先确定谁是全集、谁是要扣掉的部分再决定操作数顺序。验算方式也很简单A − B 的结果里不允许出现任何 B 的元素如果出现了说明方向反了。4.2 对称差不是并集也不是交集对称差记作 A △ B 或者 A ⊕ B含义是「只属于其中一边的元素」也就是 (A − B) ∪ (B − A)。它跟并集长得像因为都包含「两边都有」之外的成分跟交集也沾边因为都跟「重叠部分」有关。为什么混因为很多人记成「把重叠的去掉」然后顺手写成了「并集去重」而并集恰恰保留了重叠部分。怎么区分拿 A {1,2,3}、B {3,4} 试一下。并集是 {1,2,3,4}对称差是 {1,2,4}差别就在 3 这个重叠元素上——并集留对称差删。判断标准是结果里该不该出现「两边都有」的元素。该出现是并集不该出现是对称差。4.3 集合去重和数据库去重不是一回事在数据库里写SELECT DISTINCT或者UNION确实能把重复行去掉看起来和集合去重是一回事。但比较的粒度完全不同集合去重比较的是元素本身一行数据就是一个元素数据库去重比较的是整行所有列的组合两行只要有一列不同就被视为两条不同的记录。为什么混因为「去重」这个词在两边都叫去重。怎么区分问一句「重复的判断标准是什么」。如果标准是单个值相同那是集合语义如果标准是一组字段全都相同那是行语义用DISTINCT或者GROUP BY更合适。顺带说一句UNION自带去重而UNION ALL不去重这个细节在合并多份数据时经常被忽略结果行数对不上还找不到原因。4.4 子集、真子集、属于三个符号别写反属于∈描述的是元素和集合的关系比如 3 ∈ {1,2,3}子集⊆描述的是集合和集合的关系比如 {1,2} ⊆ {1,2,3}真子集⊂在子集基础上要求两个集合不相等。三者的左边放什么是它们最本质的区别。为什么混因为符号都是弯弯绕绕的曲线抄笔记时极易写串而且口语里常说「3 包含在里面」把两层关系糊成了一句。怎么区分看左边是单个元素还是花括号。左边是大括号包着的集合就往子集那边想左边是裸的元素就是属于。写代码时对应的是in和issubset两个不同层级的判断不要互相替代。4.5 交集运算和数据库的 INNER JOIN 不在一个层面INNER JOIN看起来也在做「两边都有的匹配」和交集很像。但 JOIN 是行与行的配对一对多关系会让结果行数膨胀左表一条记录匹配右表三条结果就是三条。而集合交集永远不会超过较小集合的元素个数因为它是按值判断归属天然去重。为什么混因为初学者往往先用 JOIN 实现筛选发现结果变多了再回头找原因。怎么区分看需求要的是「匹配的记录明细」还是「共有的取值列表」。要明细、要保留一对多关系、要带上其他字段用 JOIN只要「哪些值同时存在」用交集简单直接还不膨胀。5. 实验里最容易踩坑的细节空集、重复元素、顺序与类型定义看懂了、代码也写出来了实验还是可能过不了。问题常常不在算法本身而在几个边界细节上。这些点都不复杂但每一个都能让结果对不上而且报错信息往往什么也不说只能靠人工比对。5.1 空集参与运算四条规则要刻在脑子里空集是集合运算里的零元但它的行为和数字 0 并不完全一样值得单独记A ∩ ∅ ∅A ∪ ∅ AA − ∅ A∅ − A ∅。前三条基本符合直觉容易出错的是最后一条——空集减去任何集合还是空集因为本来就没有元素可以保留。为什么这四条重要因为实验数据里经常出现空输入的情况比如某个名单文件为空、某个筛选条件筛掉了全部记录。这时候如果代码里写了「取结果的第一个元素」或者「假设结果非空」就会直接崩溃。更隐蔽的情况是某些实现会把空集当成「无限定」从而返回全集这个行为差异在不同库之间未必一致动手前最好先确认。处理建议很简单在运算之前先判空明确空输入应该走哪条分支运算之后再判空把「结果为空」当作一个正常分支处理而不是异常。这两步写起来不到五行能挡掉实验里相当一部分莫名其妙的失败。5.2 重复元素集合和多重集是两种东西集合的一个基本约定是元素不重复。如果输入数据里有重复项转成集合的那一刻它们就被合并了后面再怎么算都看不到重复的痕迹。这在做「有哪些不同值」时正好在做「每个值出现几次」时就彻底跑偏。为什么容易踩坑因为现实数据里重复太常见了一份日志里同一个用户操作了好几次一份订单里同一个商品出现了多行。如果实验要求统计「某个用户操作了几次」用集合会永远得到 1看起来数据全对结论全错。区分办法是看问题问的是「有没有」还是「有多少次」。前者用集合后者需要用计数的结构比如计数器、多重集或者干脆用哈希表记录每个元素出现的次数。这两种语义在名字上很像在实现上完全是两套东西不要混用。5.3 顺序与输出集合本身无序但结果往往要稳定集合在数学上没有顺序在多数语言的实现里也没有保证的顺序。这意味着同一份数据、同一段代码两次运行打印出来的结果顺序可能不一样尤其当元素是字符串时哈希随机化会让顺序每次都变。这个特性在实验里造成的麻烦相当典型代码逻辑完全正确人工核对时却发现输出顺序和参考答案不一致于是一遍遍改算法其实只是在跟一个不存在的顺序较劲。更麻烦的是有些自动化比对工具是按行比较的顺序一变就判定失败。解决办法不复杂在输出之前显式排序。排完之后再打印或者写文件结果就稳定了。如果实验明确要求某种顺序比如按学号、按字典序那就在输出前统一处理而不是指望运算过程自带顺序。排序归并那条路线天然有序用它可以省掉这一步这也是它在实验场景里比较讨喜的原因之一。5.4 元素类型与相等判断0、0.0 和 0 不是同一个集合判断元素是否重复靠的是相等比较。而相等这件事在不同类型之间是有讲究的。在某些语言里整数 0 和浮点数 0.0 被判为相等哈希值也相同于是一个集合里放进去两个最后只剩一个但字符串 0 和数字 0 完全不相等会老老实实算两个元素。为什么这个细节容易翻车因为数据来源往往不统一有的从文件读进来是字符串有的从计算得出是数字混在一起放进集合就会出现「明明有两条结果只有一条」或者「明明是同一条被算成了两条」的玄学现象。排查的时候如果不打印类型只看值很容易被误导。处理思路是统一类型在放进集合之前把数据规整成同一种表示比如全部转成字符串或者全部转成整数。转换的时机要一致要么在读取时统一转要么在运算前统一转最忌讳一部分转了一部分没转。这一步多做十秒钟能省下半小时的困惑。5.5 大集合的性能坑别在循环里反复做差集逻辑上正确、性能上灾难是实验里最不值得的失分点。典型写法是在一个循环里每处理一个元素就做一次全量差集或者全量交集把线性操作叠成了平方级。数据量小的时候看不出来稍微大一点就跑不动。改法很直接把与循环变量无关的运算提到循环外只算一次结果复用。如果确实需要在循环里反复判断「某个元素在不在另一个集合里」那就要确保那个集合是哈希结构查找是常数时间而不是每次都遍历一遍。还有一类开销来自不必要的中间集合先算并集、再算交集、再算差集每一步都生成一个新的完整集合内存峰值可能是最终结果的几倍。能合并成一次遍历的就合并成一次确实要分步的至少确认中间结果会被及时释放。注意实验里如果给了数据规模范围先按上限估一遍操作次数再决定实现路线比写完再优化省事得多。6. 什么时候该用交并差什么时候别硬套四个判断和一个权限例子前面讲的都是「怎么算对」落到实际选择上还有一个问题这个场景到底该不该用集合运算。判断标准其实不复杂看三个条件就够了——元素是否天然唯一、顺序是否重要、是否需要记录次数。三个都满足「唯一、不关心顺序、不记次数」集合运算就是最合适的工具只要有一条不满足就该考虑别的结构。举个具体的例子。某系统做权限核对用户身上挂着一组权限标识某个接口要求一组最小权限。判断能不能访问本质是问「要求的权限是不是都被用户拥有了」用集合语言说就是「要求集合减去用户集合结果为空」。owned {order:read, order:write, user:read} # 用户实际拥有的权限 required {order:write, order:export} # 接口要求的最小权限 missing required - owned # 差集方向从「要求」里扣「已有」 if not missing: print(允许访问) else: print(缺少权限, sorted(missing)) # 输出前排序保证结果稳定required - owned得到的就是用户还缺哪些权限为空则通过非空则可以直接把缺失项返回给调用方。这里方向千万不能反写成owned - required得到的是「用户拥有但接口不需要的权限」永远不为空权限校验会全部放行属于那种不会报错但后患无穷的 bug。什么情况下别硬套也有几个明确信号。需要统计每个元素出现几次那是计数问题得用计数器需要保留元素进入的先后顺序那是有序序列得用列表或者有序结构需要表达「一个元素对应多个值」的层级关系那是映射或者图集合表达不了需要模糊匹配、相近匹配那涉及字符串相似度集合只能判断完全相等。把这些场景硬塞进集合运算代码会变得别扭结果也未必正确。场景合适的选择原因找两个名单的共同项交集只关心是否同时存在天然去重合并多份来源的数据并集要求不漏不重从全量里排除已处理项差集有明确的全集和被减项统计每个值出现次数计数器 / 多重集集合会丢掉重复信息需要保持原始顺序列表 / 有序结构集合本身不保证顺序一对多的关联查询关联表 / 连接操作集合无法表达记录明细真正做实验的时候最容易出问题的往往不是算法本身而是动笔之前没把「谁是全集、谁是要扣掉的、结果要不要排序」这三件事写清楚。从那以后我每次碰到差集都会先在草稿上写一句「从 X 里扣掉 Y」再把这句中文逐字翻译成代码多加一行断言检查结果确实不含 Y 的任何元素。这个习惯看着笨但它替我挡掉过好几次方向写反的事故。希望帮到你。本文还有配套的精品资源点击获取
)
