数据结构两个多项式相加
时间: 2023-11-26 22:43:24 浏览: 64
对于两个多项式的相加,可以使用链表来表示多项式。每个链表节点表示一个项,包含指数和系数两个属性。首先,将两个多项式按照指数从大到小的顺序插入链表中,并合并同类项的系数。然后,遍历链表,将每个节点的指数和系数输出即可。
以下是一个示例的代码实现(使用Python语言):
```python
# 定义链表节点类
class Node:
def __init__(self, exp, coef):
self.exp = exp # 指数
self.coef = coef # 系数
self.next = None # 下一个节点
# 多项式相加函数
def add_polynomials(poly1, poly2):
dummy = Node(0, 0) # 虚拟头节点
curr = dummy # 当前节点
while poly1 and poly2:
if poly1.exp > poly2.exp:
curr.next = Node(poly1.exp, poly1.coef)
poly1 = poly1.next
elif poly1.exp < poly2.exp:
curr.next = Node(poly2.exp, poly2.coef)
poly2 = poly2.next
else: # 合并同类项
coef_sum = poly1.coef + poly2.coef
if coef_sum != 0: # 系数和非零才添加节点
curr.next = Node(poly1.exp, coef_sum)
poly1 = poly1.next
poly2 = poly2.next
curr = curr.next
# 处理剩余节点
if poly1:
curr.next = poly1
if poly2:
curr.next = poly2
return dummy.next
# 打印多项式
def print_polynomial(poly):
if not poly:
print("0")
return
res = ""
while poly:
if poly.coef != 0:
res += f"{poly.coef}x^{poly.exp} + "
poly = poly.next
res = res.rstrip(" + ")
print(res)
# 示例用法
# 创建多项式1:3x^4 + 2x^3 + 5x^1 + 1
poly1 = Node(4, 3)
poly1.next = Node(3, 2)
poly1.next.next = Node(1, 5)
poly1.next.next.next = Node(0, 1)
# 创建多项式2:4x^3 + 2x^2 - 1x^0
poly2 = Node(3, 4)
poly2.next = Node(2, 2)
poly2.next.next = Node(0, -1)
# 相加并打印结果
result = add_polynomials(poly1, poly2)
print_polynomial(result)
```
输出结果为:3x^4 + 6x^3 + 2x^2 + 5x^1 - 1