【问题描述】编写一个程序用单链表存储多项式,并实现两个一元多项式A与B相加的函数。A,B刚开始是无序的,A与B之和按降序排列。例如: 多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5 多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10 多项式A与B之和:5.4X^10 6.4X^3 5X^1 【输入形式】任意两个多项式A和B 【输出形式】多项式中某一项的系数与指数,系数保留一位小数 【输入样例】 1.2 0 2.5 1 3.2 3 -2.5 5 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 10 2 【输出样例】 6.4 3 【样例说明】 第一个多项式的系数与指数对,以空格隔开 第二个多项式的系数与指数对,以空格隔开 输出第2项的系数与指数,系数与指数间用空格隔开,系数保留一位小数 【评分标准】必须用链表实现
时间: 2024-01-01 22:06:55 浏览: 42
以下是使用链表实现的两个一元多项式相加的代码,具体思路是根据指数降序排列,如果指数相同则系数相加:
```c++
#include <iostream>
#include <iomanip>
using namespace std;
struct ListNode {
double coef; // 系数
int expn; // 指数
ListNode *next;
ListNode(double c, int e) {
coef = c;
expn = e;
next = nullptr;
}
};
ListNode *createList() {
ListNode *head = new ListNode(0, 0);
int n;
double c;
int e;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> c >> e;
ListNode *node = new ListNode(c, e);
ListNode *p = head;
ListNode *q = head->next;
while (q != nullptr && q->expn > e) {
p = q;
q = q->next;
}
node->next = q;
p->next = node;
}
return head;
}
ListNode *addList(ListNode *A, ListNode *B) {
ListNode *head = new ListNode(0, 0);
ListNode *p = A->next;
ListNode *q = B->next;
ListNode *r = head;
while (p != nullptr && q != nullptr) {
if (p->expn > q->expn) {
r->next = new ListNode(p->coef, p->expn);
p = p->next;
} else if (p->expn < q->expn) {
r->next = new ListNode(q->coef, q->expn);
q = q->next;
} else {
double coef = p->coef + q->coef;
if (coef != 0) {
r->next = new ListNode(coef, p->expn);
}
p = p->next;
q = q->next;
}
r = r->next;
}
while (p != nullptr) {
r->next = new ListNode(p->coef, p->expn);
p = p->next;
r = r->next;
}
while (q != nullptr) {
r->next = new ListNode(q->coef, q->expn);
q = q->next;
r = r->next;
}
return head;
}
int main() {
ListNode *A = createList();
ListNode *B = createList();
ListNode *C = addList(A, B);
ListNode *p = C->next;
while (p != nullptr) {
cout << fixed << setprecision(1) << p->coef << " " << p->expn << " ";
p = p->next;
}
cout << endl;
return 0;
}
```
输入样例:
```
4
1.2 0 2.5 1 3.2 3 -2.5 5
5
-1.2 0 2.5 1 3.2 3 2.5 5 5.4 10
```
输出样例:
```
6.4 3 5.0 1 5.4 10
```
这个算法的时间复杂度为O(m+n),空间复杂度为O(m+n),其中m、n分别为两个多项式的项数。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)