首页 > ACM题库 > 九度OJ > 九度-1090-路径打印[解题代码]
2013
12-12

九度-1090-路径打印[解题代码]

题目来源:2005年上海交通大学计算机研究生机试真题

题目描述:

给你一串路径,譬如:
a\b\c
a\d\e
b\cst
d\
你把这些路径中蕴含的目录结构给画出来,子目录直接列在父目录下面,并比父目录向右缩一格,就像这样:
a
  b
    c
  d 
    e
b
  cst
d
同一级的需要按字母顺序排列,不能乱。

输入:

    每个测试案例第一行为一个正整数n(n<=10)表示有n个路径,当n为0时,测试结束,接下来有n行,每行有一个字串表示一个路径,长度小于50。

输出:

输出目录结构,每一个测试样例的输出紧跟一个空行。

样例输入:
4
a\b\c
a\d\e
b\cst
d\
0
样例输出:
a
  b
    c
  d
    e
b
  cst
d


java 代码如下:
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
	static int n;
	static Node root; //定义一个根节点
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			n = scanner.nextInt();
			if(n == 0)
				break;
			String str;
			Node root = new Node();
			root.key = "";
			root.subString = "";
			root.children = new TreeSet<Node>();
			for (int i = 0; i < n; i++) {
				str = scanner.next();
				root.addChild(new Node(str.split("\\\\"), 0, root));
			}

			
			root.print();
			System.out.println();
		}
	}
}

class Node implements Comparable<Node> {
	public String key;
	public String subString;
	public TreeSet<Node> children;
	public Node father;
	public int pre;

	public int compareTo(Node o) { //定义比较函数。即比较前缀 a\b\ == a\b\, 是一个目录
		return this.subString.compareTo(o.subString);
	}
	public Node() {}
	public Node(String str[], int index, Node f) {
		this.subString = "";
		if (index == str.length)
			return;
		for (int i = 1; i <= index; i++)
			this.subString += str[i] + '\\';
		if (index == 0)
			this.subString = str[0];
		this.key = str[index];
		this.pre = f.pre + f.key.length() + 1;
		this.father = f;
		if (index != str.length) {
			if (this.children == null)
				this.children = new TreeSet<Node>();
			children.add(new Node(str, index + 1, this));
		}
	}

	public void addChild(Node n) {  //添加一个孩子节点
		//由于孩子节点可能重复,重新合并
		if (children.contains(n)) {
			Node temp = null;
			for (Node temp2 : children) {
				if (temp2.compareTo(n) == 0)
					temp = temp2;
			}
			temp.addChild(n.children.first());
		} else {
			children.add(n);
		}
	}

	public void print() {
		if (this.key == null)
			return;
		if(this.key != ""){
			pre--; //由于第一个位置会多个空格
			while (pre-- > 0)
				System.out.print(" ");
			System.out.println(key);
		}
		if (this.children != null && children.size() > 0) {
			for (Node n : children)
				n.print();
		}
	}
}

/**************************************************************
	Problem: 1090
	User: coder
	Language: Java
	Result: Accepted
	Time:110 ms
	Memory:15720 kb
****************************************************************/

cpp 代码如下:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
	static int n;
	static Node root; //定义一个根节点
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			n = scanner.nextInt();
			if(n == 0)
				break;
			String str;
			Node root = new Node();
			root.key = "";
			root.subString = "";
			root.children = new TreeSet<Node>();
			for (int i = 0; i < n; i++) {
				str = scanner.next();
				root.addChild(new Node(str.split("\\\\"), 0, root));
			}

			
			root.print();
			System.out.println();
		}
	}
}

class Node implements Comparable<Node> {
	public String key;
	public String subString;
	public TreeSet<Node> children;
	public Node father;
	public int pre;

	public int compareTo(Node o) { //定义比较函数。即比较前缀 a\b\ == a\b\, 是一个目录
		return this.subString.compareTo(o.subString);
	}
	public Node() {}
	public Node(String str[], int index, Node f) {
		this.subString = "";
		if (index == str.length)
			return;
		for (int i = 1; i <= index; i++)
			this.subString += str[i] + '\\';
		if (index == 0)
			this.subString = str[0];
		this.key = str[index];
		this.pre = f.pre + f.key.length() + 1;
		this.father = f;
		if (index != str.length) {
			if (this.children == null)
				this.children = new TreeSet<Node>();
			children.add(new Node(str, index + 1, this));
		}
	}

	public void addChild(Node n) {  //添加一个孩子节点
		//由于孩子节点可能重复,重新合并
		if (children.contains(n)) {
			Node temp = null;
			for (Node temp2 : children) {
				if (temp2.compareTo(n) == 0)
					temp = temp2;
			}
			temp.addChild(n.children.first());
		} else {
			children.add(n);
		}
	}

	public void print() {
		if (this.key == null)
			return;
		if(this.key != ""){
			pre--; //由于第一个位置会多个空格
			while (pre-- > 0)
				System.out.print(" ");
			System.out.println(key);
		}
		if (this.children != null && children.size() > 0) {
			for (Node n : children)
				n.print();
		}
	}
}

/**************************************************************
	Problem: 1090
	User: coder
	Language: Java
	Result: Accepted
	Time:90 ms
	Memory:15760 kb
****************************************************************/


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。