/ 猿问

# 如何在安全Rust中表达相互递归的数据结构？

2019-10-21 09:53:31

struct Node

{

Node* parent; // should be mutable, and nullable (no parent)

std::vector<Node*> child;

virtual ~Node()

{

for(auto it = child.begin(); it != child.end(); ++it)

{

delete *it;

}

}

{

if (newNode->parent)

{

newNode->parent.child.erase(newNode->parent.child.find(newNode));

}

newNode->parent = this;

child.push_back(newNode);

}

}

## 3 回答

pub struct Node1 {

children: Vec<Node1>,

}

use std::collections::BTreeMap;

type Id = usize;

pub struct Tree {

descendants: BTreeMap<Id, Node2>,

root: Option<Id>,

}

pub struct Node2 {

parent: Id,

children: Vec<Id>,

}

use std::cell::RefCell;

use std::rc::{Rc, Weak};

// Note: do not derive Clone to make this move-only.

pub struct Node3(Rc<RefCell<Node3_>>);

pub type WeakNode3 = Weak<RefCell<Node3>>;

pub struct Node3_ {

parent: Option<WeakNode3>,

children: Vec<Node3>,

}

impl Node3 {

pub fn add(&self, node: Node3) {

// No need to remove from old parent; move semantics mean that must have

self.children.push(node);

}

}

extern crate typed_arena; // 1.4.1

use std::{cell::{Cell, RefCell}, fmt};

use typed_arena::Arena;

struct Tree<'a, T: 'a> {

nodes: Arena<Node<'a, T>>,

}

impl<'a, T> Tree<'a, T> {

fn new() -> Tree<'a, T> {

Self {

nodes: Arena::new(),

}

}

fn new_node(&'a self, data: T) -> &'a mut Node<'a, T> {

self.nodes.alloc(Node {

data,

tree: self,

parent: Cell::new(None),

children: RefCell::new(Vec::new()),

})

}

}

struct Node<'a, T: 'a> {

data: T,

tree: &'a Tree<'a, T>,

parent: Cell<Option<&'a Node<'a, T>>>,

children: RefCell<Vec<&'a Node<'a, T>>>,

}

impl<'a, T> Node<'a, T> {

fn add_node(&'a self, data: T) -> &'a Node<'a, T> {

let child = self.tree.new_node(data);

child.parent.set(Some(self));

self.children.borrow_mut().push(child);

child

}

}

impl<'a, T> fmt::Debug for Node<'a, T>

where

T: fmt::Debug,

{

fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {

write!(f, "{:?}", self.data)?;

write!(f, " (")?;

for c in self.children.borrow().iter() {

write!(f, "{:?}, ", c)?;

}

write!(f, ")")

}

}

fn main() {

let tree = Tree::new();

println!("{:?}", head); // 1 (2 (), 3 (), )

}

• 3 回答
• 0 关注
• 236 浏览

0/150