c++一元稀疏多项式运算器

实现一元稀疏多项式的运算器，可以采用链表来存储多项式中的每一项，每个节点包括系数、指数和指向下一个节点的指针。具体实现可以按照以下步骤：

1. 定义一个结构体来表示多项式的每一项，包括系数和指数：

struct PolyItem {
    double coef;    // 系数
    int exp;        // 指数
};

2. 定义一个链表节点结构体，包含一个 PolyItem 结构体作为数据域和一个指向下一个节点的指针：

struct ListNode {
    PolyItem data;      // 数据域
    ListNode* next;     // 指向下一个节点的指针
};

3. 定义一个多项式类 Poly，包含多项式的基本运算方法，如创建多项式、插入项、删除项、求和、求差、求积、求导等：

class Poly {
public:
    Poly();
    ~Poly();
    void insert(PolyItem item);     // 插入一项
    void remove(int exp);           // 删除指定指数的项
    Poly add(Poly other);           // 多项式加法
    Poly subtract(Poly other);      // 多项式减法
    Poly multiply(Poly other);      // 多项式乘法
    Poly derivative();              // 求导
    void print();                   // 打印多项式
private:
    ListNode* head;                 // 链表头节点指针
};

4. 实现多项式的各种运算方法，具体实现方式可以参考以下代码：

Poly::Poly() {
    head = new ListNode;
    head->next = nullptr;
}

Poly::~Poly() {
    ListNode* p = head;
    while (p != nullptr) {
        ListNode* q = p->next;
        delete p;
        p = q;
    }
}

void Poly::insert(PolyItem item) {
    ListNode* p = head;
    while (p->next != nullptr && p->next->data.exp > item.exp) {
        p = p->next;
    }
    if (p->next != nullptr && p->next->data.exp == item.exp) {
        p->next->data.coef += item.coef;
        if (p->next->data.coef == 0) {
            ListNode* q = p->next;
            p->next = q->next;
            delete q;
        }
    } else {
        ListNode* q = new ListNode;
        q->data = item;
        q->next = p->next;
        p->next = q;
    }
}

void Poly::remove(int exp) {
    ListNode* p = head;
    while (p->next != nullptr && p->next->data.exp > exp) {
        p = p->next;
    }
    if (p->next != nullptr && p->next->data.exp == exp) {
        ListNode* q = p->next;
        p->next = q->next;
        delete q;
    }
}

Poly Poly::add(Poly other) {
    Poly res;
    ListNode* p = head->next;
    ListNode* q = other.head->next;
    while (p != nullptr && q != nullptr) {
        if (p->data.exp > q->data.exp) {
            res.insert(p->data);
            p = p->next;
        } else if (p->data.exp < q->data.exp) {
            res.insert(q->data);
            q = q->next;
        } else {
            PolyItem item;
            item.coef = p->data.coef + q->data.coef;
            item.exp = p->data.exp;
            res.insert(item);
            p = p->next;
            q = q->next;
        }
    }
    while (p != nullptr) {
        res.insert(p->data);
        p = p->next;
    }
    while (q != nullptr) {
        res.insert(q->data);
        q = q->next;
    }
    return res;
}

Poly Poly::subtract(Poly other) {
    Poly res;
    ListNode* p = head->next;
    ListNode* q = other.head->next;
    while (p != nullptr && q != nullptr) {
        if (p->data.exp > q->data.exp) {
            res.insert(p->data);
            p = p->next;
        } else if (p->data.exp < q->data.exp) {
            PolyItem item;
            item.coef = -q->data.coef;
            item.exp = q->data.exp;
            res.insert(item);
            q = q->next;
        } else {
            PolyItem item;
            item.coef = p->data.coef - q->data.coef;
            item.exp = p->data.exp;
            res.insert(item);
            p = p->next;
            q = q->next;
        }
    }
    while (p != nullptr) {
        res.insert(p->data);
        p = p->next;
    }
    while (q != nullptr) {
        PolyItem item;
        item.coef = -q->data.coef;
        item.exp = q->data.exp;
        res.insert(item);
        q = q->next;
    }
    return res;
}

Poly Poly::multiply(Poly other) {
    Poly res;
    ListNode* p = head->next;
    while (p != nullptr) {
        ListNode* q = other.head->next;
        while (q != nullptr) {
            PolyItem item;
            item.coef = p->data.coef * q->data.coef;
            item.exp = p->data.exp + q->data.exp;
            res.insert(item);
            q = q->next;
        }
        p = p->next;
    }
    return res;
}

Poly Poly::derivative() {
    Poly res;
    ListNode* p = head->next;
    while (p != nullptr) {
        if (p->data.exp > 0) {
            PolyItem item;
            item.coef = p->data.coef * p->data.exp;
            item.exp = p->data.exp - 1;
            res.insert(item);
        }
        p = p->next;
    }
    return res;
}

void Poly::print() {
    ListNode* p = head->next;
    while (p != nullptr) {
        if (p->data.coef > 0 && p->data.exp != 0) {
            std::cout << "+";
        }
        if (p->data.coef != 1 || p->data.exp == 0) {
            std::cout << p->data.coef;
        }
        if (p->data.exp > 1) {
            std::cout << "x^" << p->data.exp;
        } else if (p->data.exp == 1) {
            std::cout << "x";
        }
        p = p->next;
    }
    std::cout << std::endl;
}

这样，我们就实现了一个简单的一元稀疏多项式运算器。