多项式相乘的链表实现：从合并同类项到边界处理

前几天整理旧电脑在文件夹深处翻出了某高校2021春数据结构课的一道经典作业多项式相乘。看到那些纯C写的链表代码当年踩过的坑一下子全回来了。多项式相乘听起来像小学算术的进阶版但真正写成程序之后要处理的事情非常多每一项怎么存、乘出来的中间结果往哪里放、指数相同怎么合并、系数算完变成0怎么办、输出格式按什么规则来。这个题其实非常典型非常适合用来检验链表基本功。这篇内容不打算只贴一份能跑的代码交差而是把做这道题时的选型思路、核心流程、调试经历和测试数据一起整理出来。无论你是正在被这道题卡住的学生还是想复习链表操作、理解“无序数据如何聚合成有序结构”的人都应该能在这里找到参考。1. 题目复盘多项式相乘到底在考什么1.1 作业描述与输入输出格式某高校2021春的这道作业题目描述大概长这样输入两个多项式第一行给多项式A的项数n后面n行每行一个系数和一个指数再输入多项式B的项数m和对应的m行系数指数。要求输出A和B相乘后的结果多项式结果按指数降序排列每行一个非零项“系数 指数” 。我当时的第一反应是这有什么难的两个循环套一下不就完了。但真正动手之后才发现题目里每一个看起来理所当然的要求都在给程序加约束。“按指数降序”“非零项”“每行一个”这些话翻译成代码就是排序逻辑、删除节点逻辑、格式判断逻辑一个都跑不掉。还有一点容易被忽略题目没有明确说输入的项数范围也没有说指数是不是连续的。这意味着不能把“指数不连续”“指数跨度很大”当成异常情况必须按正常输入处理。我在做的时候默认n和m都不会超过某个量级比如几百项但代码不能依赖这个假设去开定长数组否则就是给自己埋雷。1.2 隐藏在乘法背后的三类基本功表面上看这道题考的是乘法实际上它同时考察了三类东西。第一类是链表操作基本功。创建节点、插入节点、删除节点、遍历链表这些操作单独拿出来大家都会写但放进同一个程序里互相嵌套时很容易出现“插入完了指针丢了”“删除之后前一个节点没接上”这类问题。尤其是结果链表需要保持有序每次插入都要从头找位置这个过程的指针更新顺序必须非常清晰。第二类是边界条件处理。系数为0的项要不要参与运算两个多项式相乘后某些项合并导致系数为0要不要从结果里删掉如果两个多项式都只有一项呢如果指数很大呢这些情况测试用例不会明说但评分的时候往往就是这些边界点决定你是满分还是扣分。第三类是输出格式规范。很多人程序逻辑全对结果因为输出格式不对被扣分非常可惜。多项式输出看起来简单实际有很多约定俗成的细节比如首项系数为正时不带加号、系数为1时不省略数字还是省略数字、指数为0怎样显示、指数为1怎样显示。这些规则在不同题目里要求可能不一样必须逐字看题目要求。我当时把这三类东西拆开研究了一遍才意识到这道题的“含金量”其实很高。做完它链表这一章的核心知识基本就被串起来了。2. 数据结构选型数组方案与链表方案的真实差异2.1 数组方案的适用场景与硬伤最开始我考虑过数组方案开一个足够大的数组表示系数下标就是指数比如coef[5]3就表示3x^5。这样做乘法确实方便结果的合并同类项直接变成数组下标对应的系数相加不需要处理链表。但这个方案有一个很现实的问题指数跨度大了怎么办比如第一个多项式里有一项x^100第二个多项式里有一项x^200结果里就会出现指数300的项数组至少要开到301。这还能忍但如果题目输入里出现指数上万的项开定长数组就非常浪费内存且必须事先知道上限。更尴尬的是大部分课程测试题不会在题目里明确写出指数的最大值开小了越界开大了浪费属于两头堵的状态。数组方案还有一个隐蔽的问题结果是稀疏的。两个多项式相乘之后很多指数位置根本没有项用数组存储会把大量空间浪费在“空洞”上。遍历输出时还要跳过所有系数为0的下标逻辑也不算简单。综合来看数组方案只适合“指数范围小且密集”的特例不适合作为这道题的通解。2.2 链表方案为什么适合这道题链表方案的思路和数组完全不同有多少个项就创建多少个节点每个节点包含系数、指数、指向下一个节点的指针。存储密度和实际项数严格一致指数跨度再大也不影响空间占用。插入排序的时候只需要调整指针不需要搬动大段内存这在多项式项数较多时优势非常明显。对这道题来说链表还有一个额外的好处合并同类项的操作在链表上是“查找指数相同的节点累加系数必要时删除节点”逻辑非常清晰。用数组做合并是“索引定位直接加”确实更省事但前提还是指数范围可控。既然题目没有给范围保证我最后选了链表这也是大多数教材在这个题目上的标准做法。2.3 我的节点结构与程序约定节点结构我定义得比较简单typedef struct PolyNode { int coef; // 系数 int expo; // 指数 struct PolyNode *next; // 指向下一项 } PolyNode, *Polynomial;系数我用int指数用int。如果题目要求系数可能是浮点数就改成double但作业里一般给整数系数。我额外的几个程序约定如下创建链表时统一使用带头节点的空链表操作时不用考虑“头指针本身是不是节点”的问题插入和删除代码会简单很多。所有链表保持指数严格递减从高次到低次这样输入完成后就是有序状态后续乘法结果也能按有序方式插入。任何系数为0的项在创建阶段就直接不建节点不在链表里保留“占位项”。这里有个容易忽略的细节带头节点的链表中头节点本身是没有实际数据意义的只是为了统一操作逻辑。很多同学不带头节点也能写对但插入到头部和插入到中间要分别写两套逻辑代码量明显更多出错率也更高。我建议直接用带头节点的写法省心。3. 乘法核心流程逐项相乘与合并同类项的工程化实现3.1 算法主框架外层遍历A内层遍历B多项式乘法的基础原理很简单A的每一项分别乘以B的每一项再把所有乘积结果中指数相同的项合并。用数学语言表达就是A Σ a_i * x^(p_i)B Σ b_j * x^(q_j)A × B ΣΣ a_i * b_j * x^(p_i q_j)实现的时候就是一个嵌套循环外层指针遍历A的每个节点内层指针遍历B的每个节点。每拿到一对节点就生成一个新的中间结果项系数是a_i * b_j指数是p_i q_j。所有中间结果都不能直接当成最终结果因为不同组合可能产生相同的指数比如A的x^2乘以B的x^3和A的x^4乘以B的x^1都会得到x^5。必须有一个“合并同类项”的机制把这些指数相同的项汇总起来。3.2 结果链表的有序插入与节奏控制合并同类项最简单的做法就是让结果链表始终保持有序每生成一个新的中间项都在结果链表中找到它应该插入的位置。如果该位置已经有一个指数相同的节点就把系数加到那个节点上如果没有就新建节点插入。这种做法的好处是不需要等所有乘法算完再去排序合并动作天然发生在插入过程中。代价是每次插入都要从头遍历结果链表时间复杂度是O(nmresult_len)但课设量级完全能接受没必要为了这点性能去写哈希表。插入时的逻辑我用伪代码梳理一下for (A从第一个有效节点开始) { for (B从第一个有效节点开始) { tempCoef A-coef * B-coef tempExpo A-expo B-expo prev 结果链表的头节点 cur prev-next while (cur ! NULL cur-expo tempExpo) { prev cur; cur cur-next; } if (cur ! NULL cur-expo tempExpo) { // 指数相同合并系数 cur-coef tempCoef; if (cur-coef 0) { // 删掉这个节点注意更新prev-next } } else { // 插入新节点到prev和cur之间 } } }合并后系数可能变成0此时必须把该节点从链表中删除。删除的时候要小心prev还是指向当前节点的前一个节点直接prev-next cur-next然后free(cur)就行。但要继续保留一个指针记录cur原本的next避免free之后再访问。这里有一个细节我特别喜欢提如果你用的是带头节点的链表prev和cur的初始关系永远是“prev在前cur在后”不管插入位置在链表的中间还是头部代码都不用分支处理。这就是带头节点带来的底气。3.3 完整乘法函数代码下面是我当时提交的核心乘法函数代码结构比较直白适合用来理解流程Polynomial multiplyPolynomial(Polynomial A, Polynomial B) { Polynomial result createPoly(); // 带头节点的空结果链表 PolyNode *pA A-next; PolyNode *pB; for (; pA ! NULL; pA pA-next) { for (pB B-next; pB ! NULL; pB pB-next) { int tempCoef pA-coef * pB-coef; int tempExpo pA-expo pB-expo; if (tempCoef 0) continue; // 系数为0直接跳过 PolyNode *prev result; PolyNode *cur result-next; while (cur ! NULL cur-expo tempExpo) { prev cur; cur cur-next; } if (cur ! NULL cur-expo tempExpo) { cur-coef tempCoef; if (cur-coef 0) { // 合并后归零删除节点 prev-next cur-next; free(cur); } } else { // 指数不同插入新节点 PolyNode *node (PolyNode *)malloc(sizeof(PolyNode)); node-coef tempCoef; node-expo tempExpo; node-next cur; prev-next node; } } } return result; }这段代码的删除分支有一个细节容易出错删除cur之后prev是不动的内层循环继续生成下一个中间项时会重新从result头部开始找位置。也就是说删除不会破坏prev和cur的配对关系因为这个配对本来就是在每次生成中间项时重新建立的。还要注意一点tempCoef等于0时要直接continue虽然理论上两个非零系数相乘不会是0但如果题目输入本身就带系数0这个判断能防止无意义的节点进入结果链表。4. 稳定性细节排序规则、零系数过滤与输出格式陷阱4.1 指数排序升序还是降序题目要求“结果多项式按指数降序排列”也就是指数从大到小排列x^3的项排在x^2的项前面。我在插入时用的比较条件是cur-expo tempExpo意思是“只要当前节点的指数比新项大就继续往后走”。走到cur-expo tempExpo或者cur为空时插入位置就确定了。这个比较条件非常关键写反了结果就变成升序判题直接不给过。我建议在写循环之前先在纸上画一个简单链表比如结果里已经有一项x^5和一项x^2现在要插入x^3手动模拟一遍指针走向再对照代码检查条件符号。如果题目要求升序排列把比较符号反过来就行但插入逻辑和合并逻辑的结构完全不变。4.2 合并后系数归零必须删除节点这个坑我印象太深了。假设A x 1B x - 1乘出来是x^2 - x x - 1中间两项的系数是-1和1合并之后变成0。如果不删除这个节点最后结果会输出“系数0指数1”这一项直接不符合“只输出非零项”的要求。我在代码里用cur-coef tempCoef之后立刻判断if (cur-coef 0) { prev-next cur-next; free(cur); }这里还有一个很多人会忽略的点删除节点之后如果后续又生成一个同样指数的项理论上应该重新插入一个新节点而不是把已经删除的节点复活。我的代码因为每次插入都从头寻找所以不存在“引用已释放节点”的问题。但如果你为了优化做了“记住上次插入位置”之类的操作就要格外小心指针指向了被free掉的节点。4.3 输出格式的细节清单输出格式是这门课作业扣分的重灾区。我总结了一份检查清单每次写输出函数都对着过一遍结果链表为空时要输出“0 0”还是什么都不输出不同题目要求不同我看的题目要求输出“0 0”这个必须看仔细。第一项前不输出加号后面项如果是正系数要输出加号还是空格我用的要求是每行输出“系数 指数”不涉及加号问题但很多题目要求输出数学表达式那就复杂多了。系数为1和-1时要不要显示数字有的题目要求“x”而不是“1x”有的题目要求“1x”完全看题目约定。指数为1时要不要显示x^1同理看要求。指数为0时的项实际上是一个常数输出时指数就是0不要省略这一行。分享一个我的习惯输出函数单独写不要和乘法逻辑混在一起。这样调整格式只需要改一个函数不会动核心算法。我那版输出函数大概30行单独维护非常方便。5. 测试用例设计与边界条件排查5.1 从常规到刁钻的用例清单我做完代码之后没有直接交而是设计了八组测试用例一组一组跑。这组用例清单帮我挡掉了至少三个隐藏Bug。编号输入A输入B预期结果测试目的13x^2 2x 1x 13x^3 5x^2 3x 1基本乘法与合并25常数2x 110x 5单项乘以多项式303x 20 0零多项式4-x^2 2x - 1x - 1-x^3 3x^2 - 3x 1负系数运算5x^100 1x^200 x^50 2结果含x^300项稀疏大指数6x 1x - 1x^2 - 1合并后归零7x^2x^3x^5单项乘单项8x 1x^100 2x^101 2x x^100 2指数不连续第8组用例其实很有代表性。A只有两项B也只有两项但结果里有四项且指数跨度从1到101。这个用例能同时检验插入排序的完整性和合并逻辑是否误伤。5.2 一次真实的边界问题定位我印象最深的是第3组测试用例。输入第一个多项式为0时程序输出的结果是“0 0”还是“”完全取决于创建多项式时对零系数的处理。我当时在创建函数里把所有系数为0的项都过滤掉所以A链表是空的B链表非空乘法函数返回的空结果链表只有一个头节点输出函数遍历时发现没有有效节点按题目要求输出“0 0”。这里有个连带问题输出函数怎么判断“空链表”和“链表非空但全部被删光”这两种情况其实对带头节点的链表来说这两种情况在代码层面是等价的都是result-next NULL。所以输出函数只需要检查这一个条件不需要额外逻辑。但如果你在乘法过程中没有正确删除合并后归零的节点就会出现“节点还在但是系数为0”的状态输出函数把系数为0的项也输出出来那就错了。也就是说过滤零系数不能只靠输出函数必须在算法层就把零节点干掉。6. 常见Bug复盘与调试经验6.1 内存泄漏与指针悬挂这道题用malloc创建了很多临时节点如果删除节点时没有free或者插入节点时malloc失败没有处理程序在内存检测工具下会报一堆问题。我当时在合并后归零的分支里漏了free导致每次遇到同类项合并归零的场景都泄漏一小块内存。测试用例6跑一次泄漏一次多了之后程序行为非常诡异。后来我的检查套路是每写一个“删除节点”的分支就看一下有没有free每写一个“插入新节点”的分支就看一下有没有malloc。成对出现的东西缺一个就是问题。还有一个易错点是free之后还把指针赋给了别的变量后面通过那个变量访问节点属于典型的指针悬挂程序可能会在完全无关的地方崩溃。6.2 死循环排查插入逻辑的静态检查我最怕的Bug是程序跑起来不出结果看起来像死循环。有一次插入新节点时写了下面这种错误代码node-next prev-next; prev-next node;看起来没问题但如果我少写第一行只写了prev-next node那node-next就是一个随机值链表直接断掉遍历时可能访问非法内存也可能陷入循环。这种错误最好的排查方式不是gdb一步步跟而是在纸上把链表画出来用节点指针的指向变化走一遍插入过程。我发现一个规律链表相关的死循环和指针错乱80%都能通过“手画三节点链表模拟一次插入”发现。因为人脑走逻辑比看代码更直观尤其是指针赋值这种顺序敏感的操作。6.3 调试工具与手推验证我当时用的调试方法比较朴素但非常有效写一个debugPrint函数把链表从头到尾全部打印出来格式是“(系数,指数) - (系数,指数) - …”。每次乘法中途遇到问题时就在几个关键位置调用这个函数查看中间状态。比如我先打印A链表再打印B链表然后调用乘法函数直接打印结果链表。如果结果和预期不一致我就把乘法循环里每次插入的临时项也打印出来逐步对照。这个方法成本极低但能精确定位到是哪一对节点相乘、插入位置选错了、还是合并分支走错了。还有一个笨办法我到现在都觉得好用用小规模数据手动算一遍结果然后让程序输出逐项对比。比如A 2x 1B 3x 4手算结果是6x^2 8x 3x 4 6x^2 11x 4。程序如果输出6x^2 11x 4说明基本流程对如果输出6x^2 8x 3x 4说明合并逻辑没生效。这类数据不需要任何工具口算就能验证。7. 从多项式乘法延伸出去的扩展思考做完这道题之后我意识到这个核心流程其实可以抽象成更通用的东西两个有序列表的元素两两组合生成新的元素并按某种规则聚合成有序结果。多项式相乘只是这个抽象模型的一个特例。如果把“指数相加”换成“时间戳相加”或者把“系数相乘”换成某种自定义运算同样的链表结构和插入逻辑可以复用在不同的任务里。比如有两个事件序列要生成所有事件组合并对同一时刻的效应求和使用的就是完全相同的框架。理解了这一点这道作业的价值就从“会写链表”提升到了“掌握了一种处理配对组合的通用方法”。另外这个题还可以往两个方向扩展。第一个方向是优化复杂度合并同类项的时候用桶排序思想或者把结果链表改成基于哈希的索引可以将O(nmresult_len)降到近似O(n*m)适合指数范围可控的大规模数据。第二个方向是扩展运算支持多项式加法、减法、求导、求定积分本质上都是对链表节点的遍历和修改代码量不会突然暴增。如果学有余力我建议把多项式乘法改写成一个支持“运算符重载”的版本或者干脆用面向对象的方式封装成多项式类。那样以后再处理其他“同类项合并”问题直接调用现成的类就行。这个过程不是浪费时间而是把一道课设题变成自己的工具箱。做了这个题之后我最大的体会是像多项式相乘这种基础题目恰恰是最能暴露代码习惯的地方。指针、内存、边界、格式每一项都逼着你认真对待。如果你能把这道题写清楚、测全面数据结构链表部分的基本功基本就过关了。我当时拿着那版代码又跑了大概二十分钟的随机数据确认没有内存问题之后才提交最终拿到了满意的分数。后来再做其他链表题时明显感觉顺手太多了。