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);
}
评论