单链表存储一元多项式，求两个多项式的加减乘法运算

一元多项式可以表示为：

$P(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0$

其中，$a_n, a_{n-1}, ..., a_1, a_0$ 为系数，$x$ 为未知数，$n$ 为次数。

我们可以用单链表来存储一元多项式，每个节点存储一个系数和次数。

接下来，分别介绍一下两个多项式的加减乘法运算。

## 多项式的加法

两个多项式相加，只需要将相同次数的系数相加即可。

具体步骤如下：

1. 分别遍历两个单链表，将相同次数的系数相加。
2. 如果某个链表已经遍历完，将另一个链表剩余的项添加到结果链表中。
3. 如果最高次数的系数为0，则删除该节点。

下面是 C++ 代码实现：

struct Node {
    int coef;  // 系数
    int exp;   // 次数
    Node* next;
};

Node* addPolynomial(Node* p1, Node* p2) {
    Node* result = new Node();
    Node* tail = result;
    while (p1 && p2) {
        if (p1->exp == p2->exp) {
            int sum = p1->coef + p2->coef;
            if (sum != 0) {
                Node* node = new Node();
                node->coef = sum;
                node->exp = p1->exp;
                tail->next = node;
                tail = node;
            }
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            Node* node = new Node();
            node->coef = p1->coef;
            node->exp = p1->exp;
            tail->next = node;
            tail = node;
            p1 = p1->next;
        } else {
            Node* node = new Node();
            node->coef = p2->coef;
            node->exp = p2->exp;
            tail->next = node;
            tail = node;
            p2 = p2->next;
        }
    }
    while (p1) {
        Node* node = new Node();
        node->coef = p1->coef;
        node->exp = p1->exp;
        tail->next = node;
        tail = node;
        p1 = p1->next;
    }
    while (p2) {
        Node* node = new Node();
        node->coef = p2->coef;
        node->exp = p2->exp;
        tail->next = node;
        tail = node;
        p2 = p2->next;
    }
    Node* temp = result;
    result = result->next;
    delete temp;
    return result;
}

## 多项式的减法

两个多项式相减，只需要将相同次数的系数相减即可。

具体步骤如下：

1. 分别遍历两个单链表，将相同次数的系数相减。
2. 如果某个链表已经遍历完，将另一个链表剩余的项添加到结果链表中。
3. 如果最高次数的系数为0，则删除该节点。

下面是 C++ 代码实现：

Node* subPolynomial(Node* p1, Node* p2) {
    Node* result = new Node();
    Node* tail = result;
    while (p1 && p2) {
        if (p1->exp == p2->exp) {
            int diff = p1->coef - p2->coef;
            if (diff != 0) {
                Node* node = new Node();
                node->coef = diff;
                node->exp = p1->exp;
                tail->next = node;
                tail = node;
            }
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            Node* node = new Node();
            node->coef = p1->coef;
            node->exp = p1->exp;
            tail->next = node;
            tail = node;
            p1 = p1->next;
        } else {
            Node* node = new Node();
            node->coef = -p2->coef;
            node->exp = p2->exp;
            tail->next = node;
            tail = node;
            p2 = p2->next;
        }
    }
    while (p1) {
        Node* node = new Node();
        node->coef = p1->coef;
        node->exp = p1->exp;
        tail->next = node;
        tail = node;
        p1 = p1->next;
    }
    while (p2) {
        Node* node = new Node();
        node->coef = -p2->coef;
        node->exp = p2->exp;
        tail->next = node;
        tail = node;
        p2 = p2->next;
    }
    Node* temp = result;
    result = result->next;
    delete temp;
    return result;
}

## 多项式的乘法

两个多项式相乘，需要将每一项都相乘，最后将所有结果相加。

具体步骤如下：

1. 遍历第一个链表，取出每一项。
2. 遍历第二个链表，取出每一项。
3. 将两个节点的系数和次数相乘，得到新的节点。
4. 将新的节点插入结果链表中。
5. 重复以上步骤，直到第一个链表遍历完。

下面是 C++ 代码实现：

Node* mulPolynomial(Node* p1, Node* p2) {
    if (!p1 || !p2) {
        return nullptr;
    }
    Node* result = new Node();
    while (p1) {
        Node* p = p2;
        Node* tail = result;
        while (p) {
            int coef = p1->coef * p->coef;
            int exp = p1->exp + p->exp;
            Node* node = new Node();
            node->coef = coef;
            node->exp = exp;
            while (tail->next && tail->next->exp > exp) {
                tail = tail->next;
            }
            if (tail->next && tail->next->exp == exp) {
                tail->next->coef += coef;
            } else {
                node->next = tail->next;
                tail->next = node;
            }
            p = p->next;
        }
        p1 = p1->next;
    }
    Node* temp = result;
    result = result->next;
    delete temp;
    return result;
}

以上就是单链表存储一元多项式，以及两个多项式的加减乘法运算的实现。