》习题集答案精讲：链表栈队列实现细节)
简介严蔚敏《数据结构(C语言版)习题集》配套全答案以PDF形式提供面向正在系统学习数据结构、需要大量算法练习与代码验证的高校学生、考研复习者及自学者。答案覆盖绪论、线性表与链表等章节的代表性习题包含冒泡排序、斐波那契序列动态规划、结构体与枚举应用、多项式求值等经典算法每道题给出清晰的C语言实现思路与代码部分附有时间复杂度分析和异常处理要点。例如斐波那契部分展示了动态规划如何避免重复计算多项式求值则用霍纳法则减少乘法次数这些细节有助于读者理解算法优化并在笔试和上机中灵活运用。资源包中仅有1个PDF文件压缩后体积约431KB轻量便携下载后即可直接阅读。该资源目前已有10399人学习浏览是课内巩固、期末备考和考研复习中广受关注的高价值参考资料。1. 严蔚敏《数据结构(c语言版)习题集》全答案这本 PDF 到底该怎么吃透拿到这份答案的读者多半正处于两种状态要么是 408 考研复习刷到怀疑人生要么是本科期末考前抱着书后面的习题干瞪眼。严蔚敏的《数据结构C语言版》几乎是国内计算机专业绕不开的教材而配套的习题集答案恰恰是把“看懂”变成“会写”的关键一环。这份全答案覆盖了绪论、线性表、栈与队列、串、数组、树与二叉树、图、查找与排序等章节的算法设计题和上机题绝大部分题目都给出了可直接落地的 C 函数实现不少还附了思路分析。它适合三类人准备考研但代码题还没形成套路的人期末复习想快速核对思路的人以及自学数据结构但苦于“做完了不知道对错”的人。需要注意的是这份答案不是教材讲解而是“题目 参考实现”的组合所以你得先有教材底子再拿它来对思路、补细节、抄边界处理效果才最好。2. 线性表与链表顺序表删除、无头链表插入与有序表合并的实现细节2.1 顺序表删除 k 个元素循环边界怎么推才不出错题目要求删除顺序表a中第i个元素起的连续k个元素。书里的参考实现是这样的Status DeleteK(SqList a, int i, int k) // 删除线性表 a 中第 i 个元素起的 k 个元素 { if (i 1 || k 0 || i k - 1 a.length) return INFEASIBLE; for (count 1; i count - 1 a.length - k; count) // 注意循环结束的条件 a.elem[i count - 1] a.elem[i count k - 1]; a.length - k; return OK; }这段代码的核心在循环条件i count - 1 a.length - k。我的理解是count表示当前是第几个被移动的元素i count - 1是目标位置的下标而a.length - k是删除后新表的有效长度。只有目标位置不越过新表末尾才需要继续搬移。这个边界如果推错要么少移一个元素导致尾部残留数据要么多移一个导致越界写入。实际写代码时我更习惯先把删除后的长度算出来再写循环这样逻辑更直观不容易踩坑。Status的返回类型在不同教材里有不同定义有的用int有的用枚举。这里返回INFEASIBLE表示参数不合法是一种约定你完全可以用-1或0替代只要调用方约定一致就行。2.2 无头结点链表的插入和删除i1 必须单独处理第 2.17 和 2.18 题的考点很刁钻链表没有头结点头指针直接指向第一个元素。这意味着在头部插入或删除时必须修改头指针本身而不是修改某个头结点的 next 域。Status Insert(LinkList L, int i, int b) // 在无头结点链表 L 的第 i 个元素之前插入元素 b { p L; q (LinkList)malloc(sizeof(LNode)); q-data b; if (i 1) { q-next p; L q; // 插入在链表头部头指针要变 } else { while (--i 1) p p-next; q-next p-next; p-next q; // 插入在第 i 个元素的位置 } return OK; }注意题目原文里写的是q.datab和q.nextp这是笔误q是指针应该用-。另外while(--i 1)这个写法很紧凑--i先自减再比较当i2时循环执行一次p指向第 1 个元素然后在它后面插入新结点当i1时走的是头插分支不会进入循环。这里最容易翻车的地方是传入的i超过表长代码没有做合法性检查实际使用时要自己加防御。删除的逻辑同理删除第一个元素时直接L L-next并释放原头结点删除非首元素时找到第i-1个结点执行p-next p-next-next。如果你一直在有头结点链表上练习第一次写无头版本时很容易忘记改头指针这是血泪经验。2.3 两个递增链表合并为递减链表头插法天然解决逆序第 2.24 题要求把两个元素递增排列的链表 A 和 B 合并成 C且 C 中元素递减排列要求使用原存储空间。参考实现的核心思想是“按从小到大的顺序依次把 A 和 B 的元素插入新表的头部”void reverse_merge(LinkList A, LinkList B, LinkList C) // 把元素递增排列的链表 A 和 B 合并为 CC 中元素递减排列 { pa A-next; pb B-next; pre NULL; while (pa || pb) { if (pa-data pb-data || !pb) { pc pa; q pa-next; pa-next pre; pa q; // 将 A 的元素插入新表头部 } else { pc pb; q pb-next; pb-next pre; pb q; // 将 B 的元素插入新表头部 } pre pc; } C A; A-next pc; // 构造新表头 }这里的关键变量是pre它始终指向新链表的头结点。每次取 A 或 B 中较小的那个元素让它的 next 指向pre然后更新pre为这个元素。循环结束后A 或 B 的剩余元素会按同样方式逐个插入头部。最后A-next pc这行很多人看不懂我的理解是pc是循环最后一次插入的元素也就是新链表中值最小的那个它此时在链表头部所以让 A 的头结点指向它即可。这个思路比“先合并成递增链表再反转”少一次遍历时间复杂度只有 O(nm)。做题时我在纸上画了三个链表的指针变化才真正看懂建议你也别直接跳过去。2.4 同值元素删除与就地逆置相邻双指针的推进时机第 2.20 题要求删除递增链表 L 中所有值相同的元素只保留一个。参考实现用p和q指向相邻两元素Status Delete_Equal(Linklist L) // 删除元素递增排列的链表 L 中所有值相同的元素 { p L-next; q p-next; while (p-next) { if (p-data ! q-data) { p p-next; q p-next; // 不相等时都向后推 } else { while (q-data p-data) { free(q); q q-next; // 相等时删除 q } p-next q; p q; q p-next; } } }这个题最容易踩的坑是删除连续相同元素后p的 next 指针没有更新。比如链表是1 - 2 - 2 - 2 - 3当p指向第一个 2、q指向第二个 2 时如果只 free(q) 而不让p-next指向下一个不相同的元素链表就断了。参考代码在删除完所有重复 2 之后执行p-next q把中间断开的部分补上这一步是灵魂。顺序表就地逆置第 2.21 题就是双指针头尾交换实现很简单但要注意循环条件是i j而不是i j否则中间元素会被交换两次变回原样。链表就地逆置第 2.22 题的三个指针推进顺序p-nextNULL; while(s-next) { q-nextp; pq; qs; ss-next; }属于经典操作考场上很容易写乱建议自己在纸上走一遍 3 个结点的例子。3. 栈与队列双向栈、括号匹配与火车车厢重排的落地写法3.1 双向栈的初始化与栈满判断两栈共享数组的关键双向栈就是把一个数组的两端分别作为两个栈的栈底让两个栈向中间生长。参考实现第 3.15 题如下typedef struct { ElemType *base[2]; // 两个栈底指针 ElemType *top[2]; // 两个栈顶指针 } BDStackType; Status Init_Stack(BDStackType tws, int m) // 初始化一个大小为 m 的双向栈 tws { tws.base[0] (ElemType*)malloc(sizeof(ElemType) * m); tws.base[1] tws.base[0] m - 1; // 高端栈底在数组末尾 tws.top[0] tws.base[0]; // 低端栈顶初始在栈底 tws.top[1] tws.base[1]; // 高端栈顶初始在栈底 return OK; } Status push(BDStackType tws, int i, ElemType x) // x 入栈i0 表示低端栈i1 表示高端栈 { if (tws.top[0] tws.top[1]) return OVERFLOW; // 栈满 if (i 0) *tws.top[0] x; else if (i 1) *tws.top[1]-- x; else return ERROR; return OK; } Status pop(BDStackType tws, int i, ElemType x) { if (i 0) { if (tws.top[0] tws.base[0]) return OVERFLOW; // 低端栈空 x *--tws.top[0]; } else if (i 1) { if (tws.top[1] tws.base[1]) return OVERFLOW; // 高端栈空 x *tws.top[1]; } else return ERROR; return OK; }这里三个地方值得展开。第一初始化时base[1] base[0] m - 1高端栈底指向数组最后一个元素高端栈的 top 从尾部开始入栈时向下移动--出栈时向上移动。第二栈满条件不是“两个 top 相等”而是top[0] top[1]。因为两个 top 是相向而行的一旦低端栈顶指针超过了高端栈顶指针说明中间已经没有空闲空间。第三pop里判断栈空用的是top base而不是top base这是因为高端栈的 top 只会从base[1]向base[0]方向走永远不会越过自己的 base。3.2 三种括号匹配计数法只适用于单种括号第 3.18 题判别小括号是否匹配用计数器就能解决实现简单到不需要贴完整代码。但第 3.19 题要求同时判别(、[、{三种括号时计数法就失效了——因为([)]这种交错嵌套是计数器检测不出来的。正确做法是用栈Status AllBrackets_Test(char *str) // 判别表达式中三种括号是否匹配 { InitStack(s); for (p str; *p; p) { if (*p ( || *p [ || *p {) push(s, *p); else if (*p ) || *p ] || *p }) { if (StackEmpty(s)) return ERROR; // 右括号多于左括号 pop(s, c); if (*p ) c ! () return ERROR; if (*p ] c ! [) return ERROR; if (*p } c ! {) return ERROR; // 必须与栈顶匹配 } } if (!StackEmpty(s)) return ERROR; // 左括号多于右括号 return OK; }这段代码逻辑很干净左括号一律入栈遇到右括号时先查栈空对应右括号比左括号多的情况再弹出栈顶检查类型是否匹配。扫描结束后栈不空说明存在未闭合的左括号。这里容易忽略的是if (StackEmpty(s)) return ERROR;必须放在pop之前否则对空栈做 pop 会引发未定义行为。另外如果你想在同一个函数里同时支持“括号匹配 忽略非括号字符”只要在else if分支前排除普通字符即可但要注意字符串里可能包含转义字符或引号内括号那就需要额外的状态标记不是这个习题的范围了。3.3 火车车厢重排栈的典型应用案例第 3.16 题是经典的“火车调度”问题用字符串表示车厢序列H表示硬席S表示软席要求把软席调到前面硬席调到后面且保持相对顺序。参考实现用一个栈暂存硬席车厢void Train_arrange(char *train) // 用字符串 train 表示火车H表示硬席S表示软席 { p train; q train; InitStack(s); while (*p) { if (*p H) push(s, *p); // 把 H 存入栈中 else *(q) *p; // 把 S 调到前部 p; } while (!StackEmpty(s)) { pop(s, c); *(q) c; // 把 H 按原逆序接在后部 } }这个实现的巧妙之处在于用一个q指针在原始字符串上“原地写入”。第一遍扫描时S被依次写到字符串前部H全部压栈第二遍把栈里的H逐个弹出接到S的后面。因为栈是后进先出的所以硬席车厢的最终顺序和原来相反。如果你不想反转硬席顺序就需要改用队列或者两个栈但题目没要求所以这个解法是最简的。实际做题时我建议先拿一个具体的字符串在纸上演算比如HSHSSH第一遍扫描后字符串变成SSH前三个字符被软席占据栈里从底到顶是H H H第二遍弹栈写入后得到SSHHHH。这个演算过程能帮你验证代码逻辑也能发现q指针与p指针重叠时可能出现的读写冲突——虽然这里恰好不会冲突但理解总比死记强。3.4 逆波兰式求值与中缀转后缀运算符栈的优先级原则第 3.21 题的参考实现给出了中缀转后缀的框架核心是“运算符在栈内遵循越往栈顶优先级越高的原则”。这段代码用的是伪代码我在此基础上写了个完整的 C 实现思路// 中缀表达式转逆波兰式oper 为自定义的优先级比较函数 void NiBoLan(char *str, char *new) { p str; q new; InitStack(s); // s 为运算符栈 while (*p) { if (isalpha(*p)) *q *p; // 操作数直接输出 else { c gettop(s); if (priority(*p) priority(c)) push(s, *p); // 当前运算符优先级高于栈顶则入栈 else { while (priority(gettop(s)) priority(*p)) { pop(s, c); *q c; } push(s, *p); } } p; } while (!StackEmpty(s)) { pop(s, c); *q c; } }这个框架有一个边界当栈为空时直接gettop(s)会出错所以入栈前要先判断栈空。代码里第 3.22 题逆波兰求值就更简单了——数字入栈遇到运算符弹出两个操作数计算后把结果压回去。这类题目在考研中常以“给一个中缀表达式写出后缀表达式”的形式出现不一定要写完整代码但你要能手工模拟栈的变化过程。4. 算法复杂度与边界斐波那契的动态规划、溢出检测与多项式求值4.1 斐波那契的动态规划实现为什么递归会指数爆炸第 1.17 题要求求 k 阶斐波那契序列的第 m 项。教材给出的参考实现是动态规划思路Status fib(int k, int m, int f) // 求 k 阶斐波那契序列的第 m 项的值 f { int tempd; if (k 2 || m 0) return ERROR; if (m k - 1) f 0; else if (m k - 1) f 1; else { for (i 0; i k - 2; i) temp[i] 0; temp[k - 1] 1; // 初始化 for (i k; i m; i) { // 求出第 k 至第 m 个元素的值 sum 0; for (j i - k; j i; j) sum temp[j]; temp[i] sum; } f temp[m]; } return OK; }书里的分析写得很清楚了这个方法是“通过保存已经计算出来的结果”时间复杂度仅为 O(m^2)。如果采用递归编程时间复杂度会高达 O(k^m)。这里的差距不是常数级别的是指数级别的——当m到 30 左右递归就已经肉眼可见地卡顿而动态规划几乎是瞬时完成。实际写这段代码时要注意temp数组的下标范围。代码里for(ik; im; i)意味着temp至少要能存到下标m所以数组长度要开m1。另外内层sum temp[j]的j从i-k开始这个下界在i还小时可能是负数需要先走完初始化分支才能进入这个循环。4.2 溢出检测的除法校验法这个思路比直接比较更可靠第 1.19 题求i! * 2^i序列的值且要求不超过maxint参考实现用了一个非常巧妙的溢出检测手段Status algo119(int a[ARRSIZE]) // 求 i!*2^i 序列的值且不超过 maxint { last 1; for (i 1; i ARRSIZE; i) { a[i - 1] last * 2 * i; if ((a[i - 1] / last) ! (2 * i)) return OVERFLOW; // 除法结果异常说明溢出 last a[i - 1]; } return OK; }它的原理是如果没有溢出a[i-1]一定等于last * 2 * i那么a[i-1] / last应该恰好等于2 * i。一旦乘法结果超过了maxint整数溢出后得到的是一个被截断的值这个值除以last大概率不等于2 * i于是检测到溢出。这个方法比“预先比较 last 和 maxint/(2*i)”更巧妙但也更隐晦——如果溢出后恰好整除出了2*i理论上会漏检只是概率极低做题时可以接受。不过这个实现里有个细节2*i本身也可能溢出如果i足够大2*i先溢出后面的比较就没有意义了。所以实际使用时我会在循环里加一个if (i maxint/2)的提前判断把问题消灭在源头。但作为习题答案理解它的检测思路比纠结边界更有价值。4.3 多项式求值的霍纳法则指针遍历系数数组第 1.20 题的polyvalue函数展示了如何在 C 里用指针高效遍历数组并求多项式值void polyvalue() { float ad; float *p a; printf(Input number of terms:); scanf(%d, n); printf(Input the %d coefficients from a0 to a%d:\n, n, n); for (i 0; i n; i) scanf(%f, p); printf(Input value of x:); scanf(%f, x); p a; xp 1; sum 0; // xp 用于存放 x 的 i 次方 for (i 0; i n; i) { sum xp * (*p); xp * x; // 迭代计算 x 的下一次方 } printf(Value is:%f, sum); }严格来说这段代码不是霍纳法则而是最朴素的“逐项累乘”法——用一个xp变量保存x的当前幂次每处理完一项就乘以x。它的时间复杂度是 O(n)而霍纳法则秦九韶算法的时间复杂度同样是 O(n)但乘法次数更少数值稳定性更好。霍纳法则的写法是sum a[n]; for(in-1; i0; i--) sum sum*x a[i];考研中更喜欢考后者。这里用指针p遍历数组的写法和数组下标访问等价但要注意第一轮scanf之后p已经指向数组末尾第二轮求值前必须把p重新指回a否则会读越界。这种“指针用完后复位”的习惯是在 C 语言编程里少踩坑的重要保证。4.4 区间删除三段式定位、扫描、裁剪第 2.19 题要求在递增链表 L 中删除值大于mink且小于maxk的所有元素。参考实现是典型的三段式Status Delete_Between(Linklist L, int mink, int maxk) // 删除元素递增排列的链表 L 中值大于 mink 且小于 maxk 的所有元素 { p L; while (p-next-data mink) p p-next; // p 是最后一个不大于 mink 的元素 if (p-next) { // 如果还有比 mink 更大的元素 q p-next; while (q-data maxk) q q-next; // q 是第一个不小于 maxk 的元素 p-next q; } }第一段找到p它是最后一个值不大于mink的结点也就是待删除区间的前驱。第二段从p-next开始扫描找到第一个值不小于maxk的结点q。第三段执行p-next q把中间所有值落在(mink, maxk)区间内的结点整体剪掉。注意链表的递增性质保证了区间内的结点在链表中是连续的一段所以只需要改一次指针就能完成删除。这个算法的时间复杂度是 O(n)但有一个陷阱如果p-next本身就是 NULLwhile(p-next-data mink)会访问空指针。实际使用时要先判断L-next是否为空或者把循环条件改成p-next p-next-data mink。习题答案为了简洁省略了这个保护自己上机时一定要补上。5. 答案里的坑五个典型翻车场景与排查记录5.1 代码有编辑痕迹C 语言没有x-y这种运算符现象第 1.16 题的答案里写着if(xy) x-y;原样复制到编译器里直接报错。原因这是教材里为了描述“交换两个变量的值”而约定的伪运算符并不是 C 语言语法。PDF 是从电子版教材转过来的保留了这套记号但没有在开头说明。解决把x-y替换成标准的三行交换tempx; xy; ytemp;。如果是一个数组里两个元素交换就用ta[i]; a[i]a[j]; a[j]t;。读答案时看到任何 - 符号先翻译成交换操作再继续。5.2 大量使用未定义的变量 i、j、sum、temp现象很多函数的函数体直接使用i、j、sum、temp这些变量但没有声明。比如第 1.17 题的temp[i]、第 2.21 题的i和j直接编译会报“未声明的标识符”。原因习题集为了节省篇幅省略了函数内部的局部变量声明。这些变量在作者的完整代码里是存在的但 PDF 里没有保留。解决根据上下文自行补齐声明。i、j一般声明为intsum也是inttemp声明为int temp[MAXSIZE]之类的数组。如果题目涉及浮点数比如多项式求值sum要改成float。补完后最好在函数开头统一集中声明不要用到哪加到哪否则代码很难读。5.3 判断相等写成赋值while(p-datau)是个死循环现象第 2.30 题的答案里出现while(p-datau) pp-next;执行后程序陷入死循环链表遍历不到头。原因原文是想判断p-data是否等于u但写成了单等号变成了把u赋给p-data。这个赋值结果恒为u的值非零所以循环永远不会退出。解决改成while(p-data u) p p-next;。这类“赋值号当等号用”的笔误在 C 代码里非常常见不仅是这份答案自己写代码时也要注意。如果编译器开启警告会提示 “suggest parentheses around assignment used as truth value”看到这个警告马上回头检查是不是多写或少写了一个等号。5.4 数组下标从 1 开始顺序表的下标约定容易把人搞晕现象第 2.21 题的顺序表就地逆置写的是for(i1, jA.length; ij; i, j--)和第 1.20 题里a[0]从下标 0 开始存系数的写法不一致。原因严蔚敏教材里的顺序表在逻辑上约定元素位置从 1 开始计数但 C 语言数组下标从 0 开始。习题答案里的elem[1]是第一个元素这意味着实际存储时要么把数组长度多开一个让elem[0]空着要么所有操作都把逻辑位置减 1 再映射到数组下标。解决做题前先确定题目用的是“逻辑位序”还是“物理下标”。如果答案里从 1 开始你就把elem数组的长度定义为MAXSIZE1elem[0]不用如果从 0 开始遍历和定位都要写成i-1。最稳妥的做法是封装一个GetElem(L, i)函数内部处理下标偏移上层代码永远用逻辑位序思考。5.5 状态码定义不一致INFEASIBLE、OVERFLOW、ERROR 混用现象有的函数返回INFEASIBLE有的返回OVERFLOW有的返回ERROR但不同教材对这些宏的定义不一样直接编译会报未定义或者定义了不同的值。原因习题集默认你已经实现了教材前面章节定义的宏但 PDF 里没有附上这些定义。不同版本的配套教材里这些状态码的具体数值和含义也可能不同。解决在自己代码的头部补上一套统一定义#define OK 1、#define ERROR 0、#define INFEASIBLE -1、#define OVERFLOW -2。如果你的项目里已经有类似定义就保持项目一致。另外Status类型本质是int的别名也可以用typedef int Status;声明。这样补完以后所有函数返回值就都能正常和OK比较了。6. 一个把答案真正吃透的习惯每道题先画状态图再写代码最后分享一个我自己用下来的笨办法这也是我二刷这份答案时的固定流程。拿到一道链表题不要先看答案先在草稿纸上把链表画成一串格子标出头指针、各个结点的 data 域和 next 域。然后模拟执行你要写的算法的每一步删除结点时用红笔划掉格子把被删结点的前驱的 next 箭头改到后继上插入结点时画出新结点和两条箭头的变化逆置链表时画出三个指针 p、q、s 的移动轨迹。这一步看着慢但你只需要画一次 3 个结点的最简例子就会发现绝大多数边界问题是自己脑补出来的画出来就暴露了。举第 2.22 题链表就地逆置为例3 个结点的链表1 - 2 - 3画出来步骤p 指向q 指向s 指向当前链表状态初始化1231 - 2 - 3p-nextNULL第 1 次循环23NULL2 - 13 待处理第 2 次循环3NULL出错3 - 2 - 1第 2 次循环while(s-next)时s已经是 NULL访问s-next会崩溃所以书里的代码假设表长大于 2并在循环后单独把s接到新表头。你画完这张表就明白为什么这个函数要加“表长大于 2”的前提了——边界条件不是你背出来的是画出来的。从那以后我每次拿到这类习题答案都会先恢复它的核心逻辑再手动补齐变量声明、把 - 换成标准交换、修正单等号笔误最后把每个函数的边界条件空表、单结点、i1、i 超长穷举一遍跑测试。这个过程比直接背答案痛苦但坚持下来后续做 408 真题里的代码题时会明显轻松。答案的价值在于帮你确认思路是不是最优、边界有没有漏而不是替你省掉思考。希望这份 PDF 能帮你把那层窗户纸捅破最终变成自己的东西。本文还有配套的精品资源点击获取 严蔚敏《数据结构(C语言版)》习题集答案精讲：链表栈队列实现细节
简介严蔚敏《数据结构(C语言版)习题集》配套全答案以PDF形式提供面向正在系统学习数据结构、需要大量算法练习与代码验证的高校学生、考研复习者及自学者。答案覆盖绪论、线性表与链表等章节的代表性习题包含冒泡排序、斐波那契序列动态规划、结构体与枚举应用、多项式求值等经典算法每道题给出清晰的C语言实现思路与代码部分附有时间复杂度分析和异常处理要点。例如斐波那契部分展示了动态规划如何避免重复计算多项式求值则用霍纳法则减少乘法次数这些细节有助于读者理解算法优化并在笔试和上机中灵活运用。资源包中仅有1个PDF文件压缩后体积约431KB轻量便携下载后即可直接阅读。该资源目前已有10399人学习浏览是课内巩固、期末备考和考研复习中广受关注的高价值参考资料。1. 严蔚敏《数据结构(c语言版)习题集》全答案这本 PDF 到底该怎么吃透拿到这份答案的读者多半正处于两种状态要么是 408 考研复习刷到怀疑人生要么是本科期末考前抱着书后面的习题干瞪眼。严蔚敏的《数据结构C语言版》几乎是国内计算机专业绕不开的教材而配套的习题集答案恰恰是把“看懂”变成“会写”的关键一环。这份全答案覆盖了绪论、线性表、栈与队列、串、数组、树与二叉树、图、查找与排序等章节的算法设计题和上机题绝大部分题目都给出了可直接落地的 C 函数实现不少还附了思路分析。它适合三类人准备考研但代码题还没形成套路的人期末复习想快速核对思路的人以及自学数据结构但苦于“做完了不知道对错”的人。需要注意的是这份答案不是教材讲解而是“题目 参考实现”的组合所以你得先有教材底子再拿它来对思路、补细节、抄边界处理效果才最好。2. 线性表与链表顺序表删除、无头链表插入与有序表合并的实现细节2.1 顺序表删除 k 个元素循环边界怎么推才不出错题目要求删除顺序表a中第i个元素起的连续k个元素。书里的参考实现是这样的Status DeleteK(SqList a, int i, int k) // 删除线性表 a 中第 i 个元素起的 k 个元素 { if (i 1 || k 0 || i k - 1 a.length) return INFEASIBLE; for (count 1; i count - 1 a.length - k; count) // 注意循环结束的条件 a.elem[i count - 1] a.elem[i count k - 1]; a.length - k; return OK; }这段代码的核心在循环条件i count - 1 a.length - k。我的理解是count表示当前是第几个被移动的元素i count - 1是目标位置的下标而a.length - k是删除后新表的有效长度。只有目标位置不越过新表末尾才需要继续搬移。这个边界如果推错要么少移一个元素导致尾部残留数据要么多移一个导致越界写入。实际写代码时我更习惯先把删除后的长度算出来再写循环这样逻辑更直观不容易踩坑。Status的返回类型在不同教材里有不同定义有的用int有的用枚举。这里返回INFEASIBLE表示参数不合法是一种约定你完全可以用-1或0替代只要调用方约定一致就行。2.2 无头结点链表的插入和删除i1 必须单独处理第 2.17 和 2.18 题的考点很刁钻链表没有头结点头指针直接指向第一个元素。这意味着在头部插入或删除时必须修改头指针本身而不是修改某个头结点的 next 域。Status Insert(LinkList L, int i, int b) // 在无头结点链表 L 的第 i 个元素之前插入元素 b { p L; q (LinkList)malloc(sizeof(LNode)); q-data b; if (i 1) { q-next p; L q; // 插入在链表头部头指针要变 } else { while (--i 1) p p-next; q-next p-next; p-next q; // 插入在第 i 个元素的位置 } return OK; }注意题目原文里写的是q.datab和q.nextp这是笔误q是指针应该用-。另外while(--i 1)这个写法很紧凑--i先自减再比较当i2时循环执行一次p指向第 1 个元素然后在它后面插入新结点当i1时走的是头插分支不会进入循环。这里最容易翻车的地方是传入的i超过表长代码没有做合法性检查实际使用时要自己加防御。删除的逻辑同理删除第一个元素时直接L L-next并释放原头结点删除非首元素时找到第i-1个结点执行p-next p-next-next。如果你一直在有头结点链表上练习第一次写无头版本时很容易忘记改头指针这是血泪经验。2.3 两个递增链表合并为递减链表头插法天然解决逆序第 2.24 题要求把两个元素递增排列的链表 A 和 B 合并成 C且 C 中元素递减排列要求使用原存储空间。参考实现的核心思想是“按从小到大的顺序依次把 A 和 B 的元素插入新表的头部”void reverse_merge(LinkList A, LinkList B, LinkList C) // 把元素递增排列的链表 A 和 B 合并为 CC 中元素递减排列 { pa A-next; pb B-next; pre NULL; while (pa || pb) { if (pa-data pb-data || !pb) { pc pa; q pa-next; pa-next pre; pa q; // 将 A 的元素插入新表头部 } else { pc pb; q pb-next; pb-next pre; pb q; // 将 B 的元素插入新表头部 } pre pc; } C A; A-next pc; // 构造新表头 }这里的关键变量是pre它始终指向新链表的头结点。每次取 A 或 B 中较小的那个元素让它的 next 指向pre然后更新pre为这个元素。循环结束后A 或 B 的剩余元素会按同样方式逐个插入头部。最后A-next pc这行很多人看不懂我的理解是pc是循环最后一次插入的元素也就是新链表中值最小的那个它此时在链表头部所以让 A 的头结点指向它即可。这个思路比“先合并成递增链表再反转”少一次遍历时间复杂度只有 O(nm)。做题时我在纸上画了三个链表的指针变化才真正看懂建议你也别直接跳过去。2.4 同值元素删除与就地逆置相邻双指针的推进时机第 2.20 题要求删除递增链表 L 中所有值相同的元素只保留一个。参考实现用p和q指向相邻两元素Status Delete_Equal(Linklist L) // 删除元素递增排列的链表 L 中所有值相同的元素 { p L-next; q p-next; while (p-next) { if (p-data ! q-data) { p p-next; q p-next; // 不相等时都向后推 } else { while (q-data p-data) { free(q); q q-next; // 相等时删除 q } p-next q; p q; q p-next; } } }这个题最容易踩的坑是删除连续相同元素后p的 next 指针没有更新。比如链表是1 - 2 - 2 - 2 - 3当p指向第一个 2、q指向第二个 2 时如果只 free(q) 而不让p-next指向下一个不相同的元素链表就断了。参考代码在删除完所有重复 2 之后执行p-next q把中间断开的部分补上这一步是灵魂。顺序表就地逆置第 2.21 题就是双指针头尾交换实现很简单但要注意循环条件是i j而不是i j否则中间元素会被交换两次变回原样。链表就地逆置第 2.22 题的三个指针推进顺序p-nextNULL; while(s-next) { q-nextp; pq; qs; ss-next; }属于经典操作考场上很容易写乱建议自己在纸上走一遍 3 个结点的例子。3. 栈与队列双向栈、括号匹配与火车车厢重排的落地写法3.1 双向栈的初始化与栈满判断两栈共享数组的关键双向栈就是把一个数组的两端分别作为两个栈的栈底让两个栈向中间生长。参考实现第 3.15 题如下typedef struct { ElemType *base[2]; // 两个栈底指针 ElemType *top[2]; // 两个栈顶指针 } BDStackType; Status Init_Stack(BDStackType tws, int m) // 初始化一个大小为 m 的双向栈 tws { tws.base[0] (ElemType*)malloc(sizeof(ElemType) * m); tws.base[1] tws.base[0] m - 1; // 高端栈底在数组末尾 tws.top[0] tws.base[0]; // 低端栈顶初始在栈底 tws.top[1] tws.base[1]; // 高端栈顶初始在栈底 return OK; } Status push(BDStackType tws, int i, ElemType x) // x 入栈i0 表示低端栈i1 表示高端栈 { if (tws.top[0] tws.top[1]) return OVERFLOW; // 栈满 if (i 0) *tws.top[0] x; else if (i 1) *tws.top[1]-- x; else return ERROR; return OK; } Status pop(BDStackType tws, int i, ElemType x) { if (i 0) { if (tws.top[0] tws.base[0]) return OVERFLOW; // 低端栈空 x *--tws.top[0]; } else if (i 1) { if (tws.top[1] tws.base[1]) return OVERFLOW; // 高端栈空 x *tws.top[1]; } else return ERROR; return OK; }这里三个地方值得展开。第一初始化时base[1] base[0] m - 1高端栈底指向数组最后一个元素高端栈的 top 从尾部开始入栈时向下移动--出栈时向上移动。第二栈满条件不是“两个 top 相等”而是top[0] top[1]。因为两个 top 是相向而行的一旦低端栈顶指针超过了高端栈顶指针说明中间已经没有空闲空间。第三pop里判断栈空用的是top base而不是top base这是因为高端栈的 top 只会从base[1]向base[0]方向走永远不会越过自己的 base。3.2 三种括号匹配计数法只适用于单种括号第 3.18 题判别小括号是否匹配用计数器就能解决实现简单到不需要贴完整代码。但第 3.19 题要求同时判别(、[、{三种括号时计数法就失效了——因为([)]这种交错嵌套是计数器检测不出来的。正确做法是用栈Status AllBrackets_Test(char *str) // 判别表达式中三种括号是否匹配 { InitStack(s); for (p str; *p; p) { if (*p ( || *p [ || *p {) push(s, *p); else if (*p ) || *p ] || *p }) { if (StackEmpty(s)) return ERROR; // 右括号多于左括号 pop(s, c); if (*p ) c ! () return ERROR; if (*p ] c ! [) return ERROR; if (*p } c ! {) return ERROR; // 必须与栈顶匹配 } } if (!StackEmpty(s)) return ERROR; // 左括号多于右括号 return OK; }这段代码逻辑很干净左括号一律入栈遇到右括号时先查栈空对应右括号比左括号多的情况再弹出栈顶检查类型是否匹配。扫描结束后栈不空说明存在未闭合的左括号。这里容易忽略的是if (StackEmpty(s)) return ERROR;必须放在pop之前否则对空栈做 pop 会引发未定义行为。另外如果你想在同一个函数里同时支持“括号匹配 忽略非括号字符”只要在else if分支前排除普通字符即可但要注意字符串里可能包含转义字符或引号内括号那就需要额外的状态标记不是这个习题的范围了。3.3 火车车厢重排栈的典型应用案例第 3.16 题是经典的“火车调度”问题用字符串表示车厢序列H表示硬席S表示软席要求把软席调到前面硬席调到后面且保持相对顺序。参考实现用一个栈暂存硬席车厢void Train_arrange(char *train) // 用字符串 train 表示火车H表示硬席S表示软席 { p train; q train; InitStack(s); while (*p) { if (*p H) push(s, *p); // 把 H 存入栈中 else *(q) *p; // 把 S 调到前部 p; } while (!StackEmpty(s)) { pop(s, c); *(q) c; // 把 H 按原逆序接在后部 } }这个实现的巧妙之处在于用一个q指针在原始字符串上“原地写入”。第一遍扫描时S被依次写到字符串前部H全部压栈第二遍把栈里的H逐个弹出接到S的后面。因为栈是后进先出的所以硬席车厢的最终顺序和原来相反。如果你不想反转硬席顺序就需要改用队列或者两个栈但题目没要求所以这个解法是最简的。实际做题时我建议先拿一个具体的字符串在纸上演算比如HSHSSH第一遍扫描后字符串变成SSH前三个字符被软席占据栈里从底到顶是H H H第二遍弹栈写入后得到SSHHHH。这个演算过程能帮你验证代码逻辑也能发现q指针与p指针重叠时可能出现的读写冲突——虽然这里恰好不会冲突但理解总比死记强。3.4 逆波兰式求值与中缀转后缀运算符栈的优先级原则第 3.21 题的参考实现给出了中缀转后缀的框架核心是“运算符在栈内遵循越往栈顶优先级越高的原则”。这段代码用的是伪代码我在此基础上写了个完整的 C 实现思路// 中缀表达式转逆波兰式oper 为自定义的优先级比较函数 void NiBoLan(char *str, char *new) { p str; q new; InitStack(s); // s 为运算符栈 while (*p) { if (isalpha(*p)) *q *p; // 操作数直接输出 else { c gettop(s); if (priority(*p) priority(c)) push(s, *p); // 当前运算符优先级高于栈顶则入栈 else { while (priority(gettop(s)) priority(*p)) { pop(s, c); *q c; } push(s, *p); } } p; } while (!StackEmpty(s)) { pop(s, c); *q c; } }这个框架有一个边界当栈为空时直接gettop(s)会出错所以入栈前要先判断栈空。代码里第 3.22 题逆波兰求值就更简单了——数字入栈遇到运算符弹出两个操作数计算后把结果压回去。这类题目在考研中常以“给一个中缀表达式写出后缀表达式”的形式出现不一定要写完整代码但你要能手工模拟栈的变化过程。4. 算法复杂度与边界斐波那契的动态规划、溢出检测与多项式求值4.1 斐波那契的动态规划实现为什么递归会指数爆炸第 1.17 题要求求 k 阶斐波那契序列的第 m 项。教材给出的参考实现是动态规划思路Status fib(int k, int m, int f) // 求 k 阶斐波那契序列的第 m 项的值 f { int tempd; if (k 2 || m 0) return ERROR; if (m k - 1) f 0; else if (m k - 1) f 1; else { for (i 0; i k - 2; i) temp[i] 0; temp[k - 1] 1; // 初始化 for (i k; i m; i) { // 求出第 k 至第 m 个元素的值 sum 0; for (j i - k; j i; j) sum temp[j]; temp[i] sum; } f temp[m]; } return OK; }书里的分析写得很清楚了这个方法是“通过保存已经计算出来的结果”时间复杂度仅为 O(m^2)。如果采用递归编程时间复杂度会高达 O(k^m)。这里的差距不是常数级别的是指数级别的——当m到 30 左右递归就已经肉眼可见地卡顿而动态规划几乎是瞬时完成。实际写这段代码时要注意temp数组的下标范围。代码里for(ik; im; i)意味着temp至少要能存到下标m所以数组长度要开m1。另外内层sum temp[j]的j从i-k开始这个下界在i还小时可能是负数需要先走完初始化分支才能进入这个循环。4.2 溢出检测的除法校验法这个思路比直接比较更可靠第 1.19 题求i! * 2^i序列的值且要求不超过maxint参考实现用了一个非常巧妙的溢出检测手段Status algo119(int a[ARRSIZE]) // 求 i!*2^i 序列的值且不超过 maxint { last 1; for (i 1; i ARRSIZE; i) { a[i - 1] last * 2 * i; if ((a[i - 1] / last) ! (2 * i)) return OVERFLOW; // 除法结果异常说明溢出 last a[i - 1]; } return OK; }它的原理是如果没有溢出a[i-1]一定等于last * 2 * i那么a[i-1] / last应该恰好等于2 * i。一旦乘法结果超过了maxint整数溢出后得到的是一个被截断的值这个值除以last大概率不等于2 * i于是检测到溢出。这个方法比“预先比较 last 和 maxint/(2*i)”更巧妙但也更隐晦——如果溢出后恰好整除出了2*i理论上会漏检只是概率极低做题时可以接受。不过这个实现里有个细节2*i本身也可能溢出如果i足够大2*i先溢出后面的比较就没有意义了。所以实际使用时我会在循环里加一个if (i maxint/2)的提前判断把问题消灭在源头。但作为习题答案理解它的检测思路比纠结边界更有价值。4.3 多项式求值的霍纳法则指针遍历系数数组第 1.20 题的polyvalue函数展示了如何在 C 里用指针高效遍历数组并求多项式值void polyvalue() { float ad; float *p a; printf(Input number of terms:); scanf(%d, n); printf(Input the %d coefficients from a0 to a%d:\n, n, n); for (i 0; i n; i) scanf(%f, p); printf(Input value of x:); scanf(%f, x); p a; xp 1; sum 0; // xp 用于存放 x 的 i 次方 for (i 0; i n; i) { sum xp * (*p); xp * x; // 迭代计算 x 的下一次方 } printf(Value is:%f, sum); }严格来说这段代码不是霍纳法则而是最朴素的“逐项累乘”法——用一个xp变量保存x的当前幂次每处理完一项就乘以x。它的时间复杂度是 O(n)而霍纳法则秦九韶算法的时间复杂度同样是 O(n)但乘法次数更少数值稳定性更好。霍纳法则的写法是sum a[n]; for(in-1; i0; i--) sum sum*x a[i];考研中更喜欢考后者。这里用指针p遍历数组的写法和数组下标访问等价但要注意第一轮scanf之后p已经指向数组末尾第二轮求值前必须把p重新指回a否则会读越界。这种“指针用完后复位”的习惯是在 C 语言编程里少踩坑的重要保证。4.4 区间删除三段式定位、扫描、裁剪第 2.19 题要求在递增链表 L 中删除值大于mink且小于maxk的所有元素。参考实现是典型的三段式Status Delete_Between(Linklist L, int mink, int maxk) // 删除元素递增排列的链表 L 中值大于 mink 且小于 maxk 的所有元素 { p L; while (p-next-data mink) p p-next; // p 是最后一个不大于 mink 的元素 if (p-next) { // 如果还有比 mink 更大的元素 q p-next; while (q-data maxk) q q-next; // q 是第一个不小于 maxk 的元素 p-next q; } }第一段找到p它是最后一个值不大于mink的结点也就是待删除区间的前驱。第二段从p-next开始扫描找到第一个值不小于maxk的结点q。第三段执行p-next q把中间所有值落在(mink, maxk)区间内的结点整体剪掉。注意链表的递增性质保证了区间内的结点在链表中是连续的一段所以只需要改一次指针就能完成删除。这个算法的时间复杂度是 O(n)但有一个陷阱如果p-next本身就是 NULLwhile(p-next-data mink)会访问空指针。实际使用时要先判断L-next是否为空或者把循环条件改成p-next p-next-data mink。习题答案为了简洁省略了这个保护自己上机时一定要补上。5. 答案里的坑五个典型翻车场景与排查记录5.1 代码有编辑痕迹C 语言没有x-y这种运算符现象第 1.16 题的答案里写着if(xy) x-y;原样复制到编译器里直接报错。原因这是教材里为了描述“交换两个变量的值”而约定的伪运算符并不是 C 语言语法。PDF 是从电子版教材转过来的保留了这套记号但没有在开头说明。解决把x-y替换成标准的三行交换tempx; xy; ytemp;。如果是一个数组里两个元素交换就用ta[i]; a[i]a[j]; a[j]t;。读答案时看到任何 - 符号先翻译成交换操作再继续。5.2 大量使用未定义的变量 i、j、sum、temp现象很多函数的函数体直接使用i、j、sum、temp这些变量但没有声明。比如第 1.17 题的temp[i]、第 2.21 题的i和j直接编译会报“未声明的标识符”。原因习题集为了节省篇幅省略了函数内部的局部变量声明。这些变量在作者的完整代码里是存在的但 PDF 里没有保留。解决根据上下文自行补齐声明。i、j一般声明为intsum也是inttemp声明为int temp[MAXSIZE]之类的数组。如果题目涉及浮点数比如多项式求值sum要改成float。补完后最好在函数开头统一集中声明不要用到哪加到哪否则代码很难读。5.3 判断相等写成赋值while(p-datau)是个死循环现象第 2.30 题的答案里出现while(p-datau) pp-next;执行后程序陷入死循环链表遍历不到头。原因原文是想判断p-data是否等于u但写成了单等号变成了把u赋给p-data。这个赋值结果恒为u的值非零所以循环永远不会退出。解决改成while(p-data u) p p-next;。这类“赋值号当等号用”的笔误在 C 代码里非常常见不仅是这份答案自己写代码时也要注意。如果编译器开启警告会提示 “suggest parentheses around assignment used as truth value”看到这个警告马上回头检查是不是多写或少写了一个等号。5.4 数组下标从 1 开始顺序表的下标约定容易把人搞晕现象第 2.21 题的顺序表就地逆置写的是for(i1, jA.length; ij; i, j--)和第 1.20 题里a[0]从下标 0 开始存系数的写法不一致。原因严蔚敏教材里的顺序表在逻辑上约定元素位置从 1 开始计数但 C 语言数组下标从 0 开始。习题答案里的elem[1]是第一个元素这意味着实际存储时要么把数组长度多开一个让elem[0]空着要么所有操作都把逻辑位置减 1 再映射到数组下标。解决做题前先确定题目用的是“逻辑位序”还是“物理下标”。如果答案里从 1 开始你就把elem数组的长度定义为MAXSIZE1elem[0]不用如果从 0 开始遍历和定位都要写成i-1。最稳妥的做法是封装一个GetElem(L, i)函数内部处理下标偏移上层代码永远用逻辑位序思考。5.5 状态码定义不一致INFEASIBLE、OVERFLOW、ERROR 混用现象有的函数返回INFEASIBLE有的返回OVERFLOW有的返回ERROR但不同教材对这些宏的定义不一样直接编译会报未定义或者定义了不同的值。原因习题集默认你已经实现了教材前面章节定义的宏但 PDF 里没有附上这些定义。不同版本的配套教材里这些状态码的具体数值和含义也可能不同。解决在自己代码的头部补上一套统一定义#define OK 1、#define ERROR 0、#define INFEASIBLE -1、#define OVERFLOW -2。如果你的项目里已经有类似定义就保持项目一致。另外Status类型本质是int的别名也可以用typedef int Status;声明。这样补完以后所有函数返回值就都能正常和OK比较了。6. 一个把答案真正吃透的习惯每道题先画状态图再写代码最后分享一个我自己用下来的笨办法这也是我二刷这份答案时的固定流程。拿到一道链表题不要先看答案先在草稿纸上把链表画成一串格子标出头指针、各个结点的 data 域和 next 域。然后模拟执行你要写的算法的每一步删除结点时用红笔划掉格子把被删结点的前驱的 next 箭头改到后继上插入结点时画出新结点和两条箭头的变化逆置链表时画出三个指针 p、q、s 的移动轨迹。这一步看着慢但你只需要画一次 3 个结点的最简例子就会发现绝大多数边界问题是自己脑补出来的画出来就暴露了。举第 2.22 题链表就地逆置为例3 个结点的链表1 - 2 - 3画出来步骤p 指向q 指向s 指向当前链表状态初始化1231 - 2 - 3p-nextNULL第 1 次循环23NULL2 - 13 待处理第 2 次循环3NULL出错3 - 2 - 1第 2 次循环while(s-next)时s已经是 NULL访问s-next会崩溃所以书里的代码假设表长大于 2并在循环后单独把s接到新表头。你画完这张表就明白为什么这个函数要加“表长大于 2”的前提了——边界条件不是你背出来的是画出来的。从那以后我每次拿到这类习题答案都会先恢复它的核心逻辑再手动补齐变量声明、把 - 换成标准交换、修正单等号笔误最后把每个函数的边界条件空表、单结点、i1、i 超长穷举一遍跑测试。这个过程比直接背答案痛苦但坚持下来后续做 408 真题里的代码题时会明显轻松。答案的价值在于帮你确认思路是不是最优、边界有没有漏而不是替你省掉思考。希望这份 PDF 能帮你把那层窗户纸捅破最终变成自己的东西。本文还有配套的精品资源点击获取