如何编写一个返回嵌套表中键列表的函数？

2010-2-22 18:56:28
收藏：0
阅读：220
评论：4

我有一个层级嵌套的关联数组。它看起来像这样：

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/！）

原文链接 https://stackoverflow.com/questions/2313257

点赞
stackoverflow用户105459
stackoverflow用户105459

只需应用递归深度优先搜索来查找您指定的元素并返回路径。

递归步骤以构建元素“X”的路径。

  • 如果当前元素是“X”，则返回{X}

  • 如果当前元素不是“X”：

    1. 检查所有子节点。
    2. 获取返回有效路径的子节点，并将当前元素添加到该路径中。
    3. 如果没有有效的子节点，则返回nil。
2010-02-22 18:50:43
stackoverflow用户278947
stackoverflow用户278947 
A = {
    B = {
        C = {},
        D = {},
    },
    E = {
        F = {
            G = {}
        }
    },
    H = {}
}

function f(root, find)
    -- 迭代所有子节点值
    for k, v in pairs(root) do
        if k == find then
            -- 找到匹配点
            return({find})
        else
            -- 没有匹配，继续搜索子节点
            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")。

2010-02-22 19:34:57
stackoverflow用户102441
stackoverflow用户102441

这是我根据 Dario 的建议所想出的解决方案：

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
2010-02-22 20:33:22
stackoverflow用户107090
stackoverflow用户107090

如果层次结构中存在循环，您需要跟踪已访问的子表格。 请参见Lua live demo中的globals code。

2010-02-22 22:07:49

作者:

stackoverflow用户102441

stackoverflow用户102441
推荐文章