数据结构——多项式的加法运算

多项式加法运算图示：

基本算法思路：

多项式的具体结构类型：

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