Lua中唯一的数据结构——表Table
表构造器(Table Constructor)
空构造器{}
tableArray = {}
列表式初始化表
tableArray = {"c","c++","c#","oc","java","kotlin"}
--使用默认索引对table内值进行访问
print(tableArray[4])
--使用默认索引对table内值进行修改
tableArray[4] = "swift"
记录式初始化表
tableArray = {s1 = "python", s2 = "lua", s3 = "php"}
--上面的初始化表等价于下面的，但是因为上面的表的大小已知，所以速度快一些
tableArray = {}
tableArray.s1 = "python"; tableArray.s2 = "lua"; tableArray.s3 = "php"
--对通过记录式录入的tableArray进行访问时需要注意访问可以通过记录式tableArray.s1或者通用式tableArray["s1"]，而不是tableArray[s1]（此时的s1为一个全局或局部变量而不是特定索引"s1"）
print(tableArray["s1"])
混用式初始化表（混用记录式和列表式）
tableArray = {"c","c++","c#","oc","java","kotlin", s1 = "python", s2 = "lua", s3 = "php"}
通用式初始化表（通过方括号[]括起来表达式指定索引）
tableArray = {"c","c++","c#","oc","java","kotlin", s1 = "python", s2 = "lua", s3 = "php", ["*"] = "swift"}
s = "*"
print(tableArray[s])
print(tableArray["*"])
运行结果：
Array数组
lua表示数组或者列表，只需要使用整型作表的索引就好了，数组大小不固定，可动态增长。
tableArray = {}
for i = 1,10 do
--Read 10 number , save to the tableArray
tableArray[i] = io.read()
end
不存在空洞(hole)的数组，即所有元素都不为nil，在lua中称为序列(sequence)，我们可以通过nil来标记一个表的结束；lua也提供了#操作符 来获取序列的长度
tableArray = {}
for i = 1,10 do
tableArray[i] = i
end
print(#tableArray) --10
tableArray[#tableArray] = nil --set the last element's value to nil
print(#tableArray) --9
--If the array exist hole element
tableArray[4] = nil
print(#tableArray) --9
运行结果：
table相关问题
工作中会遇到接收到的数据有无效项，需要遍历table并且删除掉无效项的情况，在解决时当我们在table表中使用for迭代，将符合条件的元素删除之后，后面元素前移，造成循环最后的索引越界处理过的数组长度——是因为使用for i=1,#table do 这样的循环时，for循环在一开始就已经确定了循环的终点是table初始的总索引长度即在整个for运行过程中，循环的次数不会改变，所以在对无效项进行删除后会出现索引越界的情况
--file: rmtable.lua
t= {}
for i = 1,10 do
t[i] = i
end
function t.print()
for i =1 ,#t do
print(i..'-'..t[i])
end
end
t.print()
t[4] = nil
t[5] = nil
function t.check()
local i = 1
--使用while循环对元素进行检查，如果为空，则移除
while i <= #t do
if t[i] then
print(i.."-"..t[i])
i = i + 1
else
table.remove(t,i)
end
end
end
print("After check:")
t.check()
运行结果：
总结：
- Lua 内部采用数组和哈希表分别保存普通值和键值对，不推荐混合使用这两种赋值方式
- lua5.3版本去掉了获取数组table中默认索引值个数的table.getn方法，但#table仍可以在不同版本中使用
- 如果要删除数组中的某个元素，不要直接以nil值代替，如果要删除一个元素，应使用table.remove()方法
Queue队列
Deque双向队列
--file: Deque.lua
Deque = {}
Deque.__index = Deque
function Deque.new()
deque = {first = 0, last = -1}
return setmetatable(deque, Deque)
end
function Deque:pushleft(value)
local first = self.first -1
self.first = first
self[first] = value
end
function Deque:pushright(value)
local last = self.last +1
self.last = last
self[last] = value
end
function Deque:popleft()
local first = self.first
if first > self.last then error("Deque is empty") end
local value = self[first]
self[first] = nil
self.first = first+1
return value
end
function Deque:popright()
local last = self.last
if self.first > last then error("Deque is empty") end
local value = self[last]
self[last] = nil
self.last = last -1
return value
end
function Deque:print()
local point = self.last
while self.first <= point do
print(self[point])
point = point -1
end
end
测试代码：
--file: testDeque.lua
require "Deque"
deque = Deque.new()
deque:pushleft(1) --Deque[-1] = 1
deque:pushright(2) --Deque[0] = 2
deque:pushleft(3) --Deque[-2] = 3
deque:pushleft(4) --Deque[-3] = 4
deque:pushright(5) --Deque[1] = 5
--依次打印
deque:print()
print("Test deque's pop func")
--移除一个右边的和左边的
print(deque:popright()) -->5
print(deque:popleft()) -->4
运行结果：
LinkedList链表
简单链表的实现
--file: linkedList.lua
list = nil --链表的根节点
for i = 1,10 do
list = {next = list ,value = i} --这样实现的Lua链表类似于C/C++中LIFO的链表
end
--遍历该链表
local l = list
while l do
print(l.value)
l = l.next
end
对Lua链表的具体理解可以参考本文末尾REF链接中stackoverflow中的相关问题
自定义链表的实现
--Node类
Node = {}
Node.__index = Node
function Node.create(newData)
local tNode = {}
--[[
setmetatable(tNode, Node)
tNode.data = newData
return tNode
--]]
--以上代码可简写为：
tNode.data = newData
return setmetatable(tNode,Node)
end
function Node:getData()
return self.data
end
function Node:setData(newData)
self.data = newData
end
function Node:getNext()
return self.nextNode
end
function Node:setNext(newNode)
self.nextNode = newNode
end
function Node:hasNext()
if self.nextNode then
return true
else
return false
end
end
function Node:toString()
return tostring(self.data)
end
--自定义链表类LList
LList = {}
LList.__index = LList
function LList.create()
local list = {} -- our new object
setmetatable(list,LList) -- make LList handle lookup
list.count = 0 -- initialize our object
list.head = nil
return list
end
function LList:add(newNode)
if self.head then
local curr = self.head
while curr.nextNode do
curr = curr.nextNode
end
curr:setNext(newNode)
self.count = self.count + 1
else
self.head = newNode
self.count = 1
end
end
function LList:getLen()
return self.count
end
function LList:toString()
if self.head then
print(self:toStringHelper(self.head))
else
print("emptyList?")
end
end
function LList:toStringHelper(currNode)
if(currNode.nextNode)then
return currNode:toString().. "
" .. self:toStringHelper(currNode.nextNode)
else
return currNode:toString()
end
end
测试代码：
--file: testLList.lua
testerList = LList.create()
print(testerList:getLen())
tNode1=Node.create(5)
tNode2=Node.create(7)
tNode3=Node.create(2)
testerList:add(tNode1)
testerList:add(tNode2)
testerList:add(tNode3)
print(testerList:getLen())
print(testerList:toString())
运行结果：
Set集
Lua中表示一个集合的简单方法：将所有集合中的元素作为下标存放在一个table里，只需要测试给定的元素在table对应下标的值是否为nil
--file: set.lua
Set = {}
Set.mt = {}
function Set.new(t)
local set = {}
for _,v in pairs(t) do
set[v] = true
end
return setmetatable(set,Set.mt)
end
set1 = Set.new{1,2,3,4,5,}
set2 = Set.new{4,5,6,7,8,}
print("The same namber is :")
for k in pairs(set1) do
if set2[k] then
print(k)
end
end
运行结果：
Matrix矩阵
Lua中多维数组的表示方法：
数组的数组表示矩阵
Lua中矩阵的表示方法：一是“数组的数组”——table的每个元素是另一个table。
--file: matrix.lua
--creat a 4*3 matrix
data = {}
--对数组元素赋值
for i = 1,4 do
data[i] = {}
for j = 1 , 3 do
data[i][j] = 0
end
end
--输出数组元素
for i =1 ,#data do
for j =1 ,#data[i] do
print(data[i][j])
end
end
数组的下标表示矩阵
表示矩阵的另一方法，是将行和列组合起来。如果索引下标都是整数，通过第一个索引乘于一个常量（列）再加上第二个索引
data = {}
for i =0 ,3 do
for j = 0,2 do
data[i*3 + j] = 0
end
end
for i = 0 , #data do
print(i..'-'..data[i])
end
StringBuffer
Lua使用真正的垃圾收集算法，当发现程序使用太多的内存他就会遍历他所有的数据结构去释放垃圾数据，一般情况下，这个垃圾收集算法有着很好的性能——Lua的快并非偶然的
--从一个文件中逐行读入字符串
-- WARNING: bad code ahead!!
local buff = ""
for line in io.lines() do
buff = buff .. line .. "
"
end
上面代码的循环使得该情况下Lua的垃圾回收算法的效率极其低下：
“为了理解现象的本质，假定我们身在loop中间，buff已经是一个50KB的字符串，每一行的大小为20bytes，当Lua执行buff..line.." "时，她创建了一个新的字符串大小为50,020 bytes，并且从buff中将50KB的字符串拷贝到新串中。也就是说，对于每一行，都要移动50KB的内存，并且越来越多。读取100行的时候（仅仅2KB），Lua已经移动了5MB的内存”——Programing in Lua
使情况变遭的是下面的赋值语句：
buff = buff .. line .. "
"
“老的字符串变成了垃圾数据，两轮循环之后，将有两个老串包含超过100KB的垃圾数据。这个时候Lua会做出正确的决定，进行他的垃圾收集并释放100KB的内存。问题在于每两次循环Lua就要进行一次垃圾收集，读取整个文件需要进行200次垃圾收集。并且它的内存使用是整个文件大小的三倍。
这个问题并不是Lua特有的：其它的采用垃圾收集算法的并且字符串不可变的语言也都存在这个问题。Java是最著名的例子，Java专门提供StringBuffer来改善这种情况。”——Programing in Lua
解决方法：
“它连接两个小串成为一个稍微大的串，然后连接稍微大的串成更大的串。。。算法的核心是：用一个栈，在栈的底部用来保存已经生成的大的字符串，而小的串从栈定入栈。栈的状态变化和经典的汉诺塔问题类似：位于栈下面的串肯定比上面的长，只要一个较长的串入栈后比它下面的串长，就将两个串合并成一个新的更大的串，新生成的串继续与相邻的串比较如果长于底部的将继续进行合并，循环进行到没有串可以合并或者到达栈底。”——Programing in Lua
function newStack ()
return {""} -- starts with an empty string
end
function addString (stack, s)
table.insert(stack, s) -- push 's' into the the stack
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)
end
end
--使用
local s = newStack()
for line in io.lines() do
addString(s, line .. "
")
end
s = toString(s)
REF
http://lua-users.org/wiki/DataStructures
http://www.lua.org/pil/contents.html
http://www.jb51.net/article/55717.htm
https://stackoverflow.com/questions/15708621/how-does-this-linked-list-example-in-lua-actually-work