简介实验一集合交并差.zip 是一份数据结构课程的集合操作实验资源面向正在学习数据结构与算法、需要完成集合交集并集差集编程实践的学生。资源结合软件工程SE课程思路在 VS 环境下用 C 实现了集合的初始化、遍历、比较与结果验证等操作并附有复杂度分析适合作为实验报告撰写或复习参考。压缩包共 8 个文件以 3 个 cpp 源文件和 3 个 h 头文件为主涵盖可运行的集合运算代码另有 1 份 pptx 用于概念讲解与伪代码展示1 份 docx 为实验报告模板整体大小约 8.74MB。目前已有 314 人学习或下载。通过这份资料读者可以快速掌握数组、链表或哈希表实现集合运算的思路理解 O(1) 与 O(n) 不同实现的效率差异并获得可直接修改运行的代码与配套说明为后续算法学习打下基础。1. 实验一集合交并差.zip先认识再动手从课程平台下载的「实验一集合交并差.zip」是大多数数据结构或离散数学课的第一次上机作业。解压后你会看到模板代码、实验指导书和样例数据任务是实现两个集合的交、并、差三个运算再按指定格式输出。说它坑不在算法本身——三个运算的逻辑初中生都能讲明白——而在实验包的文件结构、输入输出协议和评分脚本的隐性要求上去重做没做、空集怎么输出、差集方向对不对、压缩时是不是多套了一层文件夹都可能让一次本来写得对的程序被判零分。这份笔记带你一次走通从读懂压缩包里每份文件的用途到写出数组、位图、链表三种实现最后聊判分时最容易丢分的细节。2. 交并差先算清楚数学再写代码三个运算符的本义与程序翻译2.1 交、并、差的定义用一个例子把符号变成集合集合这个词在数学里的定义不用背它就是一个“确定且互不相同的对象群体”。交、并、差是作用在两个集合 A 和 B 上的三个二元运算交集 A ∩ B所有既属于 A 又属于 B 的元素。并集 A ∪ B所有属于 A 或属于 B 的元素重复的只算一次。差集 A \ B所有属于 A 但不属于 B 的元素。用具体数字走一遍A {1, 2, 3, 5, 5}注意有重复B {2, 3, 4}。先把 A 去重成 {1, 2, 3, 5}再算A ∩ B {2, 3}A ∪ B {1, 2, 3, 4, 5}A \ B {1, 5}B \ A {4}最后这个 B \ A 是实验里最常见的分叉点题目写了“求两个集合的差集”但没有说明方向时默认要做 A \ B如果指导书写的是“差集”而不是“A 减 B”建议两个方向都实现并在输出里给出标签。实际判题一般是固定方向看清它。后面写代码时你会发现交并差函数的参数顺序在并集和交集上无所谓但差集 A \ B 的参数顺序至关重要。我一般会把do_difference(a, n, b, m)和do_difference(b, m, a, n)都写出来输出时按题目要求调换实参——这个习惯能让你快速验证两个方向不会在答辩时被问倒。2.2 程序里怎么表示集合数组、链表、位图的选型C 语言没有内置集合实验第一件事就是选容器。三种主流做法表示方式适用数据规模主要缺点适合练习点动态数组顺序表几千以内插入删除要挪元素排序和双指针单链表任意主要练指针边界条件多指针操作位图数组元素是有界非负整数范围不定时浪费空间位运算很多院系的实验指导书会直接指定“必须用带头结点的单链表实现”这时别顶着要求写数组——评分里有一项会抽查代码结构用错了不一定零分但讲评时比较难看。如果没有任何限制优先用数组代码短、逻辑直白、调试容易。C 用户如果想用 STL 的 set 一步到位注意指导书末尾那句“不得使用 STL”一旦出现就当这条捷径不存在。选型时还有一条实际经验实验平台如果是 PTA 这类自动判题系统编译时不会关心你用的是数组还是链表只看输出但如果是人工提交实验报告并要求答辩老师会对照指导书检查数据结构。对自己负责的角度优先选择指导书点名的那种结构没有点名数组。2.3 去重集合定义里最容易被忽略的第一关集合的元素互不相同但输入数据不一定守规矩。比如样例输入是3 1 1 2表示集合里有三个元素分别是 1、1、2真实含义是 {1, 2}。如果在读入后不处理重复交并差三个结果都会出现重复值交集不用双指针去重的话A 和 B 里同时有两个 1输出就成了1 1。判分脚本按参考答案逐元素比对直接给你判错。去重的两种做法。第一种是插入时就检查每来一个元素扫一遍已有数组如果存在就丢弃。这种写法直观但插入复杂度变成 O(n²)。第二种是先全部存入再 qsort 排序最后原地压缩。第二种效率更高也是我一般推荐的做法——排序顺便解决了输出顺序问题。用数组实现的去重核心只有三行qsort(a, n, sizeof(int), cmp); int idx 1; for (int i 1; i n; i) if (a[i] ! a[idx - 1]) a[idx] a[i]; n idx;逻辑说明qsort 先把所有元素排成非递减序列这样重复值一定相邻。idx 指向“下一个可写入的去重后位置”循环里把与上一个保留值不同的元素搬运到前面。最终 n 被更新为去重后的长度。参数说明cmp 是 qsort 的比较函数必须返回两个元素的大小关系数组 a 只要保证在调用前已排序这段代码就不会出错。如果输入规模小于 100也可以在插入时用两层循环手工去重代码更短但效率低实验报告里写复杂度时不太好看。2.4 空集和字符串集合让边界情况不拖后腿空集参与运算是必须处理的边界也是最容易被扣分的地方A ∅B {1, 2}交、差均为空并集是 B。A B交、并都是 A差为空。交或差为空时那一行要输出一个空行。注意有的指导书要求输出空集时打印none或EMPTY这属于“额外命题”以指导书为准。元素类型也要确认是整数还是字符串。字符串集合的排序用strcmp去重逻辑不变但相等判断要换成strcmp(s1, s2) 0双指针遍历时用strcmp的返回值决定谁小谁大不要直接比较字符串地址。实验里极少出现字符串版本但出现过一次“输入若干个英文单词求两个集合交”的题目提前知道没坏处。3. 解压实验包先别写代码文件结构与输入输出协议摸清再动手3.1 典型实验包里那四类文件分别干什么一个标准的「实验一集合交并差.zip」解压后大概长这样实验一集合交并差/ ├── 实验指导书.pdf ├── main.c ├── input_sample.txt ├── output_sample.txt └── README.txt实验指导书写的字最多是你唯一要照着做的需求文档。里面的数据规模比如“集合元素个数不超过 1000”、算法要求是否必须链表、输出格式元素间空格还是逗号都要逐句确认。模板 main.c通常已经把 main 函数和读入部分写好留三个函数给你填。input_sample.txt / output_sample.txt给你对拍用的小样例程序跑完和 output_sample.txt 逐字符比对这是最简单也是最有用的验证手段。README.txt写编译命令和提交说明多数时候还写清楚了“压缩包必须包含哪些文件”。先读指导书、再看模板 main.c、最后对着样例验证这个顺序不要颠倒。我见过不少同学把 main.c 里已经写好的读入代码整体删掉重写结果读入格式和评分脚本不一致白忙一场。3.2 输入输出协议判分脚本到底期望什么格式判题系统统一用“标准输入 标准输出”命令行对比是./main input.txt output.txt这样的重定向。最常见的输入协议是4 1 2 3 5 3 2 3 4含义A 有 4 个元素分别是 1 2 3 5B 有 3 个元素分别是 2 3 4。有的模板会在第一行先读集合 A 的个数再读元素也有的设计成“读到 EOF 为止前 n 个属于 A后 m 个属于 B”后者少见但存在。实验指导书里一定写模板 main.c 里一定有对应的 scanf 序列——照着模板读就行。输出格式一般是三行第一行交集第二行并集第三行差集方向为 A \ B。元素之间用一个空格分隔行尾没有多余空格最后有换行。空集输出空行。这就是绝大多数评分的全部要求。还要注意一个细节判断输入结束的方式。模板 main.c 若是用scanf(%d, n) 1判断读取成功那么输入文件末尾没有多余空白时不会误读如果你自己改成while (!feof(stdin))会因最后一行读取后再进循环而多读一次 EOF导致集合里多出一个未定义值。所以读入逻辑尽量沿用模板不要从零重写。3.3 解压与编译Windows 和 Linux 下的常用命令拿到 zip 先在 Windows 资源管理器里右键解压最省事编码也基本不会出问题。如果实验平台是 Linux解压命令是unzip 实验一集合交并差.zip unzip -O GBK 实验一集合交并差.zip # 文件名是中文且解出乱码时用如果没装 unzip先sudo apt update sudo apt install unzip。第一行命令解开 zip第二行-O GBK是处理 Windows 下用 GBK 压缩的中文文件名不加的话文件名解出来是乱码——这就是热词榜上“zip 乱码”的实际场景。编译用 gcc 或 ggcc main.c -o lab1 ./lab1 input_sample.txt编译参数-o lab1指定输出文件名不写的话产出a.out。命令行./lab1 input_sample.txt把文件作为标准输入重定向省去手工敲数。Windows 下是lab1.exe input_sample.txt注意别在源文件里写死freopen(input.txt, r, stdin)这类代码——评分系统直接重定向输入文件路径是否一致是另一门玄学少给自己加戏。如果你在 Windows cmd 里编译后运行./lab1系统会提示找不到路径正确写法是lab1.exe或.\lab1.exe。这个细节看似初级每年都有人因为没跑通样例就放弃挺可惜。4. 动手实现交并差数组、位图、链表三份代码与细节4.1 数组法排序去重后一次双指针遍历通吃三个运算数组法是目前最稳妥、也是代码量最小的实现。整体流程分三步读入、qsort 排序、unique 去重之后三个运算全部基于有序数组用双指针扫描。直接给一个可以编译运行的完整 main.c#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { return *(const int *)a - *(const int *)b; } int unique(int *a, int n) { if (n 1) return n; int idx 1; for (int i 1; i n; i) { if (a[i] ! a[idx - 1]) { a[idx] a[i]; } } return idx; } void do_intersection(int *a, int na, int *b, int nb) { int i 0, j 0, first 1; while (i na j nb) { if (a[i] b[j]) i; else if (a[i] b[j]) j; else { if (!first) printf( ); printf(%d, a[i]); first 0; i; j; } } printf(\n); } void do_union(int *a, int na, int *b, int nb) { int i 0, j 0, first 1; while (i na || j nb) { int v; if (i na) v b[j]; else if (j nb) v a[i]; else if (a[i] b[j]) v a[i]; else if (a[i] b[j]) v b[j]; else { v a[i]; i; j; } if (!first) printf( ); printf(%d, v); first 0; } printf(\n); } void do_difference(int *a, int na, int *b, int nb) { int i 0, j 0, first 1; while (i na j nb) { if (a[i] b[j]) { if (!first) printf( ); printf(%d, a[i]); first 0; i; } else if (a[i] b[j]) { j; } else { i; j; } } while (i na) { if (!first) printf( ); printf(%d, a[i]); first 0; i; } printf(\n); } int main() { int n, m, a[2000], b[2000]; scanf(%d, n); for (int i 0; i n; i) scanf(%d, a[i]); scanf(%d, m); for (int i 0; i m; i) scanf(%d, b[i]); qsort(a, n, sizeof(int), cmp); qsort(b, m, sizeof(int), cmp); n unique(a, n); m unique(b, m); do_intersection(a, n, b, m); do_union(a, n, b, m); do_difference(a, n, b, m); return 0; }逻辑说明unique 依赖 qsort因为只有对有序数组做相邻比较才能一次性去重。qsort 的比较函数 cmp 必须返回差值别写成恒真表达式。do_intersection 在 a[i] 与 b[j] 相等时输出并同时推进两个指针避免重复匹配do_union 使用“谁小谁输出、相等只输出一次”的策略do_difference 只在 a[i] b[j] 时输出因为此刻 b[j] 一定大于 a[i] 且不会与后续任何一个 b 相等——有序性是这个判断的前提。参数说明数组容量 2000 只是图省事给的一个量级实验若写明“元素个数不超过 100000”请在 main 里用malloc动态分配避免栈溢出。cmp 里*(const int*)a - *(const int*)b在元素接近 INT_MAX 时可能溢出但实验通常限制在 int 正数范围如果元素可能是 unsigned 或 long long把比较函数改成两段条件判断更安全。4.2 位图法元素范围确定时三行逻辑做三个运算如果指导书给出“集合元素是不超过 1000 的正整数”这类约束位图法是个像黑匣子一样简洁的解法——读入时打标记输出时扫一遍标记#include stdio.h #include string.h #define MAXV 1005 int inA[MAXV], inB[MAXV]; int main() { int n, m, v; memset(inA, 0, sizeof(inA)); memset(inB, 0, sizeof(inB)); scanf(%d, n); for (int i 0; i n; i) { scanf(%d, v); inA[v] 1; } scanf(%d, m); for (int i 0; i m; i) { scanf(%d, v); inB[v] 1; } int first 1; for (v 1; v MAXV; v) if (inA[v] inB[v]) { if (!first) printf( ); printf(%d, v); first 0; } printf(\n); first 1; for (v 1; v MAXV; v) if (inA[v] || inB[v]) { if (!first) printf( ); printf(%d, v); first 0; } printf(\n); first 1; for (v 1; v MAXV; v) if (inA[v] !inB[v]) { if (!first) printf( ); printf(%d, v); first 0; } printf(\n); return 0; }逻辑说明位图把“集合是否包含某元素”编码成数组下标inA[v] 1等价于 v ∈ A。交集判断inA[v] inB[v]并集判断inA[v] || inB[v]差集判断inA[v] !inB[v]三个循环完全对称。数组是全局变量自动初始化为 0memset 其实可以不写但写上能让读代码的人一眼明白意图。参数说明MAXV 要覆盖元素上界题目说“不超过 1000”时设 1005 留余量。这个做法的复杂度是 O(MAXV)跟集合实际大小无关。缺点是元素范围到 10^9 就没法开数组此时回到排序数组。还有一点术语上别把位图叫成“哈希表”——位图直接用下标映射值域哈希表要处理冲突实验报告里写错术语容易被答辩老师追问。4.3 链表法模板强制要求时指针边界盯紧这三处如果实验提纲明确规定用单链表实现你必须处理指针操作。核心套路是“有序合并”先把两个链表各自排序或边插入边保持有序然后用两个遍历指针扫描。下面是插入式去重的骨架struct Node { int val; struct Node *next; }; struct Node* insert_sorted(struct Node *head, int v) { struct Node *node (struct Node*)malloc(sizeof(struct Node)); node-val v; if (head NULL || v head-val) { node-next head; return node; } struct Node *cur head; while (cur-next cur-next-val v) cur cur-next; if (cur-next cur-next-val v) { // 已存在去重 free(node); return head; } node-next cur-next; cur-next node; return head; }逻辑说明插入式去重是最稳妥的链表写法——每来一个新元素按值查找到插入位置如果下一个节点的值恰好等于新值说明重复释放节点直接返回。while 循环的条件顺序是先判断cur-next再访问cur-next-val短路顺序反了就会对空指针取字段这是链表题最常见的段错误来源。参数说明链表的三个关键指针——头指针 head、遍历指针 cur、临时节点 node——命名统一提交实验报告时自己能看懂。链表版交并差的三个运算其实可以归并式扫描交集条件是元素同时出现在两条链中并集和差集套路与数组双指针完全一致只是把下标推进换成cur cur-next。4.4 main 函数的读写细节个数前缀、空集行与行尾空格三个实现的 main 有几处细节直接影响判分放在一起说。读入严格按“先个数、再元素”的顺序调用 scanf。个数那行可能和其他数据在同一行scanf 以空白符为分隔不区分空格和换行所以不用关心具体在第几行。空集输出交集或差集没有元素时循环一次都不进printf(\n)仍然执行保证输出是空行而不是缺行。判分脚本按行号对答案少一行也会挂。行尾空格代码用first标志控制“元素之间才输出空格”整行不会以空格结尾。很多判分系统用 token 比较不受影响但万一用逐字符 diff行尾空格就是零票否决。差集方向main 里调用do_difference(a, n, b, m)输出的是 A\B如果同时要 B\A就改成do_difference(b, m, a, n)再打一次别让函数内部的 i/j 搞乱顺序。5. 避坑实验一集合交并差.zip 最常翻车的 5 个现场5.1 解压后源文件注释乱码模板代码不敢动现象main.c 打开后中文注释全是乱码结构看懂了但不敢确认哪几行是题目写好的、哪几行要自己补。原因zip 打包时按 GBK 编码存储了文件名和文件内容某些解压工具默认用 UTF-8 解出内容编码不匹配。解决Windows 下直接右键解压或改用 7-Zip 的“用系统默认编码解压”Linux 下执行unzip -O GBK 实验一集合交并差.zip。VS Code 打开乱码文件后点右下角编码、选“GBK 重新加载”。注意文件内容用 GBK 存储对编译器没有影响gcc 按本地编码读源文件Windows 默认 GBK 是对的不用强转 UTF-8。5.2 忘记去重输出多出重复数字现象输入4 / 1 2 2 3交集输出1 2 2。原因数组存的是原始输入没有去重双指针在有序数组里把重复的 2 当成两个元素。解决在 qsort 之后统一跑一遍 unique或者在链表的 insert 函数里发现相等就 free。无论哪种输出前集合必须严格互异。这个错是评分脚本里扣分重点通常比排序错误还冤。5.3 在线测评平台无输出本地却跑得好好的现象本地./main input.txt一切都正常交到测评系统直接编译通过但 0 分、提示无输出。原因代码里写了system(pause)、getchar()这类调试停驻语句。测评环境把输入重定向成文件后getchar 读不到交互按键system(pause) 调用失败程序异常退出。解决提交前全局搜索 system、pause、getch、sleep 这几个字眼全删。也不要自己定义一个阻塞读入的循环去“等输入”。评测系统对返回值没有硬性要求关键是程序不能在读输出前卡住。5.4 把外层文件夹整个压缩提交后找不到 main.c现象测评日志显示编译失败提示不能打开源文件 main.c或者本地解压后路径里多了一层同名文件夹。原因压缩时对着「实验一集合交并差」文件夹右键生成的是包含文件夹本身的 zip解压后结构是实验一集合交并差/main.c而评分脚本期望在解压根目录直接看到main.c。解决压缩前双击进入该文件夹全选内部所有文件和目录再压缩把 zip 解压到临时目录验证如果第一层不是 main.c 而是文件夹说明压错了。5.5 差集方向和输出格式的隐藏规则现象程序逻辑正确手算也对就是六七十分不知差在哪。原因很可能是行尾空格、空集该输出什么、还是差集方向。指导书没写空集输出什么、没写清是 A\B 还是 B\A 时很多同学直接按自己的习惯写。解决把指导书里“输出”段落截图出来一行行对照尤其注意样例输出里的空白行。判分脚本的参考答案是固定字符串空集如果需要输出none而你输出空行直接整题 mismatch。遇到题目描述含糊最稳的一招是从模板 main.c 的注释里找答案——模板作者会把约定的输出格式写在注释里。6. 交并差实验的进阶验证从跑通到有说服力6.1 用随机测试生成器构造大样本写一个 gen_test.c生成 0~7 个元素随机个数能自然覆盖空集场景元素范围 0~9故意允许重复。把生成器输出重定向到 input.txt你的程序和暴力程序分别读它并产生两份输出用diff -w忽略空白差异做比较。暴力程序直接按集合定义写每个 A 元素判断是否在 B 中对 10 以内的小数据一定是正确答案。这个动作跑 200 次比任何手算都让人安心。#include stdio.h #include stdlib.h #include time.h int main() { srand(time(NULL)); int n rand() % 8; // 0 到 7有意构造空集 int m rand() % 8; printf(%d\n, n); for (int i 0; i n; i) printf(%d , rand() % 10); printf(\n%d\n, m); for (int i 0; i m; i) printf(%d , rand() % 10); printf(\n); return 0; }逻辑说明srand(time(NULL))让每次运行的随机序列不同rand() % 8产生 0~7 的个数rand() % 10产生 0~9 的元素值。故意不避免重复就是为了测去重逻辑。6.2 快速验证脚本与报告里的复杂度分析检查输出前再想一下方向A \ B 和 B \ A 都打印出来和手算结果比对。实验报告里如果能写“数组法时间复杂度 O(n log n)空间 O(n)位图法时间复杂度 O(V)、空间 O(V)其中 V 是元素值域”会比只贴代码更有说服力。最后一步善后把 main.c、报告 PDF 和一个 README说明编译方式一同放进压缩包解压后第一层没有文件夹层级用unzip -t或右键“测试压缩文件”验证完整性再提交。我第一次带实验课改作业时有三分之一同学的压缩包在测试环节就解不出正确目录从那以后我养成了每次提交前都重新解压一次、然后立刻运行样例的习惯。希望这份笔记能帮你省下这半个晚上的折腾。本文还有配套的精品资源点击获取
