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

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

一、數(shù)組

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

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

二、二維數(shù)組

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

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很容易實(shí)現(xiàn)鏈表，每一個(gè)節(jié)點(diǎn)是一個(gè)table，指針是這個(gè)表的一個(gè)域，并且指向另一個(gè)節(jié)點(diǎn)(table)。例如，要實(shí)現(xiàn)一個(gè)只有兩個(gè)域：值和指針的基本鏈表，代碼如下：

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

四、隊(duì)列與雙向隊(duì)列

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

List = {}

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

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

--隊(duì)列尾插入
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

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

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

五、棧

簡(jiǎn)單實(shí)現(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

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

六、集合

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

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

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