UVa 645 File Mapping-拓冰建站

题目描述

在图形用户界面出现之前，计算机用户常通过缩进形式查看目录结构。本题要求模拟文件系统的目录映射，给定一系列目录名（以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存储每个目录下的文件集合（set<string>自动排序）。
对于每个数据集：
- 输出标题DATA SET X:和ROOT。
- 初始化根目录（编号 0，名称为"ROOT"），压栈。
- 循环读取每一行：
  - 若为"*"或"#"，退出循环。
  - 若以'f'开头，将文件名插入当前目录的文件集合。
  - 若以'd'开头，创建新目录（分配新编号），输出缩进后的目录名，压栈。
  - 若为"]"，则输出当前目录的所有文件（缩进后），然后出栈。
- 数据集结束时，输出根目录的所有文件。
缩进控制：输出时，除根目录外，每层缩进为"| "，缩进次数等于当前栈深度减111（因为根目录不缩进）。

复杂度分析

每个文件或目录处理一次，时间复杂度O(Nlog⁡K)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//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;string line;while(getline(cin,line)){if(line=="#")break;if(cases++>0)cout<<'\n';cout<<"DATA SET "<<cases<<":\n";cout<<"ROOT\n";intidx=0;vector<int>indexer;map<int,string>dirs;map<int,set<string>>files;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(inti=1;i<indexer.size();i++)cout<<"| ";cout<<dirs[indexer.back()]<<'\n';}else{for(autof:files[indexer.back()]){for(inti=1;i<indexer.size();i++)cout<<"| ";cout<<f<<'\n';}indexer.pop_back();}}while((getline(cin,line)));for(autof:files[0])cout<<f<<'\n';}return0;}