首页 > ACM题库 > POJ 1057 FILE MAPPING [解题报告] Java
2013
11-09

POJ 1057 FILE MAPPING [解题报告] Java

FILE MAPPING

问题描述 :

It is often helpful for computer users to see a visual representation of the file structure on their computers. The “explorer” in Microsoft Windows is an example of such a system. Before the days of graphical user interfaces, however, such visual representations were not possible. The best that could be done was to show a static “map”of directories and files, using indentation as a guide to directory contents. For example:
ROOT

| DIR1
| File1
| File2
| File3
| DIR2
| DIR3
| File1
File1
File2

This shows that the root directory contains two files and three subdirectories. The first subdirectory contains 3 files, the second is empty and the third contains one file.

输入:

Write a program that reads a series of data sets representing a computer file structure. A data set ends with a line containing a single *, and the end of valid data is denoted by a line containing a single #. The data set contains a series of file and directory names. (The root directory is assumed to be the starting point.) The end of a directory is denoted by a ‘]’ Directory names begin with a lower case ‘d’ and file names begin with a lower case ‘f’ File names may or may not have an extension (such as fmyfile.dat or fmyfile). File and directory names may not contain spaces.

输出:

Note that the contents of any directory should list any subdirectories first, followed by files, if any. All files should be in alphabetical order within each directory. Note that each data set output is marked by the label “DATA SET x:” where x denotes the number of the set, beginning at 1. Note also the blank line between the output data sets. Each level of indentation should show a ‘|’ followed by 5 spaces.

样例输入:

file1
file2
dir3
dir2
file1
file2
]
]
file4
dir1
]
file3
*
file2
file1
*
#

样例输出:

DATA SET 1:
ROOT
|     dir3
|     |     dir2
|     |     file1
|     |     file2
|     dir1
file1
file2
file3
file4

DATA SET 2:
ROOT
file1
file2

解题代码:

/* @author:[email protected] */
import java.io.*;
public class Main {
  public static void main(String[] args) throws Exception{
//System.setIn(new FileInputStream(new File("E:\\in.txt")));
//System.setOut(new PrintStream(new File("E:\\out.txt")));
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String s;
  Node root=new Node("ROOT",null);
  Node curr=root;
  Node t,n;
  int count=1;
  tag:
  while(true){
    switch((s=br.readLine()).charAt(0)){
       case 'f':
         t=new Node(s,curr);
	  if(curr.fleftmost==null)
	  	curr.fleftmost=t;
	  else{
	     if(t.compareTo(curr.fleftmost)< 0){
	     	t.frightsib=curr.fleftmost;
	     	curr.fleftmost=t;
	     }else{
		n=curr.fleftmost;
		while(n.frightsib!=null&&t.compareTo(n.frightsib)>0){
		   n=n.frightsib;
		}
		t.frightsib=n.frightsib;
		n.frightsib=t;
	     }
	 }
	 break;
      case 'd':
	  t=new Node(s,curr);
	  if(curr.dleftmost==null)
	    curr.dleftmost=curr.drightmost=t;
	  else{
	    curr.drightmost.drightsib=t;
	    curr.drightmost=t;
	   }
	   curr=curr.drightmost;
	   break;
	case ']':
	   curr=curr.parent;
	   break;
	case '*':
	    print(root,count++);
	    curr=root=new Node("ROOT",null);
	    break;
	case '#':
	    break tag;
     }
   }
  }

 static void print(Node root,int count) {
   System.out.println("DATA SET "+count+":");
   print0(root,0);
   System.out.println();
 }

static void print0(Node root, int d) {
   for(int i=0;i< d;i++){
	System.out.print("|     ");
    }
    System.out.println(root.content);
	Node t=root.dleftmost;
	while(t!=null){
		print0(t,d+1);
		t=t.drightsib;
	}
	t=root.fleftmost;
	while(t!=null){
		print0(t,d);
		t=t.frightsib;
	}
  }
}
class Node implements Comparable< Node>{
	String content;
	Node parent;
	Node fleftmost;
	Node frightsib;
	Node dleftmost;
	Node drightsib;
	Node drightmost;
	Node(String c,Node n){
		content=c;
		parent=n;
	}
	@Override
	public int compareTo(Node o) {
		return this.content.compareTo(o.content);
	}
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  3. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧