ural(Timus) 1067. Disk Tree

数据结构：暴力（可用哈希优化）+建树+前序遍历

题意：输入行数n，下面n行是一下文件的路径（和平常使用的电脑一样），一整行数据中没有空格（还好，别有搞些空格出来），要你整理好所有文件的路径，从根开始，输出所有的文件夹名

首先一点，我们要名字，在同一个文件夹下，是不会有重名的文件夹的

即

ab

ab

这种是非法的（和电脑一样），但是输入中可以有，有的话只是一种重复输入，不是代表a下面真的有两个b

然后不同文件夹下可以由相同的名字，就好比你D盘和E盘都有一个文件夹叫“电影”

例如

ab

db

这种是合法的在输入中也是会出现的，看case就知道。

另外，每个文件夹都只有一个双亲

好像abcd , 你要找d，输入中会不会出现 ad 或者 abd  acd 呢？ 是不会的！因为这题是严格按照电脑的模式来搞的，在电脑中你要找d，其路径必定是abcd

这就可以保证每个文件夹的双亲是唯一的，就是它前面那个文件夹

最后最重要的一点：

ab

db

这里的b是两个不同的b，虽然名字一样，所以我们确定一个文件夹，是怎么确定，首先看名字，名字不同，一定是不同的文件夹，名字相同，看它的双亲（唯一的），如果双亲不同它们不是同一个人文件夹，如果相同，那么是同一个文件夹。

所以我们没读入一个文件夹，就给它映射成一个标号，每个不同的文件夹对应一个不同的标号，然后用这些标号来建树即可，建完数，将每个节点的孩子名字按字典序排序再前序遍历输出

关键是怎么映射标号，用哈希就是个不错的选择，而且题目说了，每个文件夹的名字长度为1-8。

不过我这里是用暴力，直接O(n)扫描给每个文件夹名字标号

这题应该来说是用哈希做的，或者什么其他方法，但是我是用暴力，时间比较糟糕1.1s，不过还是过，整个题目的关键是怎么给文件夹的表示，即怎么映射地好，然后建树，前序遍历整个树输出即可

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 550 //500行输入
#define M 20100 //最多文件夹数
char name[M][20];
int par[M];
int sonnum[M];
struct Son
{
int son[110]; //10000在test#10爆内存，改为1000还爆，改到100就AC了，所以孩子数最多就100
}s[M];
int n,namenum,root;
int search(char *str , int p)
{
for(int i=0; i<namenum; i++)
if(!strcmp(name[i] , str) && par[i]==p)
return i;
strcpy(name[namenum] , str);
par[namenum]=p;
sonnum[namenum]=0; //记得
return namenum;
}
void input()
{
namenum=0;
memset(par,-1,sizeof(par));
for(int nn=1; nn<=n; nn++)
{
char str[110],tmp[20];
int i,j,k,len,PAR,SON;
scanf("%s",str);
len=strlen(str);
for(i=0,j=0; i<len && str[i]!='\'; i++,j++)
tmp[j]=str[i];
tmp[j]=''; i++;
PAR=search(tmp,-1);
if(PAR==namenum) namenum++;
while(i<len)
{
for(j=0; i<len && str[i]!='\'; i++,j++)
tmp[j]=str[i];
tmp[j]=''; i++;
SON=search(tmp,PAR);
if(SON==namenum) //说明是一个新单词

{
namenum++;
int sn = sonnum[PAR]++; //PAR这个节点的孩子要增加
s[PAR].son[sn] = SON;
}
PAR=SON;
}
}
root=namenum++;
sonnum[root]=0;
for(int i=0; i<root; i++)
if(par[i]==-1)
{
par[i]=root;
int sn=sonnum[root]++;
s[root].son[sn]=i;
}
}
int cmp_str(int a ,int b)
{
char name_1[20] , name_2[20];
strcpy(name_1 , name[a]);
strcpy(name_2 , name[b]);
return strcmp(name_1 , name_2)<0 ;
}
void SORT()
{
for(int i=0; i<namenum; i++)
{
int sn=sonnum[i];
sort(s[i].son , s[i].son+sn , cmp_str);
}
}
void travel(int rt , int level)
{
for(int i=0; i<level; i++)
printf(" ");
printf("%sn",name[rt]);
for(int i=0; i<sonnum[rt]; i++)
{
int son=s[rt].son[i];
travel(son,level+1);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
input();
SORT(); //对所有节点的孩子按字典序排序
for(int i=0; i<sonnum[root]; i++)
{
int son=s[root].son[i];
travel(son,0);
}
}
return 0;
}