Lua学习笔记之数据结构

最近研究Lua，顺便写点笔记吧！数据结构是没有语言之分的，只不过不同的语言实现起来的语法不同，既然是Lua菜鸟，就来实现几个常用的数据结构来练练语法吧！首先是作为数据结构基石的数组，在Lua中数组是用表来实现的，表是个强大的东西，能表示太多东西了，当表中元素的下标都是整数的时候，我们把这个表称作数组。数组的大小不固定，可以动态的增长。

代码如下：

--创建一个简单的数组

local arr1 = {1,2,3,4,5,6}

--遍历数组中得每一个元素

for i,v in ipairs(arr1) do

print(v)

end

--另一种创建数组的方式

local arr2 = {}

for i=1,10 do

arr2[i] = i

print(arr2[i])

end


--创建数组，下标从2开始

local arr2 = {[2]="hello",[3]="xiao",[4]="ta",[5]="zaojiahua"}

--使用迭代器ipairs遍历的时候输出为空值，因为arr2[1]=nil当ipairs遇到空值的时候就返回了

for i,v in ipairs(arr2) do

print(i,v)

end

--这个时候需要使用pairs遍历

for i,v in pairs(arr2) do

print(i,v)

end

创建数组的时候整数下标最好从1开始，因为这个值是Lua中默认开始的下标，这和其他语言的下标从零开始有点区别，如果你采用其他的数字下标开始，使用某些Lua库的时候可能不能获得预期的结果。然后就是遍历数组的方式，我们用到了迭代器ipairs()和pairs()，这个使用时候的区别代码已经有体现了，ipairs中得i代表的就是整数下标，从1开始。

有一维数组当然就有多维的，下面来创建一个二维数组，也就是矩阵，其他的类推吧。

代码如下：

--创建一个10*5的二维数组

local int_arr = {}

for i=1,10 do

    int_arr[i] = {}

    for j=1,5 do

        int_arr[i][j] = j

    end

end


--遍历二维数组

for i,v in ipairs(int_arr) do

    for j,k in ipairs(v) do

        io.write(k.."\t")

    end

    print("\n")

end

接下来实现一个链表，链表的每个节点用一个table表示，table中的字段包括指向下一个节点的指针和该节点的数据元素，这里只是提供一个思路，其他的东西可以用的时候扩展。

代码如下：

--实现一个链表

local list = nil

--链表元素包含俩个字段，next代表的是指针，指向下一个链表元素，value代表的是该链表元素的值

for i=1,10 do

    list = {next = list,value = i}

end

--链表的遍历

local l = list

while l do

    print(l.value)

    l = l.next

end

接下来实现一个比较有用的数据结构――队列。我把队列封装在了一个table表中，关于队列的操作和表示队列头和队列尾的指针也封装在了一起。当对头等于队尾的时候表示没有元素，而这个队列是可以无限增大的，并没有队列满的限制，大家可以根据自己的需要进行扩展。

代码如下：

--实现一个队列 包括头指针first和尾指针last first==last的时候代表队列为空

local Que = {first=0,last=0}

--向队列中添加元素，last索引指向最后一个元素的下一个元素，first索引指向的是第一个元素

function Que:push(value)

    local last = self.last

    self[last] = value

    self.last = last+1

end

--移除元素，队列的特点是先进先出

function Que:pop()

    if self.first == self.last then

        print("队列空")

        return nil

    end

    local first = self.first

    self.first = first+1

    return self[first]

end


--显示队列中得元素

function Que:showValue()

    for i=self.first,self.last-1 do

        print("value:"..self[i])

    end

end


--测试

print("队列测试")

Que:showValue()

Que:push(2)

Que:push(3)

print("push 2,3")

Que:showValue()

Que:push(3)

print("push 3")

Que:showValue()

print("pop:"..Que:pop())

Que:showValue()

print("pop:"..Que:pop())

Que:showValue()

print("push 100")

Que:push(100)

Que:showValue()

print("pop:"..Que:pop())

Que:showValue()

print("pop:"..Que:pop())

Que:showValue()

print("pop:"..Que:pop())