02775: 文件结构“图”

http://cs101.openjudge.cn/practice/02775/

在计算机上看到文件系统的结构通常很有用。Microsoft Windows上面的"explorer"程序就是这样的一个例子。但是在有图形界面之前，没有图形化的表示方法的，那时候最好的方式是把目录和文件的结构显示成一个"图"的样子，而且使用缩排的形式来表示目录的结构。比如：

ROOT
|     dir1
|     file1
|     file2
|     file3
|     dir2
|     dir3
|     file1
file1
file2

这个图说明：ROOT目录包括三个子目录和两个文件。第一个子目录包含3个文件，第二个子目录是空的，第三个子目录包含一个文件。

输入

你的任务是写一个程序读取一些测试数据。每组测试数据表示一个计算机的文件结构。每组测试数据以 '*' 结尾，而所有合理的输入数据以 '#' 结尾。一组测试数据包括一些文件和目录的名字（虽然在输入中我们没有给出，但是我们总假设ROOT目录是最外层的目录）。在输入中,以 ']' 表示一个目录的内容的结束。目录名字的第一个字母是 'd'，文件名字的第一个字母是 'f'。文件名可能有扩展名也可能没有（比如fmyfile.dat和fmyfile）。文件和目录的名字中都不包括空格,长度都不超过30。一个目录下的子目录个数和文件个数之和不超过30。

输出

在显示一个目录中内容的时候，先显示其中的子目录（如果有的话），然后再显示文件（如果有的话）。文件要求按照名字的字母表的顺序显示（目录不用按照名字的字母表顺序显示，只需要按照目录出现的先后显示）。对每一组测试数据，我们要先输出"DATA SET x:"，这里x是测试数据的编号（从1开始）。在两组测试数据之间要输出一个空行来隔开。

你需要注意的是，我们使用一个'|'和5个空格来表示出缩排的层次。

样例输入

file1
file2
dir3
dir2
file1
file2
]
]
file4
dir1
]
file3
*
file2
file1
*
#

样例输出

DATA SET 1:
ROOT
|     dir3
|     |     dir2
|     |     file1
|     |     file2
|     dir1
file1
file2
file3
file4

DATA SET 2:
ROOT
file1
file2

提示

一个目录和它的子目录处于不同的层次 一个目录和它的里面的文件处于同一层次

来源: 翻译自 Pacific Northwest 1998 的试题

洪亮 物理学院

思路：把目录看成节点，每个目录节点设置子目录节点列表和子文件列表。输出格式：当前目录，遍历子目录，遍历子文件。

class Node:
    def __init__(self,name):
        self.name=name
        self.dirs=[]
        self.files=[]

def print_(root,m):
    pre='|     '*m
    print(pre+root.name)
    for Dir in root.dirs:
        print_(Dir,m+1)
    for file in sorted(root.files):
        print(pre+file)
        
tests,test=[],[]
while True:
    s=input()
    if s=='#':
        break
    elif s=='*':
        tests.append(test)
        test=[]
    else:
        test.append(s)
for n,test in enumerate(tests,1):
    root=Node('ROOT')
    stack=[root]
    print(f'DATA SET {n}:')
    for i in test:
        if i[0]=='d':
            Dir=Node(i)
            stack[-1].dirs.append(Dir)
            stack.append(Dir)
        elif i[0]=='f':
            stack[-1].files.append(i)
        else:
            stack.pop()
    print_(root,0)
    print()

上面代码逻辑非常清晰、可读性也很好。整体上已经是一个标准的 DFS 树结构构建 + 递归打印的写法。下面保持原有风格的前提下，做一些 优化与精简（主要是性能、结构与边界处理方面）： 优化版代码

class Node:
    __slots__ = ('name', 'dirs', 'files')
    def __init__(self, name):
        self.name = name
        self.dirs = []
        self.files = []

def print_tree(node, depth=0):
    prefix = '|     ' * depth
    print(prefix + node.name)
    for d in node.dirs:               # 子目录按出现顺序
        print_tree(d, depth + 1)
    for f in sorted(node.files):      # 文件按字母序
        print(prefix + f)

def parse_dataset(lines):
    root = Node('ROOT')
    stack = [root]
    for s in lines:
        if s[0] == 'd':               # 目录
            new_dir = Node(s)
            stack[-1].dirs.append(new_dir)
            stack.append(new_dir)
        elif s[0] == 'f':             # 文件
            stack[-1].files.append(s)
        elif s == ']':                # 目录结束
            stack.pop()
    return root

def main():
    datasets, current = [], []
    while True:
        try:
            s = input().strip()
        except EOFError:
            break
        if s == '#':
            if current:
                datasets.append(current)
            break
        elif s == '*':
            datasets.append(current)
            current = []
        else:
            current.append(s)

    for i, data in enumerate(datasets, 1):
        print(f'DATA SET {i}:')
        print_tree(parse_dataset(data))
        print()

if __name__ == "__main__":
    main()

改进要点说明

1. 更轻量的类定义

   • 使用 __slots__ 节省内存，避免动态属性创建。

   • 不改变你原来的面向对象思路。

2. 逻辑结构更清晰

   • parse_dataset() 专职解析输入 → 返回树结构；

   • print_tree() 专职输出；

   • main() 负责输入输出流程。

3. 更安全的输入处理

   • 用 try/except EOFError 避免 OJ 环境下读空出错；

   • 处理最后一组未以 * 结尾但以 # 终止的情况。

4. 性能小优化

   • 仅对子文件进行 sorted()；

   • 栈式构建比递归解析更稳定；

   • 少量字符串拼接用局部变量缓存（prefix）。

考虑递归，对于输入文件 f 开头则存起来，d 开头则多记一个缩进递归，] 结尾则将存贮的files排序输出并结束该字典。

# 夏天明，元培学院
from sys import exit

class dir:
    def __init__(self, dname):
        self.name = dname
        self.dirs = []
        self.files = []
    
    def getGraph(self):
        g = [self.name]
        for d in self.dirs:
            subg = d.getGraph()
            g.extend(["|     " + s for s in subg])
        for f in sorted(self.files):
            g.append(f)
        return g

n = 0
while True:
    n += 1
    stack = [dir("ROOT")]
    while (s := input()) != "*":
        if s == "#": exit(0)
        if s[0] == 'f':
            stack[-1].files.append(s)
        elif s[0] == 'd':
            stack.append(dir(s))
            stack[-2].dirs.append(stack[-1])
        else:
            stack.pop()
    print(f"DATA SET {n}:")
    print(*stack[0].getGraph(), sep='\n')
    print()

钟明衡-23-物理学院：写了一个File类，默认名称为'ROOT'，当出现file就存储，dir就建一个新的类接收，直到']'结束

输出时，先输出原顺序的dir，要在每一行以前加上'| '，这个可以自动嵌套，然后输出排序了的file。

OJ上大部分树题目其实不用类也能做，用defaultdict存索引还是很方便的。但是，递归思想在很多方面都可以使用，是一种省事而且优美的方法。我对递归的理解是，规定一个base case，然后告诉计算机大概要做什么，让它自己用同一套逻辑去算就好了。包括写类的时候，指针指向同样是这个类的元素，也是一种递归想法。举个例子，建树的时候，把左右子节点都看成一棵新的树，大概就是这么个想法。这种思路在各种场景下都有不错的表现。

class File:
    def __init__(self):
        self.name = 'ROOT'
        self.files = []
        self.dirs = []

    def __str__(self):
        return '\n'.join([self.name]+['|     '+s for d in self.dirs for s in str(d).split('\n')]+sorted(self.files))

    def build(self, parent, s):
        if s[0] == 'f':
            parent.files.append(s)
        else:
            dir = File()
            dir.name = s
            parent.dirs.append(dir)
            while True:
                s = input()
                if s == ']':
                    break
                dir.build(dir, s)


x = 0
while True:
    s = input()
    if s == '#':
        break
    x += 1
    root = File()
    while s != '*':
        root.build(root, s)
        s = input()
    print('DATA SET %d:' % x)
    print(root, end='\n\n')

# 蒋子轩23工学院
def print_structure(node,indent=0):
	#indent为缩进个数
    prefix='|     '*indent
    print(prefix+node['name'])
    for dir in node['dirs']:
    	#若为目录继续递归
        print_structure(dir,indent+1)
    for file in sorted(node['files']):
    	#若为文件直接打印
        print(prefix+file)
dataset=1
datas=[]
temp=[]
#读取输入
while True:
    line=input()
    if line=='#':
        break
    if line=='*':
        datas.append(temp)
        temp=[]
    else:
        temp.append(line)
for data in datas:
    print(f'DATA SET {dataset}:')
    root={'name':'ROOT','dirs':[],'files':[]}
    stack=[root]
    #用栈实现后进先出
    for line in data:
        if line[0]=='d':
            dir={'name':line,'dirs':[],'files':[]}
            stack[-1]['dirs'].append(dir)
            stack.append(dir)
        elif line[0]=='f':
            stack[-1]['files'].append(line)
        else:  #某种结束符
            stack.pop()
    print_structure(root)
    if dataset<len(datas):
        print()
    dataset+=1

罗熙佑思路：根据树的递归定义操作。这题之前拿 C++ 做过，当时几乎不会树，靠递归手搓，代码又臭又长，写起来也容易错，当时de了很久bug;现在系统学了树就感觉蛮简单了，可以用map+lambda函数来处理了缩进，其他地方模版性比较强；代码写了详细注释，可供参考。

# 罗熙佑
from typing import List
class Node:
    def __init__(self, v) -> None:
        self.v = v # value
        self.c = [] # children

def build_tree(s: List[str]) -> Node:
    '''
    从s中读取数据并建树，返回root；
    s是一组输入数据的列表，原输入的每一行是一个列表一个元素
    s: sequence
    '''
    # base case 1: s读完，说明本组数据结束
    if not s:
        return None
    
    t = s.pop() # token

    # base case 2: 读到]代表目录结束，读到f代表叶节点
    if t == ']':
        return None
    if t[0] == 'f':
        return Node(t)

    # step1: build root
    root = Node(t)

    # step2: build subtree and connect
    while nd := build_tree(s): # 如果建出None就不加，用海牛让代码更简洁
        root.c.append(nd)

    # step3: sort
    dire = [n for n in root.c if n.v[0] == 'd']
    file = [n for n in root.c if n.v[0] == 'f']
    file.sort(key=lambda u: u.v) # 把文件按字典序排序
    root.c = dire + file

    #step 4: return
    return root

def traversal(root: Node) -> List[str]:
    '''把以root为根的树的待打印内容放到sq列表，每一行内容作为一个元素；并返回sq'''
    sq = [] # sequence

    # step1: add root
    sq.append(root.v)

    # step2: add subtree, from left to right
    for n in root.c: # node
        # 2.1: if node is leaf, i.e. file
        if n.v[0] == 'f':
            sq.append(n.v)
        # 2.2: 
        else: # if node is dir, add indentation for every node of the subtree whose root is the 'dir'
            sq.extend(map(lambda x: "|     " + x, traversal(n)))

    # step3: return
    return sq
            
def main() -> None:
    # read input data
    s = ['ROOT']
    idx = []
    cnt = 0
    while True:
        t = input()
        if t == '#':
            break
        s.append(t)
        cnt += 1
        if t == '*':
            idx.append(cnt)
            s[-1] = 'ROOT'

    for i in range(1, len(idx) + 1):
        print(f"DATA SET {i}:")
        root = build_tree(s[idx[i - 1] - 1: idx[i - 2] - 1 if i > 1 else None: -1])
        print('\n'.join(traversal(root)), end='\n\n')

if __name__ == "__main__":
    main()