目录树（30 分）

阳光穿透心脏的1/2处 2022-05-07 23:26 205阅读 0赞

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

## 输入格式: ##

输入首先给出正整数N（≤104），表示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

主要思路就是对树的节点的遍历，以及处理好各节点的关系不要搞乱了，还有就是有一个坑点，这个’c\\‘虽然输出是’c’，但是它是排在‘b’前面的，也就是说可以把它当成目录处理，只不过里面没有文件。

#include <bits/stdc++.h>
    
    using namespace std;
    struct File
    {
         
        char name[300];
    };
    struct Node
    {
         
        char name[300];
        Node* next[300];
        File* files[300];
        int next_cnt=0;//子目录个数
        int files_cnt=0;//文件个数
    };
    int Nodecmp(Node* a,Node* b)//目录字典序排序
    {
         
        return strcmp(a->name,b->name)<0;
    }
    int Filecmp(File* a,File* b)//文件字典序排序
    {
         
        return strcmp(a->name,b->name)<0;
    }
    void PlantTree(Node* p,char *s)
    {
         
        int t=0,pos,len=strlen(s);
        for(pos=0;s[pos]!='\\'&&pos<len;pos++);//找到第一个‘\’
        if(s[pos]=='\\'){
         
            char str[300];
            int f=0;
            strncpy(str,s,pos);//将'\'前的字符串赋值给str
            str[pos]='\0';
            Node *a;
            for(int i=0;i<p->next_cnt;i++){
         
                if(strcmp(str,p->next[i]->name)==0){
         //如果已经存在此目录
                    f=1;
                    a=p->next[i];//赋值给a，用于下一次调用
                    break;
                }
            }
            if(f==0){
         //如果不存在此目录
                a=(Node*)malloc(sizeof(Node));
                strcpy(a->name,str);
                a->files_cnt=0;
                a->next_cnt=0;
                p->next[p->next_cnt]=a;//将此目录存入节点中
                p->next_cnt++;//子目录数+1
            }
            if(pos<strlen(s)-1)PlantTree(a,s+pos+1);//如果之后还有字符串，继续调用自身函数
            else return;
        }
        else{
         //如果是一个文件
            File* b=(File*)malloc(sizeof(File));
            strcpy(b->name,s);
            p->files[p->files_cnt]=b;//将此文件存入节点中
            p->files_cnt++;//文件数+1
            return;
        }
    }
    void PrintTree(Node* p,int n)
    {
         
        for(int i=0;i<n;i++)cout<<"  ";//每递归调用一次就是目录更深一次，空两个空格
        cout<<p->name<<endl;//输出目录
        n++;
        sort(p->next,p->next+p->next_cnt,Nodecmp);//排序
        for(int i=0;i<p->next_cnt;i++)PrintTree(p->next[i],n);//递归调用，依次输出文件和目录
        sort(p->files,p->files+p->files_cnt,Filecmp);//排序
        for(int i=0;i<p->files_cnt;i++){
         
            for(int j=0;j<n;j++)cout<<"  ";
            cout<<p->files[i]->name<<endl;//输出文件
        }
        return;
    }
    int main()
    {
         
        int n;
        cin>>n;
        Node* root=(Node*)malloc(sizeof(Node));
        strcpy(root->name,"root");
        for(int i=0;i<n;i++){
         
            char s[300];
            cin>>s;
            PlantTree(root,s);
        }
        PrintTree(root,0);
        return 0;
    }