首页 > 代码库 > POJ 1057 File Mapping 最详细的解题报告
POJ 1057 File Mapping 最详细的解题报告
题目来源：POJ 1057 File Mapping
题目大意：像我的电脑那样显示文件夹和文件信息，其中在同一级目录内，文件夹排在文件的前面并且文件夹的顺序不变，同一级目录中文件按字母序排列。文件以‘f’开头，文件夹以‘d’开头，‘*’表示一个case的结束，‘#’表示所有输入内容结束。
解题思路：递归创建，最后递归输出。算法比较简单，我就不细说了，具体看代码：
具体算法（java版，可以直接运行）
1 import java.util.*; 2 3 public class Main { 4 public static void main(String[] args) { 5 Scanner input = new Scanner(System.in); 6 Node root = null; 7 Node parent = null; 8 String line = ""; 9 int count = 1; 10 do { 11 root = new DirectoryNode("ROOT", null); 12 parent = root; 13 do { 14 line = input.next(); 15 if (line != null && !line.isEmpty()) { 16 line = line.trim(); 17 Node childNode=null; 18 if (line.startsWith("f")) { 19 childNode=new FileNode(line,parent); 20 parent.children.add(childNode); 21 }else if (line.startsWith("d")) { 22 childNode=new DirectoryNode(line,parent); 23 parent.children.add(childNode); 24 parent=childNode; 25 }else if (line.startsWith("]")) { 26 if(parent!=null){ 27 parent=parent.parent; 28 } 29 } 30 } 31 } while (!line.startsWith("*")); 32 System.out.println(String.format("DATA SET %s:", count++)); 33 root.output(); 34 if(!line.startsWith("#")){ 35 System.out.println(); 36 } 37 } while (!line.startsWith("#")); 38 } 39 } 40 41 abstract class Node { 42 public String name; 43 public Node parent; 44 public String prefix; 45 public List<Node> children; 46 47 public Node(String name, Node parent) { 48 this.name = name; 49 this.parent = parent; 50 this.prefix = ""; 51 if (this.parent != null) { 52 this.prefix = this.parent.prefix + this.prefix; 53 } 54 this.children = new ArrayList<Node>(); 55 } 56 57 public void sort() { 58 Collections.sort(this.children, new Comparator<Node>() { 59 public int compare(Node left, Node right) { 60 if (left instanceof DirectoryNode) { 61 return -1; 62 }else{ 63 if (right instanceof FileNode){ 64 return left.name.compareTo(right.name); 65 }else{ 66 return 1; 67 } 68 } 69 } 70 }); 71 } 72 73 public abstract void output(); 74 } 75 76 class FileNode extends Node { 77 78 public FileNode(String name, Node parent) { 79 super(name, parent); 80 } 81 82 @Override 83 public void output() { 84 if (this.parent != null) { 85 this.prefix = this.parent.prefix + this.prefix; 86 } 87 System.out.println(this.prefix + this.name); 88 } 89 } 90 91 class DirectoryNode extends Node { 92 93 public DirectoryNode(String name, Node parent) { 94 super(name, parent); 95 } 96 97 @Override 98 public void output() { 99 if (this.parent != null) {100 this.prefix = this.parent.prefix + "| ";101 }102 System.out.println(this.prefix + this.name);103 this.sort();104 for (Node child : this.children) {105 child.output();106 }107 }108 }
PS：本人比较喜欢设计模式，因此在写算法的时候也会想用一些设计模式里面的知识，其实在ACM比赛中，这样是不好的，效率低。
如果有哪里不清楚的，可以给我留言！
POJ 1057 File Mapping 最详细的解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。