• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Lua 之数据结构

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 

 

 

数组

通过整数下标访问的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 .. "\n"
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, '\n')

 

那么问题来了,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 .. "\n")
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("{\n")
        for k,v in pairs(o) do
            io.write(" ",k," = ")
            serialize(v)
            io.write(",\n")
        end
        io.write("}\n")
    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",
}
,
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
redis~lua脚本的使用发布时间:2022-07-22
下一篇:
一个比较完整的lisp解释器 lua实现发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap