荒芜知地

Knowhere

0%

目录管理器

发表于 分类于 Valine：

目录管理器

问题描述

写一个目录管理器。
初始时，硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。
命令 类型 实现 说明
MKDIR s 操作 在当前目录下创建一个子目录 s，s 是一个字符串 创建成功输出 “OK“；若当前目录下已有该子目录则输出 “ERR“
RM s 操作 在当前目录下删除子目录 s，s 是一个字符串 删除成功输出 “OK“；若当前目录下该子目录不存在则输出 “ERR“
CD s 操作 进入一个子目录 s，s 是一个字符串(执行后，当前目录可能会改变) 进入成功输出 “OK“；若当前目录下该子目录不存在则输出 “ERR“
特殊地，若 s 等于 “..“ 则表示返回上级目录，同理，返回成功输出 “OK“，返回失败（当前目录已是根目录没有上级目录）则输出 “ERR“
SZ 询问 输出当前目录的大小 也即输出 1+当前目录的子目录数
LS 询问 输出多行表示当前目录的 “直接子目录” 名 若没有子目录，则输出 “EMPTY“；若子目录数∈ [1,10] 则全部输出；若子目录数大于 10，则输出前 5 个，再输出一行 “...“，输出后 5 个。
TREE 询问 输出多行表示以当前目录为根的子树的前序遍历结果 若没有后代目录，则输出 “EMPTY“；若 后代目录数+1 (当前目录) ∈ [1,10] 则全部输出；若后代目录数+1 (当前目录) 大于 10，则输出前 5 个，再输出一行 “...“，输出后 5 个。若目录结构如图1，当前目录为 “root“ 执行结果如图2
UNDO 特殊 撤销操作 撤销最近一个 “成功执行” 的操作（即成功的MKDIR或RM或CD）的影响，撤销成功输出 “OK“ , 没有操作用于撤销则输出 “ERR“

directory_manager_01.png

Input

输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 T (T ≤ 20)；
每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q (Q ≤ 1e5)；
每组测试数据的 2 ~ Q+1 行为具体的操作(MKDIR、RM 操作总数不超过 5000)；

Output

每组测试数据的输出结果间需要输出一行空行。注意大小写。

Sample

Input: 
1
22
MKDIR dira
CD dirb
CD dira
MKDIR a
MKDIR b
MKDIR c
CD ..
MKDIR dirb
CD dirb
MKDIR x
CD ..
MKDIR dirc
CD dirc
MKDIR y
CD ..
SZ
LS
TREE
RM dira
TREE
UNDO
TREE

Output: 
OK
ERR
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
9
dira
dirb
dirc
root
dira
a
b
c
dirb
x
dirc
y
OK
root
dirb
x
dirc
y
OK
root
dira
a
b
c
dirb
x
dirc
y

Limitation

Time limit		6000 ms
Memory limit	1048576 kB

解题思路

挺复杂的，分步骤操作。

Step 1

先考虑输入，输入主要是操作跟操作的路径，所以用map标记输入的是什么操作，共 7 个case。

Step 2

接下来就是7个功能的实现了，可以先把大体框图class写出来，具体怎么实现先丢在一边。

Step 3

然后是考虑怎么实现这棵目录树的问题。仔细读题，它得有返回上一级的功能，所以结构体内得存有指针指向其父节点；还得输出当前目录大小，所以结构体内得有一个size记录当前目录大小。
但是问题又来了，一个目录下有多个文件夹，每个文件夹下又有多个文件夹，所以size不应该只记录当前文件夹下文件夹的个数，还得算入所有子文件夹的个数，所以可以用一个函数维持这个size，从变更的孩子节点开始，每次往上一级变更size，直到root。
文件目录是英文单词，得用map对其标记(同时也Alphabetically sorted)，将这些指向孩子的指针储存起来。

Step 4

最后就是实现这7大功能了。

类里面放个指针指向根目录，再放个指针指向当前所在文件夹的目录。

MKDIR s：新建节点直接插入，同时维护size(+1)，返回true/false。

RM s：找到当前路径是否存在该文件夹，存在则删除指针，同时维护size(- 1 × 删除的大小)，返回true/false。

CD s：找到当前路径是否存在该文件夹，存在则改变当前目录的指针，指向这，返回true/false。

SZ：因为有储存了，直接输出就好了。

LS：遍历当前目录的直接子目录，直接根据题意输出就好了。

TREE：前序遍历，结果用vector储存，根据题意输出。

UNDO：中文题意可能有歧义，直接看英文题意：只有成功的MKDIR、RM、CD才可以撤销；可多次撤销；没得再撤销了就ERR了。
可以用一个栈(stack<pair<操作, 操作用于的指针>>)储存每次成功的MKDIR、RM和CD，每次撤销取栈顶，撤销MKDIR就RM之，撤销RM就MKDIR之(必须用指针, 不可直接新建目录，否则子文件夹全部丢失)，撤销CD就进入储存的CD地址。

Step 5 细节处理

跑一下，TLE了……原因是一直TREE操作太耗时，太多次就超时了。

可以采用懒更新的方式，因为它每次TREE的结果可能是相同的，可以用一个bool updated记录当前是否更新了树，即若操作是成功的MKDIR/RM/CD/UNDO，则需要重新遍历，每次遍历完之后，将updated置于false。减少了遍历的次数，耗时也就降下来了。

再再再后来……

之后就面临的WA的疯狂调试……(好难纠错啊)

先是解决了上面提到的撤回RM操作不能直接MKDIR新目录的问题，然后是若第一个指令是TREE但前序序列是空的(没加入root), 因此输出'EMPTY'时判断条件(前序序列的size = 1)会出错。

还有就是若当前目录与其子目录中某个文件夹同名，RM会有很大的问题，因为我本来是写了个find()函数，从当前目录开始，不断向子目录找同名文件夹，RM直接调用的find()，因为刚开始读题的时候我脑子里是认为把所有子目录都算进去了……

还有个WA找了好久……反复读题后，发现CD是进入当前子目录，我又调用find()函数了……(自己随手写了个find()函数把自己坑了好几次😵，最终AC的结果就是find()完全用不上🤧)

总结

认真读题，反复读题！若有英文原题，建议先看英文题面！

源代码

#include <iostream>
#include <queue>
#include <stack>
#include <map>
using namespace std;

struct node {
	string name;
	map<string, node*> children;
	node* parent;
	int sz;
	node() { name = ""; parent = NULL; sz = 0; }
	node(string nm, node* par) :name(nm), parent(par) { sz = 1; }
};

class directory {
private:
	node* root;
	node* cur;
	vector<string> posOrder;
	stack<pair<int, node*>> opeS;
	bool updated;
public:
	directory() { root = new node("root", NULL); cur = root; updated = false; }
	~directory() { /*clear();*/ }
	node* find(node* curr, string idx) {
		queue<node*> q;
		q.push(curr);
		while (!q.empty()) {
			node* p = q.front();
			q.pop();
			if (p->name == idx)
				return p;
			for (map<string, node*>::iterator it = p->children.begin();
				it != p->children.end(); ++it)
				q.push(it->second);
		}
		return NULL;
	}
	void maintain(node* curr, int delta) {
		curr->sz += delta;
		if (curr != root)
			maintain(curr->parent, delta);
	}
	bool insert(string sub) {
		node* par = cur;
		if (par->children.find(sub) != par->children.end())
			return false;
		node* child = new node(sub, par);
		par->children.insert(make_pair(sub, child));

		maintain(cur, 1);

		opeS.push(make_pair(0, child));
		updated = true;
		return true;
	}
	bool remove(string sub) {
		node* par = cur;
		map<string, node*>::iterator it = par->children.find(sub);
		if (it == par->children.end())
			return false;

		node* child = par->children[sub];

		par->children.erase(it);
		
		maintain(cur, -1 * child->sz);

		opeS.push(make_pair(1, child));
		updated = true;
		return true;
	}
	bool enter(string sub) {
		if (sub == "..") {
			if (cur == root)
				return false;
			opeS.push(make_pair(2, cur));
			cur = cur->parent;
			updated = true;
			return true;
		}
		else {
			map<string, node*>::iterator it = cur->children.find(sub);
			if (it == cur->children.end())
				return false;

			opeS.push(make_pair(2, cur));
			cur = it->second;
			updated = true;
			return true;
		}
	}
	int curSize() {
		return cur->sz;
	}
	void currOutput() {
		int theSize = cur->children.size();
		if (theSize == 0)
			cout << "EMPTY" << endl;
		if (theSize >= 1 && theSize <= 10) {
			for (map<string, node*>::iterator it = cur->children.begin();
				it != cur->children.end(); ++it)
				cout << it->first << endl;
		}
		else if (theSize > 10) {
			map<string, node*>::iterator it = cur->children.begin();
			for (int i = 0; i < 5; i++) {
				cout << it->first << endl;
				it++;
			}

			cout << "..." << endl;

			map<string, node*>::iterator itt = cur->children.end();
			for (int i = 0; i < 5; i++)
				itt--;
			for (int i = 0; i < 5; i++) {
				cout << itt->first << endl;
				itt++;
			}
		}
	}
	void posTra(node* curr) {
		posOrder.push_back(curr->name);
		for (map<string, node*>::iterator it = curr->children.begin();
			it != curr->children.end(); ++it)
			posTra(it->second);
	}
	void output() {
		if (updated || posOrder.empty()) {
			posOrder.clear();
			posTra(cur);
		}
		updated = false;
		int theSize = posOrder.size();
		if (theSize == 1)
			cout << "EMPTY" << endl;
		if (theSize > 1 && theSize <= 10) {
			for (int i = 0; i != theSize; i++)
				cout << posOrder[i] << endl;
		}
		else if (theSize > 10) {
			for (int i = 0; i < 5; i++)
				cout << posOrder[i] << endl;
			cout << "..." << endl;
			for (int i = theSize - 5; i != theSize; i++)
				cout << posOrder[i] << endl;
		}
	}
	bool undo() {
		if (opeS.empty())
			return false;
		updated = true;
		pair<int, node*> pS = opeS.top();
		opeS.pop();
		if (pS.first == 0) {
			node* dest = pS.second;
			map<string, node*>::iterator it = cur->children.find(dest->name);
			if (it == cur->children.end())
				return false;

			cur->children.erase(it);

			maintain(cur, -1);

			return true;
		}
		if (pS.first == 1) {
			node* dest = pS.second;
			if (cur->children.find(dest->name) != cur->children.end())
				return false;

			cur->children.insert(make_pair(dest->name, dest));

			maintain(cur, dest->sz);

			return true;
		}
		if (pS.first == 2) {
			cur = pS.second;
			return true;
		}
	}
	void clear() {
		node* p0 = cur;
		delete p0;
		node* p1 = root;
		delete p1;
		root = NULL;
		cur = NULL;
		posOrder.clear();
		while (!opeS.empty())
			opeS.pop();
		p0 = NULL;
		p1 = NULL;
	}
};

int main() {
	map<string, int> Cmap;
	Cmap["MKDIR"] = 0;
	Cmap["RM"] = 1;
	Cmap["CD"] = 2;
	Cmap["SZ"] = 3;
	Cmap["LS"] = 4;
	Cmap["TREE"] = 5;
	Cmap["UNDO"] = 6;

	int T;
	cin >> T;
	int forEmptyOutput = 0;
	while (T--) {
		if (forEmptyOutput > 0)
			cout << endl;
		int Q;
		cin >> Q;
		directory D;
		while (Q--) {
			string cmder;
			cin >> cmder;
			switch (Cmap[cmder]) {
				case 0: { // make sub directory
					string s;
					cin >> s;
					bool result = D.insert(s);
					if (result)
						cout << "OK" << endl;
					if (!result)
						cout << "ERR" << endl;
					break;
				}
				case 1: { // delete sub directory
					string s;
					cin >> s;
					bool result = D.remove(s);
					if (result)
						cout << "OK" << endl;
					if (!result)
						cout << "ERR" << endl;
					break;
				}
				case 2: { // enter sub directory s
					string s;
					cin >> s;
					bool result = D.enter(s);
					if (result)
						cout << "OK" << endl;
					if (!result)
						cout << "ERR" << endl;
					break;
				}
				case 3: { // output temporary size
					cout << D.curSize() << endl;
					break;
				}
				case 4: { // output direct sub directory names
					D.currOutput();
					break;
				}
				case 5: { // posTraversal
					D.output();
					break;
				}
				case 6: { // undo MKDIR/RM/CD
					bool result = D.undo();
					if (result)
						cout << "OK" << endl;
					if (!result)
						cout << "ERR" << endl;
					break;
				}
				default:break;
			}
		}
		forEmptyOutput++;
	}

	return 0;
}

原题链接🔗

https://icpcarchive.ecs.baylor.edu/external/78/7843.pdf