简介北邮数据结构实验线性表文档面向北邮学生及数据结构初学者完整呈现实验要求、带头结点单链表的存储结构、关键算法分析与测试main()函数实现。文档首先介绍链表采用一组任意的存储单元存放结点逻辑次序与物理次序不必相同每个结点包含数据域与指针域随后逐一详解头插法、尾插法、析构函数、按位查找、按值查找、插入、删除、遍历、获取长度等核心操作每个操作均给出具体步骤与时间复杂度说明例如头插法O(n)、插入操作O(1)便于读者对照代码理解单链表的底层原理。资源共包含1个doc文件压缩包大小约6.3MB内容精炼且结构清晰并附流程示意图与运行结果适合用作实验参考、期末复习或自学材料。已有597人学习下载说明其实用性获得认可对完成北邮数据结构实验、掌握线性表编程尤其有帮助。1. 北邮数据结构实验线性表从建表到多项式运算的实验主线北邮的数据结构实验里线性表是第一个硬骨头。很多人在实验前一晚才开始敲代码结果在“就地逆转链表”这种题上卡到怀疑人生最后拿着和别人雷同的代码去验收被老师一问就翻车。这门实验表面上只要求你用顺序表或链表实现几个基本操作实际考察的是你对内存布局、指针操作和算法边界的理解深度。这篇笔记按北邮实验的常见要求把建表、插入删除、查找逆转、有序合并到多项式运算这条线走一遍给你一套能直接照着写的代码骨架也把容易扣分和容易翻车的细节全部挑出来。无论是大一刚接触数据结构的初学者还是考前突击的老手沿着这条线做一遍实验报告和代码质量都能上一个台阶。2. 顺序表和链表怎么选数据规模与操作频率决定实验分北邮实验通常要求线性表用两种存储结构各实现一遍或者至少明确说明选型理由。很多同学在报告里写“因为题目要求用链表”这等于没写。判分老师想看到的是你对两种物理结构的成本有量化认识这一章把选型逻辑讲透再给出两种结构的可运行骨架。2.1 顺序表的代价模型为什么频繁插入会让数组类实现难堪顺序表的核心优势是随机访问按下标取元素的时间复杂度是 O(1)这一点在查找类操作里碾压链表。但它的插入和删除最好情况下 O(1)——直接在表尾操作最坏情况下 O(n)——在表头操作需要把后面所有元素都搬移。北邮实验里常见的一个考核点是从表头反复插入一组数据建表这时候顺序表的时间开销是 O(n²)数据量一旦到一万级程序就会出现肉眼可见的停顿。另一个常被忽略的问题是顺序表的扩容策略。静态分配的数组定死了容量动态分配的数组需要手动 realloc。严蔚敏《数据结构C语言版》里的写法是 increment 增量扩容但这个增量给多少很讲经验。给的太小频繁 realloc 导致内存搬移和碎片给的太大浪费空间。我一般按当前容量的 1.5 到 2 倍扩每次扩容后把旧数据 memcpy 过去别用循环逐个赋值后者不仅慢代码还丑。#include stdio.h #include stdlib.h #include string.h #define INIT_SIZE 100 #define INCREMENT 50 typedef struct { int *data; int length; int max_size; } SeqList; // 初始化空表 void InitList(SeqList *L) { L-data (int *)malloc(INIT_SIZE * sizeof(int)); if (!L-data) exit(1); // 分配失败直接退出 L-length 0; L-max_size INIT_SIZE; } // 在第 pos 个位置插入元素 epos 从 1 开始计数 void ListInsert(SeqList *L, int pos, int e) { if (pos 1 || pos L-length 1) { printf(插入位置非法\n); return; } if (L-length L-max_size) { // 满了就扩容 int *new_data (int *)realloc(L-data, (L-max_size INCREMENT) * sizeof(int)); if (!new_data) exit(1); L-data new_data; L-max_size INCREMENT; } for (int i L-length - 1; i pos - 1; i--) { L-data[i 1] L-data[i]; // 从后往前搬避免覆盖 } L-data[pos - 1] e; L-length; }这段代码的关键在插入处的循环。从后往前搬移是为了防止前面元素覆盖后面还没搬走的数据这是一个新手高频错误。扩容用的 realloc 会在原地址放不下时自动搬移并返回新地址所以必须把返回值赋给 L-data直接用原来的指针会导致悬空。pos 位置逻辑从 1 开始数组下标从 0 开始这个映射关系搞错会导致插入位置整体偏移一位。2.2 链表的指针陷阱为什么表头插入比表尾插入友好得多链表不需要搬移数据插入删除只要改指针就能完成时间复杂度 O(1)。但它的代价是随机访问需要从头遍历而且每个节点额外消耗一个指针域的空间。北邮实验里最常见的链表要求是带头结点的单链表这个头结点不存数据纯粹为了让表头插入和中间插入的代码逻辑统一避免单独处理“插到空表”这种边界情况。很多同学在建立链表时按尾插法写需要维护一个尾指针每插入一个新节点都要从头遍历或者引用这个尾指针。代码写起来啰嗦就算了稍不注意尾指针没更新链表就断在中间。头插法就简单得多每次把新节点插到头结点后面代码只有三行但建出来的链表顺序和输入顺序相反这一点实验报告里必须说明。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node, *LinkList; // 头插法建立链表输入 1 2 3链表存储顺序为 3 2 1 LinkList CreateListHead() { LinkList L (Node *)malloc(sizeof(Node)); // 头结点 L-next NULL; int x; while (scanf(%d, x) ! EOF) { Node *s (Node *)malloc(sizeof(Node)); s-data x; s-next L-next; // 新节点指向原来的第一个节点 L-next s; // 头结点指向新节点 } return L; }头插法代码量少但是存在一个内存分配失败没有处理的问题——上述代码里 malloc 后没检查返回值这在验收时被问“如果分配失败怎么办”很容易卡壳。更稳的写法是分配后立刻判断失败就释放已有链表并返回 NULL。另外头结点是不参与计数的遍历时从 L-next 开始这个习惯越早养越好。2.3 选型决策表北邮实验题面里的暗示信号北邮的实验指导书一般不会直接告诉你“这题用哪种结构”但题面里通常藏着信号。按我的经验把决策条件列一张表做实验选择时直接对号入座既省时间又能在报告里写清楚理由。题面特征适合结构核心理由大量按下标/位置查找顺序表O(1) 随机访问大量在两端或中部插入删除链表O(1) 指针修改数据规模未知可能暴涨链表或动态扩容顺序表链表按需分配顺序表需控制增量需要反复遍历但不改结构顺序表缓存友好遍历速度快内存受限节点数量极大顺序表链表多存 4/8 字节指针内存开销高约瑟夫环、多项式运算等动态场景循环链表/链表删除节点频繁需 O(1) 删除这个表格可以原样写进实验报告的设计分析部分老师会觉得你确实对比过两种结构而不只是把教科书的结论抄了一遍。真实实验里还有一类隐性要求如果题面对时间复杂度有明确限制比如“算法要求在 O(n) 内完成”那么链表比顺序表更容易达标因为顺序表的插入删除往往超过这个界限。3. 单链表的就地逆转与有序合并实验报告里的高分代码段这一章是北邮线性表实验的核心战场。逆转链表和合并两个有序链表几乎每年都出现在实验或验收提问里而且这两道题能很好地暴露你对指针操作的熟练度。很多同学拿着网上抄的递归逆转代码去验收被问“递归栈深度是多少”就哑了。下面给的是迭代写法辅以必考的边界讲解。3.1 就地逆转的迭代实现三指针法与头插法变体就地逆转要求不使用额外空间只改指针方向。最稳妥的思路是三指针法pre 指向前一个节点cur 指向当前节点next 暂存 cur 的后继防止修改 cur-next 后丢失后续链表。// 就地逆转带头结点的单链表时间复杂度 O(n)空间复杂度 O(1) void ReverseList(LinkList L) { Node *pre NULL; // 前驱初始为空 Node *cur L-next; // 当前节点从头结点后的第一个节点开始 Node *next NULL; // 暂存后继 while (cur ! NULL) { next cur-next; // 先保住后面的链表 cur-next pre; // 反转当前节点的指针 pre cur; // pre 和 cur 各向前一步 cur next; } L-next pre; // 最后 pre 指向原链表的尾节点变成了新表头 }这段代码里最容易写错的是循环中的顺序。next 必须在 cur-next 被修改之前取走否则 cur 后面的节点全部丢失链表直接断掉。另一种等价写法是头插法变体把原链表从头到尾摘下来再逐个插回头结点后面。头插法更好理解但每一轮要多做一次链表遍历如果题目要求严格 O(n)还是三指针法更标准。验收时老师常追问“如果链表只有一个元素会怎样”三指针法里 cur 不为空pre 为空循环结束后 L-next 指向原节点自己逻辑正确。3.2 有序合并的两个链表谁动了你的尾指针合并两个递增有序链表成一个递增链表要求不额外建节点这点务必注意。很多实现会 malloc 新节点虽然功能对但空间复杂度超标验收时会被扣分。标准做法是把两个链表原地串起来用三个指针分别跟踪合并链表尾部、L1 当前节点和 L2 当前节点。// 合并两个递增链表 L1、L2结果存入 L1不额外分配节点 void MergeList(LinkList L1, LinkList L2) { Node *pa L1-next; // 遍历 L1 的指针 Node *pb L2-next; // 遍历 L2 的指针 Node *tail L1; // 合并后链表的尾指针初始指向 L1 头结点 while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { tail-next pa; // 接入 pa tail pa; // 更新尾指针 pa pa-next; } else { tail-next pb; tail pb; pb pb-next; } } // 把剩余部分直接接上不需要逐个搬运 tail-next (pa ! NULL) ? pa : pb; }这段代码的经典错误有两个一是循环里忘了更新 tail导致后面的节点全部挂到了链表尾部之前二是最后直接 tail-next L2 而非 pb把 L2 的头结点也挂在合并链表里造成数据错乱。合并完成后L2 的头结点虽然没有被释放但也应该把 L2-next 置为 NULL避免外部通过 L2 再访问已经被合并进 L1 的节点造成双重释放。这个小细节你在报告里写一句老师会觉得你考虑到了内存安全。3.3 删除链表中重复元素双指针还是三指针重复元素删除在实验里也有出现。要求删除有序链表中的重复节点但保留第一个出现的元素。此时需要三个指针prev 指向已确认保留的最后一个节点cur 指向当前扫描节点next 暂存后继。// 删除有序链表中的重复节点保留每个值的第一个出现位置 void DeleteDuplicates(LinkList L) { if (L-next NULL) return; Node *prev L-next; // 第一个节点一定保留 Node *cur prev-next; while (cur ! NULL) { if (prev-data cur-data) { // 遇到重复值 prev-next cur-next; // 跳过 cur free(cur); // 释放当前重复节点 } else { prev cur; // 值不同prev 前移 } cur prev-next; // 继续扫描下一个 } }注意这个写法里 cur 更新放在循环末尾而且删除节点后 prev 不动因为 prev 和它后面的新节点可能又构成重复。如果把 prev 也前移就会漏删连续三个以上相同值的情况。这个点特别适合写进实验报告的“算法正确性讨论”里属于一眼就能看出你理解了循环不变量的位置。4. 循环链表解决约瑟夫环问题把线性结构玩成闭环约瑟夫环是北邮实验里的常客它本身是线性表但因为每次出列都要从头遍历到指定位置用单向链表做会非常笨拙而循环链表加指针后移能把删除操作的时间复杂度降到 O(1) 级别代价只是初始化时多一步把尾节点指向头结点。这一章讲循环链表的建表、遍历和删除并且给出一个直接能跑的完整实现。4.1 为什么约瑟夫环用循环链表是自然选择约瑟夫环问题的描述是 n 个人围一圈从第 k 个人开始报数数到 m 的人出列然后从下一个人重新报数。用普通单链表做每次数到 m 需要从头遍历整体复杂度 O(n*m)用循环链表做报数过程就是指针移动m 次指针跳转就到目标节点而且删除一个节点只需改两个指针不需要从头找前驱。这里有一个容易忽略的设计点单向循环链表的删除需要知道前驱节点。如果只有当前节点指针删除当前节点就得再遍历一圈找前驱反而得不偿失。所以实现时我一般用每轮移动到目标节点的前驱位置再操作让当前指针始终停在待删除节点的前驱上。#include stdio.h #include stdlib.h typedef struct CNode { int id; struct CNode *next; } CNode, *CLinkList; // 创建 n 个节点的循环链表返回尾指针 CNode* CreateCircle(int n) { CNode *head (CNode *)malloc(sizeof(CNode)); head-id 1; head-next NULL; CNode *tail head; for (int i 2; i n; i) { CNode *s (CNode *)malloc(sizeof(CNode)); s-id i; s-next NULL; tail-next s; tail s; } tail-next head; // 尾指针指向头形成循环 return tail; // 返回尾指针方便从任意位置开始 } // 约瑟夫环求解n 个人从编号 start 开始报数报数为 m 的人出列 void Josephus(int n, int start, int m) { CNode *prev CreateCircle(n); CNode *cur prev-next; // 将 cur 移到 start 号节点 for (int i 1; i start; i) { prev cur; cur cur-next; } while (cur-next ! cur) { // 只剩一个节点时停止 for (int i 1; i m; i) { prev cur; cur cur-next; } printf(出列: %d\n, cur-id); prev-next cur-next; // 摘除当前节点 free(cur); cur prev-next; // 从下一个节点重新开始 } printf(最后留下: %d\n, cur-id); free(cur); free(prev); // prev 此时可能是头结点或尾节点 }这个实现的巧妙之处在于 prev 始终作为 cur 的前驱。报数循环执行 m-1 次后cur 停在待删除节点上此时 prev 正好是它的前驱直接改指针即完成删除。最后退出循环时只有一个节点这个节点的前驱是它自己free(cur) 后还要 free(prev)但这里 prev 和 cur 是同一个节点free 两次会报 double free所以正确的写法是在打印后只 free(cur)把 free(prev) 删掉。这个 bug 我当年调试了很久属于典型的指针等价关系没想清楚。4.2 循环链表的遍历终止条件do-while 比 while 友好循环链表的遍历不能简单用 while (p ! NULL)因为循环链表没有 NULL 结尾p 永远不会是 NULL。常见的做法是先保存头结点指针然后一路遍历直到回到头结点。但如果你用 while (p ! head) 来写第一次进入循环时 p 就等于 head循环体一次都不会执行所以必须用 do-while 结构让它先执行一次再判断。void TraverseCircle(CLinkList L) { if (L NULL) return; CLinkList p L; do { printf(%d , p-id); p p-next; } while (p ! L); printf(\n); }这段代码有两个坑。第一如果 L 本身是尾指针而不是头指针从尾开始遍历会漏掉一半节点所以调用前必须确认传进来的指向。第二循环条件 p ! L 是安全的因为哪怕链表绕回来了也会在起点停下不会死循环。如果初始 list 恰好只有头结点自身一个节点do-while 也会先打印再判断逻辑成立。4.3 约瑟夫环的复杂度与改进方向上面代码的复杂度是 O(n*m)n 是人数m 是报数间隔。如果 m 特别大比如一百万这个算法就非常慢。改进方案有两种一种是用数学递推直接推出最后留下的人另一种是把线性表换成树状结构维护区间信息。但北邮实验只要交基础版本即可复杂度分析写进报告就够了。报告里可以补一句“当 m n 时可以通过 m m % 当前人数 来缩短报数路程”这个优化虽然不改变渐进复杂度但能体现你思考过。5. 实验验收避坑指南指针、内存和报告里的五个高频翻车点这一章是血泪经验的汇总。每年北邮的数据结构实验验收机房里的报错声集中在几类问题上很多同学排错排到怀疑人生最后发现是低级错误。我把 5 个高频翻车点按“现象、原因、解决”列清楚每一个都是实际调试中反复出现的。5.1 插入操作后链表遍历输出成了死循环现象插入新节点后用 while (p ! NULL) 遍历程序不停输出最后按 CtrlC 强杀。原因新节点的 next 没有初始化。malloc 出来的内存是随机值不是 NULL导致链表尾部指向了一个野地址遍历停不下来。解决每次 malloc 节点后立刻执行 s-next NULL或者在创建时主动赋值。这个习惯要像写飞机稿一样刻进肌肉记忆。用 calloc 也行它会自动清零但大部分人习惯用 malloc那就必须手动初始化。5.2 释放链表时程序崩溃free 了一个已经释放过的节点现象写完销毁链表的函数一调用就 Segfault或者报 double free 错误。原因销毁函数里没有把当前指针先保存下来再 free。典型错误写法是 while (p) { free(p); p p-next; }free(p) 之后还去访问 p-next此时 p 指向的是已释放内存访问其成员属于使用悬垂指针。解决先暂存后继再释放当前节点。void DestroyList(LinkList L) { Node *p L; while (p ! NULL) { Node *tmp p-next; // 先保存后继 free(p); p tmp; } }5.3 顺序表插入位置和前一个实验的结果对不上现象向顺序表插入元素后打印出来发现元素整体往后挪了两位或头部多了一个垃圾值。原因没有区分“逻辑位置”和“数组下标”。实验题里一般说“在第 i 个位置插入”i 从 1 开始数数组下标从 0 开始实际数组下标是 i-1。很多同学直接拿 i 当数组下标用插完一看位置差了一位。解决统一约法三章函数接口的 pos 参数从 1 开始计数函数内部自己转换为下标。转换逻辑写在代码注释里报告里也写明验收时不容易嘴瓢。5.4 把头结点当成了数据节点输出现象输出链表时第一个值是一个奇怪的整数比如 0 或者一个很大的地址值。原因遍历从 L 开始而不是从 L-next 开始。头结点不存储数据直接 printf(L-data) 输出的是未定义的垃圾值。解决养成习惯带头结点的链表遍历一律从 L-next 开始。头结点存在的意义就是让空表的操作可以统一处理不是用来存数据的。5.5 两个链表合并后原链表还能“看到”已并入节点现象合并函数执行完后原链表 L2 的遍历结果还是完整的而且和 L1 里部分节点完全一样。原因合并时只是改了指针L2 的头结点仍然指向已并入 L1 的节点所以顺着 L2 头结点仍然能访问到这些节点。这在逻辑上叫“别名问题”。解决合并完成后立即把 L2-next 置为 NULL。这不释放任何内存只是切断外部访问路径防止后续误操作。虽然不是必扣分项但写上这一行老师会认为你理解了指针语义。6. 实验报告加分项用测试用例设计与复杂度分析拉开差距实验做完代码功能正确只是及格线。北邮的老师会翻报告看测试用例是否覆盖边界复杂度分析是否有深度。这一章讲怎么用最小的成本给报告加分核心是三件事边界测试、复杂度写法、代码可读性处理。6.1 边界测试用例设计很多同学测试只用一组正常数据比如建一个 5 个节点的链表插入删除各做一次就收工。老师一眼就能看出你没测过边界。至少要补齐这几组用例场景输入示例预期结果覆盖的边界空表插入在空顺序表第 1 位插入 10length 1data[0] 10插入位置上下界表尾插入在 length 位置插入 x原最后元素后新增pos 等 length1表头插入在 1 位置插入 x原第一个元素变第二个pos 等 1非法位置在 length2 插入提示非法表不变越界保护删除唯一节点只剩一个节点时删除空表长度 0空表不崩溃链表逆转为空/单节点空表或 1 个节点不崩溃链不变循环边界每组用例在报告里写清输入、输出、实际结果三项。老师浏览报告的速度很快表格能让他十秒内确认你的测试是有体系的。对应的代码可以在 main 函数里用几个断言函数配合比如 assert(ListLength(L) 0) 这一类代码里写上几行验证报告里就不用贴全部输出。// 简易自测断言适合实验报告展示 void TestSeqList() { SeqList L; InitList(L); ListInsert(L, 1, 5); // {5} ListInsert(L, 1, 3); // {3, 5} ListInsert(L, 3, 7); // {3, 5, 7} if (L.data[0] ! 3 || L.length ! 3) { printf(测试失败: 插入逻辑错误\n); exit(1); } ListDelete(L, 2); // 删除下标位置的值 5 if (L.length ! 2 || L.data[1] ! 7) { printf(测试失败: 删除逻辑错误\n); exit(1); } printf(顺序表基础测试全部通过\n); }如果实验要求支持键盘输入assert 式测试就不够用了要把标准输入重定向到测试文件或者把测试数据写死在代码里用注释标出。北邮有些实验平台要求程序从标准输入读数据这时候最好在报告里说明测试输入文件的组织方式比如第一行是操作数后续行是具体指令。这个行为本身就是一种工程素养展示。6.2 复杂度分析怎么写才不空洞报告里的复杂度分析不要只写“插入为 O(n)”要按不同位置写清楚。比如顺序表插入在最好情况下是 O(1)在表头最坏是 O(n)平均是 O(n/2)化简为 O(n)。链表插入固定 O(1)——只要能拿到前驱指针。就地逆转 O(n) 且空间 O(1)。约瑟夫环 O(n*m)。这些叙述要配上对应的解释比如为什么链表最坏情况也是 O(1)——因为插入操作本身只改指针找前驱的时间另算。还有一类容易被忽略的是空间复杂度。链表的额外空间包括 n 个节点各多一个 next 指针所以额外空间 O(n)。顺序表有扩容预留空间动态扩容时最大浪费 O(max_size - length)。报告里写“空间换时间”不能只当口号要具体到差了多少最好举一个数据量例子比如 10 万个整数时顺序表比链表省约 32 万字节这是用 sizeof(int*) 4 字节算出来的。6.3 代码风格验收提问前最后一道防线代码风格不会直接加分但会决定老师愿不愿意仔细看你的报告。重点做三件事。第一函数名用动词开头ListInsert、DeleteElem、ReverseList不要用 f1、f2。第二凡是涉及指针修改的函数在头部注释里写清参数含义和返回约定。第三main 函数不要超过 30 行核心逻辑拆分到子函数里每个子函数控制在 40 行以内。北邮的验收环节有时候会现场让你改一个功能比如“改成删除所有值为 x 的元素”。如果你的代码函数职责清晰改起来是几分钟的事如果所有逻辑都堆在 main 里现场改代码基本等于重写很容易当场翻车。这是最实用的一条血泪经验比多背几个算法都有用。数据结构实验真正练的不是背模板而是让你在指针、内存和流程控制之间建立肌肉记忆。如果你时间富余建议再做一件事把顺序表和链表两个实现放到同一个工程里用相同的测试数据跑一遍对比两者的插入耗时。这个对比实验不用写得花哨但报告里放一张简单的时间对比表你就能把线性表的选题逻辑从“老师要求的”变成“我自己验证过的”。这种细节对最终实验分的影响往往比多写一百行代码都大。希望这篇笔记能帮你顺利跑通北邮的这一次实验也给后面的树和图实验打好底子。本文还有配套的精品资源点击获取
数据结构实验线性表指南：顺序表与链表核心操作避坑
简介北邮数据结构实验线性表文档面向北邮学生及数据结构初学者完整呈现实验要求、带头结点单链表的存储结构、关键算法分析与测试main()函数实现。文档首先介绍链表采用一组任意的存储单元存放结点逻辑次序与物理次序不必相同每个结点包含数据域与指针域随后逐一详解头插法、尾插法、析构函数、按位查找、按值查找、插入、删除、遍历、获取长度等核心操作每个操作均给出具体步骤与时间复杂度说明例如头插法O(n)、插入操作O(1)便于读者对照代码理解单链表的底层原理。资源共包含1个doc文件压缩包大小约6.3MB内容精炼且结构清晰并附流程示意图与运行结果适合用作实验参考、期末复习或自学材料。已有597人学习下载说明其实用性获得认可对完成北邮数据结构实验、掌握线性表编程尤其有帮助。1. 北邮数据结构实验线性表从建表到多项式运算的实验主线北邮的数据结构实验里线性表是第一个硬骨头。很多人在实验前一晚才开始敲代码结果在“就地逆转链表”这种题上卡到怀疑人生最后拿着和别人雷同的代码去验收被老师一问就翻车。这门实验表面上只要求你用顺序表或链表实现几个基本操作实际考察的是你对内存布局、指针操作和算法边界的理解深度。这篇笔记按北邮实验的常见要求把建表、插入删除、查找逆转、有序合并到多项式运算这条线走一遍给你一套能直接照着写的代码骨架也把容易扣分和容易翻车的细节全部挑出来。无论是大一刚接触数据结构的初学者还是考前突击的老手沿着这条线做一遍实验报告和代码质量都能上一个台阶。2. 顺序表和链表怎么选数据规模与操作频率决定实验分北邮实验通常要求线性表用两种存储结构各实现一遍或者至少明确说明选型理由。很多同学在报告里写“因为题目要求用链表”这等于没写。判分老师想看到的是你对两种物理结构的成本有量化认识这一章把选型逻辑讲透再给出两种结构的可运行骨架。2.1 顺序表的代价模型为什么频繁插入会让数组类实现难堪顺序表的核心优势是随机访问按下标取元素的时间复杂度是 O(1)这一点在查找类操作里碾压链表。但它的插入和删除最好情况下 O(1)——直接在表尾操作最坏情况下 O(n)——在表头操作需要把后面所有元素都搬移。北邮实验里常见的一个考核点是从表头反复插入一组数据建表这时候顺序表的时间开销是 O(n²)数据量一旦到一万级程序就会出现肉眼可见的停顿。另一个常被忽略的问题是顺序表的扩容策略。静态分配的数组定死了容量动态分配的数组需要手动 realloc。严蔚敏《数据结构C语言版》里的写法是 increment 增量扩容但这个增量给多少很讲经验。给的太小频繁 realloc 导致内存搬移和碎片给的太大浪费空间。我一般按当前容量的 1.5 到 2 倍扩每次扩容后把旧数据 memcpy 过去别用循环逐个赋值后者不仅慢代码还丑。#include stdio.h #include stdlib.h #include string.h #define INIT_SIZE 100 #define INCREMENT 50 typedef struct { int *data; int length; int max_size; } SeqList; // 初始化空表 void InitList(SeqList *L) { L-data (int *)malloc(INIT_SIZE * sizeof(int)); if (!L-data) exit(1); // 分配失败直接退出 L-length 0; L-max_size INIT_SIZE; } // 在第 pos 个位置插入元素 epos 从 1 开始计数 void ListInsert(SeqList *L, int pos, int e) { if (pos 1 || pos L-length 1) { printf(插入位置非法\n); return; } if (L-length L-max_size) { // 满了就扩容 int *new_data (int *)realloc(L-data, (L-max_size INCREMENT) * sizeof(int)); if (!new_data) exit(1); L-data new_data; L-max_size INCREMENT; } for (int i L-length - 1; i pos - 1; i--) { L-data[i 1] L-data[i]; // 从后往前搬避免覆盖 } L-data[pos - 1] e; L-length; }这段代码的关键在插入处的循环。从后往前搬移是为了防止前面元素覆盖后面还没搬走的数据这是一个新手高频错误。扩容用的 realloc 会在原地址放不下时自动搬移并返回新地址所以必须把返回值赋给 L-data直接用原来的指针会导致悬空。pos 位置逻辑从 1 开始数组下标从 0 开始这个映射关系搞错会导致插入位置整体偏移一位。2.2 链表的指针陷阱为什么表头插入比表尾插入友好得多链表不需要搬移数据插入删除只要改指针就能完成时间复杂度 O(1)。但它的代价是随机访问需要从头遍历而且每个节点额外消耗一个指针域的空间。北邮实验里最常见的链表要求是带头结点的单链表这个头结点不存数据纯粹为了让表头插入和中间插入的代码逻辑统一避免单独处理“插到空表”这种边界情况。很多同学在建立链表时按尾插法写需要维护一个尾指针每插入一个新节点都要从头遍历或者引用这个尾指针。代码写起来啰嗦就算了稍不注意尾指针没更新链表就断在中间。头插法就简单得多每次把新节点插到头结点后面代码只有三行但建出来的链表顺序和输入顺序相反这一点实验报告里必须说明。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node, *LinkList; // 头插法建立链表输入 1 2 3链表存储顺序为 3 2 1 LinkList CreateListHead() { LinkList L (Node *)malloc(sizeof(Node)); // 头结点 L-next NULL; int x; while (scanf(%d, x) ! EOF) { Node *s (Node *)malloc(sizeof(Node)); s-data x; s-next L-next; // 新节点指向原来的第一个节点 L-next s; // 头结点指向新节点 } return L; }头插法代码量少但是存在一个内存分配失败没有处理的问题——上述代码里 malloc 后没检查返回值这在验收时被问“如果分配失败怎么办”很容易卡壳。更稳的写法是分配后立刻判断失败就释放已有链表并返回 NULL。另外头结点是不参与计数的遍历时从 L-next 开始这个习惯越早养越好。2.3 选型决策表北邮实验题面里的暗示信号北邮的实验指导书一般不会直接告诉你“这题用哪种结构”但题面里通常藏着信号。按我的经验把决策条件列一张表做实验选择时直接对号入座既省时间又能在报告里写清楚理由。题面特征适合结构核心理由大量按下标/位置查找顺序表O(1) 随机访问大量在两端或中部插入删除链表O(1) 指针修改数据规模未知可能暴涨链表或动态扩容顺序表链表按需分配顺序表需控制增量需要反复遍历但不改结构顺序表缓存友好遍历速度快内存受限节点数量极大顺序表链表多存 4/8 字节指针内存开销高约瑟夫环、多项式运算等动态场景循环链表/链表删除节点频繁需 O(1) 删除这个表格可以原样写进实验报告的设计分析部分老师会觉得你确实对比过两种结构而不只是把教科书的结论抄了一遍。真实实验里还有一类隐性要求如果题面对时间复杂度有明确限制比如“算法要求在 O(n) 内完成”那么链表比顺序表更容易达标因为顺序表的插入删除往往超过这个界限。3. 单链表的就地逆转与有序合并实验报告里的高分代码段这一章是北邮线性表实验的核心战场。逆转链表和合并两个有序链表几乎每年都出现在实验或验收提问里而且这两道题能很好地暴露你对指针操作的熟练度。很多同学拿着网上抄的递归逆转代码去验收被问“递归栈深度是多少”就哑了。下面给的是迭代写法辅以必考的边界讲解。3.1 就地逆转的迭代实现三指针法与头插法变体就地逆转要求不使用额外空间只改指针方向。最稳妥的思路是三指针法pre 指向前一个节点cur 指向当前节点next 暂存 cur 的后继防止修改 cur-next 后丢失后续链表。// 就地逆转带头结点的单链表时间复杂度 O(n)空间复杂度 O(1) void ReverseList(LinkList L) { Node *pre NULL; // 前驱初始为空 Node *cur L-next; // 当前节点从头结点后的第一个节点开始 Node *next NULL; // 暂存后继 while (cur ! NULL) { next cur-next; // 先保住后面的链表 cur-next pre; // 反转当前节点的指针 pre cur; // pre 和 cur 各向前一步 cur next; } L-next pre; // 最后 pre 指向原链表的尾节点变成了新表头 }这段代码里最容易写错的是循环中的顺序。next 必须在 cur-next 被修改之前取走否则 cur 后面的节点全部丢失链表直接断掉。另一种等价写法是头插法变体把原链表从头到尾摘下来再逐个插回头结点后面。头插法更好理解但每一轮要多做一次链表遍历如果题目要求严格 O(n)还是三指针法更标准。验收时老师常追问“如果链表只有一个元素会怎样”三指针法里 cur 不为空pre 为空循环结束后 L-next 指向原节点自己逻辑正确。3.2 有序合并的两个链表谁动了你的尾指针合并两个递增有序链表成一个递增链表要求不额外建节点这点务必注意。很多实现会 malloc 新节点虽然功能对但空间复杂度超标验收时会被扣分。标准做法是把两个链表原地串起来用三个指针分别跟踪合并链表尾部、L1 当前节点和 L2 当前节点。// 合并两个递增链表 L1、L2结果存入 L1不额外分配节点 void MergeList(LinkList L1, LinkList L2) { Node *pa L1-next; // 遍历 L1 的指针 Node *pb L2-next; // 遍历 L2 的指针 Node *tail L1; // 合并后链表的尾指针初始指向 L1 头结点 while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { tail-next pa; // 接入 pa tail pa; // 更新尾指针 pa pa-next; } else { tail-next pb; tail pb; pb pb-next; } } // 把剩余部分直接接上不需要逐个搬运 tail-next (pa ! NULL) ? pa : pb; }这段代码的经典错误有两个一是循环里忘了更新 tail导致后面的节点全部挂到了链表尾部之前二是最后直接 tail-next L2 而非 pb把 L2 的头结点也挂在合并链表里造成数据错乱。合并完成后L2 的头结点虽然没有被释放但也应该把 L2-next 置为 NULL避免外部通过 L2 再访问已经被合并进 L1 的节点造成双重释放。这个小细节你在报告里写一句老师会觉得你考虑到了内存安全。3.3 删除链表中重复元素双指针还是三指针重复元素删除在实验里也有出现。要求删除有序链表中的重复节点但保留第一个出现的元素。此时需要三个指针prev 指向已确认保留的最后一个节点cur 指向当前扫描节点next 暂存后继。// 删除有序链表中的重复节点保留每个值的第一个出现位置 void DeleteDuplicates(LinkList L) { if (L-next NULL) return; Node *prev L-next; // 第一个节点一定保留 Node *cur prev-next; while (cur ! NULL) { if (prev-data cur-data) { // 遇到重复值 prev-next cur-next; // 跳过 cur free(cur); // 释放当前重复节点 } else { prev cur; // 值不同prev 前移 } cur prev-next; // 继续扫描下一个 } }注意这个写法里 cur 更新放在循环末尾而且删除节点后 prev 不动因为 prev 和它后面的新节点可能又构成重复。如果把 prev 也前移就会漏删连续三个以上相同值的情况。这个点特别适合写进实验报告的“算法正确性讨论”里属于一眼就能看出你理解了循环不变量的位置。4. 循环链表解决约瑟夫环问题把线性结构玩成闭环约瑟夫环是北邮实验里的常客它本身是线性表但因为每次出列都要从头遍历到指定位置用单向链表做会非常笨拙而循环链表加指针后移能把删除操作的时间复杂度降到 O(1) 级别代价只是初始化时多一步把尾节点指向头结点。这一章讲循环链表的建表、遍历和删除并且给出一个直接能跑的完整实现。4.1 为什么约瑟夫环用循环链表是自然选择约瑟夫环问题的描述是 n 个人围一圈从第 k 个人开始报数数到 m 的人出列然后从下一个人重新报数。用普通单链表做每次数到 m 需要从头遍历整体复杂度 O(n*m)用循环链表做报数过程就是指针移动m 次指针跳转就到目标节点而且删除一个节点只需改两个指针不需要从头找前驱。这里有一个容易忽略的设计点单向循环链表的删除需要知道前驱节点。如果只有当前节点指针删除当前节点就得再遍历一圈找前驱反而得不偿失。所以实现时我一般用每轮移动到目标节点的前驱位置再操作让当前指针始终停在待删除节点的前驱上。#include stdio.h #include stdlib.h typedef struct CNode { int id; struct CNode *next; } CNode, *CLinkList; // 创建 n 个节点的循环链表返回尾指针 CNode* CreateCircle(int n) { CNode *head (CNode *)malloc(sizeof(CNode)); head-id 1; head-next NULL; CNode *tail head; for (int i 2; i n; i) { CNode *s (CNode *)malloc(sizeof(CNode)); s-id i; s-next NULL; tail-next s; tail s; } tail-next head; // 尾指针指向头形成循环 return tail; // 返回尾指针方便从任意位置开始 } // 约瑟夫环求解n 个人从编号 start 开始报数报数为 m 的人出列 void Josephus(int n, int start, int m) { CNode *prev CreateCircle(n); CNode *cur prev-next; // 将 cur 移到 start 号节点 for (int i 1; i start; i) { prev cur; cur cur-next; } while (cur-next ! cur) { // 只剩一个节点时停止 for (int i 1; i m; i) { prev cur; cur cur-next; } printf(出列: %d\n, cur-id); prev-next cur-next; // 摘除当前节点 free(cur); cur prev-next; // 从下一个节点重新开始 } printf(最后留下: %d\n, cur-id); free(cur); free(prev); // prev 此时可能是头结点或尾节点 }这个实现的巧妙之处在于 prev 始终作为 cur 的前驱。报数循环执行 m-1 次后cur 停在待删除节点上此时 prev 正好是它的前驱直接改指针即完成删除。最后退出循环时只有一个节点这个节点的前驱是它自己free(cur) 后还要 free(prev)但这里 prev 和 cur 是同一个节点free 两次会报 double free所以正确的写法是在打印后只 free(cur)把 free(prev) 删掉。这个 bug 我当年调试了很久属于典型的指针等价关系没想清楚。4.2 循环链表的遍历终止条件do-while 比 while 友好循环链表的遍历不能简单用 while (p ! NULL)因为循环链表没有 NULL 结尾p 永远不会是 NULL。常见的做法是先保存头结点指针然后一路遍历直到回到头结点。但如果你用 while (p ! head) 来写第一次进入循环时 p 就等于 head循环体一次都不会执行所以必须用 do-while 结构让它先执行一次再判断。void TraverseCircle(CLinkList L) { if (L NULL) return; CLinkList p L; do { printf(%d , p-id); p p-next; } while (p ! L); printf(\n); }这段代码有两个坑。第一如果 L 本身是尾指针而不是头指针从尾开始遍历会漏掉一半节点所以调用前必须确认传进来的指向。第二循环条件 p ! L 是安全的因为哪怕链表绕回来了也会在起点停下不会死循环。如果初始 list 恰好只有头结点自身一个节点do-while 也会先打印再判断逻辑成立。4.3 约瑟夫环的复杂度与改进方向上面代码的复杂度是 O(n*m)n 是人数m 是报数间隔。如果 m 特别大比如一百万这个算法就非常慢。改进方案有两种一种是用数学递推直接推出最后留下的人另一种是把线性表换成树状结构维护区间信息。但北邮实验只要交基础版本即可复杂度分析写进报告就够了。报告里可以补一句“当 m n 时可以通过 m m % 当前人数 来缩短报数路程”这个优化虽然不改变渐进复杂度但能体现你思考过。5. 实验验收避坑指南指针、内存和报告里的五个高频翻车点这一章是血泪经验的汇总。每年北邮的数据结构实验验收机房里的报错声集中在几类问题上很多同学排错排到怀疑人生最后发现是低级错误。我把 5 个高频翻车点按“现象、原因、解决”列清楚每一个都是实际调试中反复出现的。5.1 插入操作后链表遍历输出成了死循环现象插入新节点后用 while (p ! NULL) 遍历程序不停输出最后按 CtrlC 强杀。原因新节点的 next 没有初始化。malloc 出来的内存是随机值不是 NULL导致链表尾部指向了一个野地址遍历停不下来。解决每次 malloc 节点后立刻执行 s-next NULL或者在创建时主动赋值。这个习惯要像写飞机稿一样刻进肌肉记忆。用 calloc 也行它会自动清零但大部分人习惯用 malloc那就必须手动初始化。5.2 释放链表时程序崩溃free 了一个已经释放过的节点现象写完销毁链表的函数一调用就 Segfault或者报 double free 错误。原因销毁函数里没有把当前指针先保存下来再 free。典型错误写法是 while (p) { free(p); p p-next; }free(p) 之后还去访问 p-next此时 p 指向的是已释放内存访问其成员属于使用悬垂指针。解决先暂存后继再释放当前节点。void DestroyList(LinkList L) { Node *p L; while (p ! NULL) { Node *tmp p-next; // 先保存后继 free(p); p tmp; } }5.3 顺序表插入位置和前一个实验的结果对不上现象向顺序表插入元素后打印出来发现元素整体往后挪了两位或头部多了一个垃圾值。原因没有区分“逻辑位置”和“数组下标”。实验题里一般说“在第 i 个位置插入”i 从 1 开始数数组下标从 0 开始实际数组下标是 i-1。很多同学直接拿 i 当数组下标用插完一看位置差了一位。解决统一约法三章函数接口的 pos 参数从 1 开始计数函数内部自己转换为下标。转换逻辑写在代码注释里报告里也写明验收时不容易嘴瓢。5.4 把头结点当成了数据节点输出现象输出链表时第一个值是一个奇怪的整数比如 0 或者一个很大的地址值。原因遍历从 L 开始而不是从 L-next 开始。头结点不存储数据直接 printf(L-data) 输出的是未定义的垃圾值。解决养成习惯带头结点的链表遍历一律从 L-next 开始。头结点存在的意义就是让空表的操作可以统一处理不是用来存数据的。5.5 两个链表合并后原链表还能“看到”已并入节点现象合并函数执行完后原链表 L2 的遍历结果还是完整的而且和 L1 里部分节点完全一样。原因合并时只是改了指针L2 的头结点仍然指向已并入 L1 的节点所以顺着 L2 头结点仍然能访问到这些节点。这在逻辑上叫“别名问题”。解决合并完成后立即把 L2-next 置为 NULL。这不释放任何内存只是切断外部访问路径防止后续误操作。虽然不是必扣分项但写上这一行老师会认为你理解了指针语义。6. 实验报告加分项用测试用例设计与复杂度分析拉开差距实验做完代码功能正确只是及格线。北邮的老师会翻报告看测试用例是否覆盖边界复杂度分析是否有深度。这一章讲怎么用最小的成本给报告加分核心是三件事边界测试、复杂度写法、代码可读性处理。6.1 边界测试用例设计很多同学测试只用一组正常数据比如建一个 5 个节点的链表插入删除各做一次就收工。老师一眼就能看出你没测过边界。至少要补齐这几组用例场景输入示例预期结果覆盖的边界空表插入在空顺序表第 1 位插入 10length 1data[0] 10插入位置上下界表尾插入在 length 位置插入 x原最后元素后新增pos 等 length1表头插入在 1 位置插入 x原第一个元素变第二个pos 等 1非法位置在 length2 插入提示非法表不变越界保护删除唯一节点只剩一个节点时删除空表长度 0空表不崩溃链表逆转为空/单节点空表或 1 个节点不崩溃链不变循环边界每组用例在报告里写清输入、输出、实际结果三项。老师浏览报告的速度很快表格能让他十秒内确认你的测试是有体系的。对应的代码可以在 main 函数里用几个断言函数配合比如 assert(ListLength(L) 0) 这一类代码里写上几行验证报告里就不用贴全部输出。// 简易自测断言适合实验报告展示 void TestSeqList() { SeqList L; InitList(L); ListInsert(L, 1, 5); // {5} ListInsert(L, 1, 3); // {3, 5} ListInsert(L, 3, 7); // {3, 5, 7} if (L.data[0] ! 3 || L.length ! 3) { printf(测试失败: 插入逻辑错误\n); exit(1); } ListDelete(L, 2); // 删除下标位置的值 5 if (L.length ! 2 || L.data[1] ! 7) { printf(测试失败: 删除逻辑错误\n); exit(1); } printf(顺序表基础测试全部通过\n); }如果实验要求支持键盘输入assert 式测试就不够用了要把标准输入重定向到测试文件或者把测试数据写死在代码里用注释标出。北邮有些实验平台要求程序从标准输入读数据这时候最好在报告里说明测试输入文件的组织方式比如第一行是操作数后续行是具体指令。这个行为本身就是一种工程素养展示。6.2 复杂度分析怎么写才不空洞报告里的复杂度分析不要只写“插入为 O(n)”要按不同位置写清楚。比如顺序表插入在最好情况下是 O(1)在表头最坏是 O(n)平均是 O(n/2)化简为 O(n)。链表插入固定 O(1)——只要能拿到前驱指针。就地逆转 O(n) 且空间 O(1)。约瑟夫环 O(n*m)。这些叙述要配上对应的解释比如为什么链表最坏情况也是 O(1)——因为插入操作本身只改指针找前驱的时间另算。还有一类容易被忽略的是空间复杂度。链表的额外空间包括 n 个节点各多一个 next 指针所以额外空间 O(n)。顺序表有扩容预留空间动态扩容时最大浪费 O(max_size - length)。报告里写“空间换时间”不能只当口号要具体到差了多少最好举一个数据量例子比如 10 万个整数时顺序表比链表省约 32 万字节这是用 sizeof(int*) 4 字节算出来的。6.3 代码风格验收提问前最后一道防线代码风格不会直接加分但会决定老师愿不愿意仔细看你的报告。重点做三件事。第一函数名用动词开头ListInsert、DeleteElem、ReverseList不要用 f1、f2。第二凡是涉及指针修改的函数在头部注释里写清参数含义和返回约定。第三main 函数不要超过 30 行核心逻辑拆分到子函数里每个子函数控制在 40 行以内。北邮的验收环节有时候会现场让你改一个功能比如“改成删除所有值为 x 的元素”。如果你的代码函数职责清晰改起来是几分钟的事如果所有逻辑都堆在 main 里现场改代码基本等于重写很容易当场翻车。这是最实用的一条血泪经验比多背几个算法都有用。数据结构实验真正练的不是背模板而是让你在指针、内存和流程控制之间建立肌肉记忆。如果你时间富余建议再做一件事把顺序表和链表两个实现放到同一个工程里用相同的测试数据跑一遍对比两者的插入耗时。这个对比实验不用写得花哨但报告里放一张简单的时间对比表你就能把线性表的选题逻辑从“老师要求的”变成“我自己验证过的”。这种细节对最终实验分的影响往往比多写一百行代码都大。希望这篇笔记能帮你顺利跑通北邮的这一次实验也给后面的树和图实验打好底子。本文还有配套的精品资源点击获取
