多项式加减法 (二)

在多项式加法 (一)中，我们介绍了多项式对应的单链表的几个接口，现在我们来完成本次实验剩余的其他几个接口。

第五步 实现其他剩余接口

接下来我们来实现剩余的接口，包括 AddNode、 Add、 Substract 三个接口。

AddNode接口

AddNode接口主要为方便我们对已有的多项式进行新增项操作，其接口原型如下所示：

bool AddNode(Poly poly, float coef, int exp); 

需要注意的是，在新增项后，必须确保单链表中存储的多项式项的每个节点 保持指数升序存储这一性质不变，否则将会给我们后续多项式相加 Add 接口带来不必要的麻烦。

实现 AddNode 接口，需要完成如下操作：

• 参数 poly 指向已有多项式实例；
• 假设 poly 指向多项式实例中各节点按照指数升序性质进行存储，因此只需要从单链表头开始遍历多项式每一项，找到新增项应插入的合理位置；

以下给出 AddNode 接口实现代码：

bool AddNode(Poly poly, float coef, int exp) // 为poly多项式添加新项(coef, exp)
{
    PNode node;
    PNode cur, pre;

    if (poly == NULL)
    {
        return false;
    }

    node = (PNode) malloc(sizeof(Node));
    if (node == NULL)
    {
        return false;
    }

    // 初始化新节点数据域
    node->coef = coef;
    node->exp = exp;
    node->next = NULL;

    // 开始从第一个节点遍历
    cur = poly->next;
    pre = poly;

    while (cur != NULL && cur->exp < exp)
    {
        cur = cur->next;
        pre = pre->next;
    }

    if (cur != NULL) // 找到某个节点的exp域比待插入节点的exp值要大
    {
        node->next = cur;
        pre->next = node;
    }
    else // 待插入节点的exp为当前一元多项式中节点exp最大值，则直接插入尾部
    {
        pre->next = node;
    }

    return true;
}

我们来解释一下AddNode接口所做的操作：

1. 首先判断poly指向的一元多项式实例是否为空，不为空才继续执行下面步骤操作，否则直接返回；
2. 尝试分配新节点用于存储新的项 (coef, exp)，分配节点成功则继续执行下面步骤，否则直接返回；
3. 依次遍历poly指向的一元多项式各项，因为该多项式已按照各项指数从小到大排序，因此从头开始遍历，便可找到新增项所需存放的位置；这里我们使用两个指针表示遍历的节点位置，cur 指向当前遍历的节点；pre 指向当前遍历节点的前驱；
4. 遍历结束的条件为cur == NULL 或 cur->exp > exp；表示两种情况:
   a. cur == NULL，新增的节点 node 应放在当前多项式的尾部，因为其指数比所有节点的指数均大；
   b. cur->exp > exp，新增的节点node 应放在当前节点cur 之前，才能满足多项式按照各项指数从小到大排序这一性质不变；
5. 按照遍历结束条件不同，新增节点插入位置也不同，这就是代码中if (cur != NULL)分支语句操作的语义；

测试AddNode接口

完成 AddNode 接口后，我们可以利用上一篇文章的思路，尽快对新增的 AddNode 接口进行测试。修改 main.cpp 文件如下：

#include "Poly.h"
#include <stdio.h>

int main ()
{
    Poly polya = NULL;

    polya = CreatePoly();
    PrintPoly(polya);
    AddNode(polya, 5, 2);
    PrintPoly(polya);
    AddNode(polya, 5, 6);
    PrintPoly(polya);
    DestroyPoly(polya);

    return 0;
}

在通过 CreatePoly 接口新建一多项式后，我们尝试向该多项式添加新项(99, 2) 以及(99, 6)；这两个新项的指数分别是2和6。编译运行本项目，执行结果如下所示：

[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h   a.out    main.cpp
[localhost:lab01 xgqin]$ g++ main.cpp Poly.cpp 
[localhost:lab01 xgqin]$ ./a.out
请输入节点个数:5
1 -1
2 0
3 1
4 3
5 4
+1.0X^-1+2.0+3.0X^1+4.0X^3+5.0X^4
+1.0X^-1+2.0+3.0X^1+99.0X^2+4.0X^3+5.0X^4
+1.0X^-1+2.0+3.0X^1+99.0X^2+4.0X^3+5.0X^4+99.0X^6

由上述运行结果可知，(99, 2) 以及(99, 6)两个新项被加入到多项式正确的位置中，但能否说明我们新编写的接口操作逻辑正确？我们试着使用另外一个测试用例进行测试，执行结果如下所示：

[localhost:lab01 xgqin]$ ./a.out
请输入节点个数:5
3 3
4 4
5 5
6 6
7 7
+3.0X^3+4.0X^4+5.0X^5+6.0X^6+7.0X^7
+99.0X^2+3.0X^3+4.0X^4+5.0X^5+6.0X^6+7.0X^7
+99.0X^2+3.0X^3+4.0X^4+5.0X^5+99.0X^6+6.0X^6+7.0X^7

由上述运行结果可知，将(99, 2)项插入多项式的操作正确，但将 (99, 6) 插入多项式中的操作错误。

因为多项式中存在两个项 (99, 6)、(6, 6)其指数均相同 (换言之，如果多项式中已存在指数相同的项，我们编写的AddNode接口并未考虑到这类情况该如何处理)。

在 AddNode 接口的 if (cur != NULL) 分支中，所表示的情况应为 cur->exp >= exp 而不是 cur->exp > exp !!!

因此还需对该分支进行细化判断：

1. 如果 cur->exp > exp，则新增的节点node 应放在当前节点cur 之前；
2. 如果 cur->exp == exp，则不需新增节点，只需更新cur指向节点的coef域即可。当然还需判断cur->coef + coef 后新的系数域是否为0，如果为0则因删除cur指向的节点。

改进AddNode接口

让我们尝试来改进AddNode接口，根据上述分析，只需要对if (cur != NULL) 分支语句进行改进即可：

bool AddNode(Poly poly, float coef, int exp) // 为poly多项式添加新项(coef, exp)
{
    PNode node;
    PNode cur, pre;

    if (poly == NULL)
    {
        return false;
    }

    node = (PNode) malloc(sizeof(Node));
    if (node == NULL)
    {
        return false;
    }

    // 初始化新节点数据域
    node->coef = coef;
    node->exp = exp;
    node->next = NULL;

    // 开始从第一个节点遍历
    cur = poly->next;
    pre = poly;

    while (cur != NULL && cur->exp < exp)
    {
        cur = cur->next;
        pre = pre->next;
    }

    if (cur != NULL) // 找到某个节点的exp域比待插入节点的exp值要大
    {
        if (cur->exp == exp)
        {
            free(node); // 由于已存在相同exp的节点，因此释放掉之前已分配的新节点
            node = NULL;

            if ((cur->coef + coef) < delta)
            {
                pre->next = cur->next; // 如果新节点与多项式中已存在相同exp的节点
                        // 的coef域相加结果为0，则需要删除掉旧节点
                free(cur);
                cur = NULL;
            }
            else
            {
                cur->coef += coef;
            }
        }
        else
        {
            node->next = cur;
            pre->next = node;
        }
    }
    else // 待插入节点的exp为当前一元多项式中节点exp最大值，则直接插入尾部
    {
        pre->next = node;
    }

    return true;
}

在if (cur->exp != NULL)分支语句中，我们增加了如下代码段：

    if (cur != NULL) // 找到某个节点的exp域比待插入节点的exp值要大
    {
        if (cur->exp == exp)
        {
            free(node); // 由于已存在相同exp的节点，因此释放掉之前已分配的新节点
            node = NULL;

            if ((cur->coef + coef) < delta)
            {
                pre->next = cur->next; // 如果新节点与多项式中已存在相同exp的节点
                        // 的coef域相加结果为0，则需要删除掉旧节点
                free(cur);
                cur = NULL;
            }
            else
            {
                cur->coef += coef;
            }
        }

首先检查了 cur 所指向节点的 exp 域是否与 新插入的节点 exp 域相同，如果相同则需要做 节点合并 或 节点删除 操作。如何执行两个操作取决于 cur 指向节点 coef 域与 新插入节点 coef 域相加的结果。

修改完 AddNode接口后，对项目进行重新编译，并运行使用之前最后一次运行的测试用例对项目再进行测试，结果如下：

[localhost:lab01 xgqin]$ ./a.out 
请输入节点个数:5  
3 3
4 4
5 5
6 6
7 7
+3.0X^3+4.0X^4+5.0X^5+6.0X^6+7.0X^7
+99.0X^2+3.0X^3+4.0X^4+5.0X^5+6.0X^6+7.0X^7
+99.0X^2+3.0X^3+4.0X^4+5.0X^5+105.0X^6+7.0X^7

为确保新加代码中对节点删除操作的正确性，我们再引入一个新的测试用例对项目进行测试，结果如下：

[localhost:lab01 xgqin]$ ./a.out 
请输入节点个数:5
3 3
4 4
5 5
-99 6
7 7
+3.0X^3+4.0X^4+5.0X^5-99.0X^6+7.0X^7
+99.0X^2+3.0X^3+4.0X^4+5.0X^5-99.0X^6+7.0X^7
+99.0X^2+3.0X^3+4.0X^4+5.0X^5+7.0X^7

可以看到，当已有的多项式中已存在 (-99, 6) 节点时，再插入(99, 6) 节点则会引发由于 新增节点coef域与已有节点coef域相加结果为0的情况发生，此时应该能触发 节点删除 操作条件。

至此，我们完成了AddNode接口的编码工作，接下来我们来完成Add接口。

Add接口

Add接口原型如下所示：

Poly Add(Poly polya, Poly polyb); // 多项式相加

注：必须明确一点的是，对多项式 polya 和多项式 polyb 进行相加操作后，应该得到一个新的多项式表示两者的相加结果，且polya 和 polyb 指向的多项式实例保持不变。

实现多项式相加的操作有很多不同的思路，以下是我们采用的思路：

1. 首先复制 polya 指向的多项式实例；
2. 遍历 polyb 指向的多项式的所有节点，利用 AddNode 接口将 polyb 的每一个节点表示的项(coef, exp)，插入到 polya 多项式中；

如此一来，Add 接口的编写将可封装复用 AddNode接口。此外，由于 复制多项式 的操作也将频繁使用。因此我们为该操作定义一个名为 DuplicatePoly 的接口，该接口原型如下：

Poly DuplicatePoly(Poly polya);

下面先给出 DuplicatePoly 接口的实现，然后再给出 Add 接口的实现。

DuplicatePoly接口

在 Poly.cpp 中实现该接口，请别忘了在 Poly.h 头文件中增加该接口的原型声明。

实现复制多项式实例操作，我们首先调用 CreatePoly 创建一个新的多项式，只需要对传入的多项式每个节点进行遍历，并生成新节点即可。

注： 该操作亦可调用 AddNode 接口完成(先创建一个空的多项式，再向该多项式中依次添加 polya 指向的多项式每个项(coef, exp)即可。

Poly Duplicate(Poly polya) // 复制一个多项式实例
{
    Poly polyb = CreatePoly();
    PNode cur;
    PNode pre;

    cur = polya->next;
    pre = polyb;

    while (cur != NULL)
    {
        pre->next = (PNode) malloc(sizeof(Node));
        if (pre->next != NULL)
        {
            pre = pre->next;
            pre->coef = cur->coef;
            pre->exp = cur->exp;
            cur = cur->next;
        }
    }

    pre->next = NULL;

    return polyb;
}

完成 Duplicate 接口后，接下来给出 Add 接口的实现：

Poly Add(Poly polya, Poly polyb) // 多项式相加
{
    Poly polyc;
    PNode cur;

    polyc = Duplicate(polya);

    if (polyc == NULL)
    {
        return polyc;
    }
    
    cur = polyb->next;

    while (cur != NULL)
    {
        AddNode(polyc, cur->coef, cur->exp);
        cur = cur->next;
    }

    return polyc;
}

可以看到，Add 接口首先调用 Duplicate 接口复制 polya 指向的多项式实例，然后在该新实例的 polyc 的基础上，遍历 polyb 多项式，并将 polyb 多项式中的每个节点(coef, exp) 通过 AddNode 接口插入多项式 polyc 中。

修改CreatePoly接口

在对 Add 接口进行测试前，我们首先需要修改 CreatePoly 接口。

原有 CreatePoly 接口除了创建多项式实例外，还提供了用户输入多项式节点的功能。

因为已经可以通过 AddNode 方式添加新节点，因此，我们让 CreatePoly 接口实现的功能更单一一些，仅仅用于创建空多项式实例，而构造、修改多项式实例的操作可以由 AddNode 提供。

Poly CreatePoly() // 创建多项式数据结构实例
{
    Poly poly = NULL;
    PNode head = NULL; 
    PNode cur = NULL; // 始终指向存储多项式的单链表最后一个节点的指针
    int num; // 存储所需输入多项式项数
    float coef;
    int exp;

    head = (PNode) malloc(sizeof(Node));
    if (head != NULL)
    {
        // 不需要对头结点的coef和exp数据域进行设置
        head->next = NULL; // 设置头结点的next指针域为NULL
        poly = head;
    }

    /*
    cur = poly; // 初始化cur指针，cur当前指向头结点

    printf("请输入节点个数:");
    scanf("%d", &num);

    for (int i = 0; i < num; i++)
    {
        scanf("%f%d", &coef, &exp);
        cur->next = (PNode) malloc(sizeof(Node));
        if (cur->next != NULL)  // 分配节点成功
        {
            cur = cur->next;  // 确保cur指向最后一个新节点
            cur->coef = coef;
            cur->exp = exp;
            cur->next = NULL;
        }
    }
    */
    return poly;    // 如果分配头结点空间成功，
            // 则返回poly非空表示创建多项式实例操作成功，
            //  否则返回值为NULL，表示创建多项式实例操作失败
}

我们只需简单的将输入节点、创建节点的代码注释掉即可。之所以是将这段代码注释掉，是因为仍然可能需要使用 CreatePoly 接口对后续其它新接口进行测试。

测试Add接口

现在我们可以对 Add 接口进行测试，在对 Add 接口进行测试时，实际上也会对 Duplicate 接口进行测试。让我们将 main.cpp 文件的代码修改如下：

#include "Poly.h"
#include <stdio.h>

int main ()
{
    Poly polya, polyb, polyc;

    polya = CreatePoly();
    polyb = CreatePoly();

    AddNode(polya, 1, 1);
    AddNode(polya, 2, 2);
    AddNode(polya, 3, 3);
    AddNode(polya, 4, 4);
    AddNode(polya, 5, 5);

    PrintPoly(polya);

    AddNode(polya, 6, 6);
    AddNode(polyb, 7, 7);
    AddNode(polyb, 8, 8);
    AddNode(polyb, 9, 9);
    AddNode(polyb, 10, 10);

    PrintPoly(polyb);

    polyc = Add(polya, polyb);
    PrintPoly(polyc);

    DestroyPoly(polya);
    DestroyPoly(polyb);
    DestroyPoly(polyc);
    return 0;
}

在 main.cpp 文件中，我们通过 AddNode接口构造了两个多项式实例 polya 、 polyb；并调用 Add接口实现 polya 和 polyb 两个多项式相加；通过 PrintPoly 接口分别输出 polya、 polyb、 polyc 三个多项式进行结果对比。

运行结果如下：

[localhost:lab01 xgqin]$ g++ main.cpp Poly.cpp 
[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h   a.out    main.cpp
[localhost:lab01 xgqin]$ ./a.out 
+1.0X^1+2.0X^2+3.0X^3+4.0X^4+5.0X^5
+7.0X^7+8.0X^8+9.0X^9+10.0X^10
+1.0X^1+2.0X^2+3.0X^3+4.0X^4+5.0X^5+6.0X^6+7.0X^7+8.0X^8+9.0X^9+10.0X^10

至此，我们完成了本次实验项目的大部分要求，请你思考一下如何实现 Substract接口吧。