首页 > ACM题库 > HDU-杭电 > HDU 1504 Disk Tree-模拟-[解题报告] C++
2013
12-12

HDU 1504 Disk Tree-模拟-[解题报告] C++

Disk Tree

问题描述 :

Hacker Bill has accidentally lost all the information from his workstation’s hard drive and he has no backup copies of its contents. He does not regret for the loss of the files themselves, but for the very nice and convenient directory structure that he had created and cherished during years of work. Fortunately, Bill has several copies of directory listings from his hard drive. Using those listings he was able to recover full paths (like "WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86") for some directories. He put all of them in a file by writing each path he has found on a separate line. Your task is to write a program that will help Bill to restore his state of the art directory structure by providing nicely formatted directory tree.

输入:

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

The first line of the input contains single integer number N (1 <= N <= 500) that denotes a total number of distinct directory paths. Then N lines with directory paths follow. Each directory path occupies a single line and does not contain any spaces, including leading or trailing ones. No path exceeds 80 characters. Each path is listed once and consists of a number of directory names separated by a back slash ("\").

Each directory name consists of 1 to 8 uppercase letters, numbers, or the special characters from the following list: exclamation mark, number sign, dollar sign, percent sign, ampersand, apostrophe, opening and closing parenthesis, hyphen sign, commercial at, circumflex accent, underscore, grave accent, opening and closing curly bracket, and tilde ("!#$%&’()-@^_`{}~").

输出:

Write to the output the formatted directory tree. Each directory name shall be listed on its own line preceded by a number of spaces that indicate its depth in the directory hierarchy. The subdirectories shall be listed in lexicographic order immediately after their parent directories preceded by one more space than their parent directory. Top level directories shall have no spaces printed before their names and shall be listed in lexicographic order. See sample below for clarification of the output format.

样例输入:

1

7
WINNT\SYSTEM32\CONFIG
GAMES
WINNT\DRIVERS
HOME
WIN\SOFT
GAMES\DRIVERS
WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86

样例输出:

GAMES
 DRIVERS
HOME
WIN
 SOFT
WINNT
 DRIVERS
 SYSTEM32
  CERTSRV
   CERTCO~1
    X86
  CONFIG

转载请注明出处:http://blog.csdn.net/a1dark

分析:查了一下这题、发现网上没有什么关于这道题的解题报告、其实题目意思挺好懂的、就是给你一些文件的目录结构、然后让你把它们组合在一起、然后按照目录结构输出、注意是字典序、这道题是一个模拟、主要是对结构体和指针的掌握、使用嵌套结构体模拟文件的同级和子级文件、然后进行读取、插入、查询等操作、代码如下(0ms):

#include<stdio.h>
#include<string.h>
struct node{  
    node *child;
    node *brother;
    char key[10]; 
};
int n,m;
node *root;
void getname(char *str,char *key,int &j)
{
    int i;
    for(i=0;str[j]!='\0'&&str[j]!='\\';i++,j++)
        key[i]=str[j];
    key[i]='\0';
}
node *insert(node *parent,char *key)
{
    node *p,*q,*t;
    if(!parent->child||strcmp(parent->child->key,key)>0)
    {
        t=new node;
        strcpy(t->key,key);
        t->child=NULL;
        t->brother=parent->child;
        parent->child=t;
        return t;
    }
    if(strcmp(parent->child->key,key)==0)
        return parent->child;
    for(p=parent->child,q=p->brother;q&&strcmp(q->key,key)<0;p=q,q=q->brother);
    if(!q||strcmp(q->key,key)>0)
    {
        t=new node;
        strcpy(t->key,key);
        t->brother=p->brother;
        p->brother=t;
        t->child=NULL;
        return t;
    }
    return q;
}
void read()
{
    char str[90],key[9];
    int i,cur;
    node *p;
    root=new node;
    root->child=NULL;
    scanf("%d",&n);
    for(i=m=0;i<n;i++)
    {
        cur=0;
        scanf("%s",str);
        getname(str,key,cur);
        for(p=insert(root,key);str[cur]!='\0';)
        {
            getname(str,key,++cur);
            p=insert(p,key);
        }
    }
}
void find(node *p,int k)
{
    int i;
    for(;p;p=p->brother)
    {
        for(i=0;i<k;i++)
            putchar(' ');
        puts(p->key);
        if(p->child)
            find(p->child,k+1);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        read();
        find(root->child,0);
        if(t)
            printf("\n");
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/a1dark/article/details/10366437


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。