信息学实验室作业（五）

更新: 2025/3/15 字数: 0 字时长: 0 分钟

一、实验目的

本次实验旨在通过构建单向链表存储多项式信息，并编写相关子程序完成多项式的比较、加法等操作，深入理解单向链表数据结构及其在多项式处理中的应用，提升编程实践和问题解决能力。

二、实验内容

构建存储多项式信息的单向链表，链表元素包含系数和指数，且系数为零的项不存入链表。编写子程序实现：1. 检查两个以链表形式给出的多项式是否相等；2. 对两个以链表形式给出的多项式进行加法运算，并将结果以链表形式呈现。

三、实现思路

定义链表节点结构：创建一个结构体表示链表节点，包含多项式的系数、指数以及指向下一个节点的指针。
创建多项式链表：编写函数用于创建多项式链表，在插入节点时，按指数从高到低的顺序插入，同时忽略系数为零的项，以保证链表的有效性和操作的便利性。
多项式比较：分别遍历两个多项式链表，依次比较对应节点的系数和指数。若在遍历过程中发现任何不匹配的项，则两个多项式不相等；只有当两个链表完全遍历且所有对应项都相同时，两个多项式才相等。
多项式加法：同时遍历两个多项式链表，根据节点的指数大小进行合并。若指数相同，则将系数相加；若某个链表的当前节点指数较大，则先将该节点插入结果链表；若相加后系数为零，则不将该项插入结果链表。

四、代码实现

cpp

#include <iostream>

// 定义多项式链表节点结构
struct PolyNode {
    double coef;  // 系数
    int exp;      // 指数
    PolyNode* next;
    PolyNode(double c, int e) : coef(c), exp(e), next(nullptr) {}
};

// 向链表中插入节点（按指数降序，过滤系数为零的项）
void insert(PolyNode*& head, double coef, int exp) {
    if (coef == 0) return;
    PolyNode* newNode = new PolyNode(coef, exp);
    if (!head || exp > head->exp) {
        newNode->next = head;
        head = newNode;
    } else {
        PolyNode* current = head;
        while (current->next && current->next->exp > exp) {
            current = current->next;
        }
        if (current->next && current->next->exp == exp) {
            current->next->coef += coef;
            if (current->next->coef == 0) {
                PolyNode* temp = current->next;
                current->next = temp->next;
                delete temp;
            }
        } else {
            newNode->next = current->next;
            current->next = newNode;
        }
    }
}

// 创建多项式链表
PolyNode* createPoly() {
    PolyNode* head = nullptr;
    int n;
    std::cout << "请输入多项式的项数: ";
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        double coef;
        int exp;
        std::cout << "请输入第 " << i + 1 << " 项的系数和指数: ";
        std::cin >> coef >> exp;
        insert(head, coef, exp);
    }
    return head;
}

// 比较两个多项式是否相等
bool comparePoly(PolyNode* p1, PolyNode* p2) {
    while (p1 && p2) {
        if (p1->coef != p2->coef || p1->exp != p2->exp) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return (!p1 &&!p2);
}

// 两个多项式相加
PolyNode* addPoly(PolyNode* p1, PolyNode* p2) {
    PolyNode* result = nullptr;
    while (p1 || p2) {
        if (!p2 || (p1 && p1->exp > p2->exp)) {
            insert(result, p1->coef, p1->exp);
            p1 = p1->next;
        } else if (!p1 || (p2 && p2->exp > p1->exp)) {
            insert(result, p2->coef, p2->exp);
            p2 = p2->next;
        } else {
            insert(result, p1->coef + p2->coef, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    return result;
}

// 打印多项式链表
void printPoly(PolyNode* p) {
    if (!p) {
        std::cout << "0";
        return;
    }
    bool first = true;
    while (p) {
        if (!first && p->coef > 0) {
            std::cout << "+";
        }
        if (p->exp == 0) {
            std::cout << p->coef;
        } else if (p->exp == 1) {
            if (p->coef == 1) {
                std::cout << "x";
            } else if (p->coef == -1) {
                std::cout << "-x";
            } else {
                std::cout << p->coef << "x";
            }
        } else {
            if (p->coef == 1) {
                std::cout << "x^" << p->exp;
            } else if (p->coef == -1) {
                std::cout << "-x^" << p->exp;
            } else {
                std::cout << p->coef << "x^" << p->exp;
            }
        }
        first = false;
        p = p->next;
    }
}

// 释放链表内存
void freePoly(PolyNode* p) {
    while (p) {
        PolyNode* temp = p;
        p = p->next;
        delete temp;
    }
}

int main() {
    std::cout << "创建第一个多项式:" << std::endl;
    PolyNode* poly1 = createPoly();
    std::cout << "第一个多项式: ";
    printPoly(poly1);
    std::cout << std::endl;

    std::cout << "创建第二个多项式:" << std::endl;
    PolyNode* poly2 = createPoly();
    std::cout << "第二个多项式: ";
    printPoly(poly2);
    std::cout << std::endl;

    // 比较多项式
    if (comparePoly(poly1, poly2)) {
        std::cout << "两个多项式相等" << std::endl;
    } else {
        std::cout << "两个多项式不相等" << std::endl;
    }

    // 多项式加法
    PolyNode* sumPoly = addPoly(poly1, poly2);
    std::cout << "两个多项式相加的结果: ";
    printPoly(sumPoly);
    std::cout << std::endl;

    // 释放内存
    freePoly(poly1);
    freePoly(poly2);
    freePoly(sumPoly);

    return 0;
}

五、代码解释

PolyNode结构体：定义了链表节点，包含系数coef、指数exp和指向下一节点的指针next，用于存储多项式的每一项信息。
insert函数：负责将多项式的项插入链表。它首先判断系数是否为零，若为零则不插入。插入时，按指数从大到小的顺序找到合适位置插入新节点，若遇到指数相同的节点，则合并系数，若合并后系数为零，则删除该节点。
createPoly函数：通过用户输入多项式的项数、每一项的系数和指数，调用insert函数创建多项式链表。
comparePoly函数：使用while循环同时遍历两个多项式链表，比较对应节点的系数和指数，只要有一处不相等就返回false，遍历结束且所有对应项都相等则返回true。
addPoly函数：同样利用while循环遍历两个链表，根据指数大小进行合并操作。指数大的项先插入结果链表，指数相同则合并系数，最后返回合并后的结果链表。
printPoly函数：遍历多项式链表，按常见的数学表达式格式打印多项式，如3x^2 + 2x - 1。
freePoly函数：在程序结束时，用于释放链表占用的内存，防止内存泄漏。
main函数：作为程序入口，负责调用上述函数实现多项式的创建、比较、加法操作，并输出相应结果，最后释放内存。

六、编译与运行

将上述代码保存为.cpp文件，如polynomial_operations.cpp。
使用g++编译器进行编译，在命令行输入g++ polynomial_operations.cpp -o polynomial_operations。
编译成功后，运行生成的可执行文件，在命令行输入./polynomial_operations。
按照程序提示，依次输入两个多项式的项数、每一项的系数和指数，程序会输出两个多项式、比较结果以及相加后的结果。

七、实验总结

通过本次实验，成功运用单向链表实现了多项式的比较和加法操作。在实验过程中，对单向链表的插入、遍历等操作有了更深入的理解，同时掌握了多项式处理中系数和指数的逻辑处理方式。在代码编写过程中，遇到了链表节点插入位置判断不准确、系数合并后处理不当等问题，通过仔细检查和调试得以解决，这也提高了自己的编程和调试能力。后续可以进一步拓展功能，如实现多项式的减法、乘法等运算，以完善多项式的操作体系。

信息学实验室作业（五） ​

一、实验目的 ​

二、实验内容 ​

三、实现思路 ​

四、代码实现 ​

五、代码解释 ​

六、编译与运行 ​

七、实验总结 ​