使用Python编写程序将作为链表的两个多项式相加
假设我们有两个多项式,我们必须找出它们的加法。多项式必须被表示为链表;多项式的项将被表示为链表节点。每个链表节点将包含系数值、幂值和指向下一个链表节点的指针。我们必须返回一个第三个链表,它是两个链表多项式的和。
因此,如果输入如下:
1x^1 + 1x^2 = 0, 2x^1 + 3x^0 = 0
则输出将是3x^1 + 1x^2 + 3x^0 = 0
为解决这个问题,我们将遵循以下步骤-
- dummy := 新多项式节点
-
node := 新多项式节点
-
while poly1和poly2不为空,则
- 如果poly1的幂>poly2的幂,则
- node的下一个:= poly1
-
node:= poly1
-
poly1:= poly1的下一个
-
否则,当poly1的幂<poly2的幂时,则
- node的下一个:=poly2
-
node:=poly2
-
poly2:= poly2的下一个
-
否则,
- coef:= poly1的系数+poly2的系数
-
如果coef不为零,则
-
poly1:= poly1的下一个
-
poly2:= poly2的下一个
- 如果poly1的幂>poly2的幂,则
-
node的下一个:= poly1或poly2
-
返回dummy的下一个
让我们看一下以下实现,以便更好地理解-
示例
class polynomial:
def __init__(self, coeff = 0, pow = 0, nxt = None):
self.coefficient = coeff
self.power = pow
self.next = nxt
def create_poly(expression):
head = None
for element in expression:
if head == None:
head = polynomial(element[0], element[1])
else:
temp = head
while temp.next != None:
temp = temp.next
if temp.next == None:
temp.next = polynomial(element[0], element[1])
return head
def show_poly(head):
temp = head
while temp.next != None:
print(str(temp.coefficient) + 'x^' + str(temp.power), end = ' + ')
temp = temp.next
if temp.next == None:
print(str(temp.coefficient) + 'x^' + str(temp.power), end=' = 0')
def solve(poly1, poly2):
dummy = node = polynomial()
while poly1 and poly2:
if poly1.power > poly2.power:
node.next = node = poly1
poly1 = poly1.next
elif poly1.power < poly2.power:
node.next = node = poly2
poly2= poly2.next
else:
coef = poly1.coefficient + poly2.coefficient
if coef: node.next = node = polynomial(coef, poly1.power)
poly1 = poly1.next
poly2 = poly2.next
node.next = poly1 or poly2
return dummy.next
poly1 = create_poly([[1,1], [1,2]])
poly2 = create_poly([[2,1], [3, 0]])
poly3 = solve(poly1, poly2)
show_poly(poly3)
输入
poly1 = create_poly([[1,1], [1,2]])
poly2 = create_poly([[2,1], [3, 0]])
输出
3x^1 + 1x^2 + 3x^0 = 0