使用Python编写程序将作为链表的两个多项式相加

使用Python编写程序将作为链表的两个多项式相加

假设我们有两个多项式,我们必须找出它们的加法。多项式必须被表示为链表;多项式的项将被表示为链表节点。每个链表节点将包含系数值、幂值和指向下一个链表节点的指针。我们必须返回一个第三个链表,它是两个链表多项式的和。

因此,如果输入如下:

使用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的下一个

  • 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程