Lua 之数据结构

Lua 之数据结构

数组

通过整数下标访问的table中的元素，即是数组，下标默认从1开始。

一个创建二维数组的例子：

mt = {}
for i = 1, 10 do
    mt[i] = {}
    for j = 1, 10 do
        mt[i][j] = 0   
    end 
end

链表

list = nil
list = {next=list, value="world"}
list = {next=list, value="hello"}

local l = list

while l do
    print(l.value)
    l = l.next
end 

队列

queue = {}

function queue.new()
    return {first=0, last=-1}
end

function queue.push(q, val)
    local last = q.last + 1
    q.last = last
    q[last] = val
end

function queue.pop(q)
    local first = q.first

    if first > q.last then
        error("queue is empty")
    end

    local val = q[first]
    q[first] = nil
    q.first = q.first + 1
    return val
end

q = queue.new()
for i=1,10,2 do
    queue.push(q, i)
end

for i=q.first,q.last do
    print(queue.pop(q))
end

集合

类似于python的set结构，例如：

function set(list)
    local s = {}
    for _, n in ipairs(list) do
        s[n] = true
    end
    return s
end

reserved = set{"beijing", "xian"}
reserved.beijing        -- true
reserved.shanghai       -- nil

字符串缓冲

假如需要读取一个文件的内容，常用的方式如下：

local buff = ""

for line in io.lines() do
    buff = buff .. line .. "
"
end

print(buff)

假设每行有20 bytes，已读了2500行，那么buff现在就是50000B，当Lua做字符串连接时，就新建一个50020B的新字符串，并从buff中复制了50000B到这个新字符串。这样，对于后面的每一行，Lua都需要移动更多的内存，显然，这样做效率是比较低的。

下面是一个改进的版本，利用table做缓冲，最后利用table.concat将所有行连接起来：

local t = {}

for line in io.lines() do
t[#t+1] = line 
end

local s = table.concat(t, '
')

那么问题来了，concat的内部工作原理是什么呢，它在连接字符串的时候如何做到高效运行呢？

将每次需要连接的字符串压入堆栈，如果新加入的字符串比栈顶字符串更大，就将两者连接。然后，再将连接后的新字符串与更下面的字符串比较，如果是新建字符串更长的话，则再次连接它们。这样的连接一直向下延续应用，直到遇到一个更大的字符串或者达到了栈底。

function NewStack()
    return {""}
end

function push(stack, s)
    table.insert(stack, s)

    for i = table.getn(stack) - 1, 1, -1 do
        if string.len(stack[i]) > string.len(stack[i+1]) then
            break
        end

        stack[i] = stack[i] .. table.remove(stack)
    end
end

local s = NewStack()
for line in io.lines() do
    push(s, line .. "
")
end

图

下面是一个广度优先遍历有向图的例子，其中raw描述了图的所有边，每个边有两个点——起点、终点。

用了一个table来表示点，它有两个字段，name和adj，name表示该点的名称，adj表示它的终点。

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

local function name2node(graph, name)
    if not graph[name] then
        graph[name] = {name=name, adj={}}
    end
    return graph[name]
end

local function readgraph()
    local graph = {}
    for _,v in pairs(raw) do
        local namefrom, nameto = v[1], v[2]

        local from = name2node(graph, namefrom)
        local to = name2node(graph, nameto)
        from.adj[to] = true
    end
    return graph
end

function findpath(curr, to, path, visited)
    path = path or {}
    visited = visited or {}

    if visited[curr] then       -- no path
        return nil
    end

    visited[curr] = true
    path[#path+1] = curr

    if curr == to then  -- be found
        return path
    end

    for node in pairs(curr.adj) do  -- recursive
        local p = findpath(node, to, path, visited)
        if p then return p end
    end

    path[#path] = nil
end



function printpath(path)
    for i=1, #path do
        print(path[i].name)
    end
end

g = readgraph()
a = name2node(g, 'A')
b = name2node(g, 'D')
p = findpath(a, b)
if p then printpath(p) end

序列化

打印一个lua对象：

function serialize(o)
    if type(o) == "number" then
        io.write(o)
    elseif type(o) == "string" then
        io.write(string.format("%q", o))
    elseif type(o) == "table" then
        io.write("{
")
        for k,v in pairs(o) do
            io.write(" ",k," = ")
            serialize(v)
            io.write(",
")
        end
        io.write("}
")
    else
        error("cannot serialize a " .. type(o))
    end
end

local l = {name='cq', 5, like={'movie', 'music'}}

serialize(l)

输出内容：

{
 1 = 5,
 name = "cq",
 like = {
 1 = "movie",
 2 = "music",
}
,
}