题目描述在图形用户界面出现之前计算机用户常通过缩进形式查看目录结构。本题要求模拟文件系统的目录映射给定一系列目录名以d开头和文件名以f开头以及目录结束标记]输出缩进形式的目录树要求每个目录下先显示子目录按输入顺序再显示文件按字母序。每个数据集以*结束整个输入以#结束。输入格式输入包含多个数据集。每个数据集的开始是若干行每行一个字符串表示文件名以f开头或目录名以d开头或目录结束标记]。数据集以单独一行*结束。整个输入以单独一行#结束。输出格式对于每个数据集输出DATA SET X: ROOT然后按缩进方式输出目录结构子目录先出现后跟文件文件按字母序排列。每个目录的缩进为|竖线加五个空格。不同数据集之间用一个空行分隔。样例输入file1 file2 dir3 dir2 file1 file2 ] ] file4 dir1 ] file3 * file2 file1 * #输出DATA SET 1: ROOT | dir3 | | dir2 | | file1 | | file2 | dir1 file1 file2 file3 file4 DATA SET 2: ROOT file1 file2题目分析本题要求模拟文件系统的目录遍历并按特定顺序输出。目录名和文件名由首字符区分d和f目录结束用]表示。数据结构上需要维护一个当前路径栈以及每个目录下的文件集合自动按字母序排序。子目录在遇到d时立即输出缩进后并压栈遇到]时输出当前目录的所有文件缩进后然后出栈遇到f时将文件名加入当前目录的文件集合。整个数据集结束后根目录的文件也需要输出。由于输入规模较小直接模拟即可。解题思路维护一个栈indexer表示当前目录的路径使用一个映射dirs存储目录编号到目录名的对应关系另一个映射files存储每个目录下的文件集合setstring自动排序。对于每个数据集输出标题DATA SET X:和ROOT。初始化根目录编号 0名称为ROOT压栈。循环读取每一行若为*或#退出循环。若以f开头将文件名插入当前目录的文件集合。若以d开头创建新目录分配新编号输出缩进后的目录名压栈。若为]则输出当前目录的所有文件缩进后然后出栈。数据集结束时输出根目录的所有文件。缩进控制输出时除根目录外每层缩进为| 缩进次数等于当前栈深度减111因为根目录不缩进。复杂度分析每个文件或目录处理一次时间复杂度O(NlogK)O(N \log K)O(NlogK)其中NNN为条目总数KKK为每个目录下的文件数排序开销。空间复杂度O(N)O(N)O(N)。代码实现// File Mapping// UVa ID: 645// Verdict: Accepted// Submission Date: 2018-03-28// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;string line;while(getline(cin,line)){if(line#)break;if(cases0)cout\n;coutDATA SET cases:\n;coutROOT\n;intidx0;vectorintindexer;mapint,stringdirs;mapint,setstringfiles;dirs[idx]ROOT;indexer.push_back(idx);do{if(line*)break;if(line.front()f)files[indexer.back()].insert(line);elseif(line.front()d){dirs[idx]line;indexer.push_back(idx);for(inti1;iindexer.size();i)cout| ;coutdirs[indexer.back()]\n;}else{for(autof:files[indexer.back()]){for(inti1;iindexer.size();i)cout| ;coutf\n;}indexer.pop_back();}}while((getline(cin,line)));for(autof:files[0])coutf\n;}return0;}总结本题通过栈模拟目录嵌套利用set自动排序文件实现了目录结构的缩进输出。关键点在于正确处理目录的进入和退出]以及输出顺序子目录先于文件文件按字母序。由于输入规模较小模拟法简洁高效。注意输出格式中的缩进和空行控制。
基于)
