首页 > 代码库 > Lua数据结构

Lua数据结构

Lua中的table不是一种简单的数据结构,它可以作为其它数据结构的基础。如数组array、记录record、线性表list、队列queue和集合set等,在Lua中都可以通过table来表示。

数组

在lua中通过整数下标访问表中的元素即可简单的实现数组。并且数组不必事先指定大小,大小可以随需要动态的增长。

a = {}
for i = 1,100 do
    a[i] = 0
end
print("The length of array 'a' is " .. #a)

squares = {1, 4, 9, 16, 25}
print("The length of array 'a' is " .. #squares)
在Lua中习惯上数组的下表从1开始,Lua的标准库与此习惯保持一致,因此如果你的数组下标也是从1开始你就可以直接使用标准库的函数,否则就无法直接使用。

链表

Lua中用tables很容易实现链表,每一个节点是一个table,指针是这个表的一个域(field),并且指向另一个节点(table)。例如,要实现一个只有两个域:值和指针的基本链表,代码如:根节点:list = nil;在链表开头插入一个值为v的节点:list = {next = list, value = http://www.mamicode.com/v}
local list = nil
for i = 1, 10 do
    list = { next = list ,value = http://www.mamicode.com/i}>

其他类型的链表,像双向链表和循环链表类似的也是很容易实现的。然后在Lua中在很少情况下才需要这些数据结构,因为通常情况下有更简单的方式来替换链表。比如,我们可以用一个非常大的数组来表示栈,其中一个域n指向栈顶。

队列与双向队列

虽然可以使用Lua的table库提供的insert和remove操作来实现队列,但这种方式实现的队列针对大数据量时效率太低,有效的方式是使用两个索引下标,一个表示第一个元素,另一个表示最后一个元素。

下面,我们可以在常量时间内,完成在队列的两端进行插入和删除操作了。

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

function List.pushleft (list, value)
    local first = list.first - 1
    list.first = first
    list[first] = value
end
function List.pushright (list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
end
function List.popleft (list)
    local first = list.first
    if first > list.last then error("list is empty") end
    local value = http://www.mamicode.com/list[first]>对严格意义上的队列来讲,我们只能调用pushright和popleft,这样以来,first和last的索引值都随之增加,幸运的是我们使用的是Lua的table实现的,你可以访问数组的元素,通过使用下标从1到20,也可以16,777,216 到 16,777,236。

集合

假定你想列出在一段源代码中出现的所有标示符,某种程度上,你需要过滤掉那些语言本身的保留字。一些C程序员喜欢用一个字符串数组来表示,将所有的保留字放在数组中,对每一个标示符到这个数组中查找看是否为保留字,有时候为了提高查询效率,对数组存储的时候使用二分查找或者hash算法。
Lua中表示这个集合有一个简单有效的方法,将所有集合中的元素作为下标存放在一个table里,下面不需要查找table,只需要测试看对于给定的元素,表的对应下标的元素值是否为nil。比如:
reserved = {["while"] = true,    ["end"] = true,["function"] = true, ["local"] = true,}
for w in allwords() do
    if reserved[w] then
    -- `w' is a reserved word
    end
end

--还可以使用辅助函数更加清晰的构造集合:
function Set (list)
    local set = {}
    for _, l in ipairs(list) do set[l] = true end
    return set
end
reserved = Set{"while", "end", "function", "local", }
说明:集合的元素是table的键,而不是值。原始集合是:{"while", "end", "function", "local", }

在Lua中我们可以将包(Bag)看成MultiSet,与普通集合不同的是该容器中允许key相同的元素在容器中多次出现。下面的代码通过为table中的元素添加计数器的方式来模拟实现该数据结构,如:

function insert(bag, element)
    bag[element] = (bag[element] or 0) + 1
end

function remove(bag, element)
    local count = bag[element]
    bag[element] = (count and count > 1) and count - 1 or nil
end

字符串缓冲

如果想在Lua中将多个字符串连接成为一个大字符串的话,可以通过如下方式实现,如:
local buff = ""
for line in io.lines() do
    buff = buff .. line .. "\n"
end
上面的代码确实可以正常的完成工作,然而当行数较多时,这种方法将会导致大量的内存重新分配和内存间的数据拷贝,由此而带来的性能开销也是相当可观的。事实上,在很多编程语言中String都是不可变对象,如Java,因此如果通过该方式多次连接较大字符串时,均会导致同样的性能问题。为了解决该问题,Java中提供了StringBuilder类,而Lua中则可以利用table的concat方法来解决这一问题,见如下代码:
local t = {}
for line in io.lines() do
    t[#t + 1] = line .. "\n"
end
local s = table.concat(t)

--concat方法可以接受两个参数,因此上面的方式还可以改为:
local t = {}
for line in io.lines() do
    t[#t + 1] = line
end
local s = table.concat(t,"\n")


Lua数据结构