链表实现多项式加减法（多项式篇）

链表是一种可以动态增删的简单数据结构，相比于长度固定的数组，链表更加灵活。利用这些特性，我们可以使用链表存储多项式，并实现多项式的加减法。

源代码

BioniCosmos/polynomial

程序功能

从用户的输入中获取多项式。
将多项式中的每一项按照指数从大到小的顺序排好。
获取一个值，代入多项式中，计算结果并输出。
计算两个多项式相加和相减后的结果（合并同类项）并输出。

分析与设计

本项目中有三个模块（头文件）。

gc.h：垃圾回收器
list.h：链表
polynomial.h：多项式

各个头文件中声明的函数在相同名字的 .c 文件中存在对应实现。

多项式

类型

Term：项

coef 表示项的系数，exp 表示项的指数，方便起见，他们的类型均为 int。
Node、List：节点、链表

list.h 中这两个类型的前向声明，这样做而不引用 list.h 可以解决头文件循环引用的问题（list.h 中引用了 polynomial.h）。

函数

getPolynomial：获取多项式

从 stdin 中获取多项式，第一行为多项式的项数 terms，下面 terms 行为多项式的值。把获取到的每一项的系数和指数存入新创建的 TERM 类型的节点中，如果系数不为 0，就将该节点添加到链表末尾。
cmpExp：指数比较

当 a 的指数大于 b 的指数时返回 true，否则返回 false。该函数被 list.h 的排序函数 sortList 使用。
printPolynomial：输出多项式

当链表存在（多项式不为 0）时输出多项式，否则直接输出 0。多项式的第一项前无正负号，其余项有正负号（加减号）。
printCoef：输出系数

系数为 1 时不输出。
printExp：输出指数

指数为 0 时不输出；指数为 1 时只输出 x。
calcPolynomial：计算多项式

将数代入多项式中算出具体值。

编程规范性提示：当存在缩窄的隐式类型转换应显式使用强制类型转换。如此处 pow 的返回值为 double 类型，但在进行乘法运算时会被隐式转换为 int 类型，这时最好通过 (int) 进行显式转换。

在期望表达式的地方填写（赋值）语句时最好在语句外再加一层括号。如此处 do-while 的条件内正常应填写表达式，但此处为了简化代码而在其中填写了语句（不推荐该写法），此时就应该在语句外再加一层括号，便于和正常的表达式进行区分。（尤其是为了区分 = 和 ==，人们经常会把 == 写成 =，很多编译器和 IDE 都会检查出这种错误并进行提示，但如果本意就是使用 =，加上括号后就会消除提示。）
addPolynomial：多项式相加

为防止破坏原多项式，所以先将其进行复制。将复制好的两个多项式 pClone 和 qClone 按照指数从大到小的顺序合并为一个多项式 mergedList，合并的前提是两个多项式本身有序。对多项式合并同类项，消除计算后产生的 0 项（如），最后返回多项式。
subPolynomial：多项式相减

减法与加法类似，只不过在合并多项式之前先将后一个多项式 qClone 的所有系数取反。
combineLikeTerms：合并同类项

以多项式中一项为基准，向后寻找和该项指数 n 相同的项，并把这些项加到基准项中，直到指数为 n 的项只剩一个，然后以下一项为基准项，重复上述动作。
```
while 基准项存在 && 下一项存在
    if 基准项.指数 == 下一项.指数
        基准项.系数 += 下一项.系数
        下一项 = 下一项.下一项
    else
        基准项 = 下一项
```
所谓「基准项」和「下一项」是动态变换的，起初代表第一项和第二项，但随着代码的执行，他们会向后移动。

为什么要在 while 中添加下一项存在的条件？因为下一项 = 下一项.下一项，不加入判断在循环时会超出链表范围。
removeZeroTerms：移除 0 项

这个函数不会改变多项式的值，但可以优化多项式的输出。由于需要改变链表类型变量本身，所以使用了指针传递。该算法的思路是先将多项式前面的 0 删去，再将其余的 0 删去。（如，先删 x 前面的 0，再删 x 后面的 0。）其中后一段算法和 combineLikeTerms 的思路相似，都存在一个基准项。两段删 0 的原因是如果不先把前面的 0 删干净就会遗留 0。
```
while 基准项存在
    if 基准项.系数 == 0
        if 下一项存在
            基准项 = 下一项
        else
            基准项 = NULL
            return
    else
        break

while 基准项存在 && 下一项存在
    if 下一项.系数 == 0
        下一项 = 下一项.下一项
    else
        基准项 = 下一项
```
为什么需要 Node *tmp = listPtr->head;？由于是指针传递，如果直接进行遍历会破坏原链表，所以需要复制一份。

更多内容请期待《链表实现多项式加减法（链表篇）》。