使用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;
}
实测结果:
全部评论

相关推荐

珩珺:那些经历都太大太空了,实习的情况不了解,大创项目连名字、背景、目的及意义都没体现出来;地摊经济更是看完连卖的什么产品都不知道,项目成果直接写营收多少都更直观真实一点;后面那个校文体部的更是工作内容是组织活动整理流程,成果变成了当志愿者,而且你们学校本科学生会大一入学就直接当部长吗,志愿里面还提到了疫情防控,全面解封是22年12月的事情,可能时间上也有冲突。可能你花了钱人家就用AI给你随便写了点内容改了一下,没什么体现个性化的点
点赞 评论 收藏
分享
评论
11
1
分享

创作者周榜

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