如何实现链表的加法方法？

Question

如何实现链表的加法方法？

3

我想创建一个简单的链表并向其中添加一个值。为了使这段代码在第42行第二个root.print()调用时输出100 50 10 5，应如何实现add方法？

use std::rc::Rc;

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

impl Node {
    fn print(&self) {
        let mut current = self;
        loop {
            println!("{}", current.value);
            match current.next {
                Some(ref next) => {
                    current = &**next;
                }
                None => break,
            }
        }
    }

    fn add(&mut self, node: Node) {
        let item = Some(Box::new(node));
        let mut current = self;
        loop {
            match current.next {
                None => current.next = item,
                _ => {} 
                //Some(next) => { current = next; }
            }
        }
    }
}

fn main() {
    let leaf = Node {
        value: 10,
        next: None,
    };
    let branch = Node {
        value: 50,
        next: Some(Box::new(leaf)),
    };
    let mut root = Node {
        value: 100,
        next: Some(Box::new(branch)),
    };
    root.print();

    let new_leaf = Node {
        value: 5,
        next: None,
    };
    root.add(new_leaf);
    root.print();
}

我已经按照以下方式重新编写了这个函数：

(Playground)

fn add(&mut self, node: Node) {
    let item = Some(Box::new(node));
    let mut current = self;
    loop {
        match current {
            &mut Node {
                     value: _,
                     next: None,
                 } => current.next = item,
            _ => {} 
            //Some(next) => { current = next; }
        }
    }
}

但编译器报错：

error[E0382]: use of moved value: `item`
  --> <anon>:28:40
   |
28 |                 None => current.next = item,
   |                                        ^^^^ value moved here in previous iteration of loop
   |
   = note: move occurs because `item` has type `std::option::Option<std::boxed::Box<Node>>`, which does not implement the `Copy` trait

我不明白为什么它说该项曾被移动，如果它只使用了一次，以及如何实现Some(_)分支以迭代列表？

- Alex Zhukovskiy

3

你为什么认为kind应该是一个引用（&mut T）而不是一个普通的值（T）？ - Matthieu M.

因为在插入值之后，叶子节点会变成分支节点。在上面的代码中，当添加了newLeaf之后，带有value的叶子节点应该变成一个分支节点。 - Alex Zhukovskiy

2

@Shepmaster: 我不愿称之为重复；我将感到惊讶如果Alex对理解背后的原因不感兴趣而只是想要一些链表代码。在这里，问题似乎首先是继承可变性和生命周期的问题。我还注意到了主函数中过多使用的“mut”，所以也许深入理解了哪些地方需要可变性，哪些不需要存在误解。我猜移动不需要可变性也可能令人惊讶。 - Matthieu M.

1

@AlexZhukovskiy：别担心，我们都在同一条船上 :) - Matthieu M.

1

在 Rust 字典中（参见 std::collections::LinkedList），它说你可以 push_back 一个元素，但你也可以将一个列表 append 到另一个列表中。 - bluss

显示剩余14条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bluss · Accepted Answer

这是你需要编写的方式 (示例链接)。

fn add(&mut self, node: Node) {
    let item = Some(Box::new(node));
    let mut current = self;
    loop {
        match moving(current).next {
            ref mut slot @ None => {
                *slot = item;
                return;
            }
            Some(ref mut next) => current = next,
        };
    }
}

好的，那么这是什么？

步骤1，我们需要在使用值item后立即return。然后编译器会正确地看到它只被移动了一次。

ref mut slot @ None => {
    *slot = item;
    return;
}

第二步，使用我们沿途更新的&mut指针进行循环是棘手的。

默认情况下，Rust会重新借用解引用的&mut。它不会消耗引用，只要借用的产物仍然存活，就会将其视为已借用。

显然，在这里这种方法行不通。我们想要从旧的current“交接”到新的current。我们可以强制&mut指针遵守移动语义。

我们需要这个（identity函数强制执行移动！）：

match moving(current).next

我们还可以这样写：

let tmp = current;
match tmp.next

或者是这样的：

match {current}.next

第三步，在我们查找里面的内容后，我们没有当前指针，所以需要调整代码。

使用ref mut slot获取下一个值的位置。