基于链表的两个一元多项式的基本运算c++

以下是基于链表的一元多项式的基本运算的C++代码：

#include<iostream>
using namespace std;

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

// 定义多项式类
class Polynomial {
private:
    PolyNode *head;  // 指向多项式头节点的指针
public:
    Polynomial() {  // 构造函数
        head = new PolyNode;  // 创建头节点
        head->next = NULL;  // 头节点指向空
    }
    ~Polynomial() {  // 析构函数
        PolyNode *p = head, *q;
        while (p != NULL) {  // 释放链表内存
            q = p;
            p = p->next;
            delete q;
        }
    }
    void print();  // 输出多项式
    void insert(float coef, int exp);  // 插入单项式
    void add(Polynomial &b);  // 多项式加法
    void subtract(Polynomial &b);  // 多项式减法
    void multiply(Polynomial &b);  // 多项式乘法
};

void Polynomial::print() {
    PolyNode *p = head->next;
    while (p != NULL) {  // 遍历链表输出多项式
        cout << p->coef << "x^" << p->exp << " ";
        p = p->next;
    }
    cout << endl;
}

void Polynomial::insert(float coef, int exp) {
    PolyNode *p = head;
    while (p->next != NULL && exp < p->next->exp) {  // 插入单项式
        p = p->next;
    }
    if (p->next != NULL && exp == p->next->exp) {  // 指数相同合并
        p->next->coef += coef;
        if (p->next->coef == 0) {  // 系数为0删除节点
            PolyNode *q = p->next;
            p->next = q->next;
            delete q;
        }
    } else {  // 插入新单项式
        PolyNode *q = new PolyNode;
        q->coef = coef;
        q->exp = exp;
        q->next = p->next;
        p->next = q;
    }
}

void Polynomial::add(Polynomial &b) {
    PolyNode *pa = head->next, *pb = b.head->next;
    while (pa != NULL && pb != NULL) {  // 遍历两个多项式
        if (pa->exp > pb->exp) {  // pa的指数大于pb的指数
            pa = pa->next;
        } else if (pa->exp < pb->exp) {  // pa的指数小于pb的指数
            insert(pb->coef, pb->exp);
            pb = pb->next;
        } else {  // pa的指数等于pb的指数
            insert(pa->coef + pb->coef, pa->exp);
            pa = pa->next;
            pb = pb->next;
        }
    }
    while (pb != NULL) {  // 将剩余的pb插入到pa中
        insert(pb->coef, pb->exp);
        pb = pb->next;
    }
}

void Polynomial::subtract(Polynomial &b) {
    PolyNode *pa = head->next, *pb = b.head->next;
    while (pa != NULL && pb != NULL) {  // 遍历两个多项式
        if (pa->exp > pb->exp) {  // pa的指数大于pb的指数
            pa = pa->next;
        } else if (pa->exp < pb->exp) {  // pa的指数小于pb的指数
            insert(-pb->coef, pb->exp);
            pb = pb->next;
        } else {  // pa的指数等于pb的指数
            insert(pa->coef - pb->coef, pa->exp);
            pa = pa->next;
            pb = pb->next;
        }
    }
    while (pb != NULL) {  // 将剩余的-pb插入到pa中
        insert(-pb->coef, pb->exp);
        pb = pb->next;
    }
}

void Polynomial::multiply(Polynomial &b) {
    Polynomial c;  // 定义结果多项式
    PolyNode *pa = head->next, *pb;
    while (pa != NULL) {  // 遍历第一个多项式
        pb = b.head->next;
        while (pb != NULL) {  // 遍历第二个多项式
            c.insert(pa->coef * pb->coef, pa->exp + pb->exp);  // 插入单项式
            pb = pb->next;
        }
        pa = pa->next;
    }
    *this = c;  // 将结果赋值给当前多项式
}

int main() {
    Polynomial a, b;
    a.insert(1, 3);
    a.insert(2, 2);
    a.insert(3, 1);
    a.insert(4, 0);
    b.insert(2, 2);
    b.insert(3, 1);
    b.insert(4, 0);
    cout << "a(x) = ";
    a.print();
    cout << "b(x) = ";
    b.print();
    a.add(b);
    cout << "a(x) + b(x) = ";
    a.print();
    a.subtract(b);
    cout << "a(x) - b(x) = ";
    a.print();
    a.multiply(b);
    cout << "a(x) * b(x) = ";
    a.print();
    return 0;
}

上述代码中，我们使用了链表来存储多项式的每个单项式，每个单项式包含一个系数和一个指数。在插入单项式时，我们按照单项式的指数从大到小的顺序插入，如果当前指数已经存在，则将系数相加。

在加法、减法和乘法操作中，我们都需要遍历两个多项式的所有单项式，通过插入单项式来实现结果多项式的构造。

最后，我们通过调用`print()`函数来输出多项式的结果。