★ FEATURED ARTICLE 简介这份资源面向数据结构与算法课程的初学者及软件工程相关专业学生围绕集合的交集、并集、差集三种基本运算提供一套可在 Visual Studio 环境下直接运行的实验工程帮助读者通过动手编码理解集合的存储结构与运算逻辑。压缩包共 8 个文件约 8.74MB包含 3 个 cpp 源文件、3 个 h 头文件以及 1 份 pptx 实验讲解和 1 份 docx 实验报告源码与头文件对应集合类的定义与实现文档则梳理概念、伪代码与结果验证思路。资源已有 314 人学习下载适合课堂实验复现与课后巩固。读者可据此对照实现基于数组、链表或哈希表的集合操作比较不同结构在时间与空间复杂度上的差异并借助配套报告与课件完成实验整理与结果分析为后续算法设计打下基础。1. 集合交并差一个压缩包标题背后藏着的离散数学基本功看到「实验一集合交并差.zip」这个标题很多人第一反应是——这不就是数据结构课第一次上机作业吗确实集合的交、并、差是离散数学和数据结构课程里最经典的入门实验几乎每个计算机相关专业的学生都会在第一个实验课上遇到它。但别急着划走这个看似简单的题目在实际工程里的分量远比想象中重数据库的 JOIN 操作本质上是集合运算推荐系统的候选集过滤靠的是差集权限系统的角色合并用的是并集去重逻辑的核心就是交集判定。换句话说集合交并差不是「学完就扔」的课堂练习而是贯穿后端开发、数据处理、算法设计的基础设施级操作。这个实验通常要求实现两个集合的交集、并集、差集运算输入可能是整数集合、字符串集合也可能是用数组、链表或哈希表存储的元素序列。核心考察点不在于「能不能算对」而在于「用什么数据结构算、时间复杂度控制在什么量级、边界情况怎么处理」。如果你正在翻这个压缩包大概率是要交作业、要复现实验、或者想拿它练手 C/C 的指针和内存管理。接下来的内容会从选型、实现、参数、踩坑四个维度把它拆透新手能照着跑通熟手能看到自己当年踩过的那些坑。2. 集合交并差的实现选型数组、链表还是哈希表2.1 三种存储结构的取舍逻辑做集合运算实验第一个要做的决定不是写代码而是选容器。常见的选择有三种有序数组、链表、哈希表。它们直接决定了交并差的时间复杂度和代码复杂度。有序数组的优势在于交集和并集可以用双指针一趟扫完时间复杂度 O(mn)空间只需要结果集大小。缺点是插入和删除要挪元素如果实验要求动态增删集合元素数组就不太顺手。链表的好处是插入删除 O(1)但求交集时要么双重循环 O(m×n)要么先排序再归并代码量明显上去。哈希表则是「用空间换时间」的典型把第一个集合全部塞进哈希表遍历第二个集合时 O(1) 判断是否存在交集和差集都能压到 O(mn)并集也就是两次插入的事。我一般会这样建议如果实验只要求「给定两个集合输出交并差结果」不做动态增删直接用有序数组加双指针代码最短、最容易讲清楚原理。如果实验要求支持动态插入删除或者元素规模上万哈希表更稳。链表适合作为「对比实验」出现用来展示不同结构对性能的影响但不建议作为主实现调试指针太费时间。存储结构交集复杂度并集复杂度差集复杂度适用场景有序数组O(mn)O(mn)O(mn)静态集合、结果输出型实验链表O(m×n) 或 O(mn) 排序后O(mn) 排序后O(m×n) 或排序后归并动态增删频繁、教学对比哈希表O(mn)O(mn)O(mn)大规模数据、动态集合这张表里的复杂度有个前提有序数组和链表排序后的 O(mn) 都要求输入已经有序。如果输入无序排序本身要花 O(m log m n log n)这一点在写实验报告时经常被忽略答辩时容易被追问。2.2 用 C 语言实现有序数组版交并差的最小骨架下面这段代码是「有序数组 双指针」的最小可运行版本假设两个集合已经升序排列且无重复元素。实验里如果输入无序先调一个排序函数即可。#include stdio.h #include stdlib.h // 交集双指针同步推进相等则收录 int intersect(int a[], int m, int b[], int n, int out[]) { int i 0, j 0, k 0; while (i m j n) { if (a[i] b[j]) { i; // a 当前元素小a 指针后移 } else if (a[i] b[j]) { j; // b 当前元素小b 指针后移 } else { out[k] a[i]; // 相等收录到结果集 i; j; } } return k; // 返回交集元素个数 } // 并集谁小收谁相等只收一次 int unionSet(int a[], int m, int b[], int n, int out[]) { int i 0, j 0, k 0; while (i m j n) { if (a[i] b[j]) out[k] a[i]; else if (a[i] b[j]) out[k] b[j]; else { out[k] a[i]; i; j; } // 相等去重 } while (i m) out[k] a[i]; // 收尾剩余元素 while (j n) out[k] b[j]; return k; } // 差集 A-B只保留在 A 中且不在 B 中的元素 int difference(int a[], int m, int b[], int n, int out[]) { int i 0, j 0, k 0; while (i m j n) { if (a[i] b[j]) out[k] a[i]; // a 小说明不在 b 中 else if (a[i] b[j]) j; // b 小跳过 b else { i; j; } // 相等剔除 } while (i m) out[k] a[i]; // b 耗尽a 剩余全收 return k; }三个函数的逻辑完全一致两个指针分别扫两个有序数组谁小动谁相等时按运算类型决定收录还是跳过。交集在相等时收录并双指针前进并集在相等时只收一次差集在相等时直接跳过。收尾的 while 循环处理「一个数组先扫完」的情况并集和差集需要把剩余元素全部搬进结果交集则不需要。参数上唯一需要注意的是输出数组out的容量。交集最大不超过min(m,n)并集最大mn差集最大m。实验里如果开固定大小数组按这个上界开就不会越界。另外这段代码假设输入无重复如果实验数据允许重复元素交集和并集都要加去重判断否则结果里会出现重复项这是最常见的翻车点之一。2.3 哈希表版本的实现要点与参数设置如果实验要求处理大规模数据或者动态集合哈希表版本更合适。核心思路是把集合 A 的所有元素插入哈希表然后遍历集合 B用查表结果决定交、并、差。下面用 Python 演示逻辑因为哈希表在 Python 里就是 dict/set代码最直观C 语言手写哈希表则要额外处理冲突和扩容。def set_operations(a, b): # 用 set 做哈希表插入和查询平均 O(1) sa set(a) sb set(b) inter sa sb # 交集两边都有的元素 union sa | sb # 并集任一边有的元素 diff_ab sa - sb # 差集 A-B在 A 不在 B diff_ba sb - sa # 差集 B-A在 B 不在 A return sorted(inter), sorted(union), sorted(diff_ab), sorted(diff_ba)这段代码短到几乎不需要解释但有两个参数层面的细节值得说。第一set的底层是哈希表平均查询 O(1)但最坏情况大量哈希冲突会退化到 O(n)实验数据如果故意构造冲突性能会明显下降这是哈希方案的理论边界。第二输出前我加了sorted因为set的遍历顺序不保证实验如果要求结果按升序输出不排序直接打印会得到「看起来随机」的顺序答辩时容易被质疑结果不对。如果实验要求用 C 手写哈希表关键参数是桶数组大小和负载因子。桶大小一般取比元素数量大的最小质数负载因子控制在 0.7 以下超过就扩容。冲突处理用链地址法最稳开放寻址在删除元素时容易出「墓碑」问题实验里不推荐。3. 从输入解析到结果输出把实验跑通的完整步骤3.1 输入格式的约定与解析代码集合实验的输入格式通常有两种一种是直接给两行整数空格分隔另一种是给集合大小再给元素。不管哪种解析阶段最容易出的问题是「元素个数和实际读入不一致」以及「行尾换行符处理不当」。下面以「第一行两个整数 m n第二行 m 个元素第三行 n 个元素」为例写解析骨架。#include stdio.h #define MAXN 10005 int a[MAXN], b[MAXN]; int main() { int m, n; // 先读两个集合的大小 if (scanf(%d %d, m, n) ! 2) { fprintf(stderr, 输入格式错误缺少集合大小\n); return 1; } // 读集合 A for (int i 0; i m; i) { if (scanf(%d, a[i]) ! 1) { fprintf(stderr, 集合 A 第 %d 个元素读取失败\n, i 1); return 1; } } // 读集合 B for (int i 0; i n; i) { if (scanf(%d, b[i]) ! 1) { fprintf(stderr, 集合 B 第 %d 个元素读取失败\n, i 1); return 1; } } // 后续调用 intersect / unionSet / difference return 0; }这段解析代码的关键在于每个scanf都检查返回值。很多实验代码直接scanf(%d, x)不判断输入少一个数时变量保持未初始化值后续运算结果莫名其妙调试半天找不到原因。加上返回值判断和错误提示出问题时至少知道是第几个元素读失败。MAXN按实验数据规模设定一般题目会给上限没给就按 10000 开超了再调。如果输入元素可能重复解析完之后要先做一次去重。去重可以在读入时用哈希表判重也可以读完排序后相邻去重。前者适合元素范围大的情况后者适合元素范围可控、要求输出有序的情况。实验报告里最好写明「输入是否保证无重复」这是结果正确性的前提。3.2 结果输出的格式控制与空集处理输出阶段看似简单但空集是最容易被忽略的边界。交集为空时输出什么空行、{}、还是NULL不同实验的评测脚本要求不一样写之前一定要看清楚。下面是一个稳妥的输出函数统一用空格分隔、行末换行、空集输出空行。void printSet(int arr[], int len) { if (len 0) { printf(\n); // 空集输出空行避免评测脚本判格式错 return; } for (int i 0; i len; i) { if (i 0) printf( ); printf(%d, arr[i]); } printf(\n); }这个函数里if (i 0) printf( )的写法保证行首没有多余空格、行末没有尾随空格。很多在线评测系统对尾随空格敏感1 2 3和1 2 3会被判成不同输出这是血泪经验。空集输出空行而不是直接 return是因为有些评测脚本按行读取结果少一行会导致后续结果错位。如果实验要求输出集合的势元素个数在 printSet 之前单独打印len即可。如果要求按降序输出把遍历方向反过来或者输出前对结果数组做一次降序排序。这些格式细节在实验指导书里通常写得很简略但恰恰是丢分重灾区。3.3 用测试用例验证交并差结果的正确性代码写完不等于实验做完验证环节至少要覆盖四类用例普通有交集、完全不相交、一个集合是另一个的子集、两个集合完全相同。下面这组用例可以直接拿来跑。# 用例1普通有交集 # 输入3 4 / 1 2 3 / 2 3 4 # 期望交集 2 3并集 1 2 3 4差集 A-B 为 1 # 用例2完全不相交 # 输入3 3 / 1 2 3 / 4 5 6 # 期望交集为空并集 1 2 3 4 5 6差集 A-B 为 1 2 3 # 用例3子集关系 # 输入2 4 / 1 2 / 1 2 3 4 # 期望交集 1 2并集 1 2 3 4差集 A-B 为空 # 用例4完全相同 # 输入3 3 / 1 2 3 / 1 2 3 # 期望交集 1 2 3并集 1 2 3差集 A-B 为空这四类用例覆盖了双指针逻辑的所有分支相等收录、不等跳过、一方先耗尽、双方同时耗尽。跑通这四组基本逻辑就不会有大问题。如果实验还要求处理重复元素再加一组「A 有重复、B 有重复」的用例验证去重逻辑是否生效。验证时建议把输入输出重定向到文件用diff对比期望输出比肉眼核对靠谱得多。4. 集合交并差实验的避坑清单五个高频翻车点4.1 输入未去重导致结果出现重复元素现象交集或并集结果里出现两个相同的数和期望输出对不上。原因集合的定义要求元素互异但输入数据可能带重复代码直接按数组处理没有去重。解决读入后先排序再相邻去重或者用哈希表判重后再存入数组。去重这一步放在解析之后、运算之前不要混在交并差函数里否则三个函数都要重复写去重逻辑容易漏。4.2 输出数组容量按输入大小开导致越界现象并集结果末尾出现乱码或者程序在某些用例下崩溃。原因并集最大长度是 mn但输出数组只开了 max(m,n) 的大小元素多的时候写越界。解决并集的输出数组按 mn 开交集按 min(m,n) 开差集按 m 开。如果实验用动态内存malloc的大小按这个上界算用完记得free。C 语言里数组越界不一定立刻崩可能只是悄悄覆盖了相邻变量这种 bug 最难查。4.3 双指针收尾逻辑写反导致差集多收元素现象差集 A-B 的结果里混进了本应属于 B 的元素。原因收尾的 while 循环写成了「两个数组剩余都收」但差集只应该收 A 的剩余B 的剩余要丢弃。解决交集不需要收尾循环并集两个剩余都收差集只收 A 的剩余。三个函数的收尾逻辑各不相同抄代码时最容易整段复制导致差集写错。写完逐个对照定义检查一遍。4.4 哈希表版本忘记处理哈希冲突导致查询失败现象哈希表版本在数据量大时交集结果偏少某些明明存在的元素查不到。原因手写哈希表时冲突处理有 bug比如链地址法的链表插入写错、开放寻址的探测序列不完整。解决优先用语言内置的 set/dictC 语言手写时先用小数据量十几个元素验证每个元素都能正确查到再放大数据量。负载因子超过 0.7 必须扩容不扩容冲突率飙升查询退化到 O(n)。4.5 输出格式尾随空格或空集处理不一致现象本地跑结果正确提交评测判格式错误。原因行末多了空格或者空集输出和评测脚本期望不一致。解决输出循环用「第一个元素不加空格、后续元素前加空格」的写法空集按实验要求输出空行或特定标记。提交前用cat -A看输出文件的行尾确认没有多余空格和^M之类的不可见字符。5. 把集合运算用到工程里从实验代码到可复用模块的进阶技巧实验代码跑通只是起点真正有价值的是把它整理成可复用的模块。我一般会做三件事把交并差封装成带返回长度的函数、把去重和排序抽成独立工具函数、用统一的结构体管理集合。下面这个结构体版本比裸数组更适合后续扩展。typedef struct { int *data; // 元素数组 int size; // 当前元素个数 int capacity; // 容量上限 } IntSet; // 创建集合capacity 按预估最大规模设定 IntSet* setCreate(int capacity) { IntSet *s (IntSet*)malloc(sizeof(IntSet)); s-data (int*)malloc(sizeof(int) * capacity); s-size 0; s-capacity capacity; return s; } // 释放集合先释放 data 再释放结构体本身 void setFree(IntSet *s) { if (s) { free(s-data); free(s); } }结构体封装的好处是容量和长度绑在一起传递调用方不用每次额外传 size 参数减少「传错长度」的低级错误。setCreate的 capacity 参数按实验数据上界设定如果预估不准后续可以加一个setReserve做扩容。setFree里先释放data再释放s顺序反了会访问已释放内存这是 C 语言内存管理的经典坑。进阶验证方面建议给模块加一组随机对拍测试用 Python 的 set 运算生成期望结果C 模块输出实际结果两者逐行对比。随机数据跑几百组比手工构造用例更能暴露边界问题。对拍脚本的核心逻辑是「生成随机集合 → 调 C 程序 → 调 Python 内置运算 → diff 输出」跑通一次之后每次改代码都重新跑相当于给自己留了后悔药。还有一个容易被忽略的技巧如果实验要求输出集合的势或者判断集合是否相等不要在交并差函数里顺手算单独写setSize和setEqual函数。职责单一的函数更容易测试也更容易在实验报告里讲清楚每个函数的输入输出契约。我见过不少实验代码把所有逻辑塞进 main 函数两百行连在一起出问题只能靠 printf 逐段排查效率极低。最后说一个习惯每次写完交并差先用纸笔把两个小集合的双指针移动过程画一遍确认每一步的指针位置和收录动作。这个动作花不了两分钟但能拦住大部分逻辑错误。集合运算的代码短错误往往藏在「相等时该不该同时移动两个指针」这种细节里画一遍比盯着屏幕看十遍管用。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
