嵌套列表转字符串

Question

我有一个包含多个Test类实例的列表。这个类里面有一些方法，比如name和parent。

[Test('a', ''), Test('b', ''), Test('c', 'a'), Test('d', 'a'), Test('e', 'c')]

第一个参数是名字，第二个参数是父类。父类的参数其实就是父类的name。

我想把这个列表转换成一个字符串，格式像这样：

Test('a', '')
  |-- Test('c', 'a')
        |-- Test('e', 'c')
  |-- Test('d', 'a')
Test('b', '')

我在寻找一种最省CPU的方式来把这个列表转换成字符串。列表里的项目可以嵌套多层（比如10层、100层、1000层……），我对使用的内存不太在意。

Answer 1

如果你按照fiver的建议使用深度优先搜索（DFS），你可以用networkx这个库。

import networkx as nx
stuff=[('a', ''), ('b', ''), ('c', 'a'), ('d', 'a'), ('e', 'c')]
G=nx.DiGraph()
for i in stuff:
    G.add_edge(i[1],i[0])
print G.adj

然后就是用深度优先搜索来遍历它了。

Answer 2

你应该使用另一个容器，像这样：

class Test:
    def __init__(self, name, sub=None):
        self.name = name
        self.sub = sub if sub is not None else []

elements = [Test('a', [Test('c', [Test('e')]), Test('d')]), Test('b')]

然后只需遍历 elements 来打印：

def show(x, indent=0):
    for i in x:
        print('\t'*indent + 'Test(%r)' % i.name)
        show(i.sub, indent+1)

show(elements)

应该打印出：

Test('a')
    Test('c')
        Test('e')
    Test('d')
Test('b')

你可以把缩进改成你喜欢的样子（我这里用的是制表符）。

Answer 3

这里有一段可以直接使用的代码。基本上，它的作用是把一个数组转换成一棵树，然后用递归的深度优先搜索（DFS）来打印这棵树（如果你想的话，也可以用迭代的深度优先搜索）。

class Test:
    def __init__(self, name, parent):
        self.name = name
        self.parent = parent
    def __repr__(self):
        return "Test('"+self.name+"', '"+self.parent+"')"



li = [Test('a', ''), Test('b', ''), Test('c', 'a'), Test('d', 'a'), Test('e', 'c')]

dict = {"":(None,[])} #name to (node,children)
#add nodes
for item in li:
    dict[item.name] = (item, [])
#add children
for item in li:
    dict[item.parent][1].append(dict[item.name])

def printTree(dict, name, indent):
    newIndent=indent
    if name!="":
        print(indent + str(dict[name][0]))
        if indent == "": newIndent="  |-- "
        else: newIndent = "      "+indent
    for child in dict[name][1]:
        printTree(dict, child[0].name, newIndent) 


printTree(dict, "", "")