【Week9作业-A】咕咕东的目录管理器 Kattis - directorymanagement

算法

模拟

题目描述

根据题目要求，模拟实现一个目录管理器，功能包括：新建文件夹，删除文件夹，进入文件夹，显示文件夹内文件数，列出文件夹内容，列出文件夹子树以及回退。

解题思路

本题是一个十分复杂的模拟题，由于涉及到的操作十分多且复杂，我们需要对文件夹以及命令进行封装，以便于数写和修改代码。
同时，由于数据规模中，询问次数远远大于操作次数，故使用记忆化记录上一次询问的结果，以减少询问时查询所需的时间。
由于本代码过于复杂，绝大部分内容来自PPT，不再赘述。

代码

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int maxq = 100010;
char temp[20];
//目录树以及操作
struct Directory {
    string name;                    //当前目录名字
    map<string, Directory*> son;    //子目录
    Directory* far;                 //父目录
    int size;                       //目录数量
    bool update;                //更新标记
    vector<string> tenDes;      //保存当前节点的十个后代
private:
    void treeAll(vector<string>& index) {
        index.push_back(name);
        for (auto &entry : son)
            entry.second->treeAll(index);
    }
    void treeFrist(int num, vector<string>& index) {
        index.push_back(name);
        num--;
        if (num == 0)
            return;
        int n = son.size();
        auto it = son.begin();
        while (n--) {
            int its = it->second->size;
            if (its >= num) {
                //如果子树总数大于需要数量，输出子树即可
                it->second->treeFrist(num, index);
                return;
            }
            else {
                it->second->treeFrist(its, index);
                num -= its;
            }
            it++;
        }
        return;
    }
    void treeLast(int num, vector<string>& index) {
        int n = son.size();
        auto it = son.end();
        while (n--) {
            it--;
            int its = it->second->size;
            if (its >= num) {
                //如果子树总数大于需要数量，输出子树即可
                it->second->treeLast(num, index);
                return;
            }
            else {
                it->second->treeLast(its, index);
                num -= its;
            }
        }
        index.push_back(name);
        return;
    }
public:
    //构造函数
    Directory(string name, Directory* far) {
        this->name = name;
        this->far = far;
        this->size = 1;
    }
    //其他函数
    Directory* getSon(string arg) {
        auto it = son.find(arg);
        if (it == son.end())
            return nullptr;
        return it->second;
    }
    Directory* mkdir(string arg) {
        if (son.find(arg) != son.end()) {
            //已存在
            return nullptr;
        }
        Directory* opt = new Directory(arg, this);
        son[arg] = opt;
        sizeKeep(+1);
        return opt;
    }
    Directory* rm(string arg) {
        auto it = son.find(arg);
        if (it == son.end())
            return nullptr;
        sizeKeep(-1 * it->second->size);
        auto ret = it->second;
        son.erase(it);
        return ret;
        /*son.erase(it);
        return it->second;*/
    }
    Directory* cd(string arg) {
        if (arg == "..")
            return this->far;
        return getSon(arg);
    }
    bool addSons(Directory* opt) {
        if (son.find(opt->name) != son.end())
            return false;
        son[opt->name] = opt;
        sizeKeep(+opt->size);
        return true;
    }
    void sizeKeep(int dalte) {
        //向上维护子树
        update = true;
        size += dalte;
        if (far != nullptr)
            far->sizeKeep(dalte);
        return;
    }
    void sz() {
        cout << this->size << endl;
        return;
    }
    void ls() {
        int sz = son.size();
        if (sz == 0)
            cout << "EMPTY" << endl;
        else if (sz <= 10)
            for (auto &entry : son)
                cout << entry.first << endl;
        else {
            auto it = son.begin();
            for (int i = 0; i < 5; i++, it++)
                cout << it->first << endl;
            cout << "..." << endl;
            it = son.end();
            for (int i = 0; i < 5; i++)it--;
            for (int i = 0; i < 5; i++, it++)
                cout << it->first << endl;
        }
    }
    void tree() {
        if (size == 1)
            cout << "EMPTY" << endl;
        else if (size <= 10) {
            if (this->update) {
                tenDes.clear();
                treeAll(tenDes);
                this->update = false;
            }
            for (int i = 0; i < size; i++)
                cout << tenDes.at(i) << endl;
        }
        else {
            if (this->update) {
                tenDes.clear();
                treeFrist(5, tenDes);
                treeLast(5, tenDes);
                this->update = false;
            }
            for (int i = 0; i < 5; i++)
                cout << tenDes.at(i) << endl;
            cout << "..." << endl;
            for (int i = 9; i >= 5; i--)
                cout << tenDes.at(i) << endl;
        }
    }
};
//命令
struct Command {
    const string CMDNAMES[7] = { "MKDIR","RM","CD","SZ","LS","TREE","UNDO" };
    int type;               //命令类型（根据CMDNAMES转换）
    string arg;             //命令参数
public:
    Directory* lstDir;
    //构造函数
    Command(string s) {
        for (int i = 0; i < 7; i++) {
            if (CMDNAMES[i] == s) {
                type = i;
                if (i < 3) {
                    string temp;
                    cin >> temp;
                    arg = temp;
                }
                return;
            }
        }
    }
};
int main() {
    int t;
    cin >> t;
    while (t--) {
        int q;
        cin >> q;
        Directory* now = new Directory("root", nullptr);///当前目录
        vector<Command*> cmdList; ///记录操作列表备UNDO
        string s;
        while (q--) {
            cin >> s;
            //scanf("%s", temp);
            Command* cmd = new Command(s);
            Directory * opt;
            switch (cmd->type) {
            case 0:     //MKDIR 操作/传教目录
                cmd->lstDir = now->mkdir(cmd->arg);
                if (cmd->lstDir == nullptr) {
                    //若返回为空则操作有误
                    cout << "ERR" << endl;
                    //printf("ERR\n");
                }
                else {
                    cout << "OK" << endl;
                    cmdList.push_back(cmd);
                }
                break;
            case 1:     //RM    操作/删除目录
                cmd->lstDir = now->rm(cmd->arg);
                if (cmd->lstDir == nullptr) {
                    //若返回为空则操作有误
                    cout << "ERR" << endl;
                    //printf("ERR\n");
                }
                else {
                    cout << "OK" << endl;
                    //printf("OK\n");
                    cmdList.push_back(cmd);
                }
                break;
            case 2:     //CD    操作/进入目录
                opt = now->cd(cmd->arg);
                if (opt == nullptr) {
                    //若返回为空则操作有误
                    cout << "ERR" << endl;
                    //printf("ERR\n");
                }
                else {
                    cout << "OK" << endl;
                    //printf("OK\n");
                    cmd->lstDir = now;
                    now = opt;
                    cmdList.push_back(cmd);
                }
                break;
            case 3:     //SZ    询问/目录大小
                now->sz();
                break;
            case 4:     //LS    询问/列出子目录
                now->ls();
                break;
            case 5:     //TREE  询问/前序遍历子树
                now->tree();
                break;
            case 6:     //UNDO  特殊/撤销
                bool ok = 0;
                while (!ok && !cmdList.empty()) {
                    cmd = cmdList.back(); cmdList.pop_back();
                    switch (cmd->type) {
                    case 0:     //UNDO MKDIR
                        ok = now->rm(cmd->arg) != nullptr;
                        break;
                    case 1:     //UNDO RM
                        ok = now->addSons(cmd->lstDir);
                        break;
                    case 2:     //UNDO CD
                        now = cmd->lstDir;
                        ok = true;
                        break;
                    }
                }
                cout << (ok ? "OK" : "ERR") << endl;
                //printf(ok ? "OK\n" : "ERR\n");
                break;
            }
        }
        cout << endl;
    }
    return 0;
}

题目总结

对于这种十分复杂的模拟题，应该首先对整个题目有全局的规划，同时在写题的时候注意对各种操作的封装。

题目原文

题面

咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！

初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。

目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。

image

现在咕咕东可以在命令行下执行以下表格中描述的命令：

命令 类型 实现 说明
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 个。若目录结构如上图，当前目录为 "root" 执行结果如下，
image
UNDO 特殊 撤销操作 撤销最近一个 "成功执行" 的操作（即MKDIR或RM或CD）的影响，撤销成功输出 "OK" 失败或者没有操作用于撤销则输出 "ERR"
输入

输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 T （T <= 20）；

每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q （Q <= 1e5）；

每组测试数据的 2 ~ Q+1 行为具体的操作 （MKDIR、RM 操作总数不超过 5000）；
面对数据范围你要思考的是他们代表的 "命令" 执行的最大可接受复杂度，只有这样你才能知道你需要设计的是怎样复杂度的系统。

输出

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

时空限制

Time limit 6000 ms

Memory limit 1048576 kB

样例输入
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
样例输出
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
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,287评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,346评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,277评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,132评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,147评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,106评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,019评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,862评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,301评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,521评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,682评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,405评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,996评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,651评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,803评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,674评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,563评论 2赞 352