命令行软件

题目分析

本题要求模拟一个简化版的命令行文件系统，支持 mkdir、cd、cd ..、ls 四种操作。初始状态下根目录 / 包含一个子目录 /usr，当前工作目录为 /usr。

关键要点：

  • mkdir 创建子目录时，如果同名目录已存在则忽略
  • ls 需要按字典序输出当前目录下所有子目录名，若无子目录则输出一个空格
  • cd .. 回到父目录，cd name 进入子目录

思路

用树形结构模拟文件系统。每个目录节点维护：

  1. 子目录映射（名称 -> 节点编号）：用有序映射（如 C++ 的 map）可以自动按字典序排列，ls 时直接遍历即可
  2. 父节点编号：用于 cd .. 操作

所有目录节点存储在一个数组中，通过编号引用。初始化时创建根目录（编号 0）和 /usr（编号 1），当前位置指向编号 1。

逐条处理命令：

  • mkdir name：在当前节点的子目录映射中查找，不存在则新建节点
  • cd ..：将当前位置切换到父节点
  • cd name：将当前位置切换到对应子节点
  • ls：遍历当前节点的子目录映射，按序输出所有键名

代码

#include <bits/stdc++.h>
using namespace std;

struct Dir {
    map<string, int> children;
    int parent;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<Dir> dirs;
    dirs.push_back({{}, -1});       // 0: root /
    dirs.push_back({{}, 0});        // 1: /usr
    dirs[0].children["usr"] = 1;

    int cur = 1;
    int n;
    cin >> n;
    cin.ignore();

    while (n--) {
        string line;
        getline(cin, line);

        if (line.substr(0, 6) == "mkdir ") {
            string name = line.substr(6);
            if (dirs[cur].children.find(name) == dirs[cur].children.end()) {
                int id = dirs.size();
                dirs.push_back({{}, cur});
                dirs[cur].children[name] = id;
            }
        } else if (line == "cd ..") {
            if (dirs[cur].parent != -1)
                cur = dirs[cur].parent;
        } else if (line.substr(0, 3) == "cd ") {
            string name = line.substr(3);
            if (dirs[cur].children.count(name))
                cur = dirs[cur].children[name];
        } else if (line == "ls") {
            if (dirs[cur].children.empty()) {
                cout << " " << "\n";
            } else {
                bool first = true;
                for (auto& [name, id] : dirs[cur].children) {
                    if (!first) cout << " ";
                    cout << name;
                    first = false;
                }
                cout << "\n";
            }
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        List<TreeMap<String, Integer>> children = new ArrayList<>();
        List<Integer> parent = new ArrayList<>();

        children.add(new TreeMap<>());  // 0: root
        parent.add(-1);
        children.add(new TreeMap<>());  // 1: /usr
        parent.add(0);
        children.get(0).put("usr", 1);

        int cur = 1;
        int n = Integer.parseInt(br.readLine().trim());

        for (int i = 0; i < n; i++) {
            String line = br.readLine().trim();
            if (line.startsWith("mkdir ")) {
                String name = line.substring(6);
                if (!children.get(cur).containsKey(name)) {
                    int id = children.size();
                    children.add(new TreeMap<>());
                    parent.add(cur);
                    children.get(cur).put(name, id);
                }
            } else if (line.equals("cd ..")) {
                if (parent.get(cur) != -1)
                    cur = parent.get(cur);
            } else if (line.startsWith("cd ")) {
                String name = line.substring(3);
                if (children.get(cur).containsKey(name))
                    cur = children.get(cur).get(name);
            } else if (line.equals("ls")) {
                if (children.get(cur).isEmpty()) {
                    sb.append(" \n");
                } else {
                    boolean first = true;
                    for (String name : children.get(cur).keySet()) {
                        if (!first) sb.append(" ");
                        sb.append(name);
                        first = false;
                    }
                    sb.append("\n");
                }
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

children = [{}]  # 0: root
parent = [-1]
children.append({})  # 1: /usr
parent.append(0)
children[0]["usr"] = 1

cur = 1
n = int(input())
out = []

for _ in range(n):
    line = input().strip()
    if line.startswith("mkdir "):
        name = line[6:]
        if name not in children[cur]:
            idx = len(children)
            children.append({})
            parent.append(cur)
            children[cur][name] = idx
    elif line == "cd ..":
        if parent[cur] != -1:
            cur = parent[cur]
    elif line.startswith("cd "):
        name = line[3:]
        if name in children[cur]:
            cur = children[cur][name]
    elif line == "ls":
        if not children[cur]:
            out.append(" ")
        else:
            out.append(" ".join(sorted(children[cur].keys())))

print("\n".join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];

rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    const children = [{}]; // 0: root
    const parent = [-1];
    children.push({}); // 1: /usr
    parent.push(0);
    children[0]["usr"] = 1;

    let cur = 1;
    const n = parseInt(lines[0]);
    const out = [];

    for (let i = 1; i <= n; i++) {
        const line = lines[i];
        if (line.startsWith("mkdir ")) {
            const name = line.substring(6);
            if (!(name in children[cur])) {
                const id = children.length;
                children.push({});
                parent.push(cur);
                children[cur][name] = id;
            }
        } else if (line === "cd ..") {
            if (parent[cur] !== -1)
                cur = parent[cur];
        } else if (line.startsWith("cd ")) {
            const name = line.substring(3);
            if (name in children[cur])
                cur = children[cur][name];
        } else if (line === "ls") {
            const keys = Object.keys(children[cur]).sort();
            if (keys.length === 0) {
                out.push(" ");
            } else {
                out.push(keys.join(" "));
            }
        }
    }
    console.log(out.join("\n"));
});

复杂度分析

  • 时间复杂度：，其中 为命令数， 为单个目录下的最大子目录数。mkdir 和 cd 在有序映射中操作为 ，ls 遍历并输出为 （C++/Java 使用有序映射无需额外排序；Python 需 排序）。
  • 空间复杂度：，其中 为创建的目录总数。