POJ 1057 File Mapping 最详细的解题报告

浏览数：52 / 时间：2015年06月11日

题目大意：像我的电脑那样显示文件夹和文件信息，其中在同一级目录内，文件夹排在文件的前面并且文件夹的顺序不变，同一级目录中文件按字母序排列。文件以‘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 }