用 Rust 手把手实现链表多项式

为什么用链表表示多项式？

多项式中的每一项都包含一个系数（coefficient）和一个指数（exponent）。例如，在 5x³ 中，系数是 5，指数是 3。如果使用数组，会浪费大量空间（尤其是稀疏多项式，如 x¹⁰⁰ + 1）。而链表只存储非零项，节省内存且灵活。

第一步：定义链表节点

我们首先定义一个表示多项式项的结构体 Term，然后构建单向链表。

// 定义一个多项式项#[derive(Debug, Clone)]struct Term {    coefficient: i32, // 系数    exponent: u32,   // 指数（非负）}// 链表节点#[derive(Debug, Clone)]struct Node {    term: Term,    next: Option>,}// 多项式结构体#[derive(Debug, Clone)]struct Polynomial {    head: Option>,}

第二步：实现基本方法

我们需要为 Polynomial 实现添加项、打印、求值等方法。注意：为了简化，我们假设插入时按指数降序排列。

impl Polynomial {    // 创建空多项式    fn new() -> Self {        Polynomial { head: None }    }    // 按指数降序插入项    fn insert(&mut self, coeff: i32, exp: u32) {        let new_node = Box::new(Node {            term: Term { coefficient: coeff, exponent: exp },            next: None,        });        // 如果是空链表，直接作为头节点        if self.head.is_none() {            self.head = Some(new_node);            return;        }        // 找到插入位置（保持指数降序）        let mut current = &mut self.head;        while let Some(ref mut node) = current {            if exp > node.term.exponent {                // 插入到当前位置之前                let old_next = node.next.take();                node.next = Some(new_node);                if let Some(ref mut inserted) = node.next {                    inserted.next = old_next;                }                return;            } else if exp == node.term.exponent {                // 合并同类项                node.term.coefficient += coeff;                // 如果系数变为0，删除该项（简化处理）                if node.term.coefficient == 0 {                    // 此处简化：实际需处理前驱节点                    // 为教学目的，暂不实现删除逻辑                }                return;            }            current = &mut node.next;        }        // 插入到末尾        *current = Some(new_node);    }    // 打印多项式    fn display(&self) {        let mut current = &self.head;        let mut first = true;        while let Some(node) = current {            let coeff = node.term.coefficient;            let exp = node.term.exponent;            // 跳过系数为0的项            if coeff == 0 {                current = &node.next;                continue;            }            // 处理符号            if !first && coeff > 0 {                print!("+ ");            } else if coeff < 0 {                print!("- ");            }            let abs_coeff = coeff.abs();            match exp {                0 => print!("{}", abs_coeff),                1 => {                    if abs_coeff == 1 {                        print!("x")                    } else {                        print!("{}x", abs_coeff)                    }                }                _ => {                    if abs_coeff == 1 {                        print!("x^{}", exp)                    } else {                        print!("{}x^{}", abs_coeff, exp)                    }                }            }            first = false;            current = &node.next;        }        println!();    }}

第三步：测试我们的多项式

现在，让我们写一个简单的 main 函数来测试这个实现。

fn main() {    let mut poly = Polynomial::new();    poly.insert(3, 2); // 3x²    poly.insert(2, 1); // + 2x    poly.insert(1, 0); // + 1    poly.insert(-1, 2); // -x² → 合并后为 2x²    println!("多项式为:");    poly.display(); // 输出: 2x^2 + 2x + 1}

进阶思考

这个基础实现展示了如何用 Rust编程教程 中的核心概念（如所有权、Box、Option）构建数据结构。你可以进一步扩展：

• 实现两个多项式相加
• 支持浮点系数
• 优化插入逻辑以正确处理系数为0的删除
• 实现求导或积分功能

总结

通过本教程，你学会了如何用 Rust链表 表示和操作多项式。这不仅是一个有趣的 Rust数据结构 练习，也为更复杂的符号计算打下基础。希望这篇 Rust编程教程 能帮助你迈出系统编程的第一步！