如何实现链表的加法? [英] How to implement an addition method of linked list?

问题描述

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

I want to create a simple linked list and add a value into it. How should the add method be implemented to make this code output 100 50 10 5 at line 42, the second root.print() call?

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();
}

(游乐场)

我重写了这个函数:

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(_) 分支来遍历列表?

I don't understand why it says that item was previously moved if it's used only once, and how the Some(_) branch should be implemented to iterate through the list?

推荐答案

这就是你需要的写法 (游乐场链接)

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,
        };
    }
}

好的，这是什么?

第一步，我们需要在使用值item后立即return.然后编译器正确地看到它只从一次移动.

Step 1, we need to return immediately after using the value item. Then the compiler correctly sees that it is only moved from once.

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

第 2 步，使用我们沿途更新的 &mut 指针进行循环很棘手.

Step 2, to loop with a &mut pointer that we update along the way is tricky.

默认情况下，Rust 会重新借用一个被取消引用的&mut.它不会消耗引用，它只是认为它是借用的，只要借用的产品还活着.

By default, Rust will reborrow a &mut that is dereferenced. It doesn't consume the reference, it just considers it borrowed, as long as the product of the borrow is still alive.

显然，这在这里效果不佳.我们想要从旧的 current 到新的 current 的切换".我们可以强制 &mut 指针服从改为移动语义.

Obviously, this doesn't work very well here. We want a "hand off" from the old current to the new current. We can force the &mut pointer to obey move semantics instead.

我们需要这个(identity 函数强制移动！):

We need this (the identity function forces move!):

match moving(current).next 

我们也可以这样写:

let tmp = current;
match tmp.next

或者这个:

match {current}.next

第 3 步，我们在里面查找后没有当前指针，因此请调整代码.

Step 3, we have no current pointer after we looked up inside it, so adapt the code to that.

• 使用 ref mut slot 来获取下一个值的位置.

• Use ref mut slot to get a hold on the location of the next value.

这篇关于如何实现链表的加法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！