数据结构用链表实现多项式相加

对于两个多项式 $A(x)$ 和 $B(x)$，我们可以将它们表示为以下形式：

$$
A(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0
$$

$$
B(x) = b_m x^m + b_{m-1} x^{m-1} + \cdots + b_1 x + b_0
$$

其中 $n$ 和 $m$ 分别表示两个多项式的最高次幂，$a_i$ 和 $b_j$ 分别表示 $x^i$ 和 $x^j$ 的系数。

我们可以将两个多项式相加，得到一个新的多项式 $C(x)$：

$$
C(x) = A(x) + B(x) = c_k x^k + c_{k-1} x^{k-1} + \cdots + c_1 x + c_0
$$

其中 $k = \max(n, m)$，$c_i = a_i + b_i$。

为了实现多项式相加，我们可以用链表来存储多项式。链表的每个节点表示一个单项式，包含系数和次数两个属性。具体地，我们可以设计一个结构体来表示单项式：

struct Node {
    int coef;  // 系数
    int exp;   // 次数
    Node* next;  // 指向下一个节点的指针
};

然后，我们可以用一个链表来表示一个多项式，链表的每个节点存储一个单项式。链表的头指针指向第一个节点，尾指针指向最后一个节点。具体地，我们可以设计一个结构体来表示多项式：

struct Poly {
    Node* head;  // 指向第一个节点的指针
    Node* tail;  // 指向最后一个节点的指针
};

接下来，我们可以实现一个函数来创建一个多项式。这个函数会从标准输入中读取多项式的每个单项式，然后将其添加到链表中。具体地，我们可以设计一个函数如下：

Poly create_poly() {
    Poly poly;
    poly.head = poly.tail = nullptr;  // 初始化链表为空
    int coef, exp;
    while (cin >> coef >> exp) {
        Node* node = new Node{coef, exp, nullptr};
        if (poly.tail == nullptr) {
            poly.head = poly.tail = node;
        } else {
            poly.tail->next = node;
            poly.tail = node;
        }
    }
    return poly;
}

最后，我们可以实现一个函数来计算两个多项式的和。这个函数会遍历两个链表，将每个单项式相加，然后将其添加到结果链表中。具体地，我们可以设计一个函数如下：

Poly add_poly(const Poly& poly1, const Poly& poly2) {
    Poly res;
    res.head = res.tail = nullptr;  // 初始化链表为空
    Node *p1 = poly1.head, *p2 = poly2.head;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->exp > p2->exp) {
            Node* node = new Node{p1->coef, p1->exp, nullptr};
            if (res.tail == nullptr) {
                res.head = res.tail = node;
            } else {
                res.tail->next = node;
                res.tail = node;
            }
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            Node* node = new Node{p2->coef, p2->exp, nullptr};
            if (res.tail == nullptr) {
                res.head = res.tail = node;
            } else {
                res.tail->next = node;
                res.tail = node;
            }
            p2 = p2->next;
        } else {
            Node* node = new Node{p1->coef + p2->coef, p1->exp, nullptr};
            if (res.tail == nullptr) {
                res.head = res.tail = node;
            } else {
                res.tail->next = node;
                res.tail = node;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    while (p1 != nullptr) {
        Node* node = new Node{p1->coef, p1->exp, nullptr};
        if (res.tail == nullptr) {
            res.head = res.tail = node;
        } else {
            res.tail->next = node;
            res.tail = node;
        }
        p1 = p1->next;
    }
    while (p2 != nullptr) {
        Node* node = new Node{p2->coef, p2->exp, nullptr};
        if (res.tail == nullptr) {
            res.head = res.tail = node;
        } else {
            res.tail->next = node;
            res.tail = node;
        }
        p2 = p2->next;
    }
    return res;
}

这样，我们就实现了用链表来表示多项式，并且计算两个多项式的和。