头歌基于链表的两个一元多项式的基本运算

基于链表的两个一元多项式的基本运算包括加法、减法、乘法和求导运算。具体步骤如下：

加法运算：
1. 创建一个新的空链表来存储结果。
2. 从两个多项式的头节点开始，依次比较两个多项式的指数大小。
3. 如果两个多项式的指数相等，则将它们的系数相加，并将结果插入到结果链表中。
4. 如果两个多项式的指数不相等，则将指数较大的项插入到结果链表中，并向下移动指针。
5. 当其中一个多项式的指针到达尾部时，将另一个多项式的剩余项依次插入结果链表中。
6. 返回结果链表。

减法运算：
1. 创建一个新的空链表来存储结果。
2. 从两个多项式的头节点开始，依次比较两个多项式的指数大小。
3. 如果两个多项式的指数相等，则将它们的系数相减，并将结果插入到结果链表中。
4. 如果两个多项式的指数不相等，则将指数较大的项插入到结果链表中，并向下移动指针。
5. 当其中一个多项式的指针到达尾部时，将另一个多项式的剩余项的系数取相反数插入结果链表中。
6. 返回结果链表。

乘法运算：
1. 创建一个新的空链表来存储结果。
2. 遍历第一个多项式的每一项，依次与第二个多项式的每一项相乘。
3. 将乘积的系数相加，并将结果插入到结果链表中，指数为两项指数的和。
4. 返回结果链表。

求导运算：
1. 创建一个新的空链表来存储结果。
2. 遍历多项式的每一项，将每一项的系数乘以指数，并将指数减一。
3. 将结果插入到结果链表中。
4. 返回结果链表。

相关问题

【头歌】基于链表的两个一元多项式的基本运算

基于链表的两个一元多项式的基本运算包括加法、减法、乘法和求导运算。

加法运算的步骤如下：
1. 遍历链表A和链表B，将相同指数的项的系数相加，将结果存入一个新的链表C。
2. 若链表A或链表B已经遍历完，则将剩余项直接添加到链表C中。
3. 返回链表C作为结果。

减法运算的步骤如下：
1. 遍历链表A和链表B，将相同指数的项的系数相减，将结果存入一个新的链表C。
2. 若链表A或链表B已经遍历完，则将剩余项的系数取相反数后直接添加到链表C中。
3. 返回链表C作为结果。

乘法运算的步骤如下：
1. 遍历链表A的每一项，将其与链表B的每一项相乘，得到一个新的项的系数和指数。
2. 将所有新的项添加到一个新的链表C中。
3. 返回链表C作为结果。

求导运算的步骤如下：
1. 遍历链表A的每一项，将其系数与指数相乘，得到一个新的项的系数和指数。
2. 将所有新的项添加到一个新的链表C中。
3. 返回链表C作为结果。

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

链表可以用来表示一元多项式，每个节点代表一个项，包含系数和指数。基本运算包括加法、减法和乘法。

加法和减法的思路都很类似，都是将链表中对应指数的项相加或相减。具体实现时，可以先将两个链表按指数从小到大排序，然后同时遍历两个链表，按照指数大小比较，将对应项相加或相减，生成新的节点插入结果链表中。如果某一链表已经遍历结束，则将另一链表的剩余项直接插入结果链表中。

乘法的实现稍微复杂一些。可以采用两个循环嵌套的方式，分别遍历两个链表，将每个项相乘得到新的项，并将新的项插入结果链表中。具体实现时，需要注意项之间的系数和指数相乘的规律，以及结果链表中相同指数的项需要合并的问题。可以使用一个哈希表来记录每个指数在结果链表中的位置，然后在插入新项时，根据指数查找哈希表，判断是否有相同指数的项存在，如果存在，则将系数相加，否则新建一个节点并插入结果链表中，并更新哈希表中的指数位置信息。

下面是 C++ 实现示例：

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node {
    int coef;
    int exp;
    Node *next;
    Node(int coef_, int exp_) : coef(coef_), exp(exp_), next(nullptr) {}
};

void insert(Node *&head, int coef, int exp) {
    Node *node = new Node(coef, exp);
    if (head == nullptr || head->exp < exp) {
        node->next = head;
        head = node;
    } else {
        Node *prev = nullptr, *curr = head;
        while (curr != nullptr && curr->exp > exp) {
            prev = curr;
            curr = curr->next;
        }
        if (curr != nullptr && curr->exp == exp) {
            curr->coef += coef;
            if (curr->coef == 0) {
                if (prev == nullptr) {
                    head = curr->next;
                } else {
                    prev->next = curr->next;
                }
                delete curr;
            }
        } else {
            node->next = curr;
            prev->next = node;
        }
    }
}

Node *add(Node *p1, Node *p2) {
    Node *head = nullptr;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->exp == p2->exp) {
            insert(head, p1->coef + p2->coef, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            insert(head, p1->coef, p1->exp);
            p1 = p1->next;
        } else {
            insert(head, p2->coef, p2->exp);
            p2 = p2->next;
        }
    }
    while (p1 != nullptr) {
        insert(head, p1->coef, p1->exp);
        p1 = p1->next;
    }
    while (p2 != nullptr) {
        insert(head, p2->coef, p2->exp);
        p2 = p2->next;
    }
    return head;
}

Node *subtract(Node *p1, Node *p2) {
    Node *head = nullptr;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->exp == p2->exp) {
            insert(head, p1->coef - p2->coef, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            insert(head, p1->coef, p1->exp);
            p1 = p1->next;
        } else {
            insert(head, -p2->coef, p2->exp);
            p2 = p2->next;
        }
    }
    while (p1 != nullptr) {
        insert(head, p1->coef, p1->exp);
        p1 = p1->next;
    }
    while (p2 != nullptr) {
        insert(head, -p2->coef, p2->exp);
        p2 = p2->next;
    }
    return head;
}

Node *multiply(Node *p1, Node *p2) {
    Node *head = nullptr;
    unordered_map<int, Node *> m;
    for (; p1 != nullptr; p1 = p1->next) {
        for (Node *p = p2; p != nullptr; p = p->next) {
            int coef = p1->coef * p->coef;
            int exp = p1->exp + p->exp;
            if (m.count(exp) == 0) {
                m[exp] = new Node(coef, exp);
            } else {
                insert(m[exp], coef, exp);
            }
        }
    }
    for (auto &item : m) {
        if (item.second->coef != 0) {
            insert(head, item.second->coef, item.second->exp);
        }
    }
    return head;
}

void print(Node *head) {
    if (head == nullptr) {
        cout << "0" << endl;
    } else {
        while (head != nullptr) {
            cout << head->coef << "x^" << head->exp;
            head = head->next;
            if (head != nullptr) {
                cout << " + ";
            }
        }
        cout << endl;
    }
}

int main() {
    Node *p1 = nullptr, *p2 = nullptr;
    insert(p1, 2, 3);
    insert(p1, 4, 1);
    insert(p1, 3, 0);
    insert(p2, 3, 4);
    insert(p2, 1, 3);
    insert(p2, 2, 1);
    print(add(p1, p2));        // 3x^4 + 2x^3 + 2x^1 + 3
    print(subtract(p1, p2));   // -3x^4 + 2x^3 + 2x^1 - 3
    print(multiply(p1, p2));   // 6x^7 + 14x^5 + 13x^4 + 10x^3 + 9x^1 + 6
    return 0;
}