C++链表实现多项式（从零开始掌握多项式运算的链表方法）

为什么使用链表表示多项式？

多项式如 3x⁴ + 2x² + 5 包含多个项，每项有系数和指数。使用数组存储时，若指数跨度大（如 x¹⁰⁰ 和 x¹），会造成大量内存浪费。而链表数据结构只存储非零项，节省空间且便于动态插入/删除。

步骤一：定义链表节点

首先，我们需要一个结构体来表示每一项：

struct Term {    int coef;   // 系数    int exp;    // 指数    Term* next; // 指向下一个项    // 构造函数    Term(int c = 0, int e = 0) : coef(c), exp(e), next(nullptr) {}};

步骤二：创建多项式类

我们封装一个 Polynomial 类来管理整个多项式：

class Polynomial {private:    Term* head; // 头指针public:    Polynomial() : head(new Term()) {} // 带头结点的链表    // 添加一项（按指数降序插入）    void addTerm(int coef, int exp);    // 显示多项式    void display();    // 多项式加法    Polynomial add(const Polynomial& other);    // 析构函数    ~Polynomial();};

步骤三：实现关键函数

1. 添加项（保持指数降序）

void Polynomial::addTerm(int coef, int exp) {    if (coef == 0) return; // 忽略零系数    Term* current = head;    // 找到插入位置（指数降序）    while (current->next && current->next->exp > exp) {        current = current->next;    }    // 如果指数已存在，合并系数    if (current->next && current->next->exp == exp) {        current->next->coef += coef;        if (current->next->coef == 0) {            // 系数为0则删除该项            Term* temp = current->next;            current->next = temp->next;            delete temp;        }    } else {        // 插入新节点        Term* newNode = new Term(coef, exp);        newNode->next = current->next;        current->next = newNode;    }}

2. 显示多项式

void Polynomial::display() {    Term* p = head->next;    if (!p) {        std::cout << "0";        return;    }    while (p) {        if (p != head->next && p->coef > 0)            std::cout << " + ";        else if (p->coef < 0)            std::cout << " - ";        int absCoef = std::abs(p->coef);        if (p->exp == 0) {            std::cout << absCoef;        } else if (p->exp == 1) {            if (absCoef == 1)                std::cout << "x";            else                std::cout << absCoef << "x";        } else {            if (absCoef == 1)                std::cout << "x^" << p->exp;            else                std::cout << absCoef << "x^" << p->exp;        }        p = p->next;    }    std::cout << std::endl;}

3. 多项式加法

Polynomial Polynomial::add(const Polynomial& other) {    Polynomial result;    Term* p1 = this->head->next;    Term* p2 = other.head->next;    while (p1 && p2) {        if (p1->exp > p2->exp) {            result.addTerm(p1->coef, p1->exp);            p1 = p1->next;        } else if (p1->exp < p2->exp) {            result.addTerm(p2->coef, p2->exp);            p2 = p2->next;        } else {            result.addTerm(p1->coef + p2->coef, p1->exp);            p1 = p1->next;            p2 = p2->next;        }    }    // 复制剩余项    while (p1) {        result.addTerm(p1->coef, p1->exp);        p1 = p1->next;    }    while (p2) {        result.addTerm(p2->coef, p2->exp);        p2 = p2->next;    }    return result;}

完整示例：测试多项式加法

#include <iostream>#include <cmath>// （此处省略上面定义的 Term 和 Polynomial 类）int main() {    Polynomial p1, p2;    // 3x^4 + 2x^2 + 5    p1.addTerm(3, 4);    p1.addTerm(2, 2);    p1.addTerm(5, 0);    // -x^4 + 4x^3 + x^2    p2.addTerm(-1, 4);    p2.addTerm(4, 3);    p2.addTerm(1, 2);    std::cout << "P1 = "; p1.display();    std::cout << "P2 = "; p2.display();    Polynomial sum = p1.add(p2);    std::cout << "P1 + P2 = "; sum.display();    return 0;}

输出结果：

P1 = 3x^4 + 2x^2 + 5P2 = -x^4 + 4x^3 + x^2P1 + P2 = 2x^4 + 4x^3 + 3x^2 + 5

总结

通过本教程，你已经掌握了如何使用C++多项式运算结合链表数据结构来高效处理数学表达式。这种方法不仅节省内存，还便于扩展（如实现减法、乘法）。希望这篇C++编程教程能为你打下坚实基础！

动手试试吧！你可以在此基础上添加乘法、求导等功能，进一步提升你的 C++ 编程能力。