如何用数据结构链表编写一个计算多项式求和的函数

在使用链表数据结构来实现多项式求和时，我们需要定义一个节点（Node）来存储每个系数和次数对。假设我们的链表节点（PolynomialTerm）结构如下：

class PolynomialTerm:
    def __init__(self, coefficient=0, exponent=0):
        self.coefficient = coefficient
        self.exponent = exponent
        self.next = None

class PolynomialSum:
    def __init__(self):
        self.head = None

接下来，我们可以定义两个核心方法：`add_terms` 和 `evaluate`。

1. `add_terms`: 这个方法接受两个链表作为输入，遍历它们并将对应项相加。如果系数相等，仅保留较大的指数；如果系数不同，则合并两个项，并将新的系数设置为两者之和，保持当前指数。

def add_terms(self, polynomial1, polynomial2):
    current1 = polynomial1.head
    current2 = polynomial2.head
    new_head = None
    
    while current1 is not None or current2 is not None:
        if current1 is None:
            next_term = current2
            current2 = current2.next
        elif current2 is None:
            next_term = current1
            current1 = current1.next
        else:
            if current1.coefficient > current2.coefficient:
                next_term = current1
                current1 = current1.next
            else:
                next_term = current2
                current2 = current2.next
        
        if new_head is None:
            new_head = PolynomialTerm(coefficient=next_term.coefficient)
        else:
            next_node = PolynomialTerm(coefficient=new_head.coefficient + next_term.coefficient)
            new_head.next = next_node
            new_head = next_node
            
    return self

2. `evaluate`: 这个方法用于计算多项式的值，给定一个x值，通过迭代链表并应用幂规则来得出结果。这里假设我们已经有了一个`apply_power`辅助函数，可以快速计算幂。

def apply_power(self, x, term):
    return term.coefficient * (x ** term.exponent)

def evaluate(self, x):
    result = 0
    current = self.head
    while current is not None:
        result += self.apply_power(x, current)
        current = current.next
    return result

现在你可以创建一个`PolynomialSum`实例，添加多项式项，然后计算它们的和：

# 创建两个链表表示多项式 2x^2 + 3x + 5 和 x^2 + 4x + 6
polynomial1 = PolynomialSum()
term1 = PolynomialTerm(2, 2)
term2 = PolynomialTerm(3, 1)
term3 = PolynomialTerm(5)
polynomial1.head = term1
term1.next = term2
term2.next = term3

polynomial2 = PolynomialSum()
term4 = PolynomialTerm(1, 2)
term5 = PolynomialTerm(4, 1)
term6 = PolynomialTerm(6)
polynomial2.head = term4
term4.next = term5
term5.next = term6

# 求和
sum_poly = polynomial1.add_terms(polynomial2)

# 计算x=2时的和
result = sum_poly.evaluate(2)