第二章的课后习题是很多人自学数据结构时遇到的第一道坎。严蔚敏老师的《数据结构C语言版 第2版》是经典中的经典但正因为经典它的习题风格偏重原理和算法设计和大学期末考试的套路有时候反而不太一样。网上流传的答案版本很多有的只有结果没有推导有的代码连编译都过不了还有的根本就是错的。我前前后后带过几轮学生做这套题也自己从零把第二章的每个算法题用C语言实现过不止一遍今天把这一章的答案、思路和踩坑记录整理出来希望能给正在啃这本书的朋友省点时间。第二章的核心是线性表整章内容围绕顺序表和链表两种存储结构展开。课后题大致可以分成几类概念辨析题、顺序表操作题、单链表操作题、以及少量循环链表和双链表相关的综合题。其中算法设计题是重头戏考试、考研、面试里反复出现的“逆置”“合并有序表”“删除重复元素”“找中间节点”这些经典题目原型基本都在这一章。所以别只把这一章当课后作业刷它的价值是给后续栈、队列、串、图的基础操作打底子。1. 第二章整体考点与线性表的核心概念先把基础概念理清楚。第二章习题里频繁出现的核心概念包括线性表的逻辑结构、顺序存储结构和链式存储结构的对比、头结点和头指针的区分、以及各种操作的时间复杂度分析。这些概念不是背一背就完事后面的算法题都是在它们之上设计的。1.1 顺序表和链表的本质差异顺序表本质上就是数组逻辑上相邻的元素在物理内存中也相邻。优点是支持随机访问下标定位是O(1)时间缺点是插入和删除要移动大量元素平均要移动n/2个元素时间复杂度O(n)而且表满后扩容麻烦。链表则是通过指针把散落在内存各处的节点串起来插入和删除只要改指针不需要移动元素在已知位置的前提下是O(1)但查找某个位置的节点只能从头遍历复杂度O(n)。课后题里常考这两种结构在不同场景下的优劣选择。我的判断标准很朴素频繁按位置访问选顺序表频繁插入删除且操作点已知选链表。如果数据规模基本固定、很少扩容顺序表永远是第一选择如果数据量不确定、要频繁增删链表更灵活。1.2 头结点和头指针的关系这几乎是第二章最容易绕晕的点考试也特别喜欢考。头指针是指向链表中第一个节点的指针它是一个变量存储了第一个节点的地址。头结点则是在第一个元素节点之前附加的一个节点它不存储数据也可以存储表长之类的附加信息。头结点的引入是为了让“在第一个位置插入”和“删除第一个节点”这两个操作与其他位置的操作统一起来不用特殊处理指针的指向。实际操作中带头结点和不带头结点的链表代码差异非常明显。带头结点的单链表初始化时头结点的next置为NULL所有插入删除都通过“前驱节点”的next来修改不带头结点的链表第一个节点的插入要单独处理头指针本身。我建议做课后题时除非题目明确说“不带头结点”否则一律默认带头结点这样代码统一也更符合教材的算法风格。2. 顺序表课后题精讲与C语言实现顺序表相关的课后题核心就是围绕数组的下标操作。这里选几道最典型、也是考试频率最高的题目给出完整思路和可运行的C代码。2.1 顺序表元素逆置题目要求将顺序表中的所有元素原地逆置不能用辅助数组。考察点有两个理解“原地”的含义以及能否通过两头交换实现。思路很简单设两个下标变量i和j初始i指向0j指向最后一个元素循环交换a[i]和a[j]i、j--直到i j为止。这里有一个细节值得展开循环条件是i j还是i j其实都可以。当元素个数是偶数时i和j会正好交叉过去当元素个数是奇数时i和j会同时指向中间元素中间元素和自己交换没有意义。所以用i j就可以代码更干净。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SqList; void reverse(SqList *L) { int i 0, j L-length - 1; int temp; while (i j) { temp L-data[i]; L-data[i] L-data[j]; L-data[j] temp; i; j--; } }时间复杂度O(n)空间复杂度O(1)。这道题虽然简单但它是很多后续题目的基础比如后面的“将两个顺序表位置互换”本质上就是逆置思想的应用。2.2 删除顺序表中所有等于x的元素题目要求删除表中所有值等于x的元素并且要求时间复杂度尽可能低。我见过不少学生第一反应是用两层循环找到x就删除然后前面的元素整体后移。这样确实能做但最坏情况是O(n平方)在大数据量下性能很差。正确思路是用“覆盖法”也叫“双指针法”。设置两个下标变量i用于遍历原表k用于记录“保留下来的元素已经排到的位置”。遍历过程中如果当前元素不等于x就把它复制到下标k的位置然后k如果等于x直接跳过。最后把length修改为k。这样一趟遍历就能完成删除时间复杂度O(n)空间复杂度O(1)。void deleteAllX(SqList *L, int x) { int i, k 0; for (i 0; i L-length; i) { if (L-data[i] ! x) { L-data[k] L-data[i]; k; } } L-length k; }这段代码的精妙之处在于它没有真正的“删除”操作而是通过覆盖和截断表长来达到删除效果。因为顺序表的删除本质就是逻辑上的缩短表长物理上的元素内容不用清空。这道题建议亲手默写一遍它是很多复杂题目的基础套路。2.3 有序顺序表删除重复元素这题是上一题的变体条件从“删除所有等于x的元素”变成了“删除所有重复出现的元素使表中元素保持唯一”同时原表是有序的。很多人的第一反应是类似上一题的覆盖法但需要注意因为有“有序”这个条件重复元素一定是连续的所以判断条件可以简化为“当前元素不等于上一个保留下来的元素”。void deleteDuplicate(SqList *L) { if (L-length 0) return; int i, k 1; for (i 1; i L-length; i) { if (L-data[i] ! L-data[k - 1]) { L-data[k] L-data[i]; k; } } L-length k; }这里有个细节要注意k从1开始因为第一个元素肯定要保留比较的时候是和data[k-1]比较也就是已经保留下来的最后一个元素而不是和data[i-1]比较。这一点不少初学者会搞混导致结果错误。有序这个条件的价值在于不需要额外辅助空间就可以在O(n)时间内完成如果题目去掉“有序”条件就需要哈希表辅助复杂度不变但空间会变成O(n)。2.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; }这道题的时间复杂度是O(mn)m和n是两个顺序表的长度。需要注意归并完成后新表的长度就是k不能想当然地写成A.length B.length因为最后可能有一个表剩了一段而k是实际拷贝的元素个数。如果两个表里有相等的元素用可以保证新表保持稳定排序。3. 单链表课后题精讲与C语言实现单链表是第二章的重灾区。指针操作一旦逻辑没顺清楚代码写出来不是段错误就是死循环。课后题里单链表的算法设计题最多我把常考的几类全部写一遍。3.1 单链表的就地逆置这个题几乎每年考试都会出现。要求对带头结点的单链表实现就地逆置也就是不新申请节点只通过修改指针指向来改变链表的顺序。核心思路很简单把链表从第二个节点开始一个一个摘下来用头插法重新插入到头结点的后面这样顺序自然就反过来了。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; void reverseList(LinkList L) { LNode *p, *q; p L-next; L-next NULL; while (p ! NULL) { q p-next; p-next L-next; L-next p; p q; } }注意看这段代码先把p指向第一个元素节点然后把头结点的next置空这样链表断成两部分。接下来循环里q保存p的下一个节点然后把p头插到头结点后面再让p指向q继续处理。这个过程中q就是那个“用来记住后路”的临时变量缺了它链表就断了。多说一句从时间复杂度来看只需要遍历一遍链表O(n)空间O(1)。“新申请一个链表再反过来复制”的解法虽然也能实现但违反“就地”的要求而且浪费空间考试中会被扣分。3.2 删除单链表中所有值等于x的节点删除链表中值为x的所有节点需要遍历链表找到值为x的节点后让它的前驱节点直接指向它的后继节点然后释放该节点。实现上有两种常见写法一种是双指针法用pre和p分别记录当前节点和前驱节点另一种是“伪删除”直接把后继节点的值复制到当前节点再删除后继节点。对于带头结点的链表双指针法更直观。void deleteAllX(LinkList L, int x) { LNode *pre L, *p L-next, *r; while (p ! NULL) { if (p-data x) { r p-next; pre-next p-next; free(p); p r; } else { pre p; p p-next; } } }这里最关键的一步是只有删除了节点时pre才不需要移动。如果当前节点没有删除pre要跟着p一起前进。很多人的代码在这个地方出错删除一个节点后pre和p的关系就乱了导致后续节点比较不到或者指针指向错误。另外free(p)释放内存后绝对不能再访问p所以必须先用r保存p的后继节点。这一点和顺序表有本质不同顺序表不需要手动释放内存链表需要这也是C语言版本和Java、Python版本题目最大的区别之一。3.3 查找单链表的倒数第k个节点这题在面试里出现的频率更高但教材课后题也偶尔见。思路是快慢指针快指针先走k步然后慢指针和快指针一起走。当快指针到达链表末尾时慢指针正好在倒数第k个位置。int findLastK(LinkList L, int k, int *result) { LNode *fast L-next, *slow L-next; int count 0; while (count k fast ! NULL) { fast fast-next; count; } if (count k) return 0; while (fast ! NULL) { fast fast-next; slow slow-next; } *result slow-data; return 1; }这段代码有几个隐藏的坑。第一个是k大于链表长度的情况快指针还没走完k步就到了NULL说明链表长度不足此时要返回失败标志。第二是k等于链表长度时快指针最终走到NULL慢指针正好在第一个节点逻辑依然成立。第三个坑是这里的“倒数第k个”中k是从1开始计数的考题有时候会明确说“倒数第k个”有时候会说“倒数第0个”区别很大一定要先看清题目再写。3.4 判断单链表是否有环有环链表问题考研和面试常客。经典解法是快慢指针也叫龟兔赛跑算法。快指针每次走两步慢指针每次走一步。如果链表无环快指针会先到达NULL如果有环快慢指针最终会相遇。int hasCycle(LinkList L) { LNode *fast L-next, *slow L-next; while (fast ! NULL fast-next ! NULL) { fast fast-next-next; slow slow-next; if (fast slow) return 1; } return 0; }这里我用了L-next而不是L本身作为起点因为L是头结点不存数据。快指针能不能走两步必须同时判断fast本身不为空且fast-next不为空否则可能会出现访问空指针的隐患。很多初学者只判断fast ! NULL漏掉了fast-next ! NULL导致代码在前几个节点正常绕几圈后突然段错误。3.5 两个有序单链表合并这个题目是顺序表合并的链表版本思路一样但实现上可以写得非常简洁。仍然是双指针遍历比较两个链表的当前节点把较小的节点摘下来尾插到新链表中。LinkList mergeList(LinkList A, LinkList B) { LinkList C (LinkList)malloc(sizeof(LNode)); LNode *pa A-next, *pb B-next, *pc C; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { pc-next pa; pc pa; pa pa-next; } else { pc-next pb; pc pb; pb pb-next; } } pc-next (pa ! NULL) ? pa : pb; free(A); free(B); return C; }最后一行pc-next很关键不管哪个链表剩下一段直接把它挂到新链表后面就行。注意这里不需要释放节点因为新链表复用了原来的节点只是改变了指针的连接关系。如果把A和B的头结点free掉原来的节点依然链在新表里不会受影响。这个方法时间复杂度O(n)空间O(1)。4. 循环链表与双链表相关习题第二章的习题里循环链表和双链表的题虽然不如单链表多但只要出现往往是拉开分数差距的题目。循环链表的核心在于判断结束条件从NULL变成了头结点/首元节点。双链表则因为多了前驱指针操作要更谨慎。4.1 判断带头结点的循环双链表是否对称这个题目综合性很强用到了双链表的两个遍历方向。判断条件是对称也就是第一个节点的数据和最后一个节点相等第二个节点和倒数第二个相等以此类推。实现上设置两个指针p和q分别指向首元节点和尾节点循环比较p-data和q-data然后p后移、q前移。typedef struct DNode { int data; struct DNode *prior, *next; } DNode, *DLinkList; int isSymmetry(DLinkList L) { DNode *p L-next, *q L-prior; while (p ! q p-prior ! q) { if (p-data ! q-data) return 0; p p-next; q q-prior; } if (p-data ! q-data) return 0; return 1; }循环条件里p ! q p-prior ! q是为了兼容节点个数为奇数和偶数的两种情况。节点个数为奇数时p和q最终会指向同一个节点此时p ! q不成立循环退出节点个数为偶数时p和q会擦肩而过p在前q在后此时p-prior q成立也需要退出。这个细节如果不提前想清楚调试时会非常痛苦很容易因为边界条件写错导致死循环。4.2 循环链表和单链表的相互转换循环链表的最后节点的next指向头结点或首元节点而不是NULL。正因为这个特性循环链表的很多判断条件从“是否为NULL”变成了“是否等于头结点”。实际操作中把单链表转化为循环链表只要找到最后一个节点把它的next指向头结点把循环链表转换为单链表则把最后一个节点的next置为NULL。课后题里还有一种变体在循环链表中查找某个节点如果找不到最终会绕回起点。很多学生用for循环遍历结果因为结束条件设置错误而陷入死循环。我建议统一用do-while结构先执行一次循环体再判断是否回到了头结点。这一点是循环链表题目的通解。4.3 双链表节点的插入与删除双链表插入节点时必须先处理新节点的prior和next再去修改它前驱和后继节点的指针顺序不能乱。删除节点时只需要把前驱的next指向后继后继的prior指向前驱然后释放该节点。我总结了一个简单的口诀“先连后断”先让新节点和老链表的节点建立双向连接再修改老链表节点的指针去指向新节点。如果顺序反了比如先把前驱的next改成新节点那原来的后继节点就找不到了整个链表就断了。5. 复杂度分析与边界条件汇总学数据结构和算法写对代码只是第一步更重要的是能说清楚这段代码为什么高效、为什么安全。第二章的课后题里很多题目在问“设计算法”的时候没有明确要求复杂度但考试评分标准中复杂度分析占比很高。我把常见操作的复杂度对比整理成表方便复习时对照。操作顺序表单链表按位置访问O(1)O(n)在已知位置插入O(n)需移动元素O(1)改指针在已知位置删除O(n)需移动元素O(1)改指针按值查找O(n)O(n)头插/头删O(n)需移动元素O(1)这个表揭示了线性表选择的核心逻辑如果插入删除操作非常频繁链表的优势非常明显如果偶尔插入但经常按下标访问顺序表完胜。边界条件方面我总结了五个易错点这些是我批改作业时反复看到的错误第一顺序表判空和判满的条件别弄反。空表是length等于0满表是length等于MAXSIZE。很多初学者用length为0来判断满表用length为MAXSIZE判断空表写出来的代码越跑越离谱。第二链表的首元节点和头结点不能混淆。头结点是L指向的节点不存数据首元节点是L-next存第一个数据。判断链表是否为空的正确条件是L-next NULL不是L NULL。第三删除链表节点后必须释放内存。C语言不像Java有垃圾回收不free就会内存泄漏。虽然在线做题时内存泄漏不一定会报错但一个负责任的数据结构学习者应该写出内存安全的代码。第四快慢指针结束后慢指针指向的位置取决于快指针的初始位置。查找链表中点、倒数第k个节点这类题稍微改一下快指针的初始位置结果就会差一个节点建议每次写之前先画图验证一下。第五循环链表遍历时结束条件必须是“回到头结点”而不是“等于NULL”。这个错误在考试时往往会导致程序死循环白白丢时间。6. 常见编译错误与调试经验C语言版本的课后题最让人头疼的不是算法本身而是代码一编译就报错或者运行到一半就段错误。这里整理一下我平时调试顺序表和链表代码时经常遇到的问题以及对应的排查思路。6.1 段错误Segmentation Fault的三种典型原因第一种原因是指针未初始化。定义了LNode *p之后直接p-next此时p是野指针指向未知的内存区域访问它必然崩溃。解决办法是养成习惯定义指针后立即初始化或赋值为NULL。第二种原因是访问了空指针的成员。比如链表为空时L-next是NULL如果此时直接执行L-next-data就会崩溃。所以访问L-next-data之前必须确保L-next不是NULL。第三种原因是free之后继续使用指针。释放后再访问或再free一次这个错误非常隐蔽因为编译器不报错运行结果也时好时坏。我用Visual Studio的调试模式经常能捕捉到这种问题但用gcc的时候就比较难。建议在free之后加一行p NULL这样如果代码后续误用了p至少不会访问到野指针。6.2 死循环的排查思路死循环大多出现在链表遍历中。最常见的错误是循环体内没有更新循环变量。比如用p遍历单链表循环体里只有比较和判断逻辑最后忘了执行p p-next那p永远指向同一个节点循环就转不出来了。另一个容易造成死循环的场景是循环链表。如果结束条件写成了p ! NULL而循环链表里没有节点指向NULL那这个循环就会永远转下去。排查的时候可以先在循环体里加一个计数器限制最大循环次数快速定位是哪个循环出问题。6.3 修改链表后并未生效这个bug在函数传参时最常见。C语言函数参数是值传递如果你在函数内部写了p p-next修改的是形参p的指向对实参没有任何影响。想要修改头指针的指向必须传入二级指针或者使用头结点来避免直接操作头指针。这也是为什么教材里的链表算法大多设计成带头结点的形式极大简化了指针操作的复杂度。如果坚持用不带头结点的链表要实现“在第一个位置插入节点”就必须传LinkList *L再使用(*L) newnode来修改头指针。这个知识点在考试里也常考很多题目故意不带头结点考察的就是这一点。6.4 动态内存分配失败malloc返回NULL的问题在很多在线评测系统里不容易触发因为评测数据量一般不大。但在实际项目中如果大量创建节点后忘记释放内存内存使用量会越来越高最终malloc无法分配内存而返回NULL。所以每道练习题里只要用了malloc就要配套使用free这是一个完整的闭环。我批改作业时看到不少学生在删除节点的函数里写了free但主函数里反复调用插入函数插了一个又一个节点最后没有统一释放整条链表导致内存泄漏。虽然课堂教学一般不会因为内存泄漏扣分但养成这个习惯对以后做嵌入式开发或者C项目帮助很大。7. 综合应用题思路拆解第二章的课后题里有几道综合应用题特别典型它们把顺序表、链表、逆置、合并、删除等操作组合在一起单独看每一部分都不难但组合起来就考验整体把控能力。这里挑两道分析一下。7.1 顺序表元素循环左移p个位置题目将顺序表中的元素循环左移p个位置。比如{1,2,3,4,5}左移2个位置变成{3,4,5,1,2}。很多人的第一反应是申请一个辅助数组把前面的p个元素存起来然后把剩余元素前移再把p个元素放到末尾。这样做没错但空间复杂度是O(p)。更巧妙的方法是“三次逆置法”。先逆置前p个元素再逆置剩余元素最后整体逆置。原理可以用数学归纳法证明实际效果可以通过举例验证。比如{1,2,3,4,5}左移2位先逆置前两个得到{2,1,3,4,5}再逆置后三个得到{2,1,5,4,3}最后整体逆置得到{3,4,5,1,2}。整个过程只需要O(1)的辅助空间。这个思路非常经典很多考研题里“循环右移”“部分逆置”都是它的变体。7.2 同时找出链表的最大值和最小值题目要求遍历一遍链表找出最大值节点和最小值节点。思路很简单用两个指针max和min分别记录当前找到的最大值和最小值节点遍历时逐一比较并更新。这道题虽然简单但有一类变体很坑——要求找出倒数第二个节点、或者第n/2个节点这类题不能靠单一遍历解决得用快慢指针。建议把所有链表遍历类题目整理在一起总结出“单指针遍历”“双指针遍历”“快慢指针”三种模式之后看到题就能快速匹配解法。8. 从课后题到面试题的延伸第二章的课后题和面试算法题之间有一条很清晰的递进路径。很多面试题的底层原理就是这一章的题目。比如“判断链表是否有环”是快慢指针的经典应用面试中经常进一步追问“如何找到环的入口”这就需要在快慢指针相遇后再让一个指针从头出发两者同步前进再次相遇的位置就是环入口。这个结论的证明需要一点点数学推导但对理解指针行为非常有帮助。再比如“合并两个有序链表”在面试中经常要求用递归实现。递归版本代码精简到只有几行但对递归的理解要求更高。这里给出代码参考LinkList mergeRecursive(LNode *A, LNode *B) { if (A NULL) return B; if (B NULL) return A; if (A-data B-data) { A-next mergeRecursive(A-next, B); return A; } else { B-next mergeRecursive(A, B-next); return B; } }所谓“数据结构和算法是程序员的必修课”第二章就是这门课真正开始上强度的位置。把这一章的习题吃透不只是为了应付考试更是为了在后面学习栈、队列、串、树和图的时候不用回头补基础。我在带学生的时候反复强调一个观点线性表的代码量不大但每一步指针操作背后都有明确的“为什么”。把每道题的为什么想通了后面的学习会轻松很多。最后分享一个我自己的复习技巧每做完一道链表题不要直接看下一题而是把代码里的关键点用注释写清楚比如“这里为什么要保存p-next”“这里为什么pre不移动”过几天再回过头来看注释是否还能看懂。如果能看懂说明真的理解了如果看不懂说明当时只是抄对了并没有消化。这个笨办法对数据结构的学习特别有效至少在我带过的学生里坚持做的人期末成绩都不差。