欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Lua中使用table实现的其它5种数据结构

程序员文章站 2022-06-17 08:05:05
lua中的table不是一种简单的数据结构,它可以作为其他数据结构的基础,如:数组,记录,链表,队列等都可以用它来表示。 1、数组 在lua中,table的索引可以有很...

lua中的table不是一种简单的数据结构,它可以作为其他数据结构的基础,如:数组,记录,链表,队列等都可以用它来表示。

1、数组

在lua中,table的索引可以有很多种表示方式。如果用整数来表示table的索引,即可用table来实现数组,在lua中索引通常都会从1开始。

复制代码 代码如下:

--二维数组
n=10 m=10
arr={}
for i=1,n do
     arr[i]={}
   for j=1,m do
      arr[i][j]=i*j
   end
end

for i=1, n do
   for j=1, m do
      if(j~=m) then  io.write(arr[i][j].." ")
      else print(arr[i][j])
      end
   end
end

2、链表

在lua中,由于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

3、队列与双端队列

在lua中实现队列的简单方法是调用table中insert和remove函数,但是如果数据量较大的话,效率还是很慢的,下面是手动实现,效率快许多。

复制代码 代码如下:

list={}

function list.new()
   return {first=0, last=-1}
end

function list.pushfront(list,value)
   list.first=list.first-1
   list[ list.first ]=value
end

function list.pushback(list,value)
   list.last=list.last+1
   list[ list.last ]=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 last<list.first then error("list is empty!")
   end
   local value =list[last]
   list[last]=nil
   list.last=last-1
   return value
end

lp=list.new()
list.pushfront(lp,1)
list.pushfront(lp,2)
list.pushback(lp,-1)
list.pushback(lp,-2)
x=list.popfront(lp)
print(x)
x=list.popback(lp)
print(x)
x=list.popfront(lp)
print(x)
x=list.popback(lp)
print(x)
x=list.popback(lp)
print(x)
--输出结果
-- 2
-- -2
-- 1
-- -1
-- lua:... list is empty!

4、集合和包

在lua中用table实现集合是非常简单的,见如下代码:

复制代码 代码如下:

    reserved = { ["while"] = true, ["end"] = true, ["function"] = true, }
    if not reserved["while"] then
        --do something
    end

在lua中我们可以将包(bag)看成multiset,与普通集合不同的是该容器中允许key相同的元素在容器中多次出现。下面的代码通过为table中的元素添加计数器的方式来模拟实现该数据结构,如:

复制代码 代码如下:

function insert(bag,element)
    bag[element]=(bag[element] or 0)+1
end

function remove(bag,element)
   local count=bag[element]
   if count >0 then bag[element]=count-1
   else bag[element]=nil
   end
end

5、stringbuild

如果在lua中将一系列字符串连接成大字符串的话,有下面的方法:

低效率:

复制代码 代码如下:

local buff=""
for line in io.lines() do
   buff=buff..line.."\n"
end

高效率:

复制代码 代码如下:

local t={}

for line in io.lines() do
   if(line==nil) then break end
   t[#t+1]=line
end

local s=table.concat(t,"\n")  --将table t 中的字符串连接起来