При удалении узла из односвязного списка возникает ошибка «невозможно выйти из заимствованного содержимого» - PullRequest
Новая
       12

При удалении узла из односвязного списка возникает ошибка «невозможно выйти из заимствованного содержимого»

0 голосов
/ 02 июля 2018

Я делаю односвязный список. Когда вы удаляете узел, next предыдущего узла должен стать next (prev->next = curr->next;) текущего узла и вернуть data, если индекс совпадает. В противном случае предыдущий узел становится текущим узлом, а текущий узел становится следующим узлом (prev = curr; curr = curr->next;): 

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl LinkedList<i64> {
    fn remove(&mut self, index: usize) -> i64 {
        if self.len() == 0 {
            panic!("LinkedList is empty!");
        }
        if index >= self.len() {
            panic!("Index out of range: {}", index);
        }
        let mut count = 0;
        let mut head = &self.head;
        let mut prev: Option<Box<Node<i64>>> = None;
        loop {
            match head {
                None => {
                    panic!("LinkedList is empty!");
                }
                Some(c) => {
                    // I have borrowed here
                    if count == index {
                        match prev {
                            Some(ref p) => {
                                p.next = c.next;
                                //       ^ cannot move out of borrowed content
                            }
                            _ => continue,
                        }
                        return c.data;
                    } else {
                        count += 1;
                        head = &c.next;
                        prev = Some(*c);
                        //          ^^ cannot move out of borrowed content
                    }
                }
            }
        }
    }

    fn len(&self) -> usize {
        unimplemented!()
    }
}

fn main() {}

error[E0594]: cannot assign to field `p.next` of immutable binding
  --> src/main.rs:31:33
   |
30 |                             Some(ref p) => {
   |                                  ----- consider changing this to `ref mut p`
31 |                                 p.next = c.next;
   |                                 ^^^^^^^^^^^^^^^ cannot mutably borrow field of immutable binding

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:31:42
   |
31 |                                 p.next = c.next;
   |                                          ^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:40:37
   |
40 |                         prev = Some(*c);
   |                                     ^^ cannot move out of borrowed content

Playground Link для получения дополнительной информации.

Как я могу это сделать? Мой подход неверен?

1 Ответ

0 голосов
/ 02 июля 2018

Прежде чем начать, прочитайте Изучение ржавчины со слишком большим количеством связанных списков . Люди думают, что связанные списки просты , потому что их учили на языках, которые либо не заботятся о том, что вы вводите небезопасную память, либо полностью лишаете это агентство программиста.

Ржавчина не делает ни того, ни другого, а это значит, что вы должны думать о вещах, о которых вы, возможно, никогда раньше не думали.

Есть ряд проблем с вашим кодом. Тот, о котором вы спрашиваете, «не может выйти из заимствованного контента», уже хорошо охвачен множеством других вопросов, поэтому нет причин повторять все эти хорошие ответы:

TL; DR: вы пытаетесь переместить владение next из ссылки; ты не можешь. 

p.next = c.next;

Вы пытаетесь изменить неизменяемую ссылку: 

let mut head = &self.head;

Вы позволяете людям убрать один конец конца, что не имеет смысла для меня: 

if index >= self.len()

Вы итерируете все дерево не один раз, а дважды , прежде чем повторять его снова, чтобы выполнить удаление: 

if self.len() == 0
if index >= self.len()

Все это меркнет по сравнению с тем фактом, что ваш алгоритм некорректен в глазах Rust, потому что вы пытаетесь ввести изменяемый псевдоним . Если бы ваш код мог компилироваться, у вас была бы изменяемая ссылка на previous, а также изменяемая ссылка на current. Однако, вы можете получить изменяемую ссылку на current из previous. Это позволит вам нарушить гарантии безопасности памяти Rust!

Вместо этого вы можете отслеживать только current и, когда правильный индекс найден, разбить его на части и разложить кусочки: 

fn remove(&mut self, index: usize) -> T {
    self.remove_x(index)
        .unwrap_or_else(|| panic!("index {} out of range", index))
}

fn remove_x(&mut self, mut index: usize) -> Option<T> {
    let mut head = &mut self.head;

    while index > 0 {
        head = match { head }.as_mut() {
            Some(n) => &mut n.next,
            None => return None,
        };
        index -= 1;
    }

    match head.take().map(|x| *x) {
        Some(Node { data, next }) => {
            *head = next;
            Some(data)
        }
        None => None,
    }
}

Смотри также:

Playground Link для получения дополнительной информации.

Есть множество проблем с остальным кодом, например, тот факт, что результат вашего insert метода не похож ни на один, который я когда-либо видел.

Как бы я это написал .

...