链式存储实现一元多项式的加减运算数据结构

一元多项式可以用链式存储结构来实现，在这种结构中，每个节点包含两个数据项，一个是多项式的系数，另一个是多项式的指数。链表的头指针指向第一个节点，每个节点的指针指向下一个节点。

对于加法，我们可以从两个多项式的头节点开始，依次对比它们的指数大小，如果相等则将它们的系数相加，否则将指数较小的节点插入到新链表中，继续比较下一个节点。如果遍历完其中一个多项式，则直接将剩余的节点插入到新链表中。

对于减法，我们可以先将第二个多项式的系数取相反数，再按照加法的方式进行计算。

下面是链式存储实现一元多项式的加减运算的代码示例：

#include <iostream>
using namespace std;

// 定义多项式的节点结构体
struct Node {
    float coef; // 系数
    int expo;   // 指数
    Node* next; // 指向下一个节点的指针
    Node(float c, int e): coef(c), expo(e), next(NULL) {}
};

// 定义多项式类
class Polynomial {
public:
    Polynomial(): head(NULL) {}
    ~Polynomial() { clear(); }
    void clear();                   // 清空多项式
    void insert(float c, int e);    // 插入节点
    void add(Polynomial& p);        // 加法
    void subtract(Polynomial& p);   // 减法
    void print();                   // 输出多项式
private:
    Node* head; // 头指针
};

void Polynomial::clear() {
    Node* p = head;
    while (p) {
        Node* q = p;
        p = p->next;
        delete q;
    }
    head = NULL;
}

void Polynomial::insert(float c, int e) {
    if (c == 0) return; // 系数为0，不插入节点
    Node* p = head;
    Node* q = NULL; // p的前驱节点
    while (p && p->expo > e) {
        q = p;
        p = p->next;
    }
    if (p && p->expo == e) {
        p->coef += c; // 指数相同，系数相加
        if (p->coef == 0) { // 系数为0，删除节点
            if (q) q->next = p->next;
            else head = p->next;
            delete p;
        }
    } else { // 插入新节点
        Node* node = new Node(c, e);
        if (q) q->next = node;
        else head = node;
        node->next = p;
    }
}

void Polynomial::add(Polynomial& p) {
    Node* p1 = head;
    Node* p2 = p.head;
    Polynomial result;
    while (p1 && p2) {
        if (p1->expo == p2->expo) {
            result.insert(p1->coef + p2->coef, p1->expo);
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->expo > p2->expo) {
            result.insert(p1->coef, p1->expo);
            p1 = p1->next;
        } else {
            result.insert(p2->coef, p2->expo);
            p2 = p2->next;
        }
    }
    while (p1) {
        result.insert(p1->coef, p1->expo);
        p1 = p1->next;
    }
    while (p2) {
        result.insert(p2->coef, p2->expo);
        p2 = p2->next;
    }
    clear();
    head = result.head;
    result.head = NULL;
}

void Polynomial::subtract(Polynomial& p) {
    Node* p2 = p.head;
    while (p2) {
        p2->coef = -p2->coef; // 取相反数
        p2 = p2->next;
    }
    add(p);
}

void Polynomial::print() {
    Node* p = head;
    while (p) {
        cout << p->coef << "x^" << p->expo << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    Polynomial p1, p2;
    p1.insert(3, 5);
    p1.insert(-2, 3);
    p1.insert(5, 2);
    p1.insert(4, 0);
    p2.insert(2, 4);
    p2.insert(-1, 3);
    p2.insert(1, 1);
    p1.print();
    p2.print();
    p1.add(p2);
    p1.print();
    p1.subtract(p2);
    p1.print();
    return 0;
}

输出结果如下：

3x^5 -2x^3 5x^2 4x^0 
2x^4 -1x^3 1x^1 
3x^5 2x^4 -3x^3 5x^2 1x^1 4x^0 
3x^5 -2x^3 5x^2 4x^0