Lua学习笔记，八：数据结构

　　table是Lua中唯一的数据结构，其他语言所提供的数据结构，如：arrays、records、lists、queues、sets等，Lua都是通过table来实现，并且在Lua中table很好的实现了这些数据结构。

　　1、数组

　　在Lua中通过整数下标访问table中元素，既是数组，并且数组大小不固定，可动态增长。通常我们初始化数组时，就间接地定义了数组的大小，例如：

 1 a = {}        -- new array
 2 for i=1, 1000 do
 3     a[i] = 0
 4 end
 5 
 6 --数组a的大小为1000，访问1-1000范围外的值，将返回nil。
 7 --数组下标可以根据需要，从任意值开始
 8 -- creates an array with indices from -5 to 5
 9 a = {}
10 for i=-5, 5 do
11     a[i] = 0
12 end

　　然而习惯上，Lua的下标从1开始。Lua的标准库遵循此惯例，因此你的数组下标必须也是从1开始，才可以使用标准库的函数。

　　我们可以用构造器在创建数组的同时初始化数组，这样数组的大小可以任意的大。

1 squares = {1, 4, 9, 16, 25, 36, 49, 64, 81}

　　2、矩阵和多维数组

　　Lua中有两种表示矩阵的方法，一是"数组的数组"，也就是table的每个元素是另一个table。

--可以使用下面代码创建一个n行m列的矩阵
mt = {}            -- create the matrix
for i=1,N do
    mt[i] = {}        -- create a new row
    for j=1,M do
        mt[i][j] = 0
    end
end

--由于Lua中table是对象，所以每一行我们必须显示地创建一个table，比起c这显得冗余，
--但另一方面也提供了更多的灵活性，比如可修改前面的例子创建一个三角矩阵
for j=1,M do     --修改为      for j=1,i do

--这样实现的三角矩阵比起整个矩阵，仅适用一半的内存空间

　　表示矩阵的另一方法，是将行和列组合起来。如果索引下标都是整数，通过第一个索引乘于一个常量(列)再加上第二个索引。

1 --看下面的例子实现创建n行m列的矩阵
2 mt = {}            -- create the matrix
3 for i=1,N do
4     for j=1,M do
5         mt[i*M + j] = 0
6     end
7 end

　　如果索引是字符串，可用一个单字符将两个字符串索引连接起来构成一个单一的索引下标。

　　3、链表

　　Lua中用tables很容易实现链表，每一个节点是一个table，指针是这个表的一个域(field)，并且指向另一个节点(table)。

 1 --要实现一个只有两个域：值和指针的基本链表
 2 
 3 --根节点
 4 list = nil
 5 
 6 --在链表开头插入一个值为v的节点
 7 list = {next = list, value = v}
 8 
 9 --要遍历这个链表只需要
10 local l = list
11 while l do
12     print(l.value)
13     l = l.next
14 end

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

　　4、队列和双向队列

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

 1 function ListNew ()
 2     return {first = 0, last = -1}
 3 end
 4 
 5 --为了避免污染全局命名空间，我们重写上面的代码，将其放在一个名为list的table中
 6 List = {}
 7 function List.new ()
 8     return {first = 0, last = -1}
 9 end
10 
11 --下面，我们可以在常量时间内，完成在队列的两端进行插入和删除操作了
12 function List.pushleft (list, value)
13     local first = list.first - 1
14     list.first = first
15     list[first] = value
16 end
17 
18 function List.pushright (list, value)
19     local last = list.last + 1
20     list.last = last
21     list[last] = value
22 end
23 
24 function List.popleft (list)
25     local first = list.first
26     if first > list.last then error("list is empty") end
27     local value = list[first]
28     list[first] = nil        -- to allow garbage collection
29     list.first = first + 1
30     return value
31 end
32 
33 function List.popright (list)
34     local last = list.last
35     if list.first > last then error("list is empty") end
36     local value = list[last]
37     list[last] = nil        -- to allow garbage collection
38     list.last = last - 1
39     return value
40 end

　　对严格意义上的队列来讲，我们只能调用pushright和popleft，这样以来，first和last的索引值都随之增加，幸运的是我们使用的Lua的table实现的，你可以访问数组的元素，通过使用下标从1到20，也可以16,777,216带16,777,236。另外Lua使用双精度表示数字，假定你每秒钟执行100万次插入操作，在数值溢出以前你的程序可以运行200年。

　　5、集合和包

　　假定你想列出在一段源代码中出现的所有标示符，某种程度上，你需要过滤掉那些语言本身的保留字。一些C程序员喜欢用一个字符串数组来表示，将所有的保留字放在数组中，对每一个标示符到这个数组中查找看是否为保留字，有时候为了提高查询效率，对数组存储的时候使用二分查找或者hash算法。

　　Lua中表示这个集合有一个简单有效的方法，将所有集合中的元素作为下标存放在一个table里，不需要查找table，只需要测试看对于给定的元素，表的对应下标的元素值是否为nil。

 1 reserved = {
 2     ["while"] = true,        ["end"] = true,
 3     ["function"] = true,    ["local"] = true,
 4 }
 5 
 6 for w in allwords() do
 7     if reserved[w] then
 8     -- `w' is a reserved word
 9     ...
10 
11 --还可以使用辅助函数更加清晰的构造集合
12 function Set (list)
13     local set = {}
14     for _, l in ipairs(list) do set[l] = true end
15     return set
16 end
17 
18 reserved = Set{"while", "end", "function", "local", }