PTA 7-9 目录树

7-9 目录树（30 分）

在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。

输入格式:

输入首先给出正整数N（ $\leq 1 0^{ 4 }$ ），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：

路径和名称中的字符仅包括英文字母（区分大小写）；
符号“\”仅作为路径分隔符出现；
目录以符号“\”结束；
不存在重复的输入项目；
整个输入大小不超过2MB。

输出格式:

假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。

输入样例:

7
b
c\
ab\cd
a\bc
ab\d
a\d\a
a\d\z\

输出样例:

root
  a
    d
      z
      a
    bc
  ab
    cd
    d
  c
  b

作者: DS课程组

单位: 浙江大学

时间限制: 400ms

内存限制: 64MB

思考过程:

一看就是建树题。为了方便处理，分为两种节点，目录（Tree）和文件（File）。文件只储存一个name，目录则储存有：name，子目录数组（child），子文件目录（files），和两个数组的元素数目（child_num 和 files_num）。递归建树时传入字符串和父目录（parent）。

然后进行递归建树，依据传入字符串不同大致有三种情况：\后还有字符，则取第一个\前的字符串为name，查找一下父目录的child里面是否已有，无则创个加进去，修改字符串和parent后在递归（修改字符串直接用地址指针操作）；\后无字符，操作基本和前者相同，但不用在进行递归；查找不到\,说明这是个File，直接创个新的File加进去就ok。

输出自然也是递归，注意把files放在chiid后面输出，别忘了排字典序。

题外话:

对树一直略有恐惧，好歹这次分两次，一次大概两个小时，终于弄出来了，果然贼爽。其中还重写了一次，果然搞得晕了还是重写比较好，瞎改没有未来。遇到个奇怪的问题，本来是用qsort来排序的，以为会快些，但排出来总是个错的，“ab”总在“a”的前面，换用sort，比较语句也没有变，结果就对了。之前用qsort也出现过其它的奇怪现象，实在搞不懂。一开始name还有数组开的都比较小，怕超时，没想到题目还有个最长name测试例，没想到加大依然过，我好像总是低估了电脑的内存和运算能力。

代码:

#include 

using namespace std;
typedef struct File_ *File;
typedef struct File_
{
    char name[270];
};
typedef struct Node *Tree;
typedef struct Node
{
    char name[270];
    Tree child[507];
    File files[507];
    int child_num = 0;
    int files_num = 0;
};
bool cmp1(Tree a, Tree b)
{
    return strcmp(a -> name, b -> name) < 0;
}
bool cmp2(File a, File b)
{
    return strcmp(a -> name, b -> name) < 0;
}
void solve(char *s, Tree parent)
{
    int finds = 0, pos = 0,len = strlen(s);
    for(; (s[pos] != 92) && pos < len; ++pos)
        ;
    if(s[pos] == 92)
    {
            char name_[270];
            int exist = 0;
            strncpy(name_,s,pos);
            name_[pos] = '\0';
            Tree now ;
            for(int i = 0; i < parent -> child_num; ++i)
            {
                if(strcmp(name_, parent -> child[i] -> name) == 0)
                {
                    exist = 1;
                    now = parent -> child[i];
                    break;
                }
            }
            if(!exist)
            {
                now = (Tree)malloc(sizeof(Node));
                strcpy(now -> name, name_);
                now -> child_num = 0;
                now -> files_num = 0;
                parent -> child[parent ->child_num] = now;
                parent ->child_num++;
            }
            if(pos <(strlen(s)-1))
            {
                solve(s + pos +1, now);
            }
            else
            return ;
    }
    else
    {
        File newone = (File)malloc(sizeof(File_));
        strcpy(newone -> name,s);
        parent -> files[parent -> files_num] = newone;
        parent -> files_num++;
        return ;
    }
}
void PrintTree(Tree now, int depth)
{
    for(int i = 0; i < depth; ++i)
        printf("  ");
    printf("%s\n",now -> name);
    depth++;
    sort(now -> child, now -> child + now -> child_num, cmp1);
    for(int i = 0; i < now -> child_num; ++i)
        PrintTree(now -> child[i], depth);
    sort(now -> files, now -> files + now -> files_num, cmp2);
    for(int i = 0; i < now -> files_num; ++i)
    {
        for(int i1 = 0; i1 < (depth); ++i1)
        {
            printf("  ");
        }
        printf("%s\n",now -> files[i] -> name);
    }
    return ;
}
int main()
{
    int n;
    scanf("%d", &n);
    Tree root = (Tree)malloc(sizeof(Node));
    strcpy(root -> name, "root");
    while(n--)
    {
        char str[270];
        scanf("%s",str);
        solve(str, root);
    }
    PrintTree(root,0);
    return 0;
}#include
using namespace std;

const int MAXN = 2e6 +10;
const int inf = 1e5 + 10;
struct Node
{
    char id[20];
    int length;
    int next ;
    Node()
    {
        length = 0;
    }
}paser[MAXN];
int n,m,k;
int start = 0,head[MAXN];
int Hash (char *s)
{
    long long ans = 0;
    for(int i = 0; i <17; ++i)
    {
        ans = ans*10 + s[i] - '0';
    }
    if(s[17] == 'x') ans += 1e18;
    else ans = ans * 10 + s[17] - '0';
    return ans%inf;
}
void Insert ()
{
    char str[20];
    int num;
    scanf("%s%d",str, &num);
    int pos = Hash(str);
    int ok = 0;
    num = max(num,m);
    for(int i = head[pos]; i != -1; i = paser[i].next)
    {
        if(strcmp(paser[i].id, str)==0)
        {
            paser[i].length += num;
            ok = 1;
        }
    }
    if(!ok)
    {
        strcpy(paser[start].id,str);
        paser[start].length = num;
        paser[start].next = head[pos];
        head[pos] = start++;
    }
}
void PrintAns()
{
    char str[20];
    scanf("%s",str);
    int num = Hash(str),ok = 0;
    for(int i = head[num]; i != -1; i = paser[i].next)
    {
        if( strcmp(paser[i].id,str)==0)
        {
            printf("%d\n",paser[i].length);
            return ;
        }
    }
    puts("No Info");
    return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i = 0 ; i < n; ++i)
        Insert();
    scanf("%d", &k);
    while(k--)
    {
        PrintAns();
    }

}