用数据结构编写多项式相加
时间: 2023-10-17 16:15:05 浏览: 69
以下是使用链表实现多项式相加的Python代码:
```python
class Node:
def __init__(self, coef, exp, next=None):
self.coef = coef
self.exp = exp
self.next = next
class Polynomial:
def __init__(self):
self.head = Node(None, None)
def add_term(self, coef, exp):
current = self.head
while current.next and current.next.exp > exp:
current = current.next
if current.next and current.next.exp == exp:
current.next.coef += coef
else:
new_node = Node(coef, exp, current.next)
current.next = new_node
def add_poly(self, poly):
current1 = self.head.next
current2 = poly.head.next
new_poly = Polynomial()
while current1 and current2:
if current1.exp > current2.exp:
new_poly.add_term(current1.coef, current1.exp)
current1 = current1.next
elif current1.exp < current2.exp:
new_poly.add_term(current2.coef, current2.exp)
current2 = current2.next
else:
new_poly.add_term(current1.coef + current2.coef, current1.exp)
current1 = current1.next
current2 = current2.next
while current1:
new_poly.add_term(current1.coef, current1.exp)
current1 = current1.next
while current2:
new_poly.add_term(current2.coef, current2.exp)
current2 = current2.next
return new_poly
def __str__(self):
current = self.head.next
poly_str = ""
while current:
if current.coef != 0:
if current.exp == 0:
poly_str += str(current.coef)
elif current.exp == 1:
poly_str += str(current.coef) + "x"
else:
poly_str += str(current.coef) + "x^" + str(current.exp)
if current.next and current.next.coef > 0:
poly_str += " + "
current = current.next
return poly_str
p1 = Polynomial()
p1.add_term(3, 4)
p1.add_term(2, 3)
p1.add_term(5, 2)
p1.add_term(1, 1)
p1.add_term(4, 0)
p2 = Polynomial()
p2.add_term(2, 5)
p2.add_term(1, 4)
p2.add_term(3, 2)
p2.add_term(2, 1)
p2.add_term(1, 0)
p3 = p1.add_poly(p2)
print(p3)
```
输出:
```
2x^5 + 4x^4 + 2x^3 + 8x^2 + 3x + 5
```
在上面的代码中,我们使用了链表来表示多项式。每个节点包含一个系数和一个指数,以及一个指向下一个节点的指针。我们还定义了一个Polynomial类,它有一个head节点,表示多项式的头部。我们可以通过add_term方法向多项式中添加新项。在add_poly方法中,我们使用了两个while循环来合并两个多项式。最后,我们定义了__str__方法,以便我们可以打印多项式。