包头市网站建设_网站建设公司_Tailwind CSS_seo优化

(新卷,200分)- 模拟目录管理功能（Java & JS & Python & C）

题目描述

实现一个模拟目录管理功能的软件，输入一个命令序列，输出最后一条命令运行结果。

支持命令：

1. 创建目录命令：mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作。此命令无输出。
2. 进入目录命令：cd 目录名称，如 cd abc 为进入abc目录，特别地，cd .. 为返回上级目录，如果目录不存在则不执行任何操作。此命令无输出。
3. 查看当前所在路径命令：pwd，输出当前路径字符串。

约束：

1. 目录名称仅支持小写字母；mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc；不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。
2. 目录符号为/，根目录/作为初始目录。
3. 任何不符合上述定义的无效命令不做任何处理并且无输出。

输入描述

输入 N 行字符串，每一行字符串是一条命令。

输出描述

输出最后一条命令运行结果字符串。

备注

命令行数限制100行以内，目录名称限制10个字符以内。

用例

题目解析

本题感觉主要是考察树形结构定义，以及逻辑模拟。

目录结构，其实就是一个树形结构。一个父目录下面可以有多个直接子目录，而一个子目录只能有一个父目录。因此，本题需要定义出一个多叉树结构。

关于树节点定义如下：

class TreeNode {

String dicName; // 当前目录的名字

TreeNode father; // 当前目录的父目录

List<TreeNode> children; // 当前目录的子目录

}

接下来，就是实现目录管理能力：

• mkdir
• cd
• pwd

实现这三个能力前，我们需要定义出树结构：

class Tree {

TreeNode root; // 树的根目录

TreeNode cur; // 当前所在目录

}

其中，tree.cur 用于指向当前所在目录，初始时 tree.cur = tree.root。

mkdir，其实就是在 tree.cur 目录下创建一个子目录，但是前提是 tree.cur 下面不存在对应子目录名，否则不操作。mkdir操作不改变 tree.cur 指向。

cd，有两种情况：

1. cd ..
   
   cd .. 是返回上级目录（父目录），但是前提是 tree.cur.father 存在，否则不操作。如果 tree.cur.father 存在，则cd .. 会改变 tree.cur = tree.cur.father。
2. cd 目录名
   
   cd 目录名 是进入子目录，但是前提是 tree.cur 包含对应目录名的子目录，否则不操作。如果 存在对应子目录，则 cd操作会改变 tree.cur = 对应子目录

pwd 是输出当前目录的路径字符串，我们可以不停进行 tree.cur = tree.cur.father 的倒序遍历，获取遍历过程中目录名tree.cur.dicName，直到 tree.cur == NULL。最后拼接时注意反转。

上面是目录管理功能的三个能力大致实现思路，具体实现根据不同语言有不同改进，比如 cd 目录名 功能，我们需要遍历 tree.cur.children 来确认对应目录名是否存在，这里Java，JS，Py定义 tree.cur.children 时可以使用 字典Map 来定义（key是目录名，val是对应目录名的TreeNode），从而实现快速查找对应目录。

另外，本题需要对mkdir, cd, pwd的命令参数做约束：

• mkdir, cd 的参数只能是1个，如果超过1个，就不进行操作
• pwd 不需要参数，如果有参数，就不进行操作
• mkdir，cd的参数（目录名）只能由小写字母组成，否则不操作
• mkdir，cd的参数（目录名）不能是嵌套路径，或者绝对路径

算法源码

JavaScript算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { class TreeNode { constructor(curDicName, father) { this.curDicName = curDicName; this.father = father; this.children = {}; } } class Tree { constructor() { // root是根目录，根目录 / 作为初始目录 this.root = new TreeNode("/", null); // cur用于指向当前正在操作的目录 this.cur = this.root; } mkdir(dicName) { // mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作 if (!this.cur.children[dicName]) { this.cur.children[dicName] = new TreeNode(dicName + "/", this.cur); } } cd(dicName) { if (dicName == "..") { // cd .. 为返回上级目录，如果目录不存在则不执行任何操作 if (this.cur.father != null) { // cur 变更指向上级目录 this.cur = this.cur.father; } } else { // cd 目录名称，如 cd abc 为进入abc目录，如果目录不存在则不执行任何操作 if (this.cur.children[dicName]) { // cur 变更指向下级目录 this.cur = this.cur.children[dicName]; } } } pwd() { // 输出当前路径字符串 const arr = []; // 倒序路径，即不停向上找父目录 let cur = this.cur; while (cur != null) { arr.push(cur.curDicName); cur = cur.father; } // 反转后拼接 return arr.reverse().join(""); } } // 初始化目录结构 const tree = new Tree(); // 记录最后一条命令的输出 let lastCommandOutPut = ""; outer: while (true) { try { const line = await readline(); // 本地测试解开此行 // if (line == "") break; const tmp = line.split(" "); const cmd_key = tmp[0]; if (cmd_key == "pwd") { // pwd 命令不需要参数 if (tmp.length != 1) continue; lastCommandOutPut = tree.pwd(); } else if (cmd_key == "mkdir" || cmd_key == "cd") { // 约束：mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc if (tmp.length != 2) continue; // 目录名 const cmd_val = tmp[1]; if (!(cmd_key == "cd" && cmd_val == "..")) { // 目录名约束校验 // 约束：目录名称仅支持小写字母 // 约束：不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。 // 关于嵌套路径和绝对路径，我简单理解就是cmd_val含有'/'字符，可以被小写字母判断涵盖住 for (let c of cmd_val) { if (c < "a" || c > "z") continue outer; } } if (cmd_key == "mkdir") { tree.mkdir(cmd_val); // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 lastCommandOutPut = ""; } else { tree.cd(cmd_val); // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 lastCommandOutPut = ""; } } } catch (e) { break; } } console.log(lastCommandOutPut); })();

Java算法源码

import java.util.HashMap; import java.util.Scanner; public class Main { static class TreeNode { String curDicName; TreeNode father; HashMap<String, TreeNode> children; public TreeNode(String curDicName, TreeNode father) { this.curDicName = curDicName; this.father = father; this.children = new HashMap<>(); } } static class Tree { TreeNode root; TreeNode cur; public Tree() { // root是根目录，根目录 / 作为初始目录 this.root = new TreeNode("/", null); // cur用于指向当前正在操作的目录 this.cur = root; } public void mkdir(String childDicName) { // mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作 this.cur.children.putIfAbsent( childDicName, new TreeNode(childDicName + "/", this.cur)); // 目录符号为 / } public void cd(String dicName) { if (dicName.equals("..")) { // cd .. 为返回上级目录，如果目录不存在则不执行任何操作 if (this.cur.father != null) { // cur 变更指向上级目录 this.cur = this.cur.father; } } else { // cd 目录名称，如 cd abc 为进入abc目录，如果目录不存在则不执行任何操作 if (this.cur.children.containsKey(dicName)) { // cur 变更指向下级目录 this.cur = this.cur.children.get(dicName); } } } public String pwd() { // 输出当前路径字符串 StringBuilder sb = new StringBuilder(); // 倒序路径，即不停向上找父目录 TreeNode cur = this.cur; while (cur != null) { // 头插目录名，保证路径中目录层级正确 sb.insert(0, cur.curDicName); cur = cur.father; } return sb.toString(); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 初始化目录结构 Tree tree = new Tree(); // 记录最后一条命令的输出 String lastCommandOutPut = ""; outer: while (sc.hasNextLine()) { String line = sc.nextLine(); // 本地测试解开此行 // if (line.equals("")) break; String[] tmp = line.split(" "); String cmd_key = tmp[0]; if (cmd_key.equals("pwd")) { // pwd 命令不需要参数 if (tmp.length != 1) continue; lastCommandOutPut = tree.pwd(); } else if (cmd_key.equals("mkdir") || cmd_key.equals("cd")) { // 约束：mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc if (tmp.length != 2) continue; // 目录名 String cmd_val = tmp[1]; if (!(cmd_key.equals("cd") && cmd_val.equals(".."))) { // 目录名约束校验 // 约束：目录名称仅支持小写字母 // 约束：不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。 // 关于嵌套路径和绝对路径，我简单理解就是cmd_val含有'/'字符，可以被小写字母判断涵盖住 for (int i = 0; i < cmd_val.length(); i++) { char c = cmd_val.charAt(i); if (c < 'a' || c > 'z') continue outer; } } if (cmd_key.equals("mkdir")) { tree.mkdir(cmd_val); // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 lastCommandOutPut = ""; } else { tree.cd(cmd_val); // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 lastCommandOutPut = ""; } } } System.out.println(lastCommandOutPut); } }

Python算法源码

class TreeNode: def __init__(self, curDicName, father): self.curDicName = curDicName self.father = father self.children = {} class Tree: def __init__(self): # root是根目录，根目录 / 作为初始目录 self.root = TreeNode("/", None) # cur用于指向当前正在操作的目录 self.cur = self.root def mkdir(self, dicName): # mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作 self.cur.children.setdefault(dicName, TreeNode(dicName + "/", self.cur)) # 目录符号为 / def cd(self, dicName): if dicName == "..": # cd .. 为返回上级目录，如果目录不存在则不执行任何操作 if self.cur.father is not None: # cur 变更指向上级目录 self.cur = self.cur.father else: # cd 目录名称，如 cd abc 为进入abc目录，如果目录不存在则不执行任何操作 if self.cur.children.get(dicName) is not None: # cur 变更指向下级目录 self.cur = self.cur.children[dicName] def pwd(self): # 输出当前路径字符串 lst = [] # 倒序路径，即不停向上找父目录 cur = self.cur while cur is not None: lst.append(cur.curDicName) cur = cur.father # 反转后拼接 lst.reverse() return "".join(lst) # 算法逻辑 # 初始化目录结构 tree = Tree() # 记录最后一条命令的输出 lastCommandOutput = "" while True: try: line = input() # 本地测试解开此行 # if line == "": # break tmp = line.split() cmd_key = tmp[0] if cmd_key == "pwd": # pwd 命令不需要参数 if len(tmp) != 1: continue lastCommandOutput = tree.pwd() elif cmd_key == "mkdir" or cmd_key == "cd": # 约束：mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc if len(tmp) != 2: continue # 目录名 cmd_val = tmp[1] # 目录名约束校验 # 约束：目录名称仅支持小写字母 # 约束：不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。 # 关于嵌套路径和绝对路径，我简单理解就是cmd_val含有'/'字符，可以被小写字母判断涵盖住 if not (cmd_val.isalpha() and cmd_val.islower()) and not (cmd_key == 'cd' and cmd_val == '..'): continue if cmd_key == "mkdir": tree.mkdir(cmd_val) # 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 lastCommandOutput = "" else: tree.cd(cmd_val) # 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 lastCommandOutput = "" except: break print(lastCommandOutput)

C算法源码

#include <stdio.h> #include <stdlib.h> #include <string.h> /** 树节点 **/ typedef struct TreeNode { char curDicName[11]; // 当前目录名 struct TreeNode *father; // 父目录（只能有一个） struct LinkedList *children; // 子目录（可以有多个，这里使用链表记录） } TreeNode; /** 链表节点 **/ typedef struct ListNode { TreeNode *ele; // 链表用于记录多个子目录，因此链表节点的内容就是树节点 struct ListNode *next; } ListNode; /** 链表 **/ typedef struct LinkedList { ListNode *head; ListNode *tail; int size; } LinkedList; /** 树 **/ typedef struct Tree { TreeNode *root; // 记录树根节点 TreeNode *cur; // 记录当前目录对应的节点 } Tree; /** 链表结构方法 **/ // 初始化链表 LinkedList *new_LinkedList() { LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList)); link->head = NULL; link->tail = NULL; link->size = 0; return link; } // 尾插链表 void addLast_LinkedList(LinkedList *link, TreeNode *ele) { ListNode *listNode = (ListNode *) malloc(sizeof(ListNode)); listNode->ele = ele; listNode->next = NULL; if(link->size == 0) { link->head = listNode; link->tail = listNode; } else { link->tail->next = listNode; link->tail = listNode; } link->size++; } // 遍历链表，获取指定节点的内容 TreeNode *get_LinkedList(LinkedList *link, char *dicName) { ListNode *curListNode = link->head; while (curListNode != NULL) { if (strcmp(curListNode->ele->curDicName, dicName) == 0) { return curListNode->ele; } curListNode = curListNode->next; } return NULL; } /** 树形结构方法 **/ TreeNode *new_TreeNode(char *curDicName, TreeNode *father) { TreeNode *treeNode = (TreeNode *) calloc(1, sizeof(TreeNode)); strcpy(treeNode->curDicName, curDicName); treeNode->father = father; treeNode->children = new_LinkedList(); return treeNode; } // 初始化树 Tree *new_Tree() { Tree *tree = (Tree *) malloc(sizeof(Tree)); // 由于目录名结尾都要带'/'，因此可以认为根目录是空串，后期拼接时再尾部追加'/' // 另外根目录没有父目录，因此父目录设置为NULL tree->root = new_TreeNode("", NULL); // 初始时，当前目录就是根目录 tree->cur = tree->root; return tree; } // 创建指定目录 void mkdir_Tree(Tree *tree, char *dicName) { TreeNode *p = get_LinkedList(tree->cur->children, dicName); // mkdir 目录名称，如 mkdir abc 为在当前目录创建abc目录，如果已存在同名目录则不执行任何操作 if (p != NULL) { return; } TreeNode *treeNode = new_TreeNode(dicName, tree->cur); addLast_LinkedList(tree->cur->children, treeNode); } // 跳转到指定目录 void cd_Tree(Tree *tree, char *dicName) { if (strcmp(dicName, "..") == 0) { // cd .. 为返回上级目录，如果目录不存在则不执行任何操作 if (tree->cur->father != NULL) { // cur 变更指向上级目录 tree->cur = tree->cur->father; } } else { TreeNode *p = get_LinkedList(tree->cur->children, dicName); // cd 目录名称，如 cd abc 为进入abc目录，如果目录不存在则不执行任何操作 if (p != NULL) { // cur 变更指向下级目录 tree->cur = p; } } } // 输出当前路径字符串 char *pwd_Tree(Tree *tree) { char *tmp = (char *) calloc(10000, sizeof(char)); char *res = (char *) calloc(10000, sizeof(char)); // 倒序路径，即不停向上找父目录 TreeNode *cur = tree->cur; while (cur != NULL) { strcpy(tmp, res); strcpy(res, cur->curDicName); strcat(res, "/"); strcat(res, tmp); cur = cur->father; } return res; } int main() { // 初始化目录结构 Tree *tree = new_Tree(); // 记录最后一条命令的输出 char lastCommandOutPut[10000]; char s[50]; while (gets(s)) { // 本地测试解开此行注释 if(strlen(s) == 0) break; char *cmd_key = strtok(s, " "); char *cmd_val = strtok(NULL, " "); if (strcmp(cmd_key, "pwd") == 0) { // pwd 命令不需要参数 if (cmd_val != NULL) { continue; } strcpy(lastCommandOutPut, pwd_Tree(tree)); } else if (strcmp(cmd_key, "mkdir") == 0 || strcmp(cmd_key, "cd") == 0) { // 约束：mkdir 和 cd 命令的参数仅支持单个目录，如：mkdir abc 和 cd abc if (cmd_val == NULL) continue; char *p = strtok(NULL, " "); if (p != NULL) continue; if(!(strcmp(cmd_key, "cd") == 0 && strcmp(cmd_val, "..") == 0)) { unsigned long long len = strlen(cmd_val); // 目录名约束校验 // 约束：目录名称仅支持小写字母 // 约束：不支持嵌套路径和绝对路径，如 mkdir abc/efg，cd abc/efg，mkdir /abc/efg，cd /abc/efg 是不支持的。 // 关于嵌套路径和绝对路径，我简单理解就是cmd_val含有'/'字符，可以被小写字母判断涵盖住 int i = 0; for (; i < len; i++) { char c = cmd_val[i]; if (c < 'a' || c > 'z') { break; } } if(i != len) { continue; } } if(strcmp(cmd_key, "mkdir") == 0) { mkdir_Tree(tree, cmd_val); // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 memset(lastCommandOutPut, '\0', strlen(lastCommandOutPut)); } else { cd_Tree(tree, cmd_val); // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果 memset(lastCommandOutPut, '\0', strlen(lastCommandOutPut)); } } } puts(lastCommandOutPut); return 0; }