Lua程序设计（6）

Lua中的数据结构：数组、链表、队列等

数组：

在Lua语言中使用整数来索引表就可以实现数组，因此数组的大小不用非得是固定的，而是可以按需增长的。

在Lua语言中一般以1作为数组的起始索引。

矩阵及多维数组：

使用一个不规则数组：

即数组的数组，一个所有元素均是另一个表的表。

这种矩阵在创建时必须显式的创建每一行，一方面更加具体，另一方面增加了更多的灵活性。

将两个索引合并为一个：

我们通过将第一个索引乘以一个合适的常量再加上第二个索引来实现这种效果，在这种方式下，我们可以使用以下的代码来创建一个全0元素的N*M矩阵：

1
2
3
4
5
6
7

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

链表：

我们可以把每个节点用一个表来表示，链接则为一个包含指向其他表的引用的简单表字段：

根结点：list = nil

在表头插入一个值为v的元素：

1

list = {next = list,value = v}

遍历链表：

1
2
3
4
5

local l = list
while l do
	visit l.value
	l = l.next
end

队列及双端队列：

一种简单的方法是使用table标准库中的函数insert和remove，不过这种移动对于较大的结构来说开销很大。

一种更高效的实现是使用两个索引，一个指向第一个元素，另一个指向最后一个元素，这样就可以以O(1)时间复杂度同时在首尾两端插入或删除元素了。