使用Map建树并自动排序
路径打印
http://www.nowcoder.com/questionTerminal/64b472c9bed247b586859978d13145ad
使用Map建树并自动排序
刚开始没细看题目,以为只要按目录层级打印对应数量的缩进符号和目录名称就可以了,但仔细一看发现坑点来了:
- 输出结果存在全局目录结构关系(例如:第一层级的目录a包含了b、d两个子目录,但他们来自两个输入,并且在输出时父目录a只输出一次。这就需要对不同输入目录之间的包含关系进行记录)
- 同层级的目录要按字典序输出(样例中二级目录b先于目录d打印,即使两个目录输入顺序颠倒也应如此)
整理一下需求:
- 需要从原始路径串中截取每级目录的名称( 例如"a/b/cst" => {1级"a", 2级"b", 3级"cst"} )
- 需要维护一个目录树,能够查询和插入 (使用结构体Dir实现, 子目录容器用map实现提高查询效率)
- 需要按字典序输出(子目录容器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; }实测结果: