企业官网建设流程全解析

第二章的课后习题，是很多人自学数据结构时遇到的第一道坎。严蔚敏老师的《数据结构（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指向0，j指向最后一个元素，循环交换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(m+n)，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. 复杂度分析与边界条件汇总

学数据结构和算法，写对代码只是第一步，更重要的是能说清楚这段代码为什么高效、为什么安全。第二章的课后题里，很多题目在问“设计算法”的时候没有明确要求复杂度，但考试评分标准中复杂度分析占比很高。我把常见操作的复杂度对比整理成表，方便复习时对照。

这个表揭示了线性表选择的核心逻辑：如果插入删除操作非常频繁，链表的优势非常明显；如果偶尔插入但经常按下标访问，顺序表完胜。

边界条件方面，我总结了五个易错点，这些是我批改作业时反复看到的错误：

第一，顺序表判空和判满的条件别弄反。空表是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不移动”，过几天再回过头来看注释是否还能看懂。如果能看懂，说明真的理解了；如果看不懂，说明当时只是抄对了，并没有消化。这个笨办法对数据结构的学习特别有效，至少在我带过的学生里，坚持做的人期末成绩都不差。