用链表编写一个程序实现两个一元多项式相加的运算。
时间: 2023-05-24 15:05:19 浏览: 70
以下是用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)
self.current = self.head
def add_term(self, coef, exp):
self.current.next = Node(coef, exp)
self.current = self.current.next
def __add__(self, other):
result = Polynomial()
cur1 = self.head.next
cur2 = other.head.next
while cur1 and cur2:
if cur1.exp > cur2.exp:
result.add_term(cur1.coef, cur1.exp)
cur1 = cur1.next
elif cur1.exp < cur2.exp:
result.add_term(cur2.coef, cur2.exp)
cur2 = cur2.next
else:
coef_sum = cur1.coef + cur2.coef
if coef_sum != 0:
result.add_term(coef_sum, cur1.exp)
cur1 = cur1.next
cur2 = cur2.next
while cur1:
result.add_term(cur1.coef, cur1.exp)
cur1 = cur1.next
while cur2:
result.add_term(cur2.coef, cur2.exp)
cur2 = cur2.next
return result
def __str__(self):
if not self.head.next:
return '0'
result = ''
cur = self.head.next
while cur:
if cur.coef > 0 and len(result) > 0:
result += '+'
if cur.coef != 1 or cur.exp == 0:
result += str(cur.coef)
if cur.exp > 0:
result += 'x'
if cur.exp > 1:
result += '^' + str(cur.exp)
cur = cur.next
return result
p1 = Polynomial()
p1.add_term(3, 4)
p1.add_term(2, 3)
p1.add_term(-5, 2)
p1.add_term(7, 0)
p2 = Polynomial()
p2.add_term(-2, 3)
p2.add_term(4, 2)
p2.add_term(1, 1)
p2.add_term(3, 0)
p3 = p1 + p2
print(p1, '+', p2, '=', p3)
```
在这个程序中,每个多项式都是一个带头结点的有序链表,其中每个节点代表一个多项式的单项式。我们可以通过add_term()方法向链表中添加单项式,然后通过运算符重载的方式实现多项式的加法。
对于加法运算,我们首先需要遍历两个链表,将指数较小的单项式添加到结果链表中;如果两个单项式的指数相等,我们需要将它们的系数相加,然后将相加的结果加入到结果链表中。最后,我们需要将两个链表中剩余的单项式全部添加到结果链表中,并返回结果链表对应的多项式。
为了方便输出,我们还定义了__str__()方法,将多项式转换成字符串,方便输出。