这几年我带过不少学生做数据结构上机题要说哪道题最容易被低估一元稀疏多项式的计算绝对排得上号。这道题来自某高校的数据结构课程上机环节题面看起来只是“计算两个多项式之和/积”但实际做起来牵扯到链表的设计、有序插入、合并同类项、边界输出甚至还有内存释放的问题一圈下来能把基本功考察得明明白白。很多人觉得它跟“一元多项式”差不多随手就用数组写了结果测试一跑就傻眼——稀疏二字才是关键数组存稀疏多项式既浪费空间又难处理指数跨度巨大的情况上机题真正的考点是链表。这篇文章我按照自己做题和带学生做题时的思路来写把这道题从需求拆解到代码实现再到常见坑点全部过一遍适合刚学到链表、准备做这道上机题的同学也适合想系统整理多项式链表操作的读者。看完之后你不仅能顺利交差还能把“链表的插入、删除、合并、遍历”这套底层能力真正吃透。1. 题目到底在考什么上机题的文字描述一般不长大意是从键盘输入两个一元稀疏多项式的项数以及每一项的系数和指数计算它们的和与积输出结果多项式。但就是这么一道表面简单的题暗含了好几个层次的考察点。1.1 “稀疏”两个字决定了存储方案先解释一下什么是稀疏多项式。简单说就是一个多项式的次数跨度很大但实际存在的项却很少。比如 (x^{1000} 1)指数从0到1000中间999个单项式全是0系数。如果用数组存下标对应指数那就得开一个长度1001的数组里面绝大多数位置是0如果遇到 (x^{1000000} 1)数组根本开不出来。链表不一样它只存“有系数、非零”的项每一项就是一个结点指数再大也只是一个整数域不占连续空间。这就是“稀疏”二字的含义——它直接决定了你不能用固定数组去硬扛得用链式存储。明白了这一层题目就成功了一半因为很多上机失败的同学第一步就在存储方案上选错了路。1.2 功能需求拆解把题目文字翻译成具体的功能点大概是这么几个能创建多项式链表输入格式通常是先给项数n再依次输入n对(系数, 指数)能输出多项式输出格式要符合数学习惯不能出现“1x^2”这种低级错误能实现两个多项式相加返回结果链表能实现两个多项式相乘返回结果链表适当的扩展功能比如多项式求值、多项式释放内存一般写在加分项或隐含要求里。输出格式最容易被忽略也最容易失分。我见过有同学测试两个多项式输入输出的时候结果全是正常的但助教一眼就看出格式问题系数1没有省略、指数0还带着x^0、首项正号没去掉。输出格式在上机题里往往占据很大的分值比例后面我会专门讲怎么写一个好的打印函数。1.3 为什么这道题适合练链表基本功链表这个数据结构很多同学看书看懂了但一上手就发懵。多项式计算恰好给了你一个非常自然的场景结点的数据域有两个系数指数指针域一个增删查改全都要用上。加法是两个有序链表归并乘法是两层循环遍历合并同类项是链表查找与结点值修改输出是链表遍历加格式转换。几乎把单链表该有的操作一网打尽。另外这道题比约瑟夫环、学生管理系统这类题目更纯粹因为它全部操作都围着“结点”转没有文件读写、菜单交互等噪音干扰很适合作为链表专题的压轴上机题。做透它后面再做一元多项式计算器、表达式求值、集合运算这类题目套路都是通用的。2. 整体设计思路与方案选择拿到题先别急着敲代码把方案定下来后面会顺畅非常多。我讲解思路时会给两种方案做对比再说清楚我推荐的方案以及原因。2.1 带头结点还是不带头结点这是链表题的第一道选择题。不带头结点的链表第一个结点的插入和删除要单独写逻辑因为头指针本身会变带头结点的链表头结点固定存在但它不存有效数据所有结点的操作逻辑统一了插入和删除不需要区分“是不是第一个”。多项式这道题既要创建、又要合并、又要插入新结点操作特别频繁我用的是带头结点方案。代价是多占一个结点的内存但换来的是代码简洁度大幅提升逻辑出错概率明显降低。2.2 无序插入后排序还是有序插入创建多项式链表时用户输入的各项顺序是任意的可能先输入指数大的再输入指数小的也可能输入顺序乱跳。输出按指数升序是基本要求所以链表最终必须有序。处理办法有两种先按输入顺序建链全部建完之后再写一个排序函数对链表做插入排序或交换结点的排序在插入每个结点时就按照指数升序找到正确位置边读边插建出来的链表天然有序。我毫不犹豫推荐第二种。原因有两个第一排序函数写起来麻烦还要处理头尾结点的指针变动第二后续加法、合并同类项都建立在“链表有序”的基础上你可以在创建时顺手把“查找插入位置”这个操作练熟后面用起来很自然。有序插入的时间复杂度是O(n²)对这个规模的上机题完全够用。2.3 加减乘求值怎么组织我的设计里核心功能分成五个函数CreatePoly读入项数逐项有序插入创建多项式PrintPoly输出多项式处理各种格式细节AddPoly实现两个多项式相加MulPoly实现两个多项式相乘EvalPoly给定x值计算多项式结果。减法我没有单独写一个新函数。因为 A - B 本质上就是 A (-B)把B链表的每个系数取相反数再调用加法函数即可。这样既避免重复代码又降低了出错概率一个项目中少写一个函数就少一个维护点。这种“复用已有模块”的习惯在上机题里很讨巧。你写的代码越少、越清晰调试时越容易定位问题。2.4 整体流程设计主函数的逻辑简单直接创建多项式A创建多项式B打印A和B计算AB打印结果计算A×B打印结果释放三个链表的内存。流程不复杂重点全在函数实现里。我建议每个函数完成一件事命名清晰不要在主函数里写一堆实现细节。上机题的代码不仅是给机器跑的也是给人看的。3. 核心数据结构与关键函数解析确定了方案接下来就是把每个模块一层层实现出来。这一部分我讲清楚每个函数的设计思路和边界处理代码放在下一节统一给出。3.1 结点结构的定义每个结点存储三个信息系数、指数、后继指针。系数用浮点型还是整型取决于题目描述。很多版本的多项式题允许系数为整数但更通用的做法是浮点型因为乘法和加法都可能产生非整系数。我用浮点型输入时按浮点数读入输出时再按格式去控制精度。指数一般是非负整数用整型存储。这里要注意指数如果输入了负数理论上不是标准的一元多项式但在健壮性设计时至少要能处理极端输入不崩溃这个问题放到后面的常见问题章节细说。3.2 有序插入函数的写法这是整个项目的基石。插入新结点的逻辑是从链表头结点的next开始用一个前驱指针pre和当前指针cur遍历如果cur不为空且cur的指数小于新结点的指数就继续往后走循环结束后pre就是插入位置的前驱cur是插入位置的后继把新结点插到pre和cur之间。这段逻辑说起来简单但初学很容易出错的地方在于忘记边界情况——新结点的指数比所有结点都小那cur一开始就为空新结点的指数比所有结点都大那要遍历到链表尾部。无论哪种情况最终都是把新结点插到pre之后代码统一。我强调一点插入的过程不要一上来就写排序先写好“找到位置再插入”这个小函数然后创建多项式时反复调用它。你会发现这个函数写好了乘法的合并操作能复用一大半。3.3 加法函数的归并思路两个多项式有序相加最经典的做法就是归并。和归并排序的merge过程很像p指向A链表的当前结点q指向B链表的当前结点比较p和q的指数p的指数小把p的结点值赋给结果链表的新结点p后移q的指数小把q的结点值赋给结果链表的新结点q后移指数相等系数相加如果和不为0才把结果结点插入结果链表然后p和q同时后移循环结束后把p或q剩余的结点全部拷入结果链表。这个函数里最容易遗漏的就是“指数相等且系数相加为0”的情况。比如 (x 1) 减去 (x)结果应该只剩一个常数1。有些实现遇到系数和为零时不知道该怎么办直接插入了一个系数为0的结点导致输出出现“0”这种丑陋的结果。所以一定要判断和为0时不插入新结点。另一个细节是“新结点”与“原结点”的关系。最省事的方式是为结果链表逐个创建新结点复制p或q的数据而不是直接把p或q的结点挂在结果链表上。直接挂结点虽然省时间但会破坏原来的A、B链表后面乘法就没法用了。我的原则是功能函数不修改输入链表。3.4 乘法函数的实现策略多项式乘法最自然的思路是A的每一项依次乘以B的所有项得到的所有结果合并同类项。具体实现有两种先全部插入到一个结果链表中最后统一合并同类项每计算出一个乘积项就在结果链表中找到它的指数位置如果指数已经存在就把系数累加上去如果不存在就插入新结点。第二种看起来复杂但避免了二次遍历合并实现上只多一个“查找指数是否存在”的操作顺手就能写完。我推荐第二种它本质上就是有序插入函数的变体插入前先找相同指数有则累加无则插入。这部分的代码需要注意乘法结果链表的初始化以及两层循环结束后要记得清掉结果链表中可能残留的系数为0的项。虽然我们在累加时已经判断了但某些情况下比如 (x \times 0) 这种输入还是会造出0系数结点稳妥起见加一步清理更安心。3.5 打印函数的格式规则打印输出是看似简单、实际最容易翻车的部分。一个合格的多项式输出要满足以下全部规则空多项式结果为0要输出“0”首项系数为正时不输出正号首项系数为负时要输出负号系数为1或-1时不显示“1”直接显示x指数为0时不显示x只显示系数指数为1时只显示x不显示“x^1”指数大于1时显示“x^指数”非首项系数为正时前面要加“”号为负时加“-”号系数为0的结点不应该出现在链表中但打印函数最好也做个防御。这一串规则看着头大其实可以抽成几个小判断。我写的时候是逐个if处理好复杂的逻辑没有用花哨的语法保证一眼能看懂。很多同学觉得这部分不重要随便写个“3x^2 2x^1 1”的输出就交了结果在助教的严格测试下被扣分。上机题的输出格式往往是明确的验收标准宁可多花十分钟在这上面也不要为了赶时间写一个格式残缺的版本。3.6 求值函数的实现考量求值函数的需求一般是题目里带的扩展要求也可能由你自己加上去。最直观的方法就是逐个结点计算 (coef \times x^{exp}) 再累加C语言里可以调用数学库的pow函数。这里有个小坑pow函数返回的是double如果系数是整型你累加时最好用double类型的变量承接否则精度会被截断。比如 (x^2) 在 (x3) 时结果是9用整型没问题但 (x0.5) 时就不是整值了。求值的输入x一般是浮点数所以累加器用double是稳妥选择。4. 完整代码实现与解释下面给出我写的一套完整参考代码。代码用标准C语言编写编译环境可以是各类常见IDE或者命令行gcc编译没有使用平台相关的特殊头文件拿到哪里都能跑。#include stdio.h #include stdlib.h #include math.h // 多项式结点结构 typedef struct Node { double coef; // 系数 int exp; // 指数 struct Node *next; // 下一个结点 } Node, *Poly; // 创建空链表带头结点 Poly createEmptyPoly() { Poly head (Poly)malloc(sizeof(Node)); if (head NULL) { printf(内存分配失败\n); exit(1); } head-coef 0; head-exp -1; head-next NULL; return head; } // 在有序链表中插入新结点含合并同类项 void insertNode(Poly head, double coef, int exp) { if (coef 0) return; // 系数为0忽略 Node *pre head; Node *cur head-next; while (cur ! NULL cur-exp exp) { pre cur; cur cur-next; } if (cur ! NULL cur-exp exp) { // 同指数合并 cur-coef coef; if (cur-coef 0) { // 合并后系数为0删掉 pre-next cur-next; free(cur); } } else { // 不同指数插入 Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-coef coef; newNode-exp exp; newNode-next cur; pre-next newNode; } } // 创建多项式 Poly createPoly() { Poly head createEmptyPoly(); int n, exp; double coef; printf(请输入多项式的项数); scanf(%d, n); for (int i 0; i n; i) { printf(输入第%d项的系数和指数, i 1); scanf(%lf%d, coef, exp); insertNode(head, coef, exp); } return head; } // 打印多项式 void printPoly(Poly head) { Node *p head-next; if (p NULL) { printf(0\n); return; } int first 1; // 是否为首项 while (p ! NULL) { if (p-coef 0) { if (!first) printf(); } if (p-coef 0) { printf(-); } // 系数绝对值 double absCoef fabs(p-coef); if (p-exp 0) { printf(%.2f, absCoef); // 常数项输出系数 } else if (absCoef ! 1) { printf(%.2fx, absCoef); // 系数不是1输出系数和x } else { printf(x); // 系数是1省略 } if (p-exp 1) { printf(^%d, p-exp); } first 0; p p-next; } printf(\n); } // 加法 Poly addPoly(Poly a, Poly b) { Poly result createEmptyPoly(); Node *p a-next; Node *q b-next; while (p ! NULL q ! NULL) { if (p-exp q-exp) { insertNode(result, p-coef, p-exp); p p-next; } else if (p-exp q-exp) { insertNode(result, q-coef, q-exp); q q-next; } else { double sum p-coef q-coef; if (sum ! 0) { insertNode(result, sum, p-exp); } p p-next; q q-next; } } while (p ! NULL) { insertNode(result, p-coef, p-exp); p p-next; } while (q ! NULL) { insertNode(result, q-coef, q-exp); q q-next; } return result; } // 取相反数 Poly negPoly(Poly a) { Poly result createEmptyPoly(); Node *p a-next; while (p ! NULL) { insertNode(result, -p-coef, p-exp); p p-next; } return result; } // 减法复用加法 Poly subPoly(Poly a, Poly b) { Poly negB negPoly(b); Poly result addPoly(a, negB); freePoly(negB); return result; } // 乘法 Poly mulPoly(Poly a, Poly b) { Poly result createEmptyPoly(); Node *p a-next; while (p ! NULL) { Node *q b-next; while (q ! NULL) { double coef p-coef * q-coef; int exp p-exp q-exp; insertNode(result, coef, exp); // insertNode内部处理合并 q q-next; } p p-next; } return result; } // 求值 double evalPoly(Poly a, double x) { double sum 0.0; Node *p a-next; while (p ! NULL) { sum p-coef * pow(x, p-exp); p p-next; } return sum; } // 释放链表 void freePoly(Poly head) { Node *cur head; while (cur ! NULL) { Node *temp cur; cur cur-next; free(temp); } } int main() { printf(第一个多项式\n); Poly a createPoly(); printf(第二个多项式\n); Poly b createPoly(); printf(A(x) ); printPoly(a); printf(B(x) ); printPoly(b); Poly sum addPoly(a, b); printf(A(x) B(x) ); printPoly(sum); Poly diff subPoly(a, b); printf(A(x) - B(x) ); printPoly(diff); Poly prod mulPoly(a, b); printf(A(x) * B(x) ); printPoly(prod); double x; printf(请输入一个x值用于求值); scanf(%lf, x); printf(A(%.2f) %.2f\n, x, evalPoly(a, x)); printf(B(%.2f) %.2f\n, x, evalPoly(b, x)); freePoly(a); freePoly(b); freePoly(sum); freePoly(diff); freePoly(prod); return 0; }这段代码我故意把insertNode设计成“万能插入”函数——创建、加法、乘法、减法全部复用它整个项目的复杂度因此大幅下降。这是一个典型的上机题优化思路多写一个通用函数比到处复制插入代码要省事得多。代码里有一个细节需要提一下打印函数中我用%.2f控制小数位数默认保留两位小数。如果你输入的系数都是整数但打印成“2.00x”看起来会有些奇怪。如果题目没有强制要求小数精度可以把%.2f改成%g%g会自动省略小数部分的末尾零输入整数时显示整数输入小数时保留必要位数观感更自然。但注意如果用%g输出格式的规则判定会变得稍微复杂大家可以根据自己上机题的要求调整。5. 上机实测测试用例与踩坑记录代码写完不是终点上机题的重头戏在于能通过助教的测试。这一部分我把我做这道题时踩过的坑和总结出的测试方法整理出来非常有实战价值。5.1 典型测试用例一览测试用例的覆盖很大程度上决定了上机分数。我通常至少测以下这些场景场景A多项式B多项式期望结果说明普通加法(3x^2 2x 1)(4x^3 x)指数顺序正确合并(2xx3x)正负抵消(x)(-x 1)相加后只剩常数1零多项式(0)(2x1)相加为(2x1)乘法为0首项为负(-x^2 1)(x)结果首项带负号指数为1(x)(x^2)输出不带(x^1)同指数合并(5x^3)(-5x^3 2)相加后只剩常数2乘法大跨度(x^{100})(x^{100})结果为(x^{200})这个表是精简版本实际测试时我还会加入“未排序输入”“系数为-1的项”“指数为0的常数”等场景确保打印格式和排序逻辑双保险。5.2 我在调试中踩过的几个具体坑第一个坑是打印函数的正负号逻辑。最初我把非首项系数为正时输出“”这个判断写在了绝对值的判断之后结果每一项前面都出现了“”包括首项输出变成“3x^22x1”。解决方法是加一个first标志位首项以及后续项分开处理。这个标志位的思路很简单但对初学者来说却是打印函数里最容易漏写的部分。第二个坑是乘法结果的合并问题。一开始我的乘法是先插入所有乘积项最后再调一个合并同类项的函数。结果这个合并函数本身又要遍历、又要比较指数、又要处理删除结点写了三四十行还时不时出bug。后来我改成在insertNode里顺带合并乘法代码反而少了很多。这也提醒我设计一个通用的、能自动合并的插入函数远比在每个功能函数里各自写插入逻辑更加可靠。第三个坑是内存释放的顺序。我曾经在减法函数里直接返回addPoly(a, b)的逆操作结果却没有释放中间创建的负B链表导致程序在循环测试时内存不断增长。上机判题有时候不查内存泄漏但作为练手项目养成写完就释放的习惯非常重要。第四个坑比较隐蔽读取输入时系数和指数的格式。scanf(%lf%d, coef, exp)这个格式里如果用户输入的是整数系数比如“3 2”%lf也能正常读入内存里的浮点数3.0没有问题。但反过来如果你声明成了int coef却用%lf读取或者声明成double却用%d读取都会产生数据错乱且难以排查。5.3 上机前的自查清单每次学生问我“老师我这代码能过了吧”我都会让他按下面的清单自己过一遍通过率能提升一大截头文件是否齐全尤其是否包含了math.h并链接了数学库输入提示和输出格式是否跟题目要求的完全一致是否能用“A(x) B(x) ”这种易读格式打印还是直接打印裸结果两个链表是否都带头结点插入、删除时头结点的next是否正确处理空多项式输出是否为“0”而不是空白行系数为1、-1的项是否省略了数字1指数为0、1的项是否正确省略幂次加法、乘法结果链表是否按指数升序排列所有动态分配的内存是否释放干净。这九条检查过一遍一般上机环境里遇到的问题都能提前暴露。剩下的就是编译警告比如未使用的变量、隐式类型转换最好也能全部清零因为这些警告有时候暗示着真正的逻辑错误。6. 如何从“能跑”升级到“高分”先把能跑的基本功做扎实再说怎么让自己代码水平显得更高。上机题评分不只看测试点过不过有时候也看代码结构、注释质量、边界处理意识。6.1 让代码更健壮的几个额外处理我在代码基础上可以做几个加分项第一对输入的合法性做简单校验。比如项数n是负数时直接报错退出指数为负数时提示输入不合法。虽然题目不一定测试这种数据但代码里有一层防御机制体现的是工程意识。第二对乘法结果和加法结果统一使用insertNode处理让你整个项目里只有一处“插入”逻辑。这样不管后续功能怎么扩展插入的地方都不会出错。第三把求值功能、可视化打印提示、甚至多项式导函数都加进去。上机题一般不会要求这么多但加一个求值函数调用无负担还能在答辩时多一个展示点。6.2 我常用的答辩讲解思路如果上机题需要当面演示或答辩讲解顺序建议是先讲存储结构为什么选链表再讲插入函数如何保证有序然后讲加法归并和乘法两层循环最后用测试用例证明正确性。讲的时候不用把每一行代码都念出来重点放在“为什么这么设计”和“边界条件怎么处理”上。解释清楚“为什么输入顺序乱也能输出正确”往往能让助教或老师对代码的理解更深入。你可以一边演示一边说“因为我们在插入时已经按指数排好了顺序后续加法乘法都依赖这个性质”一句话就把整份代码的设计亮点点透了。6.3 拓展思考不只是多项式做完这道题你会发现链表“插入有序结点、删除指定结点、遍历合并”这套操作几乎是整个数据结构课程前半程的缩影。后面学的集合运算、稀疏矩阵的十字链表、邻接表很多操作思路都极其相似。我经常跟学生说上机题的意义不在于交作业而在于把你对抽象数据结构的理解落地成具体代码。这道多项式题做完你再回头看单链表的教材例题会明显觉得简单许多。如果学有余力可以把当前代码扩展为“稀疏矩阵”的链表存储或者把多项式计算器做成一个交互式命令行小工具这些扩展都会让你的数据结构功底更加扎实。