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

[yhz012]

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

第二眼看大概还好，感觉还能做

 

感觉基本就是构建一个树就可以了……？

四月 10, 2020，由yhz012修改

[yhz012]

刚刚, Mr.K 018 说道:

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

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

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

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

[yhz012]

1 分钟前, Mr.K 018 说道:

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

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

写C系的好累，我还是决定滚去用py写了（x

艹，等下，py没有指针有点烦（x

那我还是滚去用带类C的C++写好了（x

四月 10, 2020，由yhz012修改

[yhz012]

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

比如说

touch openGL/

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

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

换句话说，如果用的是

touch openGL/a.txt

怎么处理？

 

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

举例来说

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

mkdir /a/b/../c

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

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

四月 10, 2020，由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

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

四月 10, 2020，由yhz012修改