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

输入描述

题目描述

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

支持命令：

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

约束：

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

输入描述

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

输出描述

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

备注

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

用例

输入	mkdir abc cd abc pwd
输出	/abc/
说明	在根目录创建一个abc的目录并进入abc目录中查看当前目录路径，输出当前路径/abc/。

题目解析

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

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

关于树节点定义如下：

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，有两种情况：

cd ..
cd .. 是返回上级目录（父目录），但是前提是 tree.cur.father 存在，否则不操作。如果 tree.cur.father 存在，则cd .. 会改变 tree.cur = tree.cur.father。
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, '', strlen(lastCommandOutPut));
            } else {
                cd_Tree(tree, cmd_val);
                // 题目进要求输出最后一个命令的运行结果，因此，对于无输出的命令，我认为需要覆盖掉前面的命令的输出结果
                memset(lastCommandOutPut, '', strlen(lastCommandOutPut));
            }
        }
    }

    puts(lastCommandOutPut);

    return 0;
}

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=c%e5%8d%b7200%e5%88%86-%e6%a8%a1%e6%8b%9f%e7%9b%ae%e5%bd%95%e7%ae%a1%e7%90%86%e5%8a%9f%e8%83%bd%ef%bc%88java-js-python-c%ef%bc%89，转载请注明出处。

2024华为OD机试题库