数据结构实现一元多项式加法运算

一元多项式可以用链表来实现，每个节点表示一个项，包含系数和指数两个成员变量。加法运算就是将两个链表按照指数从小到大的顺序依次合并，如果两个节点的指数相同，则将它们的系数相加，否则将指数小的节点插入到结果链表中。

以下是 C++ 实现代码：

#include <iostream>
using namespace std;

struct Node {
    int coef; // 系数
    int exp; // 指数
    Node* next;
    Node(int c = 0, int e = 0, Node* n = nullptr) : coef(c), exp(e), next(n) {}
};

void addPoly(Node* a, Node* b) {
    Node* head = new Node(); // 结果链表的头结点
    Node* tail = head; // 结果链表的尾结点
    while (a != nullptr && b != nullptr) {
        if (a->exp < b->exp) {
            tail->next = new Node(a->coef, a->exp);
            a = a->next;
        } else if (a->exp > b->exp) {
            tail->next = new Node(b->coef, b->exp);
            b = b->next;
        } else {
            int coefSum = a->coef + b->coef;
            if (coefSum != 0) {
                tail->next = new Node(coefSum, a->exp);
            }
            a = a->next;
            b = b->next;
        }
        tail = tail->next;
    }
    // 将剩余的结点插入到结果链表中
    while (a != nullptr) {
        tail->next = new Node(a->coef, a->exp);
        a = a->next;
        tail = tail->next;
    }
    while (b != nullptr) {
        tail->next = new Node(b->coef, b->exp);
        b = b->next;
        tail = tail->next;
    }
    // 输出结果链表
    Node* p = head->next;
    while (p != nullptr) {
        cout << p->coef << "x^" << p->exp << " + ";
        p = p->next;
    }
    cout << "0" << endl;
}

int main() {
    // 构造两个多项式：a = 3x^2 + 2x + 1，b = 4x^3 + 2x^2 + 5
    Node* a = new Node(3, 2, new Node(2, 1, new Node(1, 0)));
    Node* b = new Node(4, 3, new Node(2, 2, new Node(5, 0)));
    addPoly(a, b); // 输出结果：4x^3 + 5x^2 + 2x + 1
    return 0;
}