C/C++ 链表实现一元多项式加法和乘法运算

本教程将详细讲解如何使用 C/C++ 语言中的链表数据结构来实现两个一元多项式的加法和乘法运算。

一、实验目的

掌握链表的应用和算法设计
掌握利用 C/C++ 编程语言实现数据结构的编程方法

二、实验内容与要求

利用单链表表示两个一元多项式，并完成两多项式的加法和乘法运算。

输入格式:

按指数的升序输入第一个一元多项式'polya'各项的指数和系数，且以输入 0 0 结束，按指数的升序输入第二个一元多项式'polyb'各项的指数和系数。

输出格式:

输出两一元多项式相加和相乘的一元多项式，并进行算法时间复杂度的分析。

示例:

(2 + 3x - 3x^4) + (4x^2 + 6x^6) = (2 + 3x + 4x^2 - 3x^4 + 6x^6)

(2 + 3x - 3x^4) * (4x^2 + 6x^6) = (8x^2 + 12x^3 + 18x^7 - 18x^10)

测试用例:

输入 0 2 1 3 4 -3 0 0 0 2 1 3 2 -3 0 0

2 4 6 6 0 0 1 1 2 4 0 0

加法输出:

0 2 1 3 2 4 4 -3 6 6 0 2 1 4 2 1

乘法输出:

2 8 3 12 7 18 10 -18 1 2 2 11 3 9 4 -1

三、代码实现

根据实验要求，你需要使用单链表来表示两个一元多项式，并实现它们的加法和乘法运算。

1. 定义链表节点

首先，你需要定义一个结构体来表示多项式的每一项，包括指数和系数。然后，你可以使用链表节点来构建一个单链表，每个节点存储一项的数据，并连接到下一个节点。

// 定义链表节点
struct ListNode {
    int exp;  // 指数
    int coe;  // 系数
    ListNode* next;  // 下一个节点指针
};

2. 构建一元多项式的链表

// 构建一元多项式的链表
ListNode* buildPoly() {
    ListNode* head = nullptr;
    ListNode* tail = nullptr;

    int exp, coe;
    cout << "请输入一元多项式的指数和系数，以0 0结束：" << endl;
    while (cin >> exp >> coe && !(exp == 0 && coe == 0)) {
        ListNode* newNode = new ListNode;
        newNode->exp = exp;
        newNode->coe = coe;
        newNode->next = nullptr;

        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    return head;
}

3. 实现多项式加法运算

// 多项式相加操作
ListNode* addPoly(ListNode* polya, ListNode* polyb) {
    ListNode* res = nullptr;
    ListNode* tail = nullptr;

    while (polya != nullptr && polyb != nullptr) {
        if (polya->exp < polyb->exp) {
            ListNode* newNode = new ListNode;
            newNode->exp = polya->exp;
            newNode->coe = polya->coe;
            newNode->next = nullptr;

            if (res == nullptr) {
                res = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }

            polya = polya->next;
        } else if (polya->exp > polyb->exp) {
            ListNode* newNode = new ListNode;
            newNode->exp = polyb->exp;
            newNode->coe = polyb->coe;
            newNode->next = nullptr;

            if (res == nullptr) {
                res = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }

            polyb = polyb->next;
        } else {
            ListNode* newNode = new ListNode;
            newNode->exp = polya->exp;
            newNode->coe = polya->coe + polyb->coe;
            newNode->next = nullptr;

            if (res == nullptr) {
                res = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }

            polya = polya->next;
            polyb = polyb->next;
        }
    }

    // 将剩余的项加入结果链表
    while (polya != nullptr) {
        ListNode* newNode = new ListNode;
        newNode->exp = polya->exp;
        newNode->coe = polya->coe;
        newNode->next = nullptr;

        if (res == nullptr) {
            res = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }

        polya = polya->next;
    }

    while (polyb != nullptr) {
        ListNode* newNode = new ListNode;
        newNode->exp = polyb->exp;
        newNode->coe = polyb->coe;
        newNode->next = nullptr;

        if (res == nullptr) {
            res = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }

        polyb = polyb->next;
    }

    return res;
}

4. 实现多项式乘法运算

// 多项式相乘操作
ListNode* multiplyPoly(ListNode* polya, ListNode* polyb) {
    ListNode* res = nullptr;

    while (polya != nullptr) {
        ListNode* temp = polyb;
        ListNode* tempRes = nullptr;
        ListNode* tail = nullptr;

        while (temp != nullptr) {
            ListNode* newNode = new ListNode;
            newNode->exp = polya->exp + temp->exp;
            newNode->coe = polya->coe * temp->coe;
            newNode->next = nullptr;

            if (tempRes == nullptr) {
                tempRes = newNode;
                tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }

            temp = temp->next;
        }

        res = addPoly(res, tempRes);

        polya = polya->next;
    }

    return res;
}

5. 编写主函数测试代码

int main() {
    ListNode* polya = buildPoly();
    ListNode* polyb = buildPoly();

    ListNode* addRes = addPoly(polya, polyb);
    ListNode* multiplyRes = multiplyPoly(polya, polyb);

    cout << "两个多项式相加的结果为：" << endl;
    while (addRes != nullptr) {
        cout << addRes->exp << " " << addRes->coe << " ";
        addRes = addRes->next;
    }
    cout << endl;

    cout << "两个多项式相乘的结果为：" << endl;
    while (multiplyRes != nullptr) {
        cout << multiplyRes->exp << " " << multiplyRes->coe << " ";
        multiplyRes = multiplyRes->next;
    }
    cout << endl;

    return 0;
}

四、总结

本教程详细讲解了如何使用 C/C++ 语言中的链表数据结构来实现两个一元多项式的加法和乘法运算，并附带示例代码和测试用例。你可以根据需要进行修改和优化。

希望本教程对你有帮助！如果还有其他问题，请随时提问。