Python链表实现多项式运算（小白也能看懂的数据结构实战教程）

步骤一：定义链表节点类

首先，我们需要一个节点类来存储每一项的信息：系数（coefficient）和指数（exponent）。

class TermNode:    def __init__(self, coef, exp):        self.coef = coef      # 系数        self.exp = exp        # 指数        self.next = None      # 指向下一个节点

步骤二：创建多项式链表类

接下来，我们构建一个 Polynomial 类，用于管理整个多项式链表。

class Polynomial:    def __init__(self):        self.head = None  # 链表头节点        def add_term(self, coef, exp):        """按指数降序添加项"""        new_node = TermNode(coef, exp)                # 如果链表为空，或新项指数最大        if not self.head or self.head.exp < exp:            new_node.next = self.head            self.head = new_node        else:            current = self.head            # 找到插入位置            while current.next and current.next.exp > exp:                current = current.next                        # 如果指数相同，合并系数            if current.exp == exp:                current.coef += coef                # 如果系数变为0，删除该项                if current.coef == 0:                    if current == self.head:                        self.head = current.next                    else:                        prev = self.head                        while prev.next != current:                            prev = prev.next                        prev.next = current.next            else:                new_node.next = current.next                current.next = new_node

步骤三：实现多项式加法

两个多项式相加时，我们遍历两个链表，根据指数大小决定如何合并。

    def add(self, other):        """返回当前多项式与另一个多项式相加的结果"""        result = Polynomial()        p1 = self.head        p2 = other.head                while p1 and p2:            if p1.exp > p2.exp:                result.add_term(p1.coef, p1.exp)                p1 = p1.next            elif p1.exp < p2.exp:                result.add_term(p2.coef, p2.exp)                p2 = p2.next            else:  # 指数相同                result.add_term(p1.coef + p2.coef, p1.exp)                p1 = p1.next                p2 = p2.next                # 添加剩余项        while p1:            result.add_term(p1.coef, p1.exp)            p1 = p1.next        while p2:            result.add_term(p2.coef, p2.exp)            p2 = p2.next                    return result

步骤四：打印多项式

为了方便查看结果，我们添加一个打印方法。

    def __str__(self):        if not self.head:            return "0"        terms = []        current = self.head        while current:            if current.exp == 0:                terms.append(str(current.coef))            elif current.exp == 1:                terms.append(f"{current.coef}x")            else:                terms.append(f"{current.coef}x^{current.exp}")            current = current.next        return " + ".join(terms).replace("+ -", "- ")

完整示例：运行你的第一个多项式加法

现在，让我们把所有代码组合起来并测试一下！

# 创建第一个多项式: 3x^4 + 2x^2 + 5poly1 = Polynomial()poly1.add_term(3, 4)poly1.add_term(2, 2)poly1.add_term(5, 0)# 创建第二个多项式: -x^4 + 4x^3 + x^2poly2 = Polynomial()poly2.add_term(-1, 4)poly2.add_term(4, 3)poly2.add_term(1, 2)# 相加result = poly1.add(poly2)print("Poly1:", poly1)      # 输出: 3x^4 + 2x^2 + 5print("Poly2:", poly2)      # 输出: -1x^4 + 4x^3 + 1x^2print("Sum:", result)       # 输出: 2x^4 + 4x^3 + 3x^2 + 5

总结

通过本教程，你已经掌握了如何用Python链表实现多项式的基本操作。这项技能不仅巩固了你对链表操作的理解，也为后续学习更复杂的数据结构教程打下基础。同时，你也亲手实现了多项式加法这一经典算法问题。

建议你尝试扩展功能，比如实现减法、乘法，或者从字符串解析多项式。动手实践是掌握数据结构的最佳方式！