简介实验一集合交并差压缩包是一份面向软件工程与数据结构初学者的集合操作实训资源围绕交集、并集、差集三个核心概念在可视化开发环境中提供可运行的编程实现。压缩包共包含八个文件其中三个源程序文件与三个头文件构成完整代码涵盖基于数组、链表、哈希表等多种实现方式另配有演示文稿讲解集合运算原理与伪代码以及实验报告整理初始化、运算执行和结果验证等步骤。包体体积为八点七四兆结构简明便于下载后直接打开研读。目前已有三百一十四人学习浏览适合正在学习算法与数据结构、需要结合代码理解集合运算的学生或开发者使用。通过这套资源使用者可同时获得可编译源码、课件和实验文档既能动手调试验证运算结果又能系统梳理时间与空间复杂度分析思路为后续复杂算法设计奠定扎实基础。1. 集合交并差实验包拆解先跑通再改存储结构最后避几个常见的坑集合交并差听起来只是数学里的基础运算可一旦放到数据结构课程里它就变成了第一个上机实验里最常见的拦路虎集合用数组还是链表存、重复元素要不要去重、差集方向到底是谁减谁、输出是否必须有序题目往往几句话带过试错了才发现全是要命的地方。这份实验一集合交并差.zip就是把这一套完整实现和测试数据打包好的资源解压后能同时看到主程序、集合运算模块、接口头文件、输入样例和报告框架五分钟跑通基础流程再往链式存储或位图方向扩展也比较顺手。适合正在做课程设计的学生也适合想快速拿一份规范实现当参照、再按自己思路改造的开发者。2. 拆包看门道文件结构与三类隐蔽约束2.1 解压后的常见文件布局与分工第一次拿到包不要急着编译先把目录拉出来看一下。这类实验包的命名虽然不同但文件角色通常是一致的典型结构如下实验一集合交并差/ ├── main.c // 主程序读文件、调用运算、输出结果 ├── set_ops.h // 接口声明宏定义与函数原型 ├── set_ops.c // 集合操作实现并、交、差、排序去重 ├── input_a.txt // 集合 A 的输入样例 ├── input_b.txt // 集合 B 的输入样例 ├── Makefile // 可选的编译脚本 └── 实验报告.md // 报告模板这个结构背后有一套清晰的逻辑main.c 只管流程不碰算法细节set_ops.c 只管逻辑不碰文件 IOset_ops.h 是两者的契约。我习惯先把头文件通读一遍因为接口函数签名会直接告诉你这个实验包默认采用了什么样的数据表示。多数包会看到类似下面这样的原型#ifndef SET_OPS_H #define SET_OPS_H #define MAX_SIZE 1024 int union_set(int *a, int na, int *b, int nb, int *out); int intersect_set(int *a, int na, int *b, int nb, int *out); int diff_set(int *a, int na, int *b, int nb, int *out); int sort_unique(int *arr, int n); #endif这里没有全局变量、没有结构体封装函数参数里直接出现int *a int na这种方式说明数组是默认存储结构长度由调用方显式传入。这种设计有一个好处后续若改成链表表示只需把函数内部换掉签名保持不变主程序一行都不用动。读接口的同时也要顺便确认 out 缓冲区由谁分配、容量是否就是 MAX_SIZE否则运行到结果数组末尾时很容易越界写。接着我会去看 main.c确认输入文件的格式。最常见的约定是每行一个整数直到 EOF空行自动忽略。如果 main.c 里出现fscanf(fp, %d, x)这种语句那么空格、Tab、换行都会被自动跳过输入文件里混几个空白符问题不大。真正要小心的是输入文件里带中文说明文字的行或者用逗号分隔的格式这些情况下 fscanf 会把读取位置停在第一个非数字字符上后续读取全部失败表现出来就是集合长度莫名其妙变成 0。2.2 题目没写明的三个隐含约束实验说明往往只给一句话“从文件读两个集合求并、交、差并输出。”但真正动手前有三个隐含约束每一个都会影响实现取舍。第一个是重复元素。数学集合天然去重文件里给的数据却可能包含“2 2 1 3”这种带重复值的序列。如果运算前不去重并集结果的多重性会出问题差集遇到等值但不同下标的情况指针移动也会比预期复杂。所以稳妥做法是把“排序去重”作为所有运算前的必经步骤而不是在并、交、差三个函数里各去重一遍。第二个是元素是否有序。假设输入是有序的算法可以写成线性扫描如果输入无序就必须先排序否则并归结果不会有序与标准答案比对时会因为顺序不同被判错。这个包里的样例数据通常按升序给出但这不是所有题目都成立的约定我一般会在读入后显式调用一次排序去重让自己不依赖“数据恰好有序”这个巧合。第三个是输出方向。并集和交集没有方向问题差集则分为 A-B 和 B-A结果完全不同。实验包 main.c 里通常两个方向都会算出来分别输出有的还会在行首印一个标记“A-B:”。交作业前一定要对着题目确认要的是哪个方向以及输出是否需要保持有序这是评测脚本比对结果时最容易失分的地方。如果包里的 main.c 或头文件和上述假设有出入不要立刻重写。先把已有函数和实验要求逐条对齐列出“题目要求清单”和“包内实现清单”再决定改动范围。很多时候只是输入路径或输出顺序不对改两行就能跑通重写反而会把原本能用的模块拆出新的问题。拿到手先弄清楚这套包是“数组 排序去重 线性归并”还是“链表 动态插入”再做改造效率差别很大。3. 集合存储数组、链表与位图的取舍3.1 有序数组默认情况下最顺手的选择选择哪种存储方式对并、交、差三个运算的代码结构影响很大。先看最典型的方案——用有序数组存集合。数组元素连续排列两个集合各用一个指针从头部开始扫描每一步比较当前元素大小元素相等说明同时在两个集合里出现是交集成员输出后在并集里只写一份两指针同时前进元素不等较小者只属于其中一个集合对并集和差集有意义指针前进一个集合扫描完另一个集合的剩余部分直接接到结果末尾。这种线性归并写起来最短内存布局也友好调试时看一眼数组内容就知道当前指针到了哪里。数组的代价是插入删除需要搬移元素复杂度 O(n)但对这个实验场景来说输入是一次性读入、运算只做查询和输出几乎不需要动态插入这个代价根本碰不到。所以没有任何特殊要求时有序数组是我最推荐的默认选择。数组还有一个容易被忽略的好处排序去重可以直接借助标准库的 qsort 完成不需要手写冒泡或插入排序。手写排序也不是不行只是多了一份出错的机会用 qsort 配合一个比较函数几行搞定而且越界风险低很多。下面的比较函数是很多教科书里都会给的标准写法int cmp_int(const void *p1, const void *p2) { int v1 *(const int *)p1; int v2 *(const int *)p2; return (v1 v2) - (v1 v2); }返回两个 int 差值容易在极端值上溢出用两个比较结果相减避开整数溢出的同时还能让 qsort 在遇到相等元素时返回 0行为符合标准。这个小细节决定了排序去重能否稳定跑通值得单独列出来。3.2 链表和位图各自的适用边界链表表示在概念上更贴近集合“元素数量动态变化”的特性读入阶段不方便预知总元素数时可以一边读一边往链表尾部插入后续需要持续做增量并集时插入也是 O(1)。但链表的缺点同样明显两个有序链表做线性归并每一步都要通过指针访问下一个节点调试时没法像数组那样直接看到一整块内存还要自己写辅助函数打印链表。若实验没有特别指定“必须用链表”我不建议为了展示技巧而选它那会平白增加工作量。位图表示则是另一种极端路线。当集合元素的值域小而密集比如元素都是 0 到 1023 之间的整数时可以用一个长度为值域的布尔数组表示集合元素 i 存在就把 present[i] 置为 1。这样一来并集就是两张位图逐位取或交集就是逐位取与差集就是 A 与 B 的按位取反再相与。三种运算都变成一重循环代码极其紧凑时间复杂度 O(值域)。但位图有一个致命前提值域不能太大。如果输入数据里出现 1 和 10^9位图就要开十亿个元素内存直接失控。所以位图适合值域小、元素多的场景反之就是灾难。3.3 这个实验包默认走的是哪条路从接口函数签名基本能断定包里默认实现是数组路线。数组、链表、位图三者在“并交差”运算上都能完成功能区别在适用边界数组代码最好读链表适合动态增长位图适合小值域大数据量。动手扩展前先在头文件把 MAX_SIZE 改成满足输入规模的值再在主程序里加上对读取数量超过 MAX_SIZE 的检查。我见过有人直接拿默认的 1024 去跑上万元素的数据数组越界后程序没立刻崩结果却在输出里出现莫名其妙的垃圾值那就是典型的黑匣子问题。如果不满足于数组实现想改成链表也不难关键是保持头文件里的函数签名不变。可以把结构体定义放进 set_ops.h把原来操作数组的三个函数换成操作链表主程序只追加一段把数组数据转成链表的初始化逻辑整体动的地方很有限。改成位图则要谨慎处理值域问题代码里用取或、取与、取反三个操作表达并、交、差一句话就能写完一个函数但前提是提前确认过 max_value 的范围。4. 三个集合运算落地线性归并实现与输入输出4.1 并集合并两个有序序列值相等只留一份假设两个集合经过前置的排序去重各自内部没有重复项那么并集可以用一个简单的三指针循环写出。先给代码int union_set(int *a, int na, int *b, int nb, int *out) { int i 0, j 0, k 0; while (i na j nb) { if (a[i] b[j]) { out[k] a[i]; } else if (a[i] b[j]) { out[k] b[j]; } else { out[k] a[i]; // 两个相等只需输出一份 j; } } while (i na) { out[k] a[i]; } while (j nb) { out[k] b[j]; } return k; }这个实现的关键在于 else 分支当 a[i] 等于 b[j] 时只把其中一个值写入输出另一个通过 j 跳过。这样并集输出里不会出现重复项。后面两个 while 用来处理一个集合已经扫描完、另一个集合还有剩余的情况直接把这部分追加到结果末尾顺序仍然保持升序。算法整体走一遍两个数组时间复杂度 O(nanb)空间只依赖 out 缓冲区。我一般会在写完后补一条防御性检查out 是否足够大能容纳 nanb 个元素。并集最大长度是 nanb如果 out 是按最大可能长度分配的就没问题若是按 MAX_SIZE 分配而 nanb 超过 MAX_SIZE则写入会越界。宁可多分配一点也不要等崩了才意识到。提示为结果数组分配内存时并集最大长度是 nanb交集最大长度是 min(na, nb)差集最大长度是 na。按这个上限分配打印前再用返回值控制输出数量能省掉一半越界排查。4.2 交集与差集只差一行指针移动交集和并集共享同一个归并框架区别只在相等和不相等时如何处理。先看交集int intersect_set(int *a, int na, int *b, int nb, int *out) { int i 0, j 0, k 0; while (i na j nb) { if (a[i] b[j]) { i; // a 的元素太小不可能在 b 中出现 } else if (a[i] b[j]) { j; // b 的元素太小不可能在 a 中出现 } else { out[k] a[i]; i; j; } } return k; }并集里相等时只保留一份并继续走这里相等时把它作为交集成员输出同时两个指针一起前进确保同一个元素不会参与第二次比较。小于和大于两个分支分别只前进一边的指针逻辑上正好对应“某个集合独有元素不可能出现在交集中”。差集 A-B 的方向性最容易出错代码写出来和交集只有两行差异int diff_set(int *a, int na, int *b, int nb, int *out) { int i 0, j 0, k 0; while (i na j nb) { if (a[i] b[j]) { out[k] a[i]; // b 里没有这个值属于 A 独有 } else if (a[i] b[j]) { j; // b 里的值在 A 中没有跳过 } else { i; // 两边都有不属于差集 j; } } while (i na) { out[k] a[i]; // b 已空A 剩余全部属于差集 } return k; }注意最后一段只处理 i na 的情况不像并集那样再处理 b 的剩余部分因为 B 剩余的元素在 B-A 方向上不需要输出A-B 的定义决定了 B 独有的元素不该出现。同理B-A 就是把 a、b 参数对调再调用同一个函数。这三个函数都要求输入本身有序且无重复。如果读入的数据无序或含重复需要先做排序去重否则归并结果里会残留重复元素。下面这段是通用的前置处理int sort_unique(int *arr, int n) { if (n 1) { return n; } qsort(arr, (size_t)n, sizeof(int), cmp_int); int m 1; for (int i 1; i n; i) { if (arr[i] ! arr[m - 1]) { arr[m] arr[i]; } } return m; }sort_unique 先把数组排成升序再做一趟原地去重m 维护“已经去重后的有效长度”当 arr[i] 与已保存的前一个元素不同时把它搬到 arr[m] 并递增 m。这个去重是稳定安全的因为只覆盖写已读过的位置的元素不会覆盖还没轮到比较的数据。调用方记得用返回值更新集合长度而不是继续沿用原始 n否则后面归并时仍会把重复元素带进去。4.3 主程序的输入读取与输出顺序主程序通常做的就是三件事读文件、调算法、打印结果。读取部分最常见的是这种写法int read_set(const char *path, int *arr) { FILE *fp fopen(path, r); int n 0; if (fp NULL) { perror(fopen); return -1; } while (fscanf(fp, %d, arr[n]) 1) { n; if (n MAX_SIZE) { break; } } fclose(fp); return n; }fscanf 的返回值是成功转换的参数个数所以判断它等于 1 才能继续读如果文件里出现非数字字符fscanf 会转换失败返回值变成 0循环就停了这种时候程序不会报错但读取长度会少于真实行数需要结合输入格式确认是不是数据本身有问题。我把 MAX_SIZE 的判断放在每次读取后避免因文件行数超过预设容量而越界写。输出顺序要和题目要求保持一致。有的实验要求按并集、交集、A-B、B-A 四行分别输出有的要求先打印集合长度再打印元素。我会先看 main.c 里 printf 的格式再对照题目依次写清楚每行前面要不要带标签。若包里的输出顺序和题目不一致只需要调整 main.c 的打印部分核心算法不用动。输出前留一行调试用的 printf把每个集合的“长度 前三个元素”打出来对排查“读入是否成功、排序是否生效”帮助非常大。5. 避坑指南这套实验最容易翻车的五个地方5.1 现象并集结果和答案数量对不上“并集结果和答案数量对不上”这种问题在接手排错请求时出现的频率很高。排查时算法看起来没问题最后发现是读入的集合根本没去重比如 A {1, 1, 2, 3}B {1, 2}代码把两个 1 都当成不同元素输出了。原因在于没有把“数学集合”的语义落到代码里只按数据文件里的原始序列操作。解决方法是把 sort_unique 放到所有运算之前读入后先算出去重后的长度后面再算并集、交集、差集时就都基于干净数据。我在主程序里会强制先调用 sort_unique即使题目给的数据已经有序也顺手跑一遍多一次调用不影响复杂度却能省掉排查重复问题的半天时间。5.2 现象空集合输入直接崩溃或输出残留脏数据第二个坑出现在一个集合长度为 0 的时候。数组实现里na 可能是 0循环条件 i na 直接不成立逻辑上没问题但如果某个函数像 diff_set 一样在 while 结束后直接依赖“b 有剩余元素”做追加而 b 是空数组访问 b[0] 就越界了。有人会加一段if (nb 0) { memcpy(out, a, na * sizeof(int)); return na; }这种分支提前处理属于防御式编程能避免崩溃但更根本的是要让所有函数在 na 或 nb 为 0 时都走最短正确路径不碰任何越界下标。空集是一种合法输入不是异常输入处理空集是两个指针归并的基本功。5.3 现象读取到的集合长度比文件实际行数少输入格式和 fscanf 的配合是第三个常见的坑。当文件是“1,2,3,4”这种逗号分隔格式或者行尾带着中文字符串注释时fscanf 读到第一个数字后会停在逗号或汉字前面下一次循环转换失败返回 0读取提前终止。结果就是集合长度少一大截后续运算结果面目全非。解决分两步先确认题目约定到底是“每行一个整数”还是“逗号分隔纯数字”如果是后者就改用 fgets 把每行读成字符串再按逗号或空格切分成多个整数如果约定是每行一个整数就要防止输入文件里混入非数字内容读取时对 fscanf 的返回值加一层判断读失败就打印警告而不是默默退出。5.4 现象差集方向写反A-B 变成 B-A差集不像交并集那样可交换写反方向的结果基本没有正确的时候。我自己就碰到过题目要求输出“存在于 A 但不存在于 B 的元素”代码里却把 a、b 参数传反输出结果全是 B 独有的元素。踩过这个坑之后我在 main.c 里把两个差集分别命名为 diff_ab 和 diff_ba不加简化并在打印行前加“A-B:”和“B-A:”前缀。这样运行结果一出来一眼就能判断方向对不对不用等评审看了才发现写反。代码里也可以在实际调用前加一行注释写明当前调用求的是哪个方向。5.5 现象结果正确但顺序和标准答案不一致最后一个坑不在算法而在输出顺序。数学里集合本身没有顺序概念但实验评测通常按字符串比对结果数组 [1, 3, 5] 和 [3, 5, 1] 会被判为不一致。解决方案是在所有运算前都保证输入有序这样并、交、差的结果天然有序如果题目要求输出“按输入顺序”而非有序那就要在运算后调整输出逻辑而不是临时改三个算法函数。我习惯在函数名末尾加上_sorted后缀明确告诉后续维护者这个函数的输出依赖有序输入避免有人拿无序数据直接调用得到一份看似合理但顺序不对的结果。6. 验证正确性用随机对数器把三个操作测成闭环代码写完先别急着交。我习惯再用一个小脚本做“对数器验证”思路是生成两个随机集合一个用包内实现的并、交、差一个用脚本自带的 set 运算两边结果对比一致才算通过。下面是验证脚本的核心部分import random def reference(a, b): return (sorted(set(a) | set(b)), sorted(set(a) set(b)), sorted(set(a) - set(b))) for _ in range(1000): a [random.randint(0, 20) for _ in range(random.randint(0, 10))] b [random.randint(0, 20) for _ in range(random.randint(0, 10))] u, i, d reference(a, b) # 把 a、b 按升序去重后传给 C 程序再比对三组输出 # 实际接线时可以用命令行参数传文件路径或直接用 ctypes 调三个函数这个脚本会把 C 程序输出的三行结果与 Python 内置 set 运算结果逐一比对连续一千组样本全部一致才说明核心逻辑可靠。随机范围特意限制在 0 到 20是为了让并集、交集出现大量重叠情况比只测两组手写数据更能覆盖相等分支。如果你把范围拉到 0 到 100样本数量加到一万组发现差集偶尔多一个元素那多半是去重前置没生效而不是归并本身的问题。验证通过后再向两个方向扩展。一是把输入换成 10 万级别的大数据测试排序和归并的时间消耗确认 O(n) 复杂度是否真实成立二是由数组扩展到链表实现感受接口不变、内部算法替换带来的可维护性。从那以后我每写完一个集合运算实验都强制自己跑一遍对数器哪怕只是几十行的小代码也顺手把它从“感觉对”变成“确实对”整个过程不到五分钟却能省去交作业前临时返工的大量时间。希望这个验证习惯也能帮到你。本文还有配套的精品资源点击获取