1. 章节定位为什么第二章是整本书的分水岭先聊点题外话。严蔚敏老师的《数据结构C语言版 第2版》是国内计算机专业覆盖面最广的教材之一也是很多学校考研指定的参考书。我当年备考的时候身边至少有三种不同版本的答案资料在流传有的复印模糊有的题号对不上有的代码风格跟教材差异太大。第二章线性表更是重灾区因为这一章的课后题数量和类型都比较杂从基础的概念题到需要手写完整算法的设计题都有很多同学刷到一半就卡住了。第二章之所以关键是因为它承担了两个任务一是帮你建立“逻辑结构”和“存储结构”的区分意识——同样是线性表顺序存储和链式存储的增删查改效率完全不同二是引入了大量后面章节会反复使用的编程范式比如指针操作、动态内存分配、边界条件判断。换句话说这一章如果代码功底不扎实后面学栈、队列、串、树、图都会很吃力。我见过不少同学学到二叉树时回头补线性表代码的效率反而更低。这篇博文我按章节顺序把第二章的课后习题分成“概念辨析题”“算法设计题”“上机实践题”三类来逐个拆解。重点放在需要写代码的题目上每一题都会给出我的完整实现思路、C语言代码、以及我在实际运行中遇到过的问题。比较基础的判断题和填空题我给出关键结论和理由。题目类型数量占比核心考查点建议用时概念辨析题约30%存储结构特性、时间/空间复杂度0.5小时算法设计题约50%线性表操作、边界条件2-3小时上机实践题约20%完整程序调试、测试用例设计2小时2. 先吃透这两个底层概念再做题2.1 顺序表和链表到底该怎么选课后题里反复出现的一个问题就是“什么时候用顺序表什么时候用链表”。很多同学只是机械地背结论但做题时换个问法就不会了。我建议你从三个角度去理解这件事。第一个角度是存储方式。顺序表在内存里是一块连续的区域像电影院的连排座位链表则是分散的节点像停车场里随机停的车通过指针把前后车位串起来。这个差异决定了顺序表支持随机访问下标定位的时间复杂度是O(1)而链表想找第i个节点必须从头开始数最坏是O(n)。第二个角度是插入删除操作。顺序表的插入和删除平均要移动一半的元素链表只需要修改指针指向从算法复杂度上看链表更优。但实际工程里不能只看复杂度因为顺序表的内存连续特性对CPU缓存更友好数据量不大时顺序表往往更快。我在处理一些学生项目时发现数据量在一万以内顺序表的实测性能经常反超链表。第三个角度是存储密度。顺序表除了数据本身几乎没有额外开销链表每个节点都要多存一个指针存储密度低于顺序表。如果节点数据本身很小比如只存一个int那链表的指针开销甚至会超过数据本身。理解这三点之后再回头看“设计一个算法判断一个线性表更适合用顺序表还是链表”这类题你就知道该怎么答了。2.2 C语言指针操作的三个易错点第二章的算法设计题几乎离不开指针尤其是链表部分。我批改学生代码时发现最容易翻车的不是算法思想而是指针操作的基础功底。这里列三个高频易错点。第一个是“指针悬挂”。写过free(p)之后没有把p置为NULL后面继续用p访问内存。这种错误在链表删除节点的题目里特别常见你删掉了节点但原指针还指向那块已经释放的内存再次访问就是未定义行为。正确做法是先用一个临时变量保存下一个节点的地址再释放当前节点。第二个是“头节点”的处理。严蔚敏教材里的单链表默认带头节点头节点不存储数据只是方便统一插入删除的逻辑。很多同学做题时忽略了头节点的存在导致边界判断出错。比如在一个带头节点的链表里删除第一个数据节点和删除中间节点的代码可以完全一样这是头节点最大的好处。第三个是“引用与二重指针”的混淆。C语言里没有C的引用想在函数内修改主函数里的指针变量本身必须传指针的地址也就是二重指针。教材中的一部分算法实现用了C的引用语法但如果你用纯C环境需要改成LinkList *L这种形式。这个问题在考研复试上机环节尤其容易踩坑。3. 顺序表部分课后习题算法逐题精解3.1 逆置顺序表一个原地算法两种边界条件逆置顺序表是第二章非常经典的一道题。题目要求不开辟新数组把顺序表中的元素原地逆置。核心思路是双指针一个指向表头一个指向表尾交换它们的值然后头指针后移、尾指针前移直到两个指针相遇。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SqList; void ReverseList(SqList *L) { if (L-length 1) { return; } int low 0; int high L-length - 1; while (low high) { int temp L-data[low]; L-data[low] L-data[high]; L-data[high] temp; low; high--; } }注意边界条件。长度是0或1时直接返回不需要任何操作。循环条件是low high如果写成low high在偶数长度时中间两个元素会交换两次等于白做。当然不影响最终结果但属于多余操作我在代码审查时一般会指出来。这道题的时间复杂度是O(n)空间复杂度是O(1)是典型的“原地”算法。它还有一个变体就是“前m个元素和后n个元素互换位置”本质上是三次逆置先把前m个逆置再把后n个逆置最后整体逆置。这个思路在很多公司笔试里会出现建议顺手练一下。3.2 删除所有值为x的元素两种实现思路对比这道题要求删除顺序表中所有值等于x的元素并且尽量高效。最容易想到的做法是每找到一个x就把它后面的元素全部前移但这样最坏情况时间复杂度是O(n²)不够优雅。更好的思路是“收集非x元素”。用一个变量count记录当前已经收集了多少个非x元素遍历原表遇到非x元素就把它放到位置count上然后count加一。遍历结束后把表长更新为count。这样一趟循环就能完成时间复杂度O(n)且不需要额外空间。void DeleteAllX(SqList *L, int x) { int count 0; for (int i 0; i L-length; i) { if (L-data[i] ! x) { L-data[count] L-data[i]; count; } } L-length count; }有个细节需要注意如果顺序表中元素本身就是x那我们就把“无用的元素”覆盖掉不用管原来的值。但如果x出现得很频繁count的增长速度会明显慢于i后边的非x元素会往前覆盖此时原来位置上的x已经被覆盖了不会产生残留。这个算法是稳定的吗严格说它保持了非x元素的相对顺序所以是稳定的。3.3 删除有序顺序表中重复元素快慢指针的典型应用题目给的是一个非递减有序的顺序表要求删除重复元素使表中每个元素只保留一个。比如[1, 2, 2, 3, 3, 3, 4]变成[1, 2, 3, 4]。思路是用两个下标i和j。i指向“结果表”的最后一个位置j是遍历指针。初始时i0j从1开始。每次发现data[j]不等于data[i]就把i加一然后把data[j]复制到data[i]的位置上。void DeduplicateSorted(SqList *L) { if (L-length 1) { return; } int i 0; for (int j 1; j L-length; j) { if (L-data[j] ! L-data[i]) { i; L-data[i] L-data[j]; } } L-length i 1; }这里比较的是data[j]和data[i]不是data[j]和data[j-1]。因为data[i]始终指向当前结果表的最后一个元素一旦遇到不同的值说明新元素出现了直接放到下一个位置就行。两者效果一样但和data[i]比较的思路更容易推广到“去重后保留前k个”这类变体题。一个值得思考的问题是如果把条件改成“删除所有重复出现的元素即重复元素一个都不留”算法该怎么改比如[1, 2, 2, 3, 3, 4]变成[1, 4]。这就是LeetCode 82题感兴趣可以挑战一下。3.4 两个有序顺序表合并谁的小先放谁合并两个非递减有序的顺序表要求结果仍然有序。核心思路是双指针从头开始同时遍历两个表谁的元素小就先放进结果表里然后对应指针后移。其中一个表遍历完后把另一个表的剩余元素全部拷贝过来。void MergeSqList(SqList A, SqList B, SqList *C) { int i 0, j 0, k 0; while (i A.length j B.length) { if (A.data[i] B.data[j]) { C-data[k] A.data[i]; } else { C-data[k] B.data[j]; } } while (i A.length) { C-data[k] A.data[i]; } while (j B.length) { C-data[k] B.data[j]; } C-length k; }注意这个实现里如果A和B中有相等的元素会优先取A的。这样结果表是稳定的也就是相等元素的相对顺序和原始两个表里的顺序一致。合并操作的时间复杂度是O(mn)是归并排序的核心子过程这个思路后面还会用到。我在做这道题时会额外检查一下C表是否足够大也就是C的容量必须大于等于A.length B.length否则数组越界但这种错误在上机时经常被忽略。4. 链表部分指针操作与算法设计全覆盖4.1 头插法建立单链表代码三行坑有四个用头插法建立单链表的过程很简洁但初次接触的同学很容易犯几个低级错误。标准代码是这样的typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; LinkList CreateListHeadInsert(int arr[], int n) { LinkList L (LinkList)malloc(sizeof(LNode)); L-next NULL; for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next L-next; L-next s; } return L; }第一个坑是忘记让s-next L-next这样新节点直接指向NULL链表会断。第二个坑是忘记把L-next更新为新节点这样新节点虽然创建了但没有串进链表里等于白做。第三个坑是头插法会导致数据顺序和输入顺序相反比如输入[1, 2, 3]链表里的顺序是3-2-1。有些题目要求头插法建立后按输入顺序访问这就需要最后再逆置一次。第四个坑是申请节点后没有判断malloc是否返回NULL在内存紧张时可能导致程序直接崩溃。头插法的一个重要应用是“逆序输出链表”。如果题目要求从尾到头打印链表可以通过头插法重新建立一个新链表然后顺序打印即可。4.2 两个有序单链表合并一个指针让你少写一半代码有些同学合并两个有序链表时会引入三个新指针代码写得又长又容易出bug。其实可以复用两个链表原有的头节点这样只需要一个新头指针和一条游走指针。LinkList MergeLinkList(LinkList A, LinkList B) { LinkList C A; // 复用A的头节点作为结果表的头节点 LNode *p A-next; LNode *q B-next; LNode *r C; // r始终指向结果表的尾节点 C-next NULL; free(B); // B的头节点不再使用释放 while (p ! NULL q ! NULL) { if (p-data q-data) { r-next p; p p-next; } else { r-next q; q q-next; } r r-next; } if (p ! NULL) { r-next p; } if (q ! NULL) { r-next q; } return C; }这里的r是整个算法的关键它始终指向结果表的最后一个节点每次把较小节点挂上去之后都要立即更新r。很多同学在循环里忘记更新r导致后面的节点全部丢掉了。还有一点循环结束后两个链表可能都还有剩余节点要分别处理不能漏掉。这道题和顺序表合并思路完全一致但链表只需要修改指针不需要移动数据时间复杂度同样是O(mn)。我通常会让同学把顺序表和链表的合并放在一起对比学习这样能明显感受到存储结构对操作方式的影响。4.3 反转单链表三指针法为什么比头插法更适合考试单链表反转是第二章最不能绕过的题。两种常见方案辅助空间法容易想到但空间复杂度不是最优三指针法和头插法可以通过调整指针本身完成原地反转。三指针法标准代码void ReverseLinkList(LinkList L) { LNode *prev NULL; LNode *curr L-next; LNode *next NULL; while (curr ! NULL) { next curr-next; curr-next prev; prev curr; curr next; } L-next prev; }注意三指针法的核心逻辑先保存curr-next到next再把curr-next指向prev之后三个指针整体后移。如果不变量的顺序错了链表就会断。我建议你在草稿纸上把每一步的指针变化画出来画一遍基本就记住了。另一种方案是头插法思路是把头节点摘下来然后遍历原链表每遇到一个节点就把它插入到头节点之后。头插法的优点是符合直觉缺点是改变了原来的节点连接关系如果想保持原链表不变就没那么方便。三指针法不改变原链表结构只是改变了next方向这也是为什么面试和考试中更推荐三指针法。4.4 删除链表中最小值节点双指针记录前驱这道题的要求是删除单链表中数据域值最小的那个节点。思路是遍历一遍链表记录当前最小值节点和它的前驱节点。遍历结束后把最小值节点的前驱的next指向最小值节点的next然后释放最小值节点。void DeleteMinNode(LinkList L) { if (L-next NULL) { return; } LNode *pre L; LNode *minPre L; LNode *p L-next; LNode *minNode p; while (p ! NULL) { if (p-data minNode-data) { minNode p; minPre pre; } pre p; p p-next; } minPre-next minNode-next; free(minNode); }这个题目容易错的地方在于不是记录最小节点的值就完事了删除时还需要知道它的前驱否则无法把链表重新接上。我把这个思路叫“双保险记录法”边遍历边记录“当前最小节点”和“当前最小节点的前驱”两者始终同步更新。另一个细节是最小节点可能有多个题目如果要求“只删除第一个最小值节点”那判断条件就要用而不是如果要求删除所有最小值节点就需要另外一种处理方式了。4.5 多项式相加结构体遇到链表的经典组合多项式相加是第二章综合性很强的一道题。它把一个多项式定义为若干个项组成的线性表每一项包含系数(coef)和指数(expn)。两个多项式相加本质是合并两个按指数递减排列的有序链表。实现思路比较直接两个指针p和q分别指向两个多项式的首项循环比较两者的指数。如果p的指数大于q的指数说明p这一项的结果里单独存在直接把p节点复制到结果链表如果指数相等系数相加如果和不为0则插入结果链表同时释放原来的两个节点如果指数小于说明q这一项单独存在把q节点复制到结果链表。typedef struct PolyNode { float coef; int expn; struct PolyNode *next; } PolyNode, *PolyLinkList; PolyLinkList AddPoly(PolyLinkList A, PolyLinkList B) { PolyLinkList C (PolyLinkList)malloc(sizeof(PolyNode)); C-next NULL; PolyNode *p A-next; PolyNode *q B-next; PolyNode *r C; while (p ! NULL q ! NULL) { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); if (p-expn q-expn) { float sum p-coef q-coef; if (sum 0) { p p-next; q q-next; free(s); continue; } s-coef sum; s-expn p-expn; p p-next; q q-next; } else if (p-expn q-expn) { s-coef p-coef; s-expn p-expn; p p-next; } else { s-coef q-coef; s-expn q-expn; q q-next; } s-next NULL; r-next s; r s; } while (p ! NULL) { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef p-coef; s-expn p-expn; s-next NULL; r-next s; r s; p p-next; } while (q ! NULL) { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef q-coef; s-expn q-expn; s-next NULL; r-next s; r s; q q-next; } return C; }这道题真正考察的是“能不能把实际问题抽象成线性表的操作”。如果你能直接写出这个结构体和合并逻辑说明你对链表已经有比较扎实的掌握。如果写不出来就回到前面几道基础题先练手。多项式相加的变体还包括“多项式求值”“多项式乘法”原理一样后期可以延伸练习。5. 算法题的边界条件与常见错误排查5.1 空表、单节点、头节点三个永远要先问的问题我批改代码时有一个习惯不管算法看起来多正确先拿空表、单节点表、带头节点但无数据这三个特殊情况去测试。这三个测试用例能暴露大部分边界错误。以删除链表中的值为x的节点为例。空表时需要判断L-next NULL如果没判断代码一运行就解引用空指针。单节点表时如果该节点就是要删除的节点删除后链表应该变成空表也就是L-next NULL有些同学把这部分漏了。带头节点的链表在做插入操作时头节点可以让“在第一个位置插入”和“在中间位置插入”的代码统一但如果你的算法不依赖头节点第一个数据节点和后继节点就需要分开处理。但要注意的是不要因为害怕边界条件就写出一堆冗余判断。好的代码应该是用统一逻辑覆盖特殊情况而不是每种特殊情况单独写一个分支。比如带头节点的单链表删除节点只要保证遍历时从头节点开始用pre-next-data x来判断那么删除第一个数据节点和删除中间节点用的是同一段代码。5.2 从越界到野指针C语言做题常见的五个bug这一节总结我在批改过程中遇到频率最高的五类C语言bug按照出现概率排序序号bug类型典型场景排查技巧1数组越界顺序表插入/删除时下标超出length范围插入前判断表是否已满删除时判断下标是否合法2空指针解引用链表遍历时p为NULL仍访问p-data循环条件中限制p ! NULL3指针悬挂free后没有置NULL继续使用该指针free之后立即置NULL4忘记更新表长顺序表删除元素后length没减删除操作最后必须length--5循环变量未更新while循环内忘记让p p-next每次循环结束时检查游标是否移动第三类“指针悬挂”是最隐蔽的。有些操作系统在free后访问该地址不一定会立即崩溃而是返回一个随机值导致程序行为时好时坏。这个问题排查起来很头疼只能靠规范编程来避免。我的原则是free一个指针后要么马上置空要么保证它再也不会被访问。5.3 如何验证你的算法是对的测试用例设计的三个层次很多同学写完算法后不知道怎么验证正确性就随便输入几个数据跑一遍感觉没报错就算过了。这种做法风险很大因为很多隐藏bug在特定输入下才会暴露。我建议采用三个层次的测试第一层是“功能测试”验证算法能否完成基本功能。比如删除所有值为x的数据输入[1, 2, 3]删除2期望得到[1, 3]。这一层能发现大部分逻辑错误。第二层是“边界测试”使用最小规模数据。空表、单节点、两个节点、最大值、最小值、所有元素相同、没有要删除的元素、所有元素都要删除。这些用例能发现边界处理是否完善。第三层是“压力测试”构造大规模数据。比如线性表长度取到几万把元素随机打乱再对比你的算法结果和暴力解法结果是否一致。对于链表可以随机插入几万个节点测试插入、删除、查找的性能和正确性。这一层在上机考试前做一次能极大增强信心。从经验来看能把第二层测试做全的人代码质量已经超过大多数同学了。第三层测试主要是自我加压适合冲刺高分的人。6. 顺序表和链表的综合对比从课后题到期末考6.1 一张表说清两种存储结构的所有区别第二章学完之后我建议你亲手整理一张对比表。这里给出我的版本你可以在此基础上补充比较维度顺序表链表存储方式连续内存离散节点指针连接随机访问支持O(1)不支持需遍历O(n)插入/删除平均移动n/2个元素O(n)修改指针O(1)已知位置时空间分配静态分配需要预知最大长度动态分配按需申请存储密度高只存数据低多了指针域缓存友好性高低查找按值最好的情况O(1)最坏O(n)顺序查找O(n)求长度O(1)直接读取lengthO(n)需遍历销毁操作直接释放整块内存需逐个节点释放这张表是第二章知识的浓缩。期末复习时建议把表右侧再补一列“教材例题中的体现”比如顺序表插入在哪个函数里演示过链表删除在哪个函数里演示过。这样就完成了从知识点到代码的映射。6.2 选择恐惧症怎么治先看操作频率再看数据规模面试和考试里常见的一类题是“给你一个场景你选顺序表还是链表”。这类题其实有套路。第一步看主要操作是什么。如果主要操作是按下标随机访问元素比如“取得第i个位置的元素”那顺序表是明显优势。如果主要操作是频繁在中间插入和删除比如“维护一个不断变化的任务队列”那链表更合适。第二步看数据规模。数据量小比如几百个元素两者性能差异微乎其微用顺序表即可因为代码简单、可读性好。数据量大且动态增长无法预估上限那链表更合适否则顺序表频繁扩容反而浪费时间。第三步看是否需要稳定的存储地址。顺序表扩容时元素会整体搬家原来的指针全部失效链表节点稳定存在只要不删除地址不会变化。这三步想清楚大部分选型题都不会出错。6.3 “快慢指针”这个思想从第二章就开始埋伏了第二章有一道题是“找链表中间节点”这个题的最优解用到了快慢指针一个指针每次走两步另一个每次走一步快指针到末尾时慢指针刚好指向中间节点。这个思想在第二章只是一个锻炼但后续会多次出现。判断链表是否有环时快慢指针是经典解法找链表倒数第k个节点时同样用快慢指针先让快指针先走k步然后两个指针同步前进。理解快慢指针的本质是“不同速度的遍历产生相对位移”在后面的章节里你会频繁用到。我建议在第二章就把快慢指针的两种模式练熟一是“快走两步、慢走一步”找中点二是“先走k步再同步走”找倒数第k个节点。这两种模式代码量都很小但面试和考试中出镜率很高。6.4 我自己刷第二章时踩过的坑文章最后按惯例分享几个我当初刷这章时踩过的坑。第一个坑是“眼高手低”。我当时觉得顺序表的题简单直接在草稿纸上画画逻辑就过了没有真正上机写代码。结果第一次上机做“删除所有值为x的元素”时写出来的代码在x连续出现时逻辑就出错了。后来我养成了一个习惯不管是多简单的算法题都要亲自写一遍代码并且用测试用例跑一遍。第二个坑是“死磕一道题”。遇到“多项式相加”这种综合性较强的题时我花了一整个晚上硬磕导致效率很低。后来我改变了策略一道题超过一个小时还理不清思路就先放下回头把前面链表的基础操作重新练一遍第二天再回来做往往很快就通了。这个策略后来一直用到考研复习结束。第三个坑是“忘记看输出的中间状态”。调试链表代码时很多人习惯只盯着最终结果对不对。但我建议你在关键位置加printf把每一步的指针指向打出来。比如反转单链表每经过一个节点就打印一次当前prev、curr、next的地址和数据能帮助你把指针变化过程可视化快速定位断链的位置。第四个坑是“直接抄答案”。教材附录和网上流传的答案里有一些代码风格很老甚至存在小错误。我建议把答案当作参考不要直接背一定要自己推导一遍。考试和面试时考官更看重你能否清晰地解释每一步的逻辑而不是你是否背过标准答案。这些经验虽然看起来琐碎但都是实打实趟出来的。数据结构的学习没有捷径第二章作为基础中的基础值得你多花时间把每道题都吃透。后面几章的很多代码你会发现都只是在这一章的基础上换了一层皮而已。
