转跳到内容
【重要】即日起针对里区解禁部分打码图片限制

每 日 算 法 挑 战 【第2期】

Mr.K 018

Mr.K 018，
在 三次元同好会

推荐贴

Mr.K 018 游历甚广【遍布大陆的足迹】

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

 

，由Mr.K 018修改
题目已更新，修了一些bug
  • 顶(+1) 1
链接到点评
yhz012 声名鹊起【你的名字开始为人所知】

yhz012

发布于
发布于 · 只看该作者
刚刚, Mr.K 018 说道:

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

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

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

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

链接到点评
随性而为 史莱姆勇者【哪个勇者不是从史莱姆打起】

随性而为

发布于
发布于 · 只看该作者
刚刚, 乱跑的泰兰德 说道:

:mx059:准备直接import os

os.system()来做吗哈哈哈哈哈哈哈

我还没那么厉害，关于操作系统的api我目前只知道c语言的fopen()，fclose():mx026:

我目前只知道c语言，数据结构，html5、c++（现在在学），java（现在在学）

随性而为在诱导萌新女装时被路过的随便拦下，被批评教育并收取学费-3节操

链接到点评
Mr.K 018 游历甚广【遍布大陆的足迹】

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 游历甚广【遍布大陆的足迹】

Mr.K 018

发布于
  • 作者
发布于 · 只看该作者
1 分钟前, 随性而为 说道:

欸，这就秒杀了吗:kl:

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

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

Mr.K 018收和谐资源时被小萝莉围观良心发现失去-2节操

  • 喜欢(+1) 1
链接到点评
yhz012 声名鹊起【你的名字开始为人所知】

yhz012

发布于
发布于 (已修改) · 只看该作者

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

比如说 

touch openGL/

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

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

换句话说，如果用的是 

touch openGL/a.txt

怎么处理？

 

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

举例来说

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

mkdir /a/b/../c

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

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

，由yhz012修改
链接到点评
Mr.K 018 游历甚广【遍布大陆的足迹】

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就可以执行

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

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

，由Mr.K 018修改

Mr.K 018路过听到路过酱的歌声，不小心被路过的鸡仔绊倒，受到了路过酱的赔偿金5节操

链接到点评
yhz012 声名鹊起【你的名字开始为人所知】

yhz012

发布于
发布于 (已修改) · 只看该作者
1 小时前, Mr.K 018 说道:

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

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

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

辛苦啦

 

我还是决定滚去python了（x

反正伪代码也可以，那我用py也没问题了吧（x

果然我已经是py的形状了

  

class node(object):
	#基类
	def __init__(self, name, parent):
		super(node, self).__init__()
		self.name = name
		self.parent = parent
		if self.parent is not None: 
			if hasattr(self.parent, 'childList'):
				self.parent.childList.append(self)
			else:
				print('Error: no childList')
		return

class fileNode(node):
	#文件
	def __init__(self, name, parent):
		super(fileNode, self).__init__(name, parent)
		self.isFolder = False
		return

	def remove():
		self.parent.childList.remove(self)
		return

class folderNode(node):
	#文件夹
	def __init__(self, name, parent):
		super(folderNode, self).__init__(name, parent)
		self.isFolder = True
		self.childList = []
		return

	def remove():
		for child in childList:
			child.remove()
		self.parent.childList.remove(self)
		return

class envTree(object):
	#环境
	def __init__(self, localDir):
		super(envTree, self).__init__()
		self.root = localDir #根
		self.localDir = localDir #当前相对路径
		self.tempDir = self.localDir #临时工作路径
		return

	def console(cmd):
		#解析命令
		if cmd[:3] == 'cd ':
			tempFunction = self.moveDir
			name = cmd[3:]
		elif cmd[:6] == 'mkdir ':
			tempFunction = self.mkdir
			name = cmd[6:]
		elif cmd[:6] == 'touch ':
			tempFunction = self.touch
			name = cmd[6:]
		elif cmd == 'ls':
			self.ls()
			return
		elif cmd[:3] == 'rm ':
			tempFunction = self.rm
			name = cmd[3:]
		else:
			return

		#初始化工作路径
		if name == '':
			return
		self.tempDir = self.localDir

		pathList = name.split('/')
		if pathList[0] == '':
			self.tempDir = self.root
			pathList.pop(0)
			if pathList[0] == '' and len(pathList) == 1:
				#处理根目录情况下会判定路径非法的bug
				pathList.pop(0)
		elif pathList[0] == '.':
			pathList.pop(0)
		elif pathList[0] == '..'
			if self.tempDir.parent is not None:
				self.tempDir = self.tempDir.parent:
				pathList.pop(0)
			else:
				print('Error: not found.')
				return

		#判定语法
		for path in pathList:
			if path == '' or path == '.' or path == '..':
				print('Error: invalid name.')
				return
		else:
			tempFunction(pathList)
		return

	def ls():
		for child in self.tempDir:
			if child.isFolder:
				print('/', end = '')
			print(child.name)
		return

	def _cd(path):
		for child in self.tempDir.childList:
			if child.name == path:
				if child.isFolder:
					self.tempDir = child
					return 0 #正常
				else:
					return -2 #存在同名文件
		else:
			return -1 #不存在路径

	def cd(pathList):
		rtvl = 0
		#移动临时工作路径
		while pathList:
			rtvl = self._cd(pathList[0])
			if rtvl == 0:
				pathList.pop(0)
			elif rtvl == -1:
				print('Error: not found.')
				return
			elif rtvl == -2:
				print('Error: not found.')
				return
			else:
				print('Error: unknown.')
				return
		#移动成功，改变环境
		self.localDir = self.tempDir
		return

	def _mkdir(path):
		newFolder = folderNode(path, self.tempDir)
		self.tempDir = newFolder
		return

	def mkdir(pathList):
		rtvl = 0
		#移动临时工作路径
		while pathList:
			rtvl = self._cd(pathList[0])
			if rtvl == 0:
				pathList.pop(0)
			elif rtvl == -1:
				break
			elif rtvl == -2:
				print('Error: not found.')
				return
			else:
				print('Error: unknown.')
				return
		#开始新建文件夹
		for path in pathList:
			self._mkdir(path)
		return

	def _touch(name):
		for child in self.tempDir.childList:
			if child.name == path:
				if child.isFolder:
					return -2 #存在同名文件夹
				else:
					return -1 #存在同名文件
		else:
			newFile = fileNode(name, self.tempDir)
			return 0

	def touch(pathList):
		if len(pathList) == 0:
			print('Error: invalid name.')
			return
		name = pathList.pop(-1)
		#移动临时工作路径
		while pathList:
			rtvl = self._cd(pathList[0])
			if rtvl == 0:
				pathList.pop(0)
			elif rtvl == -1:
				break
			elif rtvl == -2:
				print('Error: not found.')
				return
			else:
				print('Error: unknown.')
				return
		#开始新建文件夹
		for path in pathList:
			self._mkdir(path)
		#新建文件
		rtvl = self._touch(name)
		if rtvl == -2:
			print('Error: invalid name.')
		elif rtvl == -1:
			pass
		elif rtvl == 0:
			pass
		else:
			print('Error: unknown.')
		self._touch(name)
		return


	def rm(pathList):
		#移动临时工作路径，检查路径正确性
		rtvl = 0
		while pathList:
			rtvl = self._cd(pathList[0])
			if rtvl == 0:
				pathList.pop(0)
			elif rtvl == -1:
				print('Error: not found.')
				return
			elif rtvl == -2:
				break
			else:
				print('Error: unknown.')
				return
		#检测路径完整性
		if rtvl == -2:
			if len(pathList) != 0:
				print('Error: not found.')
				return

		self.tempDir.remove()
		return

 

我说实话我没测试，可能会有手滑的地方（逃

另外我假设不会出什么因为IO的问题导致合法的命令中途爆掉的情况，对于新建文件或者文件夹倒是好说，我在开始新建的地方记录一下，爆掉了就删回去就完了。不过如果是删除，我大概是填不回去了（笑）

 

2020-4-10 04:47:54

修了个根目录路径非法的bug

2020-4-10 04:51:20

处理了一些边界情况会越界的情况

2020-4-10 04:54:38

修了个全都判断好了就是忘了新建文件的智障错误……

，由yhz012修改
注释
Mr.K 018 Mr.K 018 20.00节操 这么大的模拟，辛苦啦~
  • 顶(+1) 2
链接到点评
随性而为 史莱姆勇者【哪个勇者不是从史莱姆打起】

随性而为

发布于
发布于 (已修改) · 只看该作者 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{
    int flag;                                   /*1代表目录（文件夹）。2代表文件*/
    char name[20];                              
    struct tree *parent;
    struct tree *child;
    struct tree *brother;
}tree,*list;
int checkdir(char dir[])                        /*先进行初次判断（绝对路径，相对路径，格式等等，当然还不太完善）*/
{
    int n=1;
    if(dir[strlen(dir)-1]=='/'&&strlen(dir)-1!=0)/*  '/'能通过而'/new/'不能  */
        n=0;
    if(dir[0]=='/'&&(strstr(dir,"../")!=NULL||strstr(dir,"./")!=NULL))/*  绝对路径下任何地方都不能有'./''../'  */
        n=0;
    if(dir[0]!='/'&&((strstr(dir,"../")-dir!=0&&strstr(&dir[3],"../")!=NULL)||(strstr(dir,"./")-dir!=0&&strstr(&dir[2],"./")!=NULL)))/*  相对路径除刚开始不能有'./''../'  */
        n=0;
    if(n==0)
    {
        printf("error:invalid name,such as '/../new','/new/'");
        return 0;
    }
    return 1;
}
/* 下面的exist函数几乎是任何一个操作都要做的，用来看路径中的文件是否存在，如果存在则一步步获取当前文件夹，不存在则看 makeornot，为0时对ls和rm有效
，提示错误终止命令，为1时代表新建目录，为2时代表新建文件，新建文件（目录）统一用make执行*/
int exist(int makeornot,char dir[],list *now,tree* root)
{
    int i,j=0,a[20],flag=0;
    tree* cache;
    tree* temp;
    if(dir[0]='/')/*绝对路径的情况*/
    {
        cache=root->child;
        *now=root;
        for(i=1;dir[i]!='\0';i++)
        {
            if(dir[i]!='/')
                a[j++]=dir[i];
            if(dir[i]=='/')
            {
                a[j]='\0';
                for(;cache;cache=cache->brother)
                    if(strcmp(a,cache->name)==0)
                    {
                        *now=cache;
                        cache=cache->child;
                        flag=1;
                        break;
                    }
                if(flag==0&&(*now)->flag==2)
                    printf("error:file can't be created");/*判断路径中的每一层，文件是不能存放目录和文件的*/
                if(flag==0&&(*now)->flag==1)
                {
                    if(makeornot==0)
                    {
                        printf("error:not found");
                        return 0;
                    }
                    else
                    {
                        make(1,dir,now,temp,root,a);
                        cache=NULL;
                    }
                }
                flag=0;
                j=0;
            }
        }
        a[j]='\0';
        for(;cache;cache=cache->brother)
            if(strcmp(a,cache->name)==0)
            {
                (*now)=cache;
                cache=cache->child;
                //j=0;
                flag=1;
                break;
            }
        if(flag==0)
        {
            if(makeornot==0)
            {
                printf("error:not found");
                return 0;
            }
            else
            {
                make(makeornot,dir,now,temp,root,a);/*倒数第一层文论是文件还是目录都可以新建*/
            }
        }
        return 1;
    }
    else/*相对路径的情况*/
    {
        cache=(*now)->child;
        //*now=(*now);
        for(i=0;dir[i]!='\0';i++)
        {
            if(dir[i]!='/')
                a[j++]=dir[i];
            if(dir[i]=='/')
            {
                a[j]='\0';
                for(;cache;cache=cache->brother)
                {
                    if(strcmp(a,"..")==0)
                    {
                        cache=(*now);
                        *now=(*now)->parent;
                    }
                    if(strcmp(a,cache->name)==0)
                    {
                        (*now)=cache;
                        cache=cache->child;
                        flag=1;
                        break;
                    }
                }
                if(flag==0&&(*now)->flag==2)
                    printf("error:file can't be created");
                if(flag==0&&(*now)->flag==1)
                {
                    if(makeornot==0)
                    {
                        printf("error:not found");
                        return 0;
                    }
                    else
                    {
                        make(1,dir,now,temp,root,a);
                        cache=NULL;
                    }
                }
                flag=0;
                j=0;
            }
        }
        a[j]='\0';
        for(;cache;cache=cache->brother)
            if(strcmp(a,cache->name)==0)
            {
                (*now)=cache;
                cache=cache->child;
                flag=1;
                break;
            }
        if(flag==0)
        {
            if(makeornot==0)
            {
                printf("error:not found");
                return 0;
            }
            else
            {
                make(makeornot,dir,now,temp,root,a);
            }
        }
        return 1;
    }
}
int rmorls(char dir[],tree* now,tree* root,int option)/* 递归操作，option为1时ls，为2时rm */
{
    if(now==NULL)
        return;
    rmorls(dir,now->brother,root,option);
    rmorls(dir,now->child,root,option);
    if(option==1)
        printf("%s/t",now->name);
    if(option==2)
        free(now);
}
int make(int option,char dir[],list *now,tree* temp,tree* root,char a[])
{
    /*现有文件和已存文件的连接*/
    tree *newnode,*p1,*p2;
    newnode=(tree*)malloc(sizeof(tree));
    newnode->brother=NULL;
    newnode->child=NULL;
    newnode->parent=(*now);
    newnode->flag=option;
    strcpy(newnode->name,a);
    /*判断新建文件（目录）是否是父目录第一个孩子*/
    if((*now)->child==NULL)
    {
        (*now)->child=newnode;
    }else
    {
        for(p1=(*now)->child;p1->brother;p1=p1->brother);
        p1->brother=newnode;
    }
    (*now)=temp=newnode;
}
int cd(char dir[],list *now,tree* root)/*转到路径指定目录，事实上大部分工作被exist函数做了*/
{
    tree *temp;
    temp=*now;
    if(exist(0,dir,now,root)==0)        /*如果路径不存在，则当前目录回到没有输入命令前的工作目录*/
        *now=temp;
    /*没有输出*/
}
int ls(char dir[],list *now,tree* root)/*因为ls与rm都是对路径递归，只是每次的操作不同，故将其递归部分结合成一个函数lsorrm()*/
{
    tree *temp;
    temp=*now;
    if(exist(0,dir,now,root)==0)
    {
        *now=temp;
    }else
    {
        printf("%s:",(*now)->name);
        rmorls(dir,(*now)->child,root,1);
    }
}
int rm(char dir[],list *now,tree* root)/*删除后停留在当前目录*/
{
    tree *temp,*a,*p1,*p2;
    temp=*now;
    if(exist(0,dir,now,root)==0)
    {
        *now=temp;
    }else
    {
        rmorls(dir,(*now)->child,root,2);
        a=(*now)->parent;
        p1=a->child;
        if(p1==*now)
        {
            p1->parent->child=p1->brother;
        }
        else
        {
            for(;p2;p2=p1,p1=p1->brother)
            {
                if(p2==*now)
                p1->brother=p2->brother;
            }
        }
        free(*now);
        *now=a->child;
        /*因为是删除，连接方式一定会改变，以上步骤就是改变过程*/
    }
}
int main()/*没什么解释的，就是将输入转化为参数，调用对应的函数*/
{
    tree *root,*now,*temp;
    root=(tree*)malloc(sizeof(tree));
    root->parent=root->child=root->brother=NULL;
    now=temp=root;
    int choose;
    char ope[10];
    char dir[100];
    while(1)
    {
        scanf("%s %s",ope,dir);
        if(!strcmp(ope,"mkdir"))
            choose=1;
        else if(!strcmp(ope,"touch"))
            choose=2;
        else if(!strcmp(ope,"cd"))
            choose=3;
        else if(!strcmp(ope,"ls"))
            choose=4;
        else if(!strcmp(ope,"rm"))
            choose=5;
        if(checkdir(dir)==1)
        {
            switch(choose)
            {
            case 1:exist(1,dir,&now,root);break;
            case 2:exist(2,dir,&now,root);break;
            case 3:cd(dir,&now,root);break;
            case 4:ls(dir,&now,root);break;
            case 5:rm(dir,&now,root);break;
            };
        }
    }
}

码了一天多终于套完了所有的娃，还没有测试，怕没有达到预期的结果而心跳骤停，再者我软件也缺失debug，要发现问题也是工程量巨大，既然不是正规的，就权当伪代码吧（虽然程序本身并没有语法错误），不过大致框架和思路就是这样，要有一些小问题也不用调整太多，讲真这是我至今为止写过的最长的代码了，也多亏了这道题，我对地址有了更深一步的了解，解决了从上学期以来的一些困惑

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

修正了些小错误

，由随性而为修改
注释
NianRuoshui NianRuoshui 20.00节操 恰糖
yhz012 yhz012 10.00节操 是C党，辛苦了
Mr.K 018 Mr.K 018 25.00节操 糖~
链接到点评
转到主题列表
×
×
  • 新建...

重要消息

为使您更好地使用该站点，请仔细阅读以下内容： 使用条款

  我接受