首页 > 代码库 > Lua数据结构

Lua数据结构

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

 

1、数组

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

--二维数组n=10 m=10arr={}for i=1,n do     arr[i]={}   for j=1,m do      arr[i][j]=i*j   endendfor i=1, n do   for j=1, m do      if(j~=m) then  io.write(arr[i][j].." ")      else print(arr[i][j])      end   endend


2、链表

在lua中,由于table是动态的实体,所以用来表示链表是很方便的,其中每个节点都用table来表示。

list = nilfor i = 1, 10 do    list = { next = list, value =http://www.mamicode.com/ i}endlocal l = listwhile l do    print(l.value)    l = l.nextend

 

3、队列与双端队列

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

List={}function List.new()   return {first=0, last=-1}endfunction List.pushFront(list,value)   list.first=list.first-1   list[ list.first ]=valueendfunction List.pushBack(list,value)   list.last=list.last+1   list[ list.last ]=valueendfunction List.popFront(list)   local first=list.first   if first>list.last then error("List is empty!")   end   local value =http://www.mamicode.com/list[first]   list[first]=nil   list.first=first+1   return valueendfunction List.popBack(list)   local last=list.last   if last<list.first then error("List is empty!")   end   local value =http://www.mamicode.com/list[last]   list[last]=nil   list.last=last-1   return valueendlp=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)+1endfunction remove(Bag,element)   local count=Bag[element]   if count >0 then Bag[element]=count-1   else Bag[element]=nil   endend   

 

 

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]=lineendlocal s=table.concat(t,"\n")  --将table t 中的字符串连接起来

 

Lua数据结构