采用单向链表实现一元多项式的存储,并实现两个多项式相加,输出结果。
时间: 2024-10-05 13:01:43 浏览: 66
在计算机科学中,可以使用单向链表来表示一元多项式,每个节点包含系数和变量的幂次信息。例如,对于多项式 `3x^2 + 5x - 7`,我们可以创建三个节点,第一个节点存储系数3,第二个节点存储系数5,第三个节点存储系数-7,对应幂次分别为2、1和0。
下面是一个简单的伪代码示例,展示了如何实现两个一元多项式相加:
```python
class Node:
def __init__(self, coefficient, power):
self.coefficient = coefficient
self.power = power
self.next = None
class Polynomial:
def __init__(self):
self.head = None
# 添加项到链表
def add_term(self, coefficient, power):
new_node = Node(coefficient, power)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next and current.next.power >= power:
current = current.next
current.next = new_node
# 相加两个多项式
def add_poly(self, other):
result = Polynomial()
current1 = self.head
current2 = other.head
carry = 0
while current1 or current2:
term1 = (current1 and current1.coefficient) or 0
term2 = (current2 and current2.coefficient) or 0
total = term1 + term2 + carry
carry = total // (power+1) # 计算进位,这里假设幂次都是整数
result.add_term(total % (power+1), max(current1.power, current2.power) if current1 and current2 else 0)
if current1:
current1 = current1.next
if current2:
current2 = current2.next
if carry > 0: # 如果有剩余的进位
result.add_term(carry, 0)
return result
# 示例
poly1 = Polynomial()
poly1.add_term(3, 2) # 3x^2
poly1.add_term(5, 1) # 5x
poly2 = Polynomial()
poly2.add_term(2, 2) # 2x^2
poly2.add_term(-4, 1) # -4x
result = poly1.add_poly(poly2)
```
当你运行这个程序后,你会得到一个表示相加后的多项式的新链表,比如`5x^2 + x - 1`。
阅读全文