基于链表的两个一元多项式的基本运算 加减乘 求导

链表可以很好地表示多项式，每个节点存储一个系数和一个指数。

先定义一下多项式的结构体：

typedef struct PolyNode *PtrToPolyNode;
struct PolyNode {
    int coef;
    int expon;
    PtrToPolyNode next;
};
typedef PtrToPolyNode Polynomial;

其中，coef表示系数，expon表示指数，next表示下一个节点的指针。

加法运算：

Polynomial PolyAdd(Polynomial P1, Polynomial P2) {
    Polynomial front, rear, temp;
    front = (Polynomial)malloc(sizeof(struct PolyNode));
    rear = front;
    while (P1 && P2) {
        if (P1->expon > P2->expon) {
            Attach(P1->coef, P1->expon, &rear);
            P1 = P1->next;
        } else if (P1->expon < P2->expon) {
            Attach(P2->coef, P2->expon, &rear);
            P2 = P2->next;
        } else {
            int sum = P1->coef + P2->coef;
            if (sum) Attach(sum, P1->expon, &rear);
            P1 = P1->next;
            P2 = P2->next;
        }
    }
    for (; P1; P1 = P1->next) Attach(P1->coef, P1->expon, &rear);
    for (; P2; P2 = P2->next) Attach(P2->coef, P2->expon, &rear);
    rear->next = NULL;
    temp = front;
    front = front->next;
    free(temp);
    return front;
}

在此函数中，我们使用了Attach函数，它的作用是把一个新节点插入到链表中。具体实现如下：

void Attach(int c, int e, Polynomial *pRear) {
    Polynomial P;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->next = NULL;
    (*pRear)->next = P;
    *pRear = P;
}

减法运算：

减法运算与加法运算类似，只需把P2的系数变为相反数，然后再调用加法运算即可。

Polynomial PolySub(Polynomial P1, Polynomial P2) {
    Polynomial temp = P2;
    while (temp) {
        temp->coef = -temp->coef;
        temp = temp->next;
    }
    return PolyAdd(P1, P2);
}

乘法运算：

乘法运算比较复杂，需要用到多层循环。具体实现如下：

Polynomial PolyMul(Polynomial P1, Polynomial P2) {
    if (!P1 || !P2) return NULL;
    Polynomial P, Rear, t1, t2, t;
    int c, e;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    Rear = P;
    t1 = P1;
    t2 = P2;
    while (t2) {
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->next;
    }
    t1 = t1->next;
    while (t1) {
        t2 = P2, Rear = P;
        while (t2) {
            e = t1->expon + t2->expon;
            c = t1->coef * t2->coef;
            while (Rear->next && Rear->next->expon > e) Rear = Rear->next;
            if (Rear->next && Rear->next->expon == e) {
                if (Rear->next->coef + c)
                    Rear->next->coef += c;
                else {
                    t = Rear->next;
                    Rear->next = t->next;
                    free(t);
                }
            } else {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->next = Rear->next;
                Rear->next = t;
                Rear = Rear->next;
            }
            t2 = t2->next;
        }
        t1 = t1->next;
    }
    t2 = P;
    P = P->next;
    free(t2);
    return P;
}

求导：

求导比较简单，只需将每一项的系数乘以指数，指数减1即可。

Polynomial PolyDerivative(Polynomial P) {
    Polynomial t = P;
    while (t) {
        t->coef *= t->expon;
        t->expon--;
        t = t->next;
    }
    return P;
}