多項式加減法 (二)

在多項式加法 (一)中，我們介紹了多項式對應的單鏈表的幾個接口，現(xiàn)在我們來完成本次實驗剩余的其他幾個接口。

第五步 實現(xiàn)其他剩余接口

接下來我們來實現(xiàn)剩余的接口，包括 AddNode、 Add、 Substract 三個接口。

AddNode接口

AddNode接口主要為方便我們對已有的多項式進行新增項操作，其接口原型如下所示：

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

需要注意的是，在新增項后，必須確保單鏈表中存儲的多項式項的每個節(jié)點 保持指數(shù)升序存儲這一性質(zhì)不變，否則將會給我們后續(xù)多項式相加 Add 接口帶來不必要的麻煩。

實現(xiàn) AddNode 接口，需要完成如下操作：

  • 參數(shù) poly 指向已有多項式實例；
  • 假設 poly 指向多項式實例中各節(jié)點按照指數(shù)升序性質(zhì)進行存儲，因此只需要從單鏈表頭開始遍歷多項式每一項，找到新增項應插入的合理位置；

以下給出 AddNode 接口實現(xiàn)代碼：

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;
    }

    // 初始化新節(jié)點數(shù)據(jù)域
    node->coef = coef;
    node->exp = exp;
    node->next = NULL;

    // 開始從第一個節(jié)點遍歷
    cur = poly->next;
    pre = poly;

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

    if (cur != NULL) // 找到某個節(jié)點的exp域比待插入節(jié)點的exp值要大
    {
        node->next = cur;
        pre->next = node;
    }
    else // 待插入節(jié)點的exp為當前一元多項式中節(jié)點exp最大值，則直接插入尾部
    {
        pre->next = node;
    }

    return true;
}

我們來解釋一下AddNode接口所做的操作：

  1. 首先判斷poly指向的一元多項式實例是否為空，不為空才繼續(xù)執(zhí)行下面步驟操作，否則直接返回；
  2. 嘗試分配新節(jié)點用于存儲新的項 (coef, exp)，分配節(jié)點成功則繼續(xù)執(zhí)行下面步驟，否則直接返回；
  3. 依次遍歷poly指向的一元多項式各項，因為該多項式已按照各項指數(shù)從小到大排序，因此從頭開始遍歷，便可找到新增項所需存放的位置；這里我們使用兩個指針表示遍歷的節(jié)點位置，cur 指向當前遍歷的節(jié)點；pre 指向當前遍歷節(jié)點的前驅(qū)；
  4. 遍歷結(jié)束的條件為cur == NULL 或 cur->exp > exp；表示兩種情況:
    a. cur == NULL，新增的節(jié)點 node 應放在當前多項式的尾部，因為其指數(shù)比所有節(jié)點的指數(shù)均大；
    b. cur->exp > exp，新增的節(jié)點node 應放在當前節(jié)點cur 之前，才能滿足多項式按照各項指數(shù)從小到大排序這一性質(zhì)不變；
  5. 按照遍歷結(jié)束條件不同，新增節(jié)點插入位置也不同，這就是代碼中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)；這兩個新項的指數(shù)分別是2和6。編譯運行本項目，執(zhí)行結(jié)果如下所示：

[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
請輸入節(jié)點個數(shù):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

由上述運行結(jié)果可知，(99, 2) 以及(99, 6)兩個新項被加入到多項式正確的位置中，但能否說明我們新編寫的接口操作邏輯正確？我們試著使用另外一個測試用例進行測試，執(zhí)行結(jié)果如下所示：

[localhost:lab01 xgqin]$ ./a.out
請輸入節(jié)點個數(shù):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

由上述運行結(jié)果可知，將(99, 2)項插入多項式的操作正確，但將 (99, 6) 插入多項式中的操作錯誤。

因為多項式中存在兩個項 (99, 6)、(6, 6)其指數(shù)均相同 (換言之，如果多項式中已存在指數(shù)相同的項，我們編寫的AddNode接口并未考慮到這類情況該如何處理)。

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

因此還需對該分支進行細化判斷：

  1. 如果 cur->exp > exp，則新增的節(jié)點node 應放在當前節(jié)點cur 之前；
  2. 如果 cur->exp == exp，則不需新增節(jié)點，只需更新cur指向節(jié)點的coef域即可。當然還需判斷cur->coef + coef 后新的系數(shù)域是否為0，如果為0則因刪除cur指向的節(jié)點。

改進AddNode接口

讓我們嘗試來改進AddNode接口，根據(jù)上述分析，只需要對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;
    }

    // 初始化新節(jié)點數(shù)據(jù)域
    node->coef = coef;
    node->exp = exp;
    node->next = NULL;

    // 開始從第一個節(jié)點遍歷
    cur = poly->next;
    pre = poly;

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

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

            if ((cur->coef + coef) < delta)
            {
                pre->next = cur->next; // 如果新節(jié)點與多項式中已存在相同exp的節(jié)點
                        // 的coef域相加結(jié)果為0，則需要刪除掉舊節(jié)點
                free(cur);
                cur = NULL;
            }
            else
            {
                cur->coef += coef;
            }
        }
        else
        {
            node->next = cur;
            pre->next = node;
        }
    }
    else // 待插入節(jié)點的exp為當前一元多項式中節(jié)點exp最大值，則直接插入尾部
    {
        pre->next = node;
    }

    return true;
}

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

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

            if ((cur->coef + coef) < delta)
            {
                pre->next = cur->next; // 如果新節(jié)點與多項式中已存在相同exp的節(jié)點
                        // 的coef域相加結(jié)果為0，則需要刪除掉舊節(jié)點
                free(cur);
                cur = NULL;
            }
            else
            {
                cur->coef += coef;
            }
        }

首先檢查了 cur 所指向節(jié)點的 exp 域是否與 新插入的節(jié)點 exp 域相同，如果相同則需要做 節(jié)點合并 或 節(jié)點刪除 操作。如何執(zhí)行兩個操作取決于 cur 指向節(jié)點 coef 域與 新插入節(jié)點 coef 域相加的結(jié)果。

修改完 AddNode接口后，對項目進行重新編譯，并運行使用之前最后一次運行的測試用例對項目再進行測試，結(jié)果如下：

[localhost:lab01 xgqin]$ ./a.out 
請輸入節(jié)點個數(shù):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

為確保新加代碼中對節(jié)點刪除操作的正確性，我們再引入一個新的測試用例對項目進行測試，結(jié)果如下：

[localhost:lab01 xgqin]$ ./a.out 
請輸入節(jié)點個數(shù):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) 節(jié)點時，再插入(99, 6) 節(jié)點則會引發(fā)由于 新增節(jié)點coef域與已有節(jié)點coef域相加結(jié)果為0的情況發(fā)生，此時應該能觸發(fā) 節(jié)點刪除 操作條件。

至此，我們完成了AddNode接口的編碼工作，接下來我們來完成Add接口。

Add接口

Add接口原型如下所示：

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

注：必須明確一點的是，對多項式 polya 和多項式 polyb 進行相加操作后，應該得到一個新的多項式表示兩者的相加結(jié)果，且polya 和 polyb 指向的多項式實例保持不變。

實現(xiàn)多項式相加的操作有很多不同的思路，以下是我們采用的思路：

  1. 首先復制 polya 指向的多項式實例；
  2. 遍歷 polyb 指向的多項式的所有節(jié)點，利用 AddNode 接口將 polyb 的每一個節(jié)點表示的項(coef, exp)，插入到 polya 多項式中；

如此一來，Add 接口的編寫將可封裝復用 AddNode接口。此外，由于 復制多項式 的操作也將頻繁使用。因此我們?yōu)樵摬僮鞫x一個名為 DuplicatePoly 的接口，該接口原型如下：

Poly DuplicatePoly(Poly polya);

下面先給出 DuplicatePoly 接口的實現(xiàn)，然后再給出 Add 接口的實現(xiàn)。

DuplicatePoly接口

在 Poly.cpp 中實現(xiàn)該接口，請別忘了在 Poly.h 頭文件中增加該接口的原型聲明。

實現(xiàn)復制多項式實例操作，我們首先調(diào)用 CreatePoly 創(chuàng)建一個新的多項式，只需要對傳入的多項式每個節(jié)點進行遍歷，并生成新節(jié)點即可。

注： 該操作亦可調(diào)用 AddNode 接口完成(先創(chuàng)建一個空的多項式，再向該多項式中依次添加 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 接口的實現(xiàn)：

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 接口首先調(diào)用 Duplicate 接口復制 polya 指向的多項式實例，然后在該新實例的 polyc 的基礎上，遍歷 polyb 多項式，并將 polyb 多項式中的每個節(jié)點(coef, exp) 通過 AddNode 接口插入多項式 polyc 中。

修改CreatePoly接口

在對 Add 接口進行測試前，我們首先需要修改 CreatePoly 接口。

原有 CreatePoly 接口除了創(chuàng)建多項式實例外，還提供了用戶輸入多項式節(jié)點的功能。

因為已經(jīng)可以通過 AddNode 方式添加新節(jié)點，因此，我們讓 CreatePoly 接口實現(xiàn)的功能更單一一些，僅僅用于創(chuàng)建空多項式實例，而構(gòu)造、修改多項式實例的操作可以由 AddNode 提供。

Poly CreatePoly() // 創(chuàng)建多項式數(shù)據(jù)結(jié)構(gòu)實例
{
    Poly poly = NULL;
    PNode head = NULL; 
    PNode cur = NULL; // 始終指向存儲多項式的單鏈表最后一個節(jié)點的指針
    int num; // 存儲所需輸入多項式項數(shù)
    float coef;
    int exp;

    head = (PNode) malloc(sizeof(Node));
    if (head != NULL)
    {
        // 不需要對頭結(jié)點的coef和exp數(shù)據(jù)域進行設置
        head->next = NULL; // 設置頭結(jié)點的next指針域為NULL
        poly = head;
    }

    /*
    cur = poly; // 初始化cur指針，cur當前指向頭結(jié)點

    printf("請輸入節(jié)點個數(shù):");
    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)  // 分配節(jié)點成功
        {
            cur = cur->next;  // 確保cur指向最后一個新節(jié)點
            cur->coef = coef;
            cur->exp = exp;
            cur->next = NULL;
        }
    }
    */
    return poly;    // 如果分配頭結(jié)點空間成功，
            // 則返回poly非空表示創(chuàng)建多項式實例操作成功，
            //  否則返回值為NULL，表示創(chuàng)建多項式實例操作失敗
}

我們只需簡單的將輸入節(jié)點、創(chuàng)建節(jié)點的代碼注釋掉即可。之所以是將這段代碼注釋掉，是因為仍然可能需要使用 CreatePoly 接口對后續(xù)其它新接口進行測試。

測試Add接口

現(xiàn)在我們可以對 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接口構(gòu)造了兩個多項式實例 polya 、 polyb；并調(diào)用 Add接口實現(xiàn) polya 和 polyb 兩個多項式相加；通過 PrintPoly 接口分別輸出 polya、 polyb、 polyc 三個多項式進行結(jié)果對比。

運行結(jié)果如下：

[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

至此，我們完成了本次實驗項目的大部分要求，請你思考一下如何實現(xiàn) Substract接口吧。

最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容