Как иметь несколько ссылок для одного узла в древовидной структуре, используя Rust - PullRequest
Новая
       42

Как иметь несколько ссылок для одного узла в древовидной структуре, используя Rust

0 голосов
/ 03 ноября 2019

Попытка создать дерево в ржавчине со следующей структурой: 

pub struct Node{
    pub children: Vec<Box<Node>>,
    pub parent: Option<Box<Node>>,
    pub value: f32,
    //.....
}

Для создания нового узла используется следующая функция: 

pub fn build_node(parent: Option<Box<Node>>)-> Node{
    Node{
        children: vec![],
        parent,
        value: 0.0,

    }
}

При попытке добавить узлы,например, с: 

let mut root_nd = tree::build_node(None, 5, state);
let mut next_nd = tree::build_node(Some(Box::new(root_nd)), 2);
root_nd.children.push(Box::new(next_nd));

Будут ошибки, потому что я заимствую, например, root_nd, а затем пытаюсь добавить next_nd в список root.children, и даже если не было этой ошибки, япо-прежнему нужно иметь ссылку для next_nd после добавления ее к потомкам root_nd. Я знаю, что в ржавчине невозможно иметь несколько изменяемых ссылок одновременно для одного и того же элемента. Таким образом, вопрос заключается в том, как можно создать древовидную структуру данных с двунаправленными ссылками в ржавчине? В моей голове это конфликт, так как rust не хочет множественных ссылок, но мне нужен узел в середине дерева, на который будут ссылаться как его родительский узел, так и его дочерние узлы.

1 Ответ

1 голос
/ 03 ноября 2019

В последнее время я довольно много врывался в деревья в Русте. Для работы с деревьями в ржавчине вам понадобится Rc (однопоточный указатель подсчета ссылок) , чтобы вы могли иметь несколько владельцев. Вам также понадобится RefCell, чтобы включить внутреннюю изменчивость, так как компилятор не допускает множественные изменяемые ссылки. С Rc и RefCell вы можете определить свой TreeNode следующим образом: 

use std::rc::Rc;
use std::cell::RefCell;

pub struct TreeNode {
    pub children: Vec<Rc<RefCell<TreeNode>>>,
    pub parent: Option<Rc<RefCell<TreeNode>>>,
    pub value: f32,
}

И вот один способ создать два узла, которые ссылаются друг на друга: 

impl TreeNode {
  #[inline]
  pub fn new(value: f32) -> Self {
    TreeNode {
      value,
      children: vec![],
      parent: None
    }
  }
}

let mut root_nd = Rc::new(RefCell::new(TreeNode::new(5.0)));
let mut child_nd = Rc::new(RefCell::new(TreeNode::new(2.0)));

child_nd.borrow_mut().parent = Some(root_nd.clone());  // use Rc::clone to create a new reference to root_nd
root_nd.borrow_mut().children.push(child_nd.clone());

Поскольку мы используем Rc::clone для создания новой ссылки на узел, root_nd и child_nd не используются и могут быть доступны в более поздней программе.

Дополнительные примеры деревьев вRust:

...