一元多项式加法与乘法运算 - C++实现与算法分析

一元多项式加法与乘法运算 (C++实现)

本文将介绍如何使用链表实现一元多项式的加法和乘法运算，并提供完整的C++代码示例和算法分析。

问题描述

给定两个一元多项式，按照指数递增的顺序存储在链表中，每个节点包含系数和指数两部分信息。要求实现以下功能：

1. 多项式相加：计算两个多项式的和，并将结果存储在新的链表中。
2. 多项式相乘：计算两个多项式的积，并将结果存储在新的链表中。

算法设计

1. 多项式表示

我们使用链表来表示一元多项式，每个节点包含系数和指数两个数据项。例如，多项式 '3x^2 + 2x + 1' 可以表示为如下链表：

(1, 0) -> (2, 1) -> (3, 2) 

其中，每个节点 '(coefficient, exponent)' 分别表示系数和指数。

2. 多项式相加

多项式相加可以通过遍历两个链表并合并相同指数的项来实现。具体步骤如下：

1. 创建一个新的链表用于存储结果。
2. 分别设置两个指针指向两个输入链表的头节点。
3. 比较两个指针所指节点的指数：
   • 如果指数相同，则将系数相加，并将结果添加到结果链表中。
   • 如果第一个多项式的指数较小，则将该节点添加到结果链表中，并将指针移至下一个节点。
   • 如果第二个多项式的指数较小，则将该节点添加到结果链表中，并将指针移至下一个节点。
4. 重复步骤3，直到遍历完两个链表。

3. 多项式相乘

多项式相乘可以通过嵌套循环实现。具体步骤如下：

1. 创建一个新的链表用于存储结果。
2. 遍历第一个多项式的每个节点。
3. 对于第一个多项式的每个节点，遍历第二个多项式的每个节点。
4. 将两个节点的系数相乘，指数相加，并将结果添加到结果链表中。
5. 合并结果链表中指数相同的项。

C++ 代码实现

#include <iostream>
using namespace std;

// 定义多项式的节点结构
struct Node {
    int coefficient;  // 系数项
    int exponent;     // 指数项
    Node* next;
};

// 创建多项式链表
Node* createList(int length) {
    Node* head = new Node();
    Node* tail = head;

    for (int i = 0; i < length; i++) {
        int coefficient, exponent;
        cin >> coefficient >> exponent;

        Node* node = new Node();
        node->coefficient = coefficient;
        node->exponent = exponent;
        node->next = nullptr;

        tail->next = node;
        tail = node;
    }

    return head;
}

// 多项式相加运算
Node* addPolynomials(Node* poly1, Node* poly2) {
    Node* head = new Node();
    Node* tail = head;
    Node* p1 = poly1->next;
    Node* p2 = poly2->next;

    while (p1 != nullptr && p2 != nullptr) {
        if (p1->exponent < p2->exponent) {
            tail->next = p1;
            p1 = p1->next;
        } else if (p1->exponent > p2->exponent) {
            tail->next = p2;
            p2 = p2->next;
        } else {
            int coefficient = p1->coefficient + p2->coefficient;
            if (coefficient != 0) {
                Node* node = new Node();
                node->coefficient = coefficient;
                node->exponent = p1->exponent;
                node->next = nullptr;
                tail->next = node;
                tail = node;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
    }

    while (p1 != nullptr) {
        tail->next = p1;
        p1 = p1->next;
        tail = tail->next;
    }

    while (p2 != nullptr) {
        tail->next = p2;
        p2 = p2->next;
        tail = tail->next;
    }

    return head;
}

// 多项式相乘运算
Node* multiplyPolynomials(Node* poly1, Node* poly2) {
    Node* head = new Node();
    Node* p1 = poly1->next;

    while (p1 != nullptr) {
        Node* p2 = poly2->next;
        Node* tempHead = new Node();
        Node* tail = tempHead;

        while (p2 != nullptr) {
            int coefficient = p1->coefficient * p2->coefficient;
            int exponent = p1->exponent + p2->exponent;

            Node* node = new Node();
            node->coefficient = coefficient;
            node->exponent = exponent;
            node->next = nullptr;
            tail->next = node;
            tail = node;

            p2 = p2->next;
        }

        head = addPolynomials(head, tempHead);

        p1 = p1->next;
    }

    return head;
}

// 释放多项式链表的内存
void deleteList(Node* head) {
    Node* p = head;
    while (p != nullptr) {
        Node* temp = p;
        p = p->next;
        delete temp;
    }
}

// 按指数从小到大输出多项式链表
void printList(Node* head) {
    Node* p = head->next;
    while (p != nullptr) {
        cout << p->coefficient << ' ' << p->exponent << ' ';
        p = p->next;
    }
    cout << endl;
}

int main() {
    int m, n;
    cin >> m;
    
    Node* poly1 = createList(m);

    cin >> n;

    Node* poly2 = createList(n);

    int operation;
    cin >> operation;

    if (operation == 0) {
        Node* result = addPolynomials(poly1, poly2);
        printList(result);
        deleteList(result);
    } else if (operation == 1) {
        Node* result = multiplyPolynomials(poly1, poly2);
        printList(result);
        deleteList(result);
    } else if (operation == 2) {
        Node* addResult = addPolynomials(poly1, poly2);
        Node* multiplyResult = multiplyPolynomials(poly1, poly2);
        printList(addResult);
        printList(multiplyResult);
        deleteList(addResult);
        deleteList(multiplyResult);
    }

    deleteList(poly1);
    deleteList(poly2);

    return 0;
}

复杂度分析

• 时间复杂度:
  • 多项式相加：O(m+n)，其中 m 和 n 分别为两个多项式的项数。
  • 多项式相乘：O(m*n)，其中 m 和 n 分别为两个多项式的项数。
• 空间复杂度: O(m+n)，主要用于存储结果链表。

总结

本文介绍了如何使用链表实现一元多项式的加法和乘法运算，并提供了详细的C++代码示例和算法分析。希望本文能够帮助您更好地理解和应用链表这一重要的数据结构。