数据结构书上的多项式运算的代码

以下是基于链表实现的多项式运算代码：

#include <iostream>

using namespace std;

// 多项式结构体
struct PolyNode {
    int coef;  // 系数
    int expon; // 指数
    PolyNode* next; // 指向下一个节点的指针
};

// 多项式加法
PolyNode* PolyAdd(PolyNode* poly1, PolyNode* poly2) {
    PolyNode* p1 = poly1;
    PolyNode* p2 = poly2;
    PolyNode* result = new PolyNode; // 创建一个新的多项式作为结果
    PolyNode* tail = result; // 用于尾插法
    while (p1 && p2) {
        if (p1->expon > p2->expon) {
            tail->next = new PolyNode{ p1->coef, p1->expon, nullptr };
            p1 = p1->next;
        }
        else if (p1->expon < p2->expon) {
            tail->next = new PolyNode{ p2->coef, p2->expon, nullptr };
            p2 = p2->next;
        }
        else {
            int sum = p1->coef + p2->coef;
            if (sum != 0) {
                tail->next = new PolyNode{ sum, p1->expon, nullptr };
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        tail = tail->next;
    }
    while (p1) {
        tail->next = new PolyNode{ p1->coef, p1->expon, nullptr };
        p1 = p1->next;
        tail = tail->next;
    }
    while (p2) {
        tail->next = new PolyNode{ p2->coef, p2->expon, nullptr };
        p2 = p2->next;
        tail = tail->next;
    }
    PolyNode* temp = result;
    result = result->next;
    delete temp; // 删除多余的头节点
    return result;
}

// 多项式乘法
PolyNode* PolyMul(PolyNode* poly1, PolyNode* poly2) {
    PolyNode* p1 = poly1;
    PolyNode* p2 = poly2;
    PolyNode* result = new PolyNode{ 0, 0, nullptr }; // 创建一个新的多项式作为结果，初始值为 0
    while (p1) {
        PolyNode* tail = result;
        p2 = poly2;
        while (p2) {
            int coef = p1->coef * p2->coef;
            int expon = p1->expon + p2->expon;
            while (tail->next && tail->next->expon > expon) {
                tail = tail->next;
            }
            if (tail->next && tail->next->expon == expon) {
                tail->next->coef += coef;
                if (tail->next->coef == 0) {
                    PolyNode* temp = tail->next;
                    tail->next = temp->next;
                    delete temp;
                }
            }
            else {
                tail->next = new PolyNode{ coef, expon, tail->next };
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    PolyNode* temp = result;
    result = result->next;
    delete temp; // 删除多余的头节点
    return result;
}

// 输出多项式
void PolyPrint(PolyNode* poly) {
    if (!poly) {
        cout << "0" << endl;
        return;
    }
    while (poly) {
        if (poly->expon == 0) {
            cout << poly->coef << endl;
        }
        else if (poly->expon == 1) {
            cout << poly->coef << "x + ";
        }
        else {
            cout << poly->coef << "x^" << poly->expon << " + ";
        }
        poly = poly->next;
    }
}

// 主函数
int main() {
    // 创建多项式 1
    PolyNode* poly1 = new PolyNode{ 5, 0, nullptr };
    poly1->next = new PolyNode{ 3, 2, nullptr };
    poly1->next->next = new PolyNode{ 1, 3, nullptr };
    cout << "多项式 1: ";
    PolyPrint(poly1);

    // 创建多项式 2
    PolyNode* poly2 = new PolyNode{ 5, 1, nullptr };
    poly2->next = new PolyNode{ 2, 2, nullptr };
    poly2->next->next = new PolyNode{ 1, 4, nullptr };
    cout << "多项式 2: ";
    PolyPrint(poly2);

    // 多项式加法
    PolyNode* polyAdd = PolyAdd(poly1, poly2);
    cout << "多项式加法: ";
    PolyPrint(polyAdd);

    // 多项式乘法
    PolyNode* polyMul = PolyMul(poly1, poly2);
    cout << "多项式乘法: ";
    PolyPrint(polyMul);

    return 0;
}

上述代码中，`PolyNode` 结构体表示一个多项式的节点，包含三个成员变量：系数 `coef`、指数 `expon` 和指向下一个节点的指针 `next`。

`PolyAdd` 函数实现两个多项式的加法，采用尾插法构建结果多项式。当指数相同时，系数相加，如果结果系数为 0，则不插入该项。

`PolyMul` 函数实现两个多项式的乘法，先遍历多项式 1 的每一项，然后遍历多项式 2 的每一项，将两项的系数和指数相乘，得到新的一项，并将其插入到结果多项式中。如果结果多项式中已有该项，则将其系数相加，如果结果系数为 0，则删除该项。

`PolyPrint` 函数用于输出一个多项式，格式为：`系数x^指数 + 系数x^指数 + ...`。

在主函数中，创建了两个多项式 `poly1` 和 `poly2`，分别进行加法和乘法运算，并输出结果。