首页 > 代码库 > Lua 之数据结构
Lua 之数据结构
Lua 之数据结构
数组
通过整数下标访问的table中的元素，即是数组，下标默认从1开始。
一个创建二维数组的例子：
mt = {}for i = 1, 10 do mt[i] = {} for j = 1, 10 do mt[i][j] = 0 end end
链表
list = nillist = {next=list, value=http://www.mamicode.com/"world"}list = {next=list, value=http://www.mamicode.com/"hello"}local l = listwhile l do print(l.value) l = l.nextend
队列
queue = {}function queue.new() return {first=0, last=-1}endfunction queue.push(q, val) local last = q.last + 1 q.last = last q[last] = valendfunction 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 valendq = queue.new()for i=1,10,2 do queue.push(q, i)endfor 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 sendreserved = set{"beijing", "xian"}reserved.beijing -- truereserved.shanghai -- nil
字符串缓冲
假如需要读取一个文件的内容，常用的方式如下：
local buff = ""for line in io.lines() do buff = buff .. line .. "\n"endprint(buff)
假设每行有20 bytes，已读了2500行，那么buff现在就是50000B，当Lua做字符串连接时，就新建一个50020B的新字符串，并从buff中复制了50000B到这个新字符串。这样，对于后面的每一行，Lua都需要移动更多的内存，显然，这样做效率是比较低的。
下面是一个改进的版本，利用table做缓冲，最后利用table.concat将所有行连接起来：
local t = {}for line in io.lines() dot[#t+1] = line endlocal s = table.concat(t, ‘\n‘)
那么问题来了，concat的内部工作原理是什么呢，它在连接字符串的时候如何做到高效运行呢？
将每次需要连接的字符串压入堆栈，如果新加入的字符串比栈顶字符串更大，就将两者连接。然后，再将连接后的新字符串与更下面的字符串比较，如果是新建字符串更长的话，则再次连接它们。这样的连接一直向下延续应用，直到遇到一个更大的字符串或者达到了栈底。
function NewStack() return {""}endfunction 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) endendlocal 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]endlocal 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 graphendfunction 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] = nilendfunction printpath(path) for i=1, #path do print(path[i].name) endendg = 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)) endendlocal l = {name=‘cq‘, 5, like={‘movie‘, ‘music‘}}serialize(l)
输出内容：
{ 1 = 5, name = "cq", like = { 1 = "movie", 2 = "music",},}
Lua 之数据结构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。