用链表实现一元多项式的加、减、乘、求导运算

好的，我来为您解答这个问题。

首先，我们需要定义一个节点来表示多项式中的每一项，包含系数和指数。节点的定义如下：

struct Node {
    double coef;  // 系数
    int exp;      // 指数
    Node* next;   // 指向下一个节点的指针
};

接下来，我们可以定义一个链表类来实现多项式的各种运算。链表类的定义如下：

class Polynomial {
public:
    Polynomial();           // 构造函数
    ~Polynomial();          // 析构函数
    void insert(double c, int e);  // 插入一项
    void add(Polynomial p);         // 多项式加法
    void subtract(Polynomial p);    // 多项式减法
    void multiply(Polynomial p);    // 多项式乘法
    void differentiate();           // 多项式求导
    void print();                   // 打印多项式
private:
    Node* head;  // 头节点指针
};

接下来，我们逐个实现各个函数。

1. 构造函数

构造函数需要初始化头节点指针为空。

Polynomial::Polynomial() {
    head = NULL;
}

2. 析构函数

析构函数需要释放链表中的所有节点。

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

3. 插入一项

插入一项需要按照指数从大到小的顺序插入。

void Polynomial::insert(double c, int e) {
    if (c == 0) return;  // 系数为0不插入
    Node* p = new Node;
    p->coef = c;
    p->exp = e;
    if (head == NULL || e > head->exp) {
        p->next = head;
        head = p;
    } else {
        Node* q = head;
        while (q->next != NULL && e < q->next->exp) {
            q = q->next;
        }
        p->next = q->next;
        q->next = p;
    }
}

4. 多项式加法

多项式加法需要遍历两个多项式的链表，将相同指数的项相加，并插入到一个新的链表中。

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

5. 多项式减法

多项式减法可以用多项式加法和系数取相反数来实现。

void Polynomial::subtract(Polynomial p) {
    Node* p1 = p.head;
    while (p1 != NULL) {
        p1->coef = -p1->coef;
        p1 = p1->next;
    }
    add(p);
}

6. 多项式乘法

多项式乘法需要遍历两个多项式的链表，将它们的每一项相乘，并插入到一个新的链表中。

void Polynomial::multiply(Polynomial p) {
    Polynomial result;
    Node* p1 = head;
    while (p1 != NULL) {
        Node* p2 = p.head;
        while (p2 != NULL) {
            double c = p1->coef * p2->coef;
            int e = p1->exp + p2->exp;
            result.insert(c, e);
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    *this = result;
}

7. 多项式求导

多项式求导需要遍历多项式的链表，将每一项的系数乘以指数，并将指数减1。

void Polynomial::differentiate() {
    Node* p = head;
    while (p != NULL) {
        p->coef *= p->exp;
        p->exp--;
        p = p->next;
    }
}

8. 打印多项式

打印多项式需要遍历链表，按照格式输出每一项。

void Polynomial::print() {
    Node* p = head;
    if (p == NULL) {
        cout << "0" << endl;
        return;
    }
    while (p != NULL) {
        if (p->coef > 0 && p != head) {
            cout << "+";
        }
        if (p->coef == -1) {
            cout << "-";
        } else if (p->coef != 1) {
            cout << p->coef;
        }
        if (p->exp == 0) {
            cout << " ";
        } else if (p->exp == 1) {
            cout << "x" << " ";
        } else {
            cout << "x^" << p->exp << " ";
        }
        p = p->next;
    }
    cout << endl;
}

至此，我们就完成了用链表实现一元多项式的加、减、乘、求导运算的实现。