题目描述

Problem B: 目录树
Time Limit: 1 Sec Memory Limit: 128 MB
Total Submissions: 276 Accepted: 198 Creator: admin

Problem Description

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

Input Description

输入首先给出正整数N（≤10^4），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：
•路径和名称中的字符仅包括英文字母（区分大小写）；
•符号“\”仅作为路径分隔符出现；
•目录以符号“\”结束；
•不存在重复的输入项目；
•整个输入大小不超过2MB。

Output Description

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

Sample Input

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

Sample Output

root
a
d
z
a
bc
ab
cd
d
c
b

Hint

基本概念

构建树的思路

在这里插入图片描述

ac代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
    char name[300];
    struct node *child_head;
    struct node *child_file;
    struct node *next;
}lg;
int zd_strcmp(char *s1,char *s2)	//排序
{
    int len1=strlen(s1);
    int len2=strlen(s2);
    int len;
    if(len1<=len2)len=len1;
    else if(len1>len2)len=len2;
    for(int i=0;i<len;i++)
    {
        if(s1[i]<s2[i])return -1;
        else if(s1[i]>s2[i])return 1;
    }
    if(len1==len2)return 0;
    else if(len1<len2)return -1;
    else return 1;
}
void get_name(char *str,int s,int e,char *ss)	//取字符名字函数
{
    for(int i=0;i<e-s+1;i++)
    {
        str[i]=ss[s+i];
    }
}
void file_insert(char *name,char *pre,lg** root)	//文件插入
{
    lg *p,*q,*cur=NULL;
    p=(lg*)malloc(sizeof(lg));
    strcpy(p->name,name);
    p->child_file=NULL;
    p->child_head=NULL;
    p->next=NULL;
    q=(*root)->child_file;
    if(q==NULL)
    {
        (*root)->child_file=p;
        return ;
    }
    for(;q!=NULL;cur=q,q=q->next)
    {
        if(cur==NULL)
        {
            if(zd_strcmp(p->name,q->name)==0)return ;
            if(zd_strcmp(p->name,q->name)<0)
            {
                (*root)->child_file=p;
                p->next=q;
                return ;
            }
        }
        else
        {
            if(zd_strcmp(p->name,q->name)==0)return ;
            if(zd_strcmp(p->name,cur->name)>0&&zd_strcmp(p->name,q->name)<0)
            {
                cur->next=p;
                p->next=q;
                return ;
            }
        }
    }
    cur->next=p;
    p->next=NULL;
    return ;
}
lg* tree_insert(char *name,char *pre,lg* root)		//目录插入
{
    lg* p,*cur=NULL,*q;
    p=(lg*)malloc(sizeof(lg));
    strcpy(p->name,name);
    p->child_head=NULL;
    p->child_file=NULL;
    p->next=NULL;
    q=root->child_head;
    if(q==NULL)
    {
        root->child_head=p;
        return p;
    }
    for(;q!=NULL;cur=q,q=q->next)
    {
        if(cur==NULL)
        {
            if(zd_strcmp(p->name,q->name)==0)
            {
                return q;
            }
            if(zd_strcmp(p->name,q->name)<0)
            {
                root->child_head=p;
                p->next=q;
                return p;
            }
        }
        else
        {
            if(zd_strcmp(p->name,q->name)==0)return q;
            if(zd_strcmp(p->name,cur->name)>0&&zd_strcmp(p->name,q->name)<0)
            {
                cur->next=p;
                p->next=q;
                return p;
            }
        }
    }
    cur->next=p;
    p->next=NULL;
    return p;
}
void BL(lg* root,int num)		//遍历输出
{
    lg *p,*q;

    if(root!=NULL){
    for(int i=0;i<num;i++)
        printf("  ");
    printf("%s\n",root->name);
    BL(root->child_head,num+1);
    BL(root->child_file,num+1);
    BL(root->next,num);
    }
}
int main()
{
    int n,len;
    char l[300],name[300],pre_name[300];
    lg *root;
    root=(lg*)malloc(sizeof(lg));
    strcpy(root->name,"root");
    root->child_head=NULL;
    root->next=NULL;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",l);
        len=strlen(l);
        int start=0,end=0;
        lg *gg;
        gg=root;
        strcpy(pre_name,"root");
        for(int i=0;i<len;i++)
        {
            if(i==len-1)
            {
                memset(name,0,sizeof(name));
                if(l[i]=='\\'){
                    end=i-1;
                    get_name(&name,start,end,l);
                    gg=tree_insert(name,pre_name,gg);
                }
                else{ end=i;
                get_name(&name,start,end,l);
                file_insert(name,pre_name,&gg);}
                memset(pre_name,0,sizeof(pre_name));
            }
            else if(l[i]=='\\')
            {
                memset(name,0,sizeof(name));
                end=i-1;
                get_name(&name,start,end,l);
                gg=tree_insert(name,pre_name,gg);
                strcpy(pre_name,name);
                start=i+1;
            }
        }
    }
    BL(root,0);
    return 0;
}
/*
7
b
c\
ab\cd
a\bc
ab\d
a\d\a
a\d\z\
*/