尧图网站建设 
简介严蔚敏《数据结构C语言版习题集》全答案是一份面向计算机专业学生、考研及自学者的一站式习题解答文档帮助读者逐题对照算法思路与C语言实现巩固数据结构核心知识。压缩包内共1个PDF文件大小约431KB便于下载后直接阅读或打印。目前已有10389人学习浏览受到较多学习者认可。内容覆盖第一章绪论、第二章线性表等经典习题包含冒泡排序、斐波那契序列、结构体与枚举、数组边界处理、多项式求值等典型题目的完整代码与简要分析兼顾原理讲解和代码落地。由于答案按章节组织、思路清晰既能用于课后自测与查漏补缺也可作为考研复习或期末备考的速查资料。1. 这份习题集为什么值得一本正经地刷两遍严蔚敏老师的《数据结构C语言版》大多数科班生手里都有但真正把它当成能动手验算的书来读的人不多。多数人翻开目录看到线性表、树、图、查找、排序顺手能把概念背出来真到用C语言把一个双向循环链表的插入写对、把平衡二叉树旋转的角度算明白就又卡住了。这本习题集的价值恰好不在记住定义而在逼迫你把每个抽象结构落实成指针、数组下标和递归边界。我一般建议两类人认真刷一类是准备算法岗位笔试、需要在纸上快速写对代码的应届生另一类是工作三五年后想把自己零散的经验重新对齐到经典数据结构框架上的工程师。客观讲出版社或课程组流传的全答案PDF在内容版本上差异很大——有的带注释、有的只有代码、有的连时间复杂度分析都缺直接照抄意义有限。更稳妥的做法是把它当成题目来源自己先解再用答案对边界条件和空间复杂度。本文按解题视角—典型结构—复杂度临界—验证方法的路径把这本习题集在C语言环境下的打开方式讲清楚。2. 算法设计题的作答规范答案对不等于能得分习题集里大量题目是编写算法实现某某操作。这些题没有唯一解评分时看的是结构是否清晰、边界是否完整、复杂度是否达标。用能跑出正确结果作为唯一标准恰恰是刷题最常踩的坑。2.1 判卷视角下的四个评分维度我和做过这门课助教的同事聊过批改算法题基本看四件事变量命名是否可读、是否先处理空表或空树、循环条件是否依赖长度而不是指针本身、以及空间上有没有无谓的拷贝。答案PDF里很多解法的价值不在代码本身而在它对这些维度的取舍。以顺序表删除一段连续元素为例// 删除顺序表L中从位置i开始长度为k的元素 typedef struct { int *elem; int length; int listsize; } SqList; Status ListDelete_Sq(SqList *L, int i, int k) { if (i 1 || k 0 || i k - 1 L-length) { return ERROR; // 表头表尾边界统一在这里挡掉 } for (int pos i k - 1; pos L-length; pos) { L-elem[pos - k] L-elem[pos]; // 前移长度为k的窗口 } L-length - k; return OK; }这段代码里的pos - k覆盖了待删除块右侧元素逐个左移的全部改动k为0时循环体不执行length不变。相比先把第i个元素逐个左移k次的写法这种窗口移动的语义更接近整块搬迁也更好解释复杂度是O(n)而不是O(n·k)。2.2 从答案反推题目到底在考什么习题集每个章节的编排有内在顺序线性表的题集中在在指定位置插入/删除/合并栈和队列的题集中在用两个栈模拟队列循环队列的判定这种结构变换上。看答案时重点不是逐行看懂而是标出每道题的考点标签比如考点典型题面信号答案里常出现的动作指针操作带头结点/不带头结点判断p-next而非p递归树先序/中序/后序递归出口写在函数第一行空间复杂度不使用额外数组原地倒置/两两交换边界设计多个长度参数先在纸上画i、k的区间图这样刷完一章你会发现自己能总结出题规律——这比背下几十个函数签名有用得多。2.3 一道题的价值密度怎么判断不是所有题目都值得花四十分钟死磕。我自己的筛选方法是题面里出现设计一个算法使得时间复杂度为O(n)这种显式约束的优先级最高只写完成插入操作的如果思路三分钟就能想到直接看答案确认边界即可。习题集的PDF版本通常会把这两种题混排所以你第一遍刷时最好按约束强→边界多→纯实现的顺序排序而不是从第1题按到第n题。3. 线性表、栈和队列指针边界就是全部的考点这章是整本习题集的分母。链表题哪怕改用Java或Python写核心逻辑仍然不变但C语言强迫你手动管理结点内存反而把谁指向谁这件事暴露得更清楚。3.1 带头结点 vs 不带头结点两种代码风格的分水岭习题集里建立单链表逆置链表合并有序链表这类题答案通常默认带头结点。带头结点的好处是插入和删除不必单独处理表头指针统一用p L; while (p-next)的节奏扫描。不带头结点的版本在头插法时每次都要L newNode代码更短但写错概率更高。3.1.1 就地逆置单链表的三个指针循环// 带头结点逆置把数据结点一个个摘下头插回链表 void ReverseList(LinkList L) { Node *p L-next; // p指向第一个数据结点 Node *q NULL; // 暂存后继 L-next NULL; // 断开头结点链表变空 while (p) { q p-next; // 先保留下一个要处理的结点 p-next L-next; // 当前结点头插到链表最前端 L-next p; p q; } }这里最容易被忽略的是循环体内的赋值顺序q p-next必须在p-next被改写之前执行。如果把两行顺序颠倒第三个结点就再也找不回来了。答案里常见的变体是用p-next临时存下一个结点那样空间少一个指针但可读性明显下降实际评分时并不加分。3.1.2 为什么循环队列的牺牲一个单元是标准答案习题集里有一类经典题设计循环队列要求区分队空和队满。教科书式答案牺牲一个存储单元用(rear 1) % MAXSIZE front判断队满。我的建议是如果题目没限制额外变量加一个size计数器更不容易写错——因为判空和判满条件变成size 0和size MAXSIZE且入队出队时只需要维护同一个计数器不需要关心front和rear的相对位置。两种做法在答案PDF里都有评分时用size计数往往被归为设计合理但非书内默认思路不会扣分反而更容易在面试中体现你清楚两种方案各自要付的代价。3.2 栈的应用题中缀转后缀和括号匹配的代码差异习题集在栈的章节必有一组表达式求值和括号匹配的题。许多答案在括号匹配时用一个整型计数器来代替真正的栈但题目明确要求利用栈时这种简化会失分。// 括号匹配只有(和)用栈实现 int MatchBrackets(char *s) { SqStack stack; InitStack(stack); for (int i 0; s[i] ! \0; i) { if (s[i] () { Push(stack, s[i]); } else if (s[i] )) { if (StackEmpty(stack)) return 0; // 右括号多出来了 char top; Pop(stack, top); } } return StackEmpty(stack); // 左括号多出来时stack非空 }注意这里每一个return 0都要先判断栈是否为空而不是只做电平计数。因为表达式里的括号必须严格嵌套(()))这种输入如果用计数器判断到最后一个右括号时才可能发现负数而中间步骤等于提前放过了多种错误序列。栈式匹配的另一个优势是如果题目扩展到{ [ ( ] ) }只需要加配对判断不需要改数据结构。4. 树与图从递归形式到遍历框架的进阶树和图是习题集最厚的部分也是看着答案都懂、合上书就懵的重灾区。这个章节的题不再考单一操作而是考你对递归出口、访问时机和状态标记的组合能力。4.1 二叉树遍历框架前中后序的差别只在visit的位置很多答案给出这样的标准递归void PreOrder(BiTree T) { if (T) { visit(T-data); // 前序先访问根 PreOrder(T-lchild); PreOrder(T-rchild); } }把visit移到中间就是中序移到后面就是后序。习题集里真正拉开差距的不是这三种简单遍历而是非递归遍历层次遍历和根据遍历序列重建二叉树。4.1.1 非递归中序遍历栈里存的是还没访问的左子树非递归中序的标准写法是从根开始一路压左孩子压到左子树为空后弹出访问再把指针移到右孩子重复整个过程。答案PDF里普遍用这种双循环结构void InOrder_NonRecursive(BiTree T) { SqStack S; InitStack(S); BiTree p T; while (p || !StackEmpty(S)) { if (p) { Push(S, p); // 左子树先压栈 p p-lchild; } else { Pop(S, p); // 左子树到头弹栈访问 visit(p-data); p p-rchild; // 处理后转向右子树 } } }这里最容易出错的是每次Pop之后p p-rchild如果右孩子为空while外层会再次进入else分支继续弹栈如果右孩子非空则会再次进入内层的左压过程。整个写法可以背下来但要理解栈里永远存储着祖先链而不是某个时刻的全部结点。4.1.2 层次遍历与二叉树层序重建的对应关系层次遍历用队列实现每出一个结点就将其左右孩子入队。习题集里相关的变体包括求二叉树宽度和判断是否为完全二叉树。int TreeWidth(BiTree T) { if (!T) return 0; Queue Q; InitQueue(Q); EnQueue(Q, T); int width 0; while (!QueueEmpty(Q)) { int count QueueLength(Q); // 当前层结点数 if (count width) width count; for (int i 0; i count; i) { BiTree p; DeQueue(Q, p); if (p-lchild) EnQueue(Q, p-lchild); if (p-rchild) EnQueue(Q, p-rchild); } } return width; }注意这里必须先取QueueLength(Q)再用for循环消费完整个当前层否则出队过程中长度不断变化会把两层混在一起。这个按层快照的模式在树形结构的BFS里非常通用图的最短路径层数统计也用它。4.2 图的两种遍历DFS栈还是递归BFS队列的入队时机图章节的题集中在邻接矩阵 vs 邻接表的选择DFS和BFS代码最小生成树、最短路径。习题集答案里DFS的邻接表实现常常直接用递归因为递归本身就是栈而邻接矩阵实现时用visited数组标记这恰恰是题目的第一个考点。void DFS_AMGraph(AMGraph G, int v, int visited[]) { visited[v] 1; visit(G.vexs[v]); for (int w 0; w G.vexnum; w) { if (G.arcs[v][w] ! 0 !visited[w]) { DFS_AMGraph(G, w, visited); // 递归深入 } } }这个函数有两个必须提的点一是递归前必须先置visited再进入下一层如果在递归深处才标记会重复访问祖先结点二是邻接矩阵的DFS复杂度固定为O(n²)不管图里实际边有多少条。习题集里的真题经常问为什么邻接表的DFS时间复杂度和矩阵不同答案就是邻接矩阵的for循环扫描了整行。 图搜索中对visited的检查时机是区分理解深浅的分水岭。4.3 连通分量与生成树答案里常见的省略说明习题集里求连通分量个数的常见做法是对每个未访问顶点调用一次DFS或BFS调用次数就是连通分量数量。很多答案的代码只有主函数和visited数组的声明却省略了整个图的顶点可能不是连通图这个前提。实际阅卷时直接用顶点循环覆盖所有起点的人拿满分而只写一个DFS的只能说明你记住了遍历本身没理解图的结构。这个意识和代面试中的岛屿数量完全一致。5. 查找和排序答案里反复出现的复杂度临界点查找和排序章节的答案最适合用来核对理论上限与实际实现之间的差距。习题集里哈希表、二叉排序树、快速排序、堆排序、归并排序几乎是固定套餐而这些题恰好也是数据结构C语言版热词里检索量最大的部分。5.1 顺序查找和折半查找边界条件不看死记看区间表示折半查找的坑集中在while条件、left和right的更新方式上。习题集答案里最常见的是左闭右闭区间写法int BinarySearch(int a[], int n, int key) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; // 防溢出写法 if (a[mid] key) return mid; else if (a[mid] key) left mid 1; else right mid - 1; } return -1; }两个细节值得对比left (right - left) / 2等价于(left right) / 2但在数组很大时避免整型溢出而while (left right)对应左闭右闭区间若改成while (left right)则返回位置需要额外考虑。习题集的答案通常不会给你这两种变体只给一种但真正考试时的选择题会考这两个边界条件的正误所以看答案时要主动做把LEFT改成RIGHT、把改成的自测。5.2 二叉排序树的删除三种情况的完整处理删除结点是查找章节的重头戏。答案里把被删结点分成三类叶子结点、只有左或右子树、左右子树都存在。第三种情况的标准做法是用左子树最大结点或右子树最小结点替换被删结点然后删除那个替换结点。写这道题时我建议用指针的三层结构实现否则特别容易多写代码BiTree DeleteBST(BiTree T, int key) { if (!T) return T; if (key T-data) { T-lchild DeleteBST(T-lchild, key); // 递归到左子树 } else if (key T-data) { T-rchild DeleteBST(T-rchild, key); // 递归到右子树 } else { if (!T-lchild) { BiTree temp T-rchild; free(T); return temp; // 只有右子树或无子树 } else if (!T-rchild) { BiTree temp T-lchild; free(T); return temp; // 只有左子树 } else { BiTree minNode T-rchild; while (minNode-lchild) minNode minNode-lchild; T-data minNode-data; // 用右子树最小值覆盖 T-rchild DeleteBST(T-rchild, T-data); // 删除右子树里那个最小值结点 } } return T; }递归返回新子树根这个手法让父结点的指针能自动接到删除后的结果不需要额外写父亲指针。很多全答案PDF喜欢用二级指针改变原结点思路更省内存但可读性差很多。我一般推荐上面的递归替换写法因为它的结构直接展示了每一次递归都返回一个完整的子树根与后续讲到AVL树的旋转调整时也衔接得上。5.3 排序章节的必背结论稳定性的判定不看代码看等值元素的相对次序习题集里请分析各排序算法的稳定性这类问答在C语言版的习题集里经常出成填空题。直接记结论插入排序、冒泡排序、归并排序和基数排序是稳定的简单选择排序、快速排序和堆排序不稳定。快速排序的不稳定例子是枢轴交换后跨越了等值元素堆排序的不稳定来自堆调整时父子交换可能改变相同键值元素的相对顺序而简单选择排序不稳定这个结论很多人会记错——因为选择听起来像是按次序来的。排序算法平均时间最坏时间空间稳定性直接插入O(n²)O(n²)O(1)稳定快速排序O(nlogn)O(n²)O(logn)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定这张表的意义不只是背而是用于选型内存紧张选堆排序要求稳定选归并数据基本有序选插入。习题集后面有几道综合应用题会给出一个数组让你分别写出每一步的排序过程这类题只有亲手演算一遍才能过关光看答案是没用的。5.4 哈希表的查找长度平均查找长度的计算是纯算术别者在代码里找哈希章节的题目通常给出一组关键字、一个表长和一个哈希函数然后要求计算线性探测再散列或链地址法下的平均查找长度。计算时要注意查找成功时比较次数等于探测次数而查找失败时要从每个哈希位置出发一直探测到空位为止。答案PDF里这段往往只有结果没有过程容易让人误以为ASL很抽象实际就是加减乘除。我在刷题时会先在草稿纸上画出表的下标槽位把每个关键字的探测路径标出来再数总比较次数。这个方法对哈希排序这类热词下的题目也适用。6. 用测试代码验证习题答案的边界情况最后一章回到一个非常务实的习惯拿到书上的答案代码时不要直接用肉眼判断对错把它们编译执行一遍并且主动构造边界测试往往能发现答案印刷或排版中的笔误。很多习题集全答案PDF是从早期版本扫描或重排的代码可能存在括号缺失、变量名错位甚至是mid (lowhigh)/2这种在极端输入下溢出的写法。下面这个流程可以帮你在十分钟内验证一小节的所有答案。6.1 最小验证环境gcc 一个带断言的主函数我自己习惯的做法是把习题答案复制到一个answer_check.c里然后再写一个test_answer.c用assert测试边界。#include stdio.h #include assert.h #include string.h // 测试折半查找的边界空数组、单元素数组、目标不存在 int BinarySearch(int a[], int n, int key); // 声明习题答案函数 void test_binary_search(void) { int empty[] {0}; assert(BinarySearch(empty, 0, 5) -1); // 空数组必然返回-1 int one[] {3}; assert(BinarySearch(one, 1, 3) 0); // 单元素命中 assert(BinarySearch(one, 1, 4) -1); // 单元素不命中 int arr[] {1, 3, 5, 7, 9, 11}; assert(BinarySearch(arr, 6, 1) 0); // 最左边界 assert(BinarySearch(arr, 6, 11) 5); // 最右边界 assert(BinarySearch(arr, 6, 6) -1); // 不存在且位于区间中间 printf(binary search boundary tests passed\n); } int main(void) { test_binary_search(); return 0; }编译命令为gcc -g -Wall -Werror answer_check.c test_answer.c -o check加上-Wall -Werror后任何未初始化变量或比较类型不匹配都会被拦截。上面的测试故意覆盖了空数组单元素左右端点中间不存在四种情况比随便跑一个正常输入要有效得多。6.2 链表和树结构如何构造最小复现场景验证链表的逆置和二叉树的删除时不能靠手打几十行数据我会直接写一个从数组建链表的工具函数LinkList ListFromArray(int arr[], int n) { LinkList L (Node*)malloc(sizeof(Node)); L-next NULL; Node *tail L; for (int i 0; i n; i) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data arr[i]; newNode-next NULL; tail-next newNode; tail newNode; } return L; }配合题目场景把K取1、n、n1三种情况分别传入。链表逆置时特别要测长度为0、1、2三种情况这是循环里指针跟踪最容易错的地方。对二叉树删除我一般先建一棵只有根、只有左子树、只有右子树、左右子树都存在的四棵树分别调用删除函数看看返回值是不是符合预期。这样做的另一个好处是如果书里答案是错的你的用例可以直接定位到是哪一行出了问题。6.3 输出可测性把遍历结果序列化树的遍历题目直接print到标准输出很难断言结果我统一把它们序列化成字符串或int数组再比较。例如中序遍历时用一个全局数组收集访问顺序然后在测试里用memcmp比较。这个方法同样适用于图的BFS和DFS顺序判断。做完这些再看一遍章节答案里的时间复杂度分析就能形成代码正确、边界正确、复杂度也正确的完整判断。习题集PDF说到底只是静态资源真正值钱的是这些静态答案在你环境里被编译、被测试、被修正的过程。本文还有配套的精品资源点击获取 严蔚敏《数据结构（C语言版）》习题集高效刷题指南
简介严蔚敏《数据结构C语言版习题集》全答案是一份面向计算机专业学生、考研及自学者的一站式习题解答文档帮助读者逐题对照算法思路与C语言实现巩固数据结构核心知识。压缩包内共1个PDF文件大小约431KB便于下载后直接阅读或打印。目前已有10389人学习浏览受到较多学习者认可。内容覆盖第一章绪论、第二章线性表等经典习题包含冒泡排序、斐波那契序列、结构体与枚举、数组边界处理、多项式求值等典型题目的完整代码与简要分析兼顾原理讲解和代码落地。由于答案按章节组织、思路清晰既能用于课后自测与查漏补缺也可作为考研复习或期末备考的速查资料。1. 这份习题集为什么值得一本正经地刷两遍严蔚敏老师的《数据结构C语言版》大多数科班生手里都有但真正把它当成能动手验算的书来读的人不多。多数人翻开目录看到线性表、树、图、查找、排序顺手能把概念背出来真到用C语言把一个双向循环链表的插入写对、把平衡二叉树旋转的角度算明白就又卡住了。这本习题集的价值恰好不在记住定义而在逼迫你把每个抽象结构落实成指针、数组下标和递归边界。我一般建议两类人认真刷一类是准备算法岗位笔试、需要在纸上快速写对代码的应届生另一类是工作三五年后想把自己零散的经验重新对齐到经典数据结构框架上的工程师。客观讲出版社或课程组流传的全答案PDF在内容版本上差异很大——有的带注释、有的只有代码、有的连时间复杂度分析都缺直接照抄意义有限。更稳妥的做法是把它当成题目来源自己先解再用答案对边界条件和空间复杂度。本文按解题视角—典型结构—复杂度临界—验证方法的路径把这本习题集在C语言环境下的打开方式讲清楚。2. 算法设计题的作答规范答案对不等于能得分习题集里大量题目是编写算法实现某某操作。这些题没有唯一解评分时看的是结构是否清晰、边界是否完整、复杂度是否达标。用能跑出正确结果作为唯一标准恰恰是刷题最常踩的坑。2.1 判卷视角下的四个评分维度我和做过这门课助教的同事聊过批改算法题基本看四件事变量命名是否可读、是否先处理空表或空树、循环条件是否依赖长度而不是指针本身、以及空间上有没有无谓的拷贝。答案PDF里很多解法的价值不在代码本身而在它对这些维度的取舍。以顺序表删除一段连续元素为例// 删除顺序表L中从位置i开始长度为k的元素 typedef struct { int *elem; int length; int listsize; } SqList; Status ListDelete_Sq(SqList *L, int i, int k) { if (i 1 || k 0 || i k - 1 L-length) { return ERROR; // 表头表尾边界统一在这里挡掉 } for (int pos i k - 1; pos L-length; pos) { L-elem[pos - k] L-elem[pos]; // 前移长度为k的窗口 } L-length - k; return OK; }这段代码里的pos - k覆盖了待删除块右侧元素逐个左移的全部改动k为0时循环体不执行length不变。相比先把第i个元素逐个左移k次的写法这种窗口移动的语义更接近整块搬迁也更好解释复杂度是O(n)而不是O(n·k)。2.2 从答案反推题目到底在考什么习题集每个章节的编排有内在顺序线性表的题集中在在指定位置插入/删除/合并栈和队列的题集中在用两个栈模拟队列循环队列的判定这种结构变换上。看答案时重点不是逐行看懂而是标出每道题的考点标签比如考点典型题面信号答案里常出现的动作指针操作带头结点/不带头结点判断p-next而非p递归树先序/中序/后序递归出口写在函数第一行空间复杂度不使用额外数组原地倒置/两两交换边界设计多个长度参数先在纸上画i、k的区间图这样刷完一章你会发现自己能总结出题规律——这比背下几十个函数签名有用得多。2.3 一道题的价值密度怎么判断不是所有题目都值得花四十分钟死磕。我自己的筛选方法是题面里出现设计一个算法使得时间复杂度为O(n)这种显式约束的优先级最高只写完成插入操作的如果思路三分钟就能想到直接看答案确认边界即可。习题集的PDF版本通常会把这两种题混排所以你第一遍刷时最好按约束强→边界多→纯实现的顺序排序而不是从第1题按到第n题。3. 线性表、栈和队列指针边界就是全部的考点这章是整本习题集的分母。链表题哪怕改用Java或Python写核心逻辑仍然不变但C语言强迫你手动管理结点内存反而把谁指向谁这件事暴露得更清楚。3.1 带头结点 vs 不带头结点两种代码风格的分水岭习题集里建立单链表逆置链表合并有序链表这类题答案通常默认带头结点。带头结点的好处是插入和删除不必单独处理表头指针统一用p L; while (p-next)的节奏扫描。不带头结点的版本在头插法时每次都要L newNode代码更短但写错概率更高。3.1.1 就地逆置单链表的三个指针循环// 带头结点逆置把数据结点一个个摘下头插回链表 void ReverseList(LinkList L) { Node *p L-next; // p指向第一个数据结点 Node *q NULL; // 暂存后继 L-next NULL; // 断开头结点链表变空 while (p) { q p-next; // 先保留下一个要处理的结点 p-next L-next; // 当前结点头插到链表最前端 L-next p; p q; } }这里最容易被忽略的是循环体内的赋值顺序q p-next必须在p-next被改写之前执行。如果把两行顺序颠倒第三个结点就再也找不回来了。答案里常见的变体是用p-next临时存下一个结点那样空间少一个指针但可读性明显下降实际评分时并不加分。3.1.2 为什么循环队列的牺牲一个单元是标准答案习题集里有一类经典题设计循环队列要求区分队空和队满。教科书式答案牺牲一个存储单元用(rear 1) % MAXSIZE front判断队满。我的建议是如果题目没限制额外变量加一个size计数器更不容易写错——因为判空和判满条件变成size 0和size MAXSIZE且入队出队时只需要维护同一个计数器不需要关心front和rear的相对位置。两种做法在答案PDF里都有评分时用size计数往往被归为设计合理但非书内默认思路不会扣分反而更容易在面试中体现你清楚两种方案各自要付的代价。3.2 栈的应用题中缀转后缀和括号匹配的代码差异习题集在栈的章节必有一组表达式求值和括号匹配的题。许多答案在括号匹配时用一个整型计数器来代替真正的栈但题目明确要求利用栈时这种简化会失分。// 括号匹配只有(和)用栈实现 int MatchBrackets(char *s) { SqStack stack; InitStack(stack); for (int i 0; s[i] ! \0; i) { if (s[i] () { Push(stack, s[i]); } else if (s[i] )) { if (StackEmpty(stack)) return 0; // 右括号多出来了 char top; Pop(stack, top); } } return StackEmpty(stack); // 左括号多出来时stack非空 }注意这里每一个return 0都要先判断栈是否为空而不是只做电平计数。因为表达式里的括号必须严格嵌套(()))这种输入如果用计数器判断到最后一个右括号时才可能发现负数而中间步骤等于提前放过了多种错误序列。栈式匹配的另一个优势是如果题目扩展到{ [ ( ] ) }只需要加配对判断不需要改数据结构。4. 树与图从递归形式到遍历框架的进阶树和图是习题集最厚的部分也是看着答案都懂、合上书就懵的重灾区。这个章节的题不再考单一操作而是考你对递归出口、访问时机和状态标记的组合能力。4.1 二叉树遍历框架前中后序的差别只在visit的位置很多答案给出这样的标准递归void PreOrder(BiTree T) { if (T) { visit(T-data); // 前序先访问根 PreOrder(T-lchild); PreOrder(T-rchild); } }把visit移到中间就是中序移到后面就是后序。习题集里真正拉开差距的不是这三种简单遍历而是非递归遍历层次遍历和根据遍历序列重建二叉树。4.1.1 非递归中序遍历栈里存的是还没访问的左子树非递归中序的标准写法是从根开始一路压左孩子压到左子树为空后弹出访问再把指针移到右孩子重复整个过程。答案PDF里普遍用这种双循环结构void InOrder_NonRecursive(BiTree T) { SqStack S; InitStack(S); BiTree p T; while (p || !StackEmpty(S)) { if (p) { Push(S, p); // 左子树先压栈 p p-lchild; } else { Pop(S, p); // 左子树到头弹栈访问 visit(p-data); p p-rchild; // 处理后转向右子树 } } }这里最容易出错的是每次Pop之后p p-rchild如果右孩子为空while外层会再次进入else分支继续弹栈如果右孩子非空则会再次进入内层的左压过程。整个写法可以背下来但要理解栈里永远存储着祖先链而不是某个时刻的全部结点。4.1.2 层次遍历与二叉树层序重建的对应关系层次遍历用队列实现每出一个结点就将其左右孩子入队。习题集里相关的变体包括求二叉树宽度和判断是否为完全二叉树。int TreeWidth(BiTree T) { if (!T) return 0; Queue Q; InitQueue(Q); EnQueue(Q, T); int width 0; while (!QueueEmpty(Q)) { int count QueueLength(Q); // 当前层结点数 if (count width) width count; for (int i 0; i count; i) { BiTree p; DeQueue(Q, p); if (p-lchild) EnQueue(Q, p-lchild); if (p-rchild) EnQueue(Q, p-rchild); } } return width; }注意这里必须先取QueueLength(Q)再用for循环消费完整个当前层否则出队过程中长度不断变化会把两层混在一起。这个按层快照的模式在树形结构的BFS里非常通用图的最短路径层数统计也用它。4.2 图的两种遍历DFS栈还是递归BFS队列的入队时机图章节的题集中在邻接矩阵 vs 邻接表的选择DFS和BFS代码最小生成树、最短路径。习题集答案里DFS的邻接表实现常常直接用递归因为递归本身就是栈而邻接矩阵实现时用visited数组标记这恰恰是题目的第一个考点。void DFS_AMGraph(AMGraph G, int v, int visited[]) { visited[v] 1; visit(G.vexs[v]); for (int w 0; w G.vexnum; w) { if (G.arcs[v][w] ! 0 !visited[w]) { DFS_AMGraph(G, w, visited); // 递归深入 } } }这个函数有两个必须提的点一是递归前必须先置visited再进入下一层如果在递归深处才标记会重复访问祖先结点二是邻接矩阵的DFS复杂度固定为O(n²)不管图里实际边有多少条。习题集里的真题经常问为什么邻接表的DFS时间复杂度和矩阵不同答案就是邻接矩阵的for循环扫描了整行。 图搜索中对visited的检查时机是区分理解深浅的分水岭。4.3 连通分量与生成树答案里常见的省略说明习题集里求连通分量个数的常见做法是对每个未访问顶点调用一次DFS或BFS调用次数就是连通分量数量。很多答案的代码只有主函数和visited数组的声明却省略了整个图的顶点可能不是连通图这个前提。实际阅卷时直接用顶点循环覆盖所有起点的人拿满分而只写一个DFS的只能说明你记住了遍历本身没理解图的结构。这个意识和代面试中的岛屿数量完全一致。5. 查找和排序答案里反复出现的复杂度临界点查找和排序章节的答案最适合用来核对理论上限与实际实现之间的差距。习题集里哈希表、二叉排序树、快速排序、堆排序、归并排序几乎是固定套餐而这些题恰好也是数据结构C语言版热词里检索量最大的部分。5.1 顺序查找和折半查找边界条件不看死记看区间表示折半查找的坑集中在while条件、left和right的更新方式上。习题集答案里最常见的是左闭右闭区间写法int BinarySearch(int a[], int n, int key) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; // 防溢出写法 if (a[mid] key) return mid; else if (a[mid] key) left mid 1; else right mid - 1; } return -1; }两个细节值得对比left (right - left) / 2等价于(left right) / 2但在数组很大时避免整型溢出而while (left right)对应左闭右闭区间若改成while (left right)则返回位置需要额外考虑。习题集的答案通常不会给你这两种变体只给一种但真正考试时的选择题会考这两个边界条件的正误所以看答案时要主动做把LEFT改成RIGHT、把改成的自测。5.2 二叉排序树的删除三种情况的完整处理删除结点是查找章节的重头戏。答案里把被删结点分成三类叶子结点、只有左或右子树、左右子树都存在。第三种情况的标准做法是用左子树最大结点或右子树最小结点替换被删结点然后删除那个替换结点。写这道题时我建议用指针的三层结构实现否则特别容易多写代码BiTree DeleteBST(BiTree T, int key) { if (!T) return T; if (key T-data) { T-lchild DeleteBST(T-lchild, key); // 递归到左子树 } else if (key T-data) { T-rchild DeleteBST(T-rchild, key); // 递归到右子树 } else { if (!T-lchild) { BiTree temp T-rchild; free(T); return temp; // 只有右子树或无子树 } else if (!T-rchild) { BiTree temp T-lchild; free(T); return temp; // 只有左子树 } else { BiTree minNode T-rchild; while (minNode-lchild) minNode minNode-lchild; T-data minNode-data; // 用右子树最小值覆盖 T-rchild DeleteBST(T-rchild, T-data); // 删除右子树里那个最小值结点 } } return T; }递归返回新子树根这个手法让父结点的指针能自动接到删除后的结果不需要额外写父亲指针。很多全答案PDF喜欢用二级指针改变原结点思路更省内存但可读性差很多。我一般推荐上面的递归替换写法因为它的结构直接展示了每一次递归都返回一个完整的子树根与后续讲到AVL树的旋转调整时也衔接得上。5.3 排序章节的必背结论稳定性的判定不看代码看等值元素的相对次序习题集里请分析各排序算法的稳定性这类问答在C语言版的习题集里经常出成填空题。直接记结论插入排序、冒泡排序、归并排序和基数排序是稳定的简单选择排序、快速排序和堆排序不稳定。快速排序的不稳定例子是枢轴交换后跨越了等值元素堆排序的不稳定来自堆调整时父子交换可能改变相同键值元素的相对顺序而简单选择排序不稳定这个结论很多人会记错——因为选择听起来像是按次序来的。排序算法平均时间最坏时间空间稳定性直接插入O(n²)O(n²)O(1)稳定快速排序O(nlogn)O(n²)O(logn)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定这张表的意义不只是背而是用于选型内存紧张选堆排序要求稳定选归并数据基本有序选插入。习题集后面有几道综合应用题会给出一个数组让你分别写出每一步的排序过程这类题只有亲手演算一遍才能过关光看答案是没用的。5.4 哈希表的查找长度平均查找长度的计算是纯算术别者在代码里找哈希章节的题目通常给出一组关键字、一个表长和一个哈希函数然后要求计算线性探测再散列或链地址法下的平均查找长度。计算时要注意查找成功时比较次数等于探测次数而查找失败时要从每个哈希位置出发一直探测到空位为止。答案PDF里这段往往只有结果没有过程容易让人误以为ASL很抽象实际就是加减乘除。我在刷题时会先在草稿纸上画出表的下标槽位把每个关键字的探测路径标出来再数总比较次数。这个方法对哈希排序这类热词下的题目也适用。6. 用测试代码验证习题答案的边界情况最后一章回到一个非常务实的习惯拿到书上的答案代码时不要直接用肉眼判断对错把它们编译执行一遍并且主动构造边界测试往往能发现答案印刷或排版中的笔误。很多习题集全答案PDF是从早期版本扫描或重排的代码可能存在括号缺失、变量名错位甚至是mid (lowhigh)/2这种在极端输入下溢出的写法。下面这个流程可以帮你在十分钟内验证一小节的所有答案。6.1 最小验证环境gcc 一个带断言的主函数我自己习惯的做法是把习题答案复制到一个answer_check.c里然后再写一个test_answer.c用assert测试边界。#include stdio.h #include assert.h #include string.h // 测试折半查找的边界空数组、单元素数组、目标不存在 int BinarySearch(int a[], int n, int key); // 声明习题答案函数 void test_binary_search(void) { int empty[] {0}; assert(BinarySearch(empty, 0, 5) -1); // 空数组必然返回-1 int one[] {3}; assert(BinarySearch(one, 1, 3) 0); // 单元素命中 assert(BinarySearch(one, 1, 4) -1); // 单元素不命中 int arr[] {1, 3, 5, 7, 9, 11}; assert(BinarySearch(arr, 6, 1) 0); // 最左边界 assert(BinarySearch(arr, 6, 11) 5); // 最右边界 assert(BinarySearch(arr, 6, 6) -1); // 不存在且位于区间中间 printf(binary search boundary tests passed\n); } int main(void) { test_binary_search(); return 0; }编译命令为gcc -g -Wall -Werror answer_check.c test_answer.c -o check加上-Wall -Werror后任何未初始化变量或比较类型不匹配都会被拦截。上面的测试故意覆盖了空数组单元素左右端点中间不存在四种情况比随便跑一个正常输入要有效得多。6.2 链表和树结构如何构造最小复现场景验证链表的逆置和二叉树的删除时不能靠手打几十行数据我会直接写一个从数组建链表的工具函数LinkList ListFromArray(int arr[], int n) { LinkList L (Node*)malloc(sizeof(Node)); L-next NULL; Node *tail L; for (int i 0; i n; i) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data arr[i]; newNode-next NULL; tail-next newNode; tail newNode; } return L; }配合题目场景把K取1、n、n1三种情况分别传入。链表逆置时特别要测长度为0、1、2三种情况这是循环里指针跟踪最容易错的地方。对二叉树删除我一般先建一棵只有根、只有左子树、只有右子树、左右子树都存在的四棵树分别调用删除函数看看返回值是不是符合预期。这样做的另一个好处是如果书里答案是错的你的用例可以直接定位到是哪一行出了问题。6.3 输出可测性把遍历结果序列化树的遍历题目直接print到标准输出很难断言结果我统一把它们序列化成字符串或int数组再比较。例如中序遍历时用一个全局数组收集访问顺序然后在测试里用memcmp比较。这个方法同样适用于图的BFS和DFS顺序判断。做完这些再看一遍章节答案里的时间复杂度分析就能形成代码正确、边界正确、复杂度也正确的完整判断。习题集PDF说到底只是静态资源真正值钱的是这些静态答案在你环境里被编译、被测试、被修正的过程。本文还有配套的精品资源点击获取