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

多项式在数学中是一个非常重要的概念，因为它可以用来描述实际问题，例如物理学、经济学等领域的问题。在计算机科学中，多项式也是一个非常重要的概念，因为它可以用来描述算法的复杂度、编写数据结构等。因此，本文将介绍使用Python编写程序将作为链表的两个多项式相加的方法。

什么是多项式

在数学中，多项式是由系数和变量的乘积组成的表达式。例如：3x^2 – 2x + 1就是一个二次多项式，其中3、-2、1是多项式的系数，x是多项式的变量，2是多项式的次数。一般地，多项式的系数可以是实数、复数、整数、分数等等。

什么是链表

在计算机科学中，链表是一种用于存储和管理数据的数据结构。链表由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。链表中的节点是动态创建的，因此链表可以根据需要动态增长或缩小。链表与数组相比，具有更好的灵活性和可扩展性。

多项式的表示方法

考虑多项式的表达式：3x^2 – 2x + 1，我们可以用链表来表示它。具体来说，我们可以将多项式中的每一项表示为一个节点，节点的数据部分存储系数和次数，节点的指针部分指向下一项。例如，上述多项式可以表示为以下链表：

         +---+    +---+    +---+
head --> | 3 | -> |2,2| -> |-2,1| -> |1,0| -> None
         +---+    +---+    +---+

程序实现

本文将采用Python语言来编写程序，实现将两个多项式相加的功能。具体实现过程如下：

首先，定义一个多项式类Polynomial，每个多项式都是由若干个节点组成的链表。类中定义一个head节点表示链表的头部，一个tail节点表示链表的尾部。类中定义的addTerm方法可以向链表中加入一项，方法的参数为系数和次数。

class Polynomial:
    def __init__(self):
        self.head = None
        self.tail = None

    def addTerm(self, coeff, exp):
        newTerm = PolyTerm(coeff, exp)
        if self.head == None:
            self.head = newTerm
            self.tail = newTerm
        else:
            self.tail.next = newTerm
            self.tail = newTerm

接下来，定义一个多项式项类PolyTerm，每个多项式项都是链表中的一个节点。类中定义了两个实例变量coeff和exp，表示该项的系数和次数。类中还定义了一个next变量，表示该节点的下一个节点。

class PolyTerm:
    def __init__(self, coeff=0, exp=0, nxt=None):
        self.coeff = coeff
        self.exp = exp
        self.next = nxt

最后，定义一个名为addPolynomials的函数，将两个多项式相加。函数的参数为两个多项式对象，返回值为相加后的多项式对象。函数首先取出两个链表的第一项，然后按照次数进行比较（从高到低），将系数相加后加入新链表中。如果某个链表已经到达末尾，直接将另一个链表的剩余项加入新链表中。最后返回相加后的多项式对象。

def addPolynomials(poly1, poly2):
    result = Polynomial()
    current1 = poly1.head
    current2 = poly2.head
    while current1 or current2:
        if current1 and current2:
            if current1.exp == current2.exp:
                result.addTerm(current1.coeff + current2.coeff, current1.exp)
                current1 = current1.next
                current2 = current2.next
            elif current1.exp > current2.exp:
                result.addTerm(current1.coeff, current1.exp)
                current1 = current1.next
            else:
                result.addTerm(current2.coeff, current2.exp)
                current2 = current2.next
        elif current1:
            result.tail.next = current1
            result.tail = poly1.tail
            current1 = None
        else:
            result.tail.next = current2
            result.tail = poly2.tail
            current2 = None
    return result

使用示例：假设我们有两个多项式。多项式1为3x^2 – 2x + 1，多项式2为x^3 + 2x – 1。我们将它们相加。

p1 = Polynomial()
p1.addTerm(3, 2)
p1.addTerm(-2, 1)
p1.addTerm(1, 0)

p2 = Polynomial()
p2.addTerm(1, 3)
p2.addTerm(2, 1)
p2.addTerm(-1, 0)

result = addPolynomials(p1, p2)

# 输出相加后的结果
current = result.head
while current:
    print(current.coeff, "x^", current.exp, sep='', end='')
    if current.next:
        if current.next.coeff >= 0:
            print(" + ", end='')
    current = current.next

输出结果为：1x^3 + 3x^2 + 4x