单向链表中的每个结点都需要动态分配内存空间。
时间: 2024-05-10 11:20:51 浏览: 9
思路:
首先,我们需要定义一个结构体来存储多项式的每一项,包括系数和指数。然后,我们需要定义一个链表结构来存储多项式,链表的每个节点存储一个多项式项。
在建立多项式链表时,我们需要按照指数从大到小的顺序插入新的节点。当插入新节点时,我们需要遍历链表,找到插入位置。如果链表中已经存在相同指数的项,则需要将其系数相加。
最后,我们需要定义一个函数来计算两个多项式的和,即将两个多项式的每一项相加,并返回一个新的多项式链表。
代码实现:
```python
class PolyNode:
def __init__(self, coef=0, exp=0, next=None):
self.coef = coef
self.exp = exp
self.next = next
class PolyList:
def __init__(self):
self.head = PolyNode()
def insert(self, coef, exp):
p = self.head
while p.next and p.next.exp > exp:
p = p.next
if p.next and p.next.exp == exp:
p.next.coef += coef
if p.next.coef == 0:
p.next = p.next.next
else:
p.next = PolyNode(coef, exp, p.next)
def __str__(self):
p = self.head.next
s = ''
while p:
s += '{}x^{} + '.format(p.coef, p.exp)
p = p.next
return s[:-3]
def add_poly(poly1, poly2):
res = PolyList()
p1, p2 = poly1.head.next, poly2.head.next
while p1 and p2:
if p1.exp > p2.exp:
res.insert(p1.coef, p1.exp)
p1 = p1.next
elif p1.exp < p2.exp:
res.insert(p2.coef, p2.exp)
p2 = p2.next
else:
res.insert(p1.coef + p2.coef, p1.exp)
p1 = p1.next
p2 = p2.next
while p1:
res.insert(p1.coef, p1.exp)
p1 = p1.next
while p2:
res.insert(p2.coef, p2.exp)
p2 = p2.next
return res
```
测试代码:
```python
poly1 = PolyList()
poly1.insert(3, 5)
poly1.insert(-2, 3)
poly1.insert(5, 1)
print(poly1)
poly2 = PolyList()
poly2.insert(2, 4)
poly2.insert(4, 3)
poly2.insert(-1, 2)
poly2.insert(3, 1)
print(poly2)
res = add_poly(poly1, poly2)
print(res)
```
输出结果:
```
3x^5 + -2x^3 + 5x^1
2x^4 + 4x^3 + -1x^2 + 3x^1
3x^5 + 2x^4 + 2x^3 + -3x^2 + 8x^1
```