Lua 常用数据结构

最后更新于:2022-04-01 10:07:28

Lua中的table不是一种简单的数据结构,它可以作为其它数据结构的基础。如数组、记录、线性表、队列和集合等,在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中主要有两种表示矩阵的方法,第一种是用数组的数组表示。也就是说一个表的元素是另一个表。 ~~~ 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很容易实现链表,每一个节点是一个table,指针是这个表的一个域,并且指向另一个节点(table)。例如,要实现一个只有两个域:值和指针的基本链表,代码如下: ~~~ 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操作来实现队列,但这种方式实现的队列针对大数据量时效率太低,有效的方式是使用两个索引下标,一个表示第一个元素,另一个表示最后一个元素。 ~~~ List = {} --创建 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)) ~~~ ## 五、栈 简单实现堆栈功能,代码如下: ~~~ 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实现集合是非常简单的,见如下代码: ~~~ reserved = { ["while"] = true, ["end"] = true, ["function"] = true, ["local"] = true, } for k,v in pairs(reserved) do print(k,"->",v) end ~~~
';