链表实现多项式加减法(多项式篇)

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

源代码

BioniCosmos/polynomial

程序功能

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

分析与设计

本项目中有三个模块(头文件)。

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

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

多项式

类型

  • Term:项

    coef 表示项的系数,exp 表示项的指数,方便起见,他们的类型均为 int

  • NodeList:节点、链表

    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:多项式相加

    为防止破坏原多项式,所以先将其进行复制。将复制好的两个多项式 pCloneqClone 按照指数从大到小的顺序合并为一个多项式 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;?由于是指针传递,如果直接进行遍历会破坏原链表,所以需要复制一份。

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