資料結構——多項式的加法運算

多項式加法運算圖示：

基本算法思路：

多項式的具體結構類型：

#include <iostream>
#define MAXSIZE 100        //定義最大元素個數 
#define ElemType int        //定義資料類型 
#define ERROR 0
#define TRUE 1 
#define OVERFLOW -1

using namespace std;

typedef struct PloyNode *PN;
struct  PloyNode{
    int coef;
    int expon;
    PN link;
};
           

多項式加法的代碼實作：

PN PloyAdd(PN P1, PN P2){
    PN front, rear, temp;        //定義雙指針作為标記 
    int sum;
    rear = new(PloyNode);
    front = rear;        //初始化指針位置 
    while(P1 && P2){        //當兩個多項式都有非零項可以處理時 
        switch(Compare(P1->expon, P2->expon)){
            case 1:
                Attach(P1->coef, P1->expon, &rear);        //添加元素 
                P1 = P1->link;        //指針後移 
                break;
            case -1:
                Attach(P1->coef, P1->expon, &rear);
                P2 = P2->link;
                break;
            case 0:
                sum = P1->coef + P2->coef;
                if(sum)
                    Attach(sum, P1->coef, &rear);
                P1 = P1->link;
                P2 = P2->link;
                break;
        }
    }
    while(P1)        //處理之前未處理完的值（僅剩P1還有非零項時）
        Attach(P1->coef, P1->expon, &rear);
    while(P2)
        Attach(P1->coef, P1->expon, &rear);
    rear->link = nullptr;        //尾指針 
    temp = front;
    front = front->link;        //頭指針 
    delete temp;
    return front;
}           

其中的一些小函數：

int Compare(int a, int b){        //做兩多項式的系數比較
    if(a > b)
        return 1;
    else if(a < b)
        return -1;
    else
        return 0;
}           

void Attach(ElemType CoefTemp, ElemType ExponTemp, PN *Prear){        //做多項式相加的函數 
    PN P;
    P = new PloyNode;
    P->coef = CoefTemp;
    P->expon = ExponTemp;
    P->link = nullptr;
    (*Prear)->link = P;
    *Prear = P;
}