Lua 常用數(shù)據(jù)結(jié)構(gòu)

Lua中的table不是一種簡單的數(shù)據(jù)結(jié)構(gòu)，它可以作為其它數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。如數(shù)組、記錄、線性表、隊列和集合等，在Lua中都可以通過table來表示。 

一、數(shù)組

在lua中通過整數(shù)下標(biāo)訪問表中的元素即可簡單的實現(xiàn)數(shù)組。并且數(shù)組不必事先指定大小，大小可以隨需要動態(tài)的增長。

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中習(xí)慣上數(shù)組的下表從1開始，Lua的標(biāo)準(zhǔn)庫與此習(xí)慣保持一致，因此如果你的數(shù)組下標(biāo)也是從1開始你就可以直接使用標(biāo)準(zhǔn)庫的函數(shù)，否則就無法直接使用。

二、二維數(shù)組

Lua中主要有兩種表示矩陣的方法，第一種是用數(shù)組的數(shù)組表示。也就是說一個表的元素是另一個表。

local N = 3
local M = 3
mt = {}
for i = 1,N do
    mt[i] = {}
    for j = 1,M do
        mt[i][j] = i * j
    end
end

mt = {}
for i = 1, N do
    for j = 1, M do
        mt[(i - 1) * M + j] = i * j
    end
end

三、鏈表

Lua中用tables很容易實現(xiàn)鏈表，每一個節(jié)點是一個table，指針是這個表的一個域，并且指向另一個節(jié)點(table)。例如，要實現(xiàn)一個只有兩個域：值和指針的基本鏈表，代碼如下：

list = nil
for i = 1, 10 do
    list = { next = list ,value = i}
end

local l = list
while l do 
    --print(l.value)
    l = l.next
end

四、隊列與雙向隊列

雖然可以使用Lua的table庫提供的insert和remove操作來實現(xiàn)隊列，但這種方式實現(xiàn)的隊列針對大數(shù)據(jù)量時效率太低，有效的方式是使用兩個索引下標(biāo)，一個表示第一個元素，另一個表示最后一個元素。

List = {}

--創(chuàng)建
function List.new()
    return {first = 0,last = -1}
end

--隊列頭插入
function List.pushFront(list,value)
    local first = list.first - 1
    list.first = first
    list[first] = value
end

--隊列尾插入
function List.popFront(list)
    local first = list.first
    if first > list.last then
        error("List is empty")
    end

    local value = list[first]
    list[first] = nil
    list.first = first + 1
    return value
end

function List.popBack(list)
    local last = list.last
    if list.first > last then
        error("List is empty")
    end
    local value = list[last]
    list[last] = nil
    list.last = last - 1 
    return value
end

--測試代碼
local testList = {first = 0,last = -1}
local tableTest = 12

List.pushFront(testList,tableTest)
print( List.popFront(testList))

五、棧

簡單實現(xiàn)堆棧功能，代碼如下：

local stackMng = {}
stackMng.__index = stackMng

function stackMng:new()
    local temp = {}
    setmetatable(temp,stackMng)
    return temp
end

function stackMng:init()
    self.stackList = {}
end

function stackMng:reset()
    self:init()
end

function stackMng:clear()
    self.stackList = {}
end

function stackMng:pop()
    if #self.stackList == 0 then
        return
    end
    if self.stackList[1] then
        print(self.stackList[1])
    end

    return table.remove(self.stackList,1)
end

function stackMng:push(t)
    table.insert(self.stackList,t)
end

function stackMng:Count()
    return #self.stackList
end

--測試代碼
object = stackMng:new()
object:init()
object:push(1)
object:pop()

六、集合

在Lua中用table實現(xiàn)集合是非常簡單的，見如下代碼：

reserved = {
["while"] = true, ["end"] = true,
["function"] = true, ["local"] = true,
}

for k,v in pairs(reserved) do
    print(k,"->",v)
end