7-30 目录树 (30分)-轻识

7-30 目录树 (30分)

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

输入格式:

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

代码：

#include <iostream>
#include <string.h>
#include<algorithm>
using namespace std;

struct File{
	char Name[300];
}; 
struct Node{
	char Name[300];
	Node* Next[300];//子目录 
	File* Files[300];//文件 
	int NextCnt = 0;//子目录个数
	int FilesCnt = 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);//目录树的构建
void PrintTree(Node* p, int n);//按要求输出目录树

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;
} 

void PlantTree(Node* p, char *s){//p为当前根节点，s为当前路径//p初始为root,随递归调用向后移
	int t=0, pos, len=strlen(s);
	for(pos=0;s[pos]!='\\' && pos<len;pos++);//找到第一个'\',即当前路径起始节点结束位置
	if(s[pos]=='\\'){//字符格式为'\x'
		char str[300];//暂存此路径起始节点
		int f=0;//f=0表示此路径起始节点在目录树中尚未收录
		strncpy(str,s,pos);//将'\'前的字符串赋值给str
		str[pos] = '\0';//末尾位置为\0结束
		Node* a;//暂存当前路径起始节点，若已有则存为Next[i]，否则新建
		for(int i=0;i<p->NextCnt;i++){//依次检查当前根节点的所有子目录//因为题中说所有目录相对于root
			if(strcmp(str, p->Next[i]->Name)==0){//如果已经存在此目录 
				f = 1;//f置1，表示已收录
				a = p->Next[i];//赋值给a，用于下一次调用
				break; //已收录并找到则终止循环
			}
		}
		if(f==0){//如果尚未收录
			a = (Node*)malloc(sizeof(Node));//新建节点
			strcpy(a->Name, str);//名称为之前暂存的名称
			a->FilesCnt = 0;//文件数为0
			a->NextCnt = 0;//子目录数为0
			p->Next[p->NextCnt] = a;//将此目录存入当前根节点的子目录中
			p->NextCnt++;//当前根节点子目录数+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->FilesCnt] = b;//将此文件存入当前根节点文件中 
		p->FilesCnt++;//文件数+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->NextCnt, NodeCmp);//子目录排序
	for(int i=0;i<p->NextCnt;i++) PrintTree(p->Next[i], n);//递归调用，依次输出文件和目录
	sort(p->Files, p->Files+p->FilesCnt, FileCmp);//文件排序
	for(int i=0;i<p->FilesCnt;i++){
		for(int j=0;j<n;j++) cout<<"  ";//n为当前层数 
		cout<<p->Files[i]->Name<<endl;//输出文件 
	} 
	return; 
}

思路：

建树，结点包含文件夹名字以及子文件夹数组和文件数组，按照要求输出。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct cata {
    char name[300];
    vector<cata> sub;
    vector<string> file;
    cata(){} 
    cata(char *name) {
        strcpy(this -> name,name);
    }
    cata *find1(char *subname) {
        for(int i = 0;i < sub.size();i ++) {
            if(!strcmp(sub[i].name,subname)) return &sub[i];
        }
        return NULL;
    }
    bool find2(char *filename) {
        for(int i = 0;i < file.size();i ++) {
            if(!strcmp(file[i].c_str(),filename)) return true;
        }
        return false;
    }
}root,*l,*temp;
int n,c;
char s[300],ch;
void print(const char *t,int h) {
    for(int i = 0;i < h;i ++) printf("  ");
    printf("%s\n",t);
}
bool cmp(cata &a,cata &b) {
    return strcmp(a.name,b.name) < 0;
}
void dfs(cata node,int h) {
    for(int i = 0;i < h;i ++) printf("  ");
    printf("%s\n",node.name);
    sort(node.sub.begin(),node.sub.end(),cmp);
    for(int i = 0;i < node.sub.size();i ++) {
        dfs(node.sub[i],h + 1);
    }
    sort(node.file.begin(),node.file.end());
    for(int i = 0;i < node.file.size();i ++) {
        print(node.file[i].c_str(),h + 1);
    }
}
int main() {
    scanf("%d",&n);
    strcpy(root.name,"root");
    getchar();
    for(int i = 0;i < n;i ++) {
        l = &root;
        while((ch = getchar()) != '\n') {
            if(ch == '\\') {
                s[c] = 0;
                c = 0;
                temp = l -> find1(s);
                if(!temp) l -> sub.push_back(cata(s)),temp = &*(l -> sub.rbegin());
                l = temp;
            }
            else s[c ++] = ch;
        }
        if(c) {
            s[c] = 0;
            c = 0;
            if(!l -> find2(s)) l -> file.push_back(s);
        }
    }
    dfs(root,0);
}