dan*_*nda 4 tree recursion hierarchy hierarchical rust
我的输入是文件系统路径的平面列表，这些路径都是单个顶级目录的子目录（或其中的文件）。
\n\n我的最终输出应该是：
\n\n我创建了一个中间数据结构，它是一个自引用，具有名称和\'ed childstruct Dir向量。Boxstruct Dir
我可以成功地Dir用来表示任意目录树，如下面的输出所示。
我正在考虑使用堆栈来处理列表，Dir为每个子目录添加一个并在升序时弹出，但我似乎无法像使用 C 或其他语言那样使用 Rust。无论我尝试什么，我都会遇到编译器错误。
如何将平面列表转换为 aDir并使编译器满意？或者，如何以不同的方式实现（1）和（2）？
代码：
\n\n// A type to represent a path, split into its component parts\n#[derive(Debug)]\nstruct Path {\n parts: Vec<String>,\n}\nimpl Path {\n pub fn new(path: &str) -> Path {\n Path {\n parts: path.to_string().split("/").map(|s| s.to_string()).collect(),\n }\n }\n}\n\n// A recursive type to represent a directory tree.\n// Simplification: If it has children, it is considered\n// a directory, else considered a file.\n#[derive(Debug)]\nstruct Dir {\n name: String,\n children: Vec<Box<Dir>>,\n}\n\nimpl Dir {\n fn new(name: &str) -> Dir {\n Dir {\n name: name.to_string(),\n children: Vec::<Box<Dir>>::new(),\n }\n }\n\n fn has_child(&self, name: &str) -> bool {\n for c in self.children.iter() {\n if c.name == name {\n return true;\n }\n }\n false\n }\n\n fn add_child<T>(mut self, leaf: T) -> Self\n where\n T: Into<Dir>,\n {\n self.children.push(Box::new(leaf.into()));\n self\n }\n}\n\nfn dir(val: &str) -> Dir {\n Dir::new(val)\n}\n\nfn main() {\n // Form our INPUT: a list of paths.\n let paths = vec![\n Path::new("root/child1/grandchild1.txt"),\n Path::new("root/child1/grandchild2.json"),\n Path::new("root/child2/grandchild3.pdf"),\n Path::new("root/child3"),\n ];\n println!("Input Paths:\\n{:#?}\\n", paths);\n\n // Transformation:\n // I need an algorithm here that converts the list of paths\n // above to a recursive struct (tree) below.\n // ie: paths --> dir\n let top = dir("root");\n let mut cwd = ⊤\n for p in paths.iter() {\n for part in p.parts.iter() {\n if !cwd.has_child(part) {\n // cwd.add_child(dir(part));\n // cwd = &cwd.children[cwd.children.len() - 1];\n }\n }\n }\n\n // Intermediate Representation:\n // The above transformation should result in the following\n // hierarchical structure.\n let top = dir("root")\n .add_child(\n dir("child1")\n .add_child(dir("grandchild1.txt"))\n .add_child(dir("grandchild2.json")),\n )\n .add_child(dir("child2").add_child(dir("grandchild3.pdf")))\n .add_child(dir("child3"));\n println!("Intermediate Representation of Dirs:\\n{:#?}\\n\\nOutput Tree Format:\\n", top);\n\n // Output: textual `tree` format\n print_dir(&top, 0);\n}\n\n// A function to print a Dir in format similar to unix `tree` command.\nfn print_dir(dir: &Dir, depth: u32) {\n if depth == 0 {\n println!("{}", dir.name);\n } else {\n println!(\n "{:indent$}{} {}",\n "",\n "\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80",\n dir.name,\n indent = ((depth as usize) - 1) * 4\n );\n }\n\n for child in dir.children.iter() {\n print_dir(child, depth + 1)\n }\n}\n输出：
\n\n// A type to represent a path, split into its component parts\n#[derive(Debug)]\nstruct Path {\n parts: Vec<String>,\n}\nimpl Path {\n pub fn new(path: &str) -> Path {\n Path {\n parts: path.to_string().split("/").map(|s| s.to_string()).collect(),\n }\n }\n}\n\n// A recursive type to represent a directory tree.\n// Simplification: If it has children, it is considered\n// a directory, else considered a file.\n#[derive(Debug)]\nstruct Dir {\n name: String,\n children: Vec<Box<Dir>>,\n}\n\nimpl Dir {\n fn new(name: &str) -> Dir {\n Dir {\n name: name.to_string(),\n children: Vec::<Box<Dir>>::new(),\n }\n }\n\n fn has_child(&self, name: &str) -> bool {\n for c in self.children.iter() {\n if c.name == name {\n return true;\n }\n }\n false\n }\n\n fn add_child<T>(mut self, leaf: T) -> Self\n where\n T: Into<Dir>,\n {\n self.children.push(Box::new(leaf.into()));\n self\n }\n}\n\nfn dir(val: &str) -> Dir {\n Dir::new(val)\n}\n\nfn main() {\n // Form our INPUT: a list of paths.\n let paths = vec![\n Path::new("root/child1/grandchild1.txt"),\n Path::new("root/child1/grandchild2.json"),\n Path::new("root/child2/grandchild3.pdf"),\n Path::new("root/child3"),\n ];\n println!("Input Paths:\\n{:#?}\\n", paths);\n\n // Transformation:\n // I need an algorithm here that converts the list of paths\n // above to a recursive struct (tree) below.\n // ie: paths --> dir\n let top = dir("root");\n let mut cwd = ⊤\n for p in paths.iter() {\n for part in p.parts.iter() {\n if !cwd.has_child(part) {\n // cwd.add_child(dir(part));\n // cwd = &cwd.children[cwd.children.len() - 1];\n }\n }\n }\n\n // Intermediate Representation:\n // The above transformation should result in the following\n // hierarchical structure.\n let top = dir("root")\n .add_child(\n dir("child1")\n .add_child(dir("grandchild1.txt"))\n .add_child(dir("grandchild2.json")),\n )\n .add_child(dir("child2").add_child(dir("grandchild3.pdf")))\n .add_child(dir("child3"));\n println!("Intermediate Representation of Dirs:\\n{:#?}\\n\\nOutput Tree Format:\\n", top);\n\n // Output: textual `tree` format\n print_dir(&top, 0);\n}\n\n// A function to print a Dir in format similar to unix `tree` command.\nfn print_dir(dir: &Dir, depth: u32) {\n if depth == 0 {\n println!("{}", dir.name);\n } else {\n println!(\n "{:indent$}{} {}",\n "",\n "\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80",\n dir.name,\n indent = ((depth as usize) - 1) * 4\n );\n }\n\n for child in dir.children.iter() {\n print_dir(child, depth + 1)\n }\n}\n由于有人删除了我之前的答案并附有工作代码的链接，因此我将在此处发布完整的工作代码。
\n\n// A type to represent a path, split into its component parts\n#[derive(Debug)]\nstruct Path {\n parts: Vec<String>,\n}\nimpl Path {\n pub fn new(path: &str) -> Path {\n Path {\n parts: path.to_string().split("/").map(|s| s.to_string()).collect(),\n }\n }\n}\n\n// A recursive type to represent a directory tree.\n// Simplification: If it has children, it is considered\n// a directory, else considered a file.\n#[derive(Debug, Clone)]\nstruct Dir {\n name: String,\n children: Vec<Box<Dir>>,\n}\n\nimpl Dir {\n fn new(name: &str) -> Dir {\n Dir {\n name: name.to_string(),\n children: Vec::<Box<Dir>>::new(),\n }\n }\n\n fn find_child(&mut self, name: &str) -> Option<&mut Dir> {\n for c in self.children.iter_mut() {\n if c.name == name {\n return Some(c);\n }\n }\n None\n }\n\n fn add_child<T>(&mut self, leaf: T) -> &mut Self\n where\n T: Into<Dir>,\n {\n self.children.push(Box::new(leaf.into()));\n self\n }\n}\n\nfn dir(val: &str) -> Dir {\n Dir::new(val)\n}\n\nfn main() {\n // Form our INPUT: a list of paths.\n let paths = vec![\n Path::new("child1/grandchild1.txt"),\n Path::new("child1/grandchild2.json"),\n Path::new("child2/grandchild3.pdf"),\n Path::new("child3"),\n ];\n println!("Input Paths:\\n{:#?}\\n", paths);\n\n // Transformation:\n // A recursive algorithm that converts the list of paths\n // above to Dir (tree) below.\n // ie: paths --> dir\n let mut top = dir("root");\n for path in paths.iter() {\n build_tree(&mut top, &path.parts, 0);\n }\n\n println!(\n "Intermediate Representation of Dirs:\\n{:#?}\\n\\nOutput Tree Format:\\n",\n top\n );\n\n // Output: textual `tree` format\n print_dir(&top, 0);\n}\n\nfn build_tree(node: &mut Dir, parts: &Vec<String>, depth: usize) {\n if depth < parts.len() {\n let item = &parts[depth];\n\n let mut dir = match node.find_child(&item) {\n Some(d) => d,\n None => {\n let d = Dir::new(&item);\n node.add_child(d);\n match node.find_child(&item) {\n Some(d2) => d2,\n None => panic!("Got here!"),\n }\n }\n };\n build_tree(&mut dir, parts, depth + 1);\n }\n}\n\n// A function to print a Dir in format similar to unix `tree` command.\nfn print_dir(dir: &Dir, depth: u32) {\n if depth == 0 {\n println!("{}", dir.name);\n } else {\n println!(\n "{:indent$}{} {}",\n "",\n "\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80",\n dir.name,\n indent = ((depth as usize) - 1) * 4\n );\n }\n\n for child in dir.children.iter() {\n print_dir(child, depth + 1)\n }\n}\n| 归档时间： |
|
| 查看次数： |
1736 次 |
| 最近记录： |