使用Map建树并自动排序

路径打印

http://www.nowcoder.com/questionTerminal/64b472c9bed247b586859978d13145ad

使用Map建树并自动排序

刚开始没细看题目,以为只要按目录层级打印对应数量的缩进符号和目录名称就可以了,但仔细一看发现坑点来了:
  1. 输出结果存在全局目录结构关系(例如:第一层级的目录a包含了b、d两个子目录,但他们来自两个输入,并且在输出时父目录a只输出一次。这就需要对不同输入目录之间的包含关系进行记录)
  2. 同层级的目录要按字典序输出(样例中二级目录b先于目录d打印,即使两个目录输入顺序颠倒也应如此)
整理一下需求:
  1. 需要从原始路径串中截取每级目录的名称( 例如"a/b/cst" => {1级"a", 2级"b", 3级"cst"} )
  2. 需要维护一个目录树,能够查询插入 (使用结构体Dir实现, 子目录容器用map实现提高查询效率)
  3. 需要按字典序输出(子目录容器map以<string name, Dir>对表示,自动以name的字典序排序)
C++ STL 中的map容器底层是一颗红黑树,排序准则是key的升序,使用迭代器访问元素实体即可得到其排序序列,所以是实现以上需求的最佳选择。
#include <iostream>
#include <string>
#include <map>
using namespace std;

struct Dir{
    int level; map<string, Dir> kids;  // map的迭代器将将按照key升序序, string的比较器默认为字典序
    Dir():level(0){}
    Dir(int l):level(l){}
};

void print_dir(Dir& d){
    for(auto pair : d.kids){
        for(int i=0;i<d.level;i++) cout<<"  ";  // 按层级打印缩进符号 (题目缩进 = 两个空格)
        cout<<pair.first<<endl;  // 打印目录名称
        print_dir(pair.second); // 递归打印子目录
    }
}

int main(){
    iostream::sync_with_stdio(false);
    int n; string path;
    while(cin>>n && n!=0){
        Dir root(0);
        while(n--){
            cin>>path;
            int pos=0, end=0; Dir* p = &root;
            while(pos<path.size()){  // 截取各级目录名称并构建目录树
                end = path.find('\\', pos);
                if(end == string::npos) end = path.size()+1;  // 边界处理
                const string& cwd = path.substr(pos, end-pos);  // 目录名截取
                if(p->kids.find(cwd) == p->kids.end()) // 查询并插入
                    p->kids[cwd] = Dir(p->level+1);
                pos = end+1; p = &(p->kids[cwd]);
            }
        }
        print_dir(root); cout<<endl;
    }
    return 0;
}
实测结果:
全部评论

相关推荐

半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
评论
11
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务