如何編寫一個返回嵌套表中的鍵列表的函數？

Question

我有一個分層嵌套的關聯數組。它看起來像這樣：

A = { 
    B = { 
     C = {}, 
     D = {}, 
    }, 
    E = { 
     F = { 
      G = {} 
     } 
    }, 
    H = {} 
} 

我想寫一個函數，返回每個鍵的「祖先」。

所以：

f("A") = {"A"} 
f("B") = {"B","A"} 
f("C") = {"C","B","A"} 
f("G") = {"G","F","E","A"} 
f("fake") = {} 

我已經工作了，我需要使用遞歸，但我有困難的寫入功能。有人能給我一些關於如何編寫這樣一個函數的指針嗎？

（請不要把我同http://xkcd.com/138/！）

Answer 1

只需申請一個遞歸depth-first search找到你的特定元素，並返回路徑。

構建元素路徑的遞歸步驟X。

• 如果當前元素爲X：返回{X}

• 如果當前元素不是X：

  1. 檢查所有的子節點。
  2. 獲取返回有效路徑並向其中添加當前元素的子節點。
  3. 如果沒有有效的子節點，則返回nil。

Answer 2

A = { 
    B = { 
     C = {}, 
     D = {}, 
    }, 
    E = { 
     F = { 
      G = {} 
     } 
    }, 
    H = {} 
} 

function f(root, find) 
    -- iterate over all child values 
    for k, v in pairs(root) do 
     if k == find then 
      -- found the match 
      return({find}) 
     else 
      -- no match, search the children 
      tmp = f(root[k], find) 
      if tmp ~= nil then 
       table.insert(tmp, 1, k) 
       return tmp 
      end 
     end 
    end 
end 

print(table.concat(f(A, "G"), " ")) 

，因爲你無法檢索次序最高的表的名稱（在這種情況下，A），則可能需要嵌套該表到另一個表，如下面的例子：

r = {A = { 
    B = { 
     C = {}, 
     D = {}, 
    }, 
    E = { 
     F = { 
      G = {} 
     } 
    }, 
    H = {} 
} 
} 

在這種情況下，您需要調用f（r，「G」）的原因。

Answer 3

這是我想出了用達里奧的建議解決方案：

function checkTable(t, key) 
    if t[key] then 
     return {key} 
    else 
     for k, subtable in pairs(t) do 
      local children = checkTable(subtable,key) 
      if #children ~= 0 then 
       table.insert(children,1,k) 
       return children 
      end 
     end 
     return {} 
    end 
end 

Answer 4

如果有層次的循環，你需要跟蹤訪問子表。 請參閱Lua live demo中的globals code。