將字典列表轉換爲層次結構

我發現自己需要一些幫助，我試圖將字典列表（您會看到）轉換爲某種樹/層次結構。我需要處理的是深度參數列表的當前順序（這是正確的）。將字典列表轉換爲層次結構

functions = [ 
    {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'}, 
    {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'}, 
    {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'}, 
    {'depth': 1, 'line': 12, 'type': 'def', 'name': 'find_multi(self)'}, 
    {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'}, 
    {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'}, 
    {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'} 
]

我cosidering得到的結果看起來像以下層次：

functions_hir = [{ 
    'value': {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    'children': [{ 

     'value': {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'}, 
     'children': [{ 

      'value': {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'}, 
      'children': [] 
     }] 
    },{ 
     'value': {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'}, 
     'children': [] 
    },{ 
     'value': {'depth': 1, 'line': 12, 'type': 'def', 'name': 'find_multi(self)'}, 
     'children': [] 
    }] 
},{ 
    'value': {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'}, 
    'children': [] 
},{ 
    'value': {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'}, 
    'children': [{ 

     'value': {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'}, 
     'children': [] 
    }] 
}]

現在，它的簡單對我來說，迭代它/遞歸。但我從沒有運氣從我的列表中產生這樣的層次結構（我甚至沒有接近，我猜）..而且我實際上不知道從哪裏開始..希望任何人都能設法幫助我！

來源

2013-07-10 JHolta

對於所示的簡單的情況下，你可以只保留父母的跟蹤和建立你的樹從列表中的一個傳球，像這樣的工作：

hir = {'children': [], 'parent': None} 
depth, current = 0, hir 

for f in functions: 
    f['children'] = [] 
    f_depth = f['depth'] 
    if depth == f_depth: 
     current['children'].append(f) 
     f['parent'] = current 
     current = f 
     depth += 1 
    else: 
     while depth > f_depth: 
      depth -= 1 
      current = current['parent'] 
     current['children'].append(f) 
     f['parent'] = current 
     current = f 
     depth += 1

您希望您的根節點的樣子其他節點，或者你將不得不添加特別的處理，這是混亂的。

來源

2013-07-10 07:41:42

看起來像一個真正的昂貴的解決方案。我需要花點時間考慮我是否會接受它。我不太喜歡這種方式。 – JHolta

昂貴的如何？它引入了一個父指針和一個子列表，但沒有複製。 –

我明白了。那麼，仍然不是我想要的，但我很難理解如何在我的工作中使用這種結構。 – JHolta

你可以使用遞歸方法，該功能將讓你線性時間想詞典：

functions = [ 
    {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'}, 
    {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'}, 
    {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'}, 
    {'depth': 1, 'line': 12, 'type': 'def', 'name': 'find_multi(self)'}, 
    {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'}, 
    {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'}, 
    {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'} 
] 

i = 0 
def gather(d): 
    global i 
    res = [] 
    while i < len(functions): 
     if functions[i]["depth"] < d: 
      return res 
     elif functions[i]["depth"] == d: 
      value, i = functions[i], i + 1 
      children = gather(d + 1) 
      res.append({"value": value, "children": children}) 
    return res 

result = gather(0)

，或者你可以做到這一點沒有全局變量：

def gather(d, i): 
    res = [] 
    while i < len(functions): 
     if functions[i]["depth"] < d: 
      return i, res 
     elif functions[i]["depth"] == d: 
      value = functions[i] 
      i, children = gather(d + 1, i + 1) 
      res.append({"value": value, "children": children}) 
    return i, res 

result = gather(0, 0)[1]

來源

2013-07-10 08:19:46

將字典列表轉換爲層次結構

回答

相關問題