多项式乘法问题

article/2025/8/15 6:16:47

多项式乘法问题

实验目的：设计一个一元稀疏多项式简单计算器。

实验内容与要求：

一元稀疏多项式简单计算器的基本功能是：

（1）输入并建立多项式；

（2）输出多项式，序列按指数降序排列。

（3）多项式a与多项式b相乘，建立多项式。

实验内容和实验步骤：

概览：

输入：a项的项数以及分别输入每项的系数和指数，可以不按指数的大小乱序输入，可以输入多项带有相同指数的项（程序会将其自动累加）；项数c是float型（输出时保留一位小数），指数e是int型。

输出：相乘的结果。结果按指数的大小降序排列，其中的项的系数若是负号，则不输出加号，系数为0的项删除，指数为1的项只输出该项系数而不输出x。题目要求的输出太过简略，而本程序输出比题目要求更加直观易懂，但实现起来更为复杂，下面再来讨论。

设计概要：

从主函数进入后，先初始化链表。再依次用循环输入数据并以此建立a、b两个链表。每建立一个链表，用check函数检查并删掉多余项，最后用multiple函数求积（内置check函数删掉多余项），通过toString函数输出答案。

本程序采用链表实现：链表单元是PNode；cmp用来比较排序（用于insertList）；insertList用来输入多项式（按照指数的降序顺序排列）；checkList用来遍历检查链表，若发现系数为0的项就将其剔除（用于运算操作之后），multiple用来实现乘法运算，toString用来打印多项式。

注：为了使输入和输出看起来更加舒服，toString输出的格式更符合人们的习惯，比如：

x^2 - 2x^1 + 1

15.0x^3 + 16.0x^2 + 9.0x^1 + 2.0

以下是程序的详细说明：

#include<iostream>
using namespace std;
typedef struct PNode { //定义链表中的节点float c; //系数int e; //指数struct PNode *next;
}PNode, *PNodeList;void InitList(PNodeList &l) {//初始化链表函数，为链表加一个头节点//头节点只是指向作用，其系数指数均为0l = new PNode();
}int cmp(PNodeList a, PNodeList b) {return b->e - a->e;
}void insertList(PNodeList &L, float c, int e) {//插入新节点，以指数的降序顺序排列。int status = 1; //用来指示节点是否在中途插入，也可以用bool型变量来表示PNodeList p = L;PNodeList temp = new PNode(); //初始化要插入的节点temp->c = c;temp->e = e;while (p->next != NULL) {if (cmp(temp, p->next)<0) { //如果要插入的节点比后一个大，则将其插在后一个之前。temp->next = p->next;p->next = temp;status = 0;break;}else if(!cmp(temp, p->next)){ //如果要插入的节点等于后一个节点，则只改变后一个节点系数即可。p->next->c += c;status = 0;break;}p = p->next;}if (status) {//要插入的节点比所有的节点小。则放在链表最后即可。p->next = temp; }
}//双for循环遍历两表，将结果依次加入结果
void multiple(PNodeList a, PNodeList b, PNodeList c) {//用来检查并删掉系数为0的项PNodeList pa = a;PNodeList pb = b;if (pa->next == NULL || pb->next == NULL) return; //若a、b为0，则直接退出for (pa = a; pa->next != NULL;) {pa = pa->next;for (pb = b; pb->next != NULL;) {pb = pb->next;insertList(c, pa->c*pb->c, pa->e + pb->e);}
void checkList(PNodeList c) {//用来检查并删掉系数为0的项PNodeList delete_node;while (c != NULL&&c->next != NULL) {//这里要考虑到两种情况：末尾节点和非末尾节点if (c->next->c == 0) {delete_node = c->next;c->next = delete_node->next;delete[] delete_node;}c = c->next;}
}void toString(PNodeList L) { //打印链表if (L->next == NULL) {printf("\n");}else {L = L->next;if(L->e==0)printf("%.1f", L->c);elseprintf("%.1fx^%d", L->c, L->e);L = L->next;while (L != NULL) {if (L->e == 0) {if (L->c > 0) printf(" +");printf(" %.1f", L->c);}else {if (L->c > 0) printf(" +");printf(" %.1fx^%d", L->c, L->e);}L = L->next;}}printf("\n");
}int main() {PNodeList a,b,c;InitList(a);InitList(b);InitList(c);int n1, n2;cout << "请输入a表中的多项式项数：";cin >> n1;cout << "请依次输入a表中的系数和指数：" << endl;for (int i = 0; i < n1; i++) {printf("第%d项的系数和指数分别是：",i + 1);float c;int e;cin >> c;cin >> e;insertList(a, c, e);}checkList(a);cout << "您输入的a式是：" << endl;toString(a);cout << "请输入b表中的多项式系数：";cin >> n2;cout << "请依次输入b表中的系数和指数：" << endl;for (int i = 0; i < n2; i++) {printf("第%d项的系数和指数分别是：", i + 1);float c;int e;cin >> c;cin >> e;insertList(b, c, e);}checkList(b);cout << "您输入的b式是：" << endl;toString(b);cout << "相乘的结果为：" << endl;multiple(a, b, c);toString(c);return 0;
}

实验用测试数据和相关结果分析：

例如：

在这里插入图片描述