根据提示,在右侧编辑器补充代码,利用链表实现整系数多项式的加法Node* add_poly(Node* a, Node* b)。多项式a和b用链表表示,链表定义如下: struct Node { int order, coeff; // 次数 和 系数 Node* nxt; // 指向后一项的指针 } 多项式a和b保证每一项系数coeff都是整数,保证每一项次数order >= 0。输入order=-1表示输入结束。保证从链表的头到尾,次数递减,详见 sample case。 结果多项式的表示和a,b的规则一样,从最高次项到最低次项,不要包含系数为0的项。但是如果结果多项式等于0(即有且仅有常数项0)则需要包含该项。计算过程中涉及的整数加法不会溢出。
时间: 2024-03-03 16:49:16 浏览: 54
用链表实现多项式的加法和乘法
下面是一个根据题意实现的代码:
```c++
#include <iostream>
using namespace std;
struct Node {
int order;
int coeff;
Node* nxt;
};
Node* add_poly(Node* a, Node* b) {
Node* c = new Node();
Node* tail = c;
while (a != nullptr && b != nullptr) {
if (a->order > b->order) {
tail->nxt = a;
a = a->nxt;
} else if (a->order < b->order) {
tail->nxt = b;
b = b->nxt;
} else {
int sum = a->coeff + b->coeff;
if (sum != 0) {
Node* node = new Node();
node->order = a->order;
node->coeff = sum;
tail->nxt = node;
tail = node;
}
a = a->nxt;
b = b->nxt;
}
}
while (a != nullptr) {
tail->nxt = a;
a = a->nxt;
tail = tail->nxt;
}
while (b != nullptr) {
tail->nxt = b;
b = b->nxt;
tail = tail->nxt;
}
return c->nxt;
}
int main() {
Node* a = new Node();
Node* b = new Node();
Node* tail = a;
int order, coeff;
cin >> order >> coeff;
while (order != -1) {
Node* node = new Node();
node->order = order;
node->coeff = coeff;
tail->nxt = node;
tail = node;
cin >> order >> coeff;
}
tail = b;
cin >> order >> coeff;
while (order != -1) {
Node* node = new Node();
node->order = order;
node->coeff = coeff;
tail->nxt = node;
tail = node;
cin >> order >> coeff;
}
Node* c = add_poly(a->nxt, b->nxt);
if (c == nullptr) {
cout << 0 << " " << 0 << endl;
} else {
while (c != nullptr) {
cout << c->order << " " << c->coeff << endl;
c = c->nxt;
}
}
return 0;
}
```
该程序首先读入两个多项式的系数和次数,然后将它们存储到链表 a 和 b 中。接下来调用 add_poly 函数计算它们的和,并将结果存储到链表 c 中。最后输出链表 c 中的项,即为结果多项式。
需要注意的是,如果结果多项式等于 0,则需要输出一个系数为 0 的项。
阅读全文