用链表编写一个程序实现两个一元多项式相加的运算

假设一元多项式的数据结构为：

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

则可以使用链表来存储一元多项式。具体实现如下：

#include <iostream>

using namespace std;

struct Node {
    int coef;
    int exp;
    Node* next;
};

Node* create_poly() {
    Node* head = new Node;
    head->next = nullptr;
    Node* tail = head;
    int coef, exp;
    char c;
    do {
        cout << "输入系数和指数（如 3x^2 输入 3 2）：";
        cin >> coef >> exp;
        Node* p = new Node;
        p->coef = coef;
        p->exp = exp;
        p->next = nullptr;
        tail->next = p;
        tail = p;
        cout << "继续输入吗？(y/n)";
        cin >> c;
    } while (c == 'y' || c == 'Y');
    return head;
}

void print_poly(Node* p) {
    while (p->next) {
        cout << p->next->coef << "x^" << p->next->exp;
        p = p->next;
        if (p->next) {
            cout << " + ";
        }
    }
    cout << endl;
}

Node* add_poly(Node* p1, Node* p2) {
    Node* head = new Node;
    head->next = nullptr;
    Node* tail = head;
    Node* p = p1->next;
    Node* q = p2->next;
    while (p && q) {
        if (p->exp == q->exp) {
            int coef = p->coef + q->coef;
            if (coef != 0) {
                Node* r = new Node;
                r->coef = coef;
                r->exp = p->exp;
                r->next = nullptr;
                tail->next = r;
                tail = r;
            }
            p = p->next;
            q = q->next;
        } else if (p->exp > q->exp) {
            Node* r = new Node;
            r->coef = p->coef;
            r->exp = p->exp;
            r->next = nullptr;
            tail->next = r;
            tail = r;
            p = p->next;
        } else {
            Node* r = new Node;
            r->coef = q->coef;
            r->exp = q->exp;
            r->next = nullptr;
            tail->next = r;
            tail = r;
            q = q->next;
        }
    }
    while (p) {
        Node* r = new Node;
        r->coef = p->coef;
        r->exp = p->exp;
        r->next = nullptr;
        tail->next = r;
        tail = r;
        p = p->next;
    }
    while (q) {
        Node* r = new Node;
        r->coef = q->coef;
        r->exp = q->exp;
        r->next = nullptr;
        tail->next = r;
        tail = r;
        q = q->next;
    }
    return head;
}

int main() {
    cout << "输入第一个多项式：";
    Node* p1 = create_poly();
    cout << "第一个多项式：";
    print_poly(p1);

    cout << "输入第二个多项式：";
    Node* p2 = create_poly();
    cout << "第二个多项式：";
    print_poly(p2);

    Node* p3 = add_poly(p1, p2);
    cout << "相加后的多项式：";
    print_poly(p3);

    return 0;
}

该程序先输入两个多项式，然后使用 `add_poly` 函数将其相加，最后输出结果。