娱乐 每 日 算 法 挑 战 【第2期】

[Mr.K 018]

第二期来啦！！！！！！！！

本来打算放一道BIT校赛的题，搬运完后感觉有点难，于是留给周末两天做吧。

今天就换成了一道模拟题。模拟题不难，依题意模拟即可。

前排提示：这个题不是个操作系统题，原题是给大一同学（非ACM）做的寒假集训题

嘛 召唤阵忘掉了，这次就算了（

第2期 Linux目录系统

众所周知，在没有图形用户界面的年代，想要做事情都得输入命令才行。时至今日在Linux中还可以选择“打开控制台”来输入命令，通过在控制台输入命令可以做到很多只点鼠标做不到的事情。今天我们模拟的主题是基于命令行的Linux目录系统。

Linux中目录和Windows中文件夹的概念差不多。但是和Windows中每个盘有一个根目录不同，这里的目录系统只有一个根目录，叫做/。子目录和父目录间用斜杠/隔开，形如：/usr/src。

程序执行时有一个“工作目录”的概念，表示现在执行的程序在哪个目录上执行。根据工作目录可以定义相对目录，如当前工作目录若是/home/MrK018，那么相对目录Desktop/dir1就表示/home/MrK018/Desktop/dir1这个目录。特别地，我们定义.表示当前目录，..表示当前目录的父目录。

不妨认为目录系统是存在于内存上的，初始时只有根目录/。请实现如下内容：

• cd 将工作目录变为另一个目录；
• mkdir 新建一个目录；
• touch 新建一个文件（放心，我们没有文件读写方面的需求）
• ls 列出当前目录的所有直接子目录和文件；
• rm 删除文件，若是目录则递归地删除所有子目录和下属文件；

目录应首先当作视为相对目录，不能视为相对目录再视为绝对目录。在cd,rm等命令中遇找不到目录或文件的，输出一行Error: not found。文件名不允许为空也不允许带有斜杠，若与无法解析的文件名，输出一行Error: invalid name。

输入

输入包含多行，请读入到文件尾。每一行包含一个命令。

输出

命令的输出结果。除错误信息和ls的输出外，没有其他输出。

样例输入

mkdir usr
mkdir usr/src
mkdir usr/lib
cd usr/lib
touch anode
touch glibc
mkdir Apple
mkdir /home/K/Desktop
ls
touch /home/K/Desktop/hello.txt
mkdir ../include
cd .
cd ..
cd inc
ls
rm lib
touch openGL/
ls
cd /
touch etc/driver/sda1
touch etc/driver/sda1
touch etc2/driver/
cd etc/driver/
ls

样例输出

anode
Apple/
glibc
Error: not found
include/
lib/
src/
Error: invalid name
include/
src/
Error: invalid name
Error: invalid name
sda1

 

四月 10, 2020，由Mr.K 018修改
题目已更新，修了一些bug

[Mr.K 018]

10 分钟前, ssynn 说道:

想起了当年操作系统的课程设计，不过这个网站上玩这个你是认真的？sstm oj指日可待

 

10 分钟前, yhz012 说道:

第一眼看是操作系统题，溜了溜了.jpg

这个题不是操作系统题哦~

[Mr.K 018]

刚刚, 随性而为 说道:

这个题的意思是输入 mkdir 就真的在目录下创建文件，还是只是模拟，只在程序中意思意思创建啊

模拟，不真建文件

也不会有操作系统API供使用的（盯

[Mr.K 018]

4 分钟前, 随性而为 说道:

小心思被发现了

有一说一，这是个模拟题

而且就算用了操作系统API，本质上树还是那棵树啊（

还是说能贪一行就贪一行wwwww

[Mr.K 018]

刚刚, yhz012 说道:

看了一下，感觉最暴力的方法就是维护一个树结构

struct node{
    bool folderFlag;
    char nameLen;
    char name[128]:
    struct node *parent;
    struct node *childrenListHead;
    struct node *next;
};

层间用树结构组织，层内用循环链表组织大概就可以了吧……

没错，这就是本题的全部算法

也正因为如此，本期算法po上来是不够的~

[Mr.K 018]

1 分钟前, 随性而为 说道:

欸，这就秒杀了吗

这题是个模拟题啊，算法就是这么个算法

模拟题的性质就是几乎没有啥算法，难点全在复杂的程序逻辑（a.k.a.代码量）上面，因此这个题要到伪代码/代码层面才算数哦~

[Mr.K 018]

30 分钟前, yhz012 说道:

提个问题，mkdir是可以一个命令建立多层文件夹的，但是touch看起来是不能连带着文件夹一起建立文件的？

比如说

touch openGL/

这句话，是因为不存在openGL这个文件夹，所以认为 openGL/ 整个是个文件名，带了反斜杠所以失败了

还是因为后面的文件名为空失败了？

换句话说，如果用的是

touch openGL/a.txt

怎么处理？

 

以及对于mkdir一个命令建立多层文件夹，如果其中出现了非法文件夹名，怎么处理，把之前的新建文件夹全都撤销掉，还是建了的保留？

举例来说

原来只有根目录的情况，执行

mkdir /a/b/../c

中间的..是非法文件夹名的吧？

这种情况下，我需要把文件夹a和文件夹b也一起撤销掉吗？还是说留着/a/b就可以了？

touch openGL/失败是因为不能把openGL/识别为一个指向文件名的目录元素。touch openGL/lib.lib就可以执行

指令应该有一些原子性，如果执行失败，整个命令应该什么都不做

抱歉题目有一些不完整，我稍后做补充

四月 10, 2020，由Mr.K 018修改

[Mr.K 018]

20 分钟前, 随性而为 说道:

这真的是给大一学生做的么，太魔鬼了

这个啊，这个是当初ACM队选拔总结赛里面的一道题，确实是给大一同学做的

我之所以能这么肯定是因为我当时面对的就是这种题

[Mr.K 018]

3 分钟前, 随性而为 说道:

woc，有压轴题内味了，感觉这道题是真的……很少人能当场做出来吧，你们当时学过数据结构么……

没学，要现场领悟树的C语言表示2333

不过真正的压轴题不是这道，我记得是一个很奇怪的dp

32 分钟前, 随性而为 说道:

我软件也缺失debug

安利一发Visual Studio