首页 > 代码库 > 1777:文件结构“图”

1777:文件结构“图”

这是一个关于格式化输出目录结构的问题,感觉这类问题用堆栈做更顺手,不过题目在递归里面,那就用递归做。

总时间限制: 1000ms 内存限制: 65536kB描述在计算机上看到文件系统的结构通常很有用。Microsoft Windows上面的"explorer"程序就是这样的一个例子。但是在有图形界面之前,没有图形化的表示方法的,那时候最好的方式是把目录和文件的结构显示成一个""的样子,而且使用缩排的形式来表示目录的结构。比如:ROOT|     dir1|     file1|     file2|     file3|     dir2|     dir3|     file1file1file2这个图说明:ROOT目录包括三个子目录和两个文件。第一个子目录包含3个文件,第二个子目录是空的,第三个子目录包含一个文件。输入你的任务是写一个程序读取一些测试数据。每组测试数据表示一个计算机的文件结构。每组测试数据以*结尾,而所有合理的输入数据以#结尾。一组测试数据包括一些文件和目录的名字(虽然在输入中我们没有给出,但是我们总假设ROOT目录是最外层的目录)。在输入中,以]表示一个目录的内容的结束。目录名字的第一个字母是d,文件名字的第一个字母是f。文件名可能有扩展名也可能没有(比如fmyfile.dat和fmyfile)。文件和目录的名字中都不包括空格,长度都不超过30。一个目录下的子目录个数和文件个数之和不超过30。输出在显示一个目录中内容的时候,先显示其中的子目录(如果有的话),然后再显示文件(如果有的话)。文件要求按照名字的字母表的顺序显示(目录不用按照名字的字母表顺序显示,只需要按照目录出现的先后显示)。对每一组测试数据,我们要先输出"DATA SET x:",这里x是测试数据的编号(从1开始)。在两组测试数据之间要输出一个空行来隔开。你需要注意的是,我们使用一个|和5个空格来表示出缩排的层次。样例输入file1file2dir3dir2file1file2]]file4dir1]file3*file2file1*#样例输出DATA SET 1:ROOT|     dir3|     |     dir2|     |     file1|     |     file2|     dir1file1file2file3file4DATA SET 2:ROOTfile1file2提示一个目录和它的子目录处于不同的层次一个目录和它的里面的文件处于同一层次

在编码的时候,一直用的是string类,所以长度不超过30什么的就呵呵了。解码的思路就是遇到“]”的时候返回上级,遇到"d"开头(目录)的时候进入下级,遇到文件就在当前级。所以构建一个目录结构:

struct dir{    string name;                //目录名    dir *parent;                //父目录    vector<dir*>childs;        //子目录    vector<string>files;        //所含文件    dir(){        name="ROOT";        parent=0;    }    dir(string name){        this->name=name;    }    void clear(){        parent=0;        this->childs.clear();        this->files.clear();    }};

这里遇到一个问题,现在还不理解,就是结构中用vector<dir>childs,声明时用dir *child=new child的时候,虽然在我的电脑上得到的结果与现在的相同,但不会通过。c++这低级的高级语言确实挺烦人的,指针和引用、垃圾回收、关键字多用途等等很多不统一的东西,总感觉这楼什么地方被刻意扭曲了,难道.和->也统一不了吗,==和=、&&和&等等也统一不了吗?很多冗余的东西,越写越烦。有了这个结构之后,先处理一组输入数据:

void readdir(dir &cur,vector<string>&str,int i){    if(i<int(str.size())){        if(str[i][0]==]){                    //返回上级目录            readdir(*cur.parent,str,i+1);        }else if(str[i][0]==f){            //所含文件            cur.files.push_back(str[i]);            readdir(cur,str,i+1);        }else if(str[i][0]==d){            //子目录            dir *child=new dir(str[i]);            child->parent=&cur;            cur.childs.push_back(child);            readdir(*child,str,i+1);        }        }}

这样就把str表示的目录转换成了一个树形。之后就是输出的问题了,依次输出目录名、子目录、文件,子目录进行递归,文件先排序:

void outputdir(dir cur,int depth){    int i;    string tab;    for(i=0;i<depth;i++){                            //计算缩进        tab+="|     ";    }    cout<<tab<<cur.name<<endl;    for(i=0;i<int(cur.childs.size());i++){        //输出目录        outputdir(*cur.childs[i],depth+1);    }    sort(cur.files.begin(),cur.files.end());        //排序文件    for(i=0;i<int(cur.files.size());i++){            //输出文件        cout<<tab<<cur.files[i]<<endl;    }}void outputdataset(dir root,int idx){    cout<<"DATA SET "<<idx<<":"<<endl;    outputdir(root,0);    cout<<endl;}

后面那个小函数怎么说呢,和算法一点也没关系的东西,硬添加进去还全然没有意义。main函数的处理很简单:

int main(){    dir root;    vector<string>str;    string line;    cin>>line;    int idx=1;    while(line!="#"){        if(line=="*"){            readdir(root,str,0);                //解析            outputdataset(root,idx);        //输出            idx++;                                //输入数据组数计数            str.clear();                            //清理            root.clear();        }else{            str.push_back(line);            //保存目录数据        }        cin>>line;    }}

使用的头文件如下:

#include<iostream>#include<string>#include<vector>#include<algorithm>

代码不多,但是这个题做的确实很烦得慌。

 

1777:文件结构“图”