数据结构

其他编程语言中的几乎所有数据结构都可以用table来实现,,而且table的功能更加强大。

一、字典

tmap ={} ;

tmap["键"] = 1 ;

tmap ={键a=1,键b=2;键c=3} ;

win.consoleOpen();--打开控制台窗口,用来支持print函数
tab = {a="字符串", b= 123,c="字符串2",d=23,e=56,78,99,123,0}

for k,v in pairs(tab) do
--k为键,v是匹配的值,在这里键值对无序的随机出现。
print(k,v); -->显示: 键,值
end;

二、动态数组

通过数字索引(整数下标)即可在table中创建数组
数组大小可以动态改变,数组元素可以是任意的数据类型.
数组元素的类型与大小都可以自由的改变.

注意在LAScript中约定数组下标从1开始(c++是从0开始),
从1开始更容易理解.标准库所有函数遵循这个约定.

1、通过索字索引(即整数下标)创建数组

tab = {};--创建一个空的table

tab[1] = "字符串" --元素是一人字符串
tab[2] = 123; --元素是一个数字
tab[3] = {}; --元素是一个table
tab[4] = function() win.messageBox("hello") end;
--元素是一个匿名函数

--我们也可以用一个循环来创建数组
for i=1,10,1 do--for循环计数器从1递增到10
tab[i] = 0;
end;

tab = {"字符串", 123,"字符串2",23,56,78,99,123,0}

tab = {"字符串", 123,"字符串2",23,56,78,99,123,0}
local n = table.maxn(tab);--获取数组大小

win.messageBox("数组大小: "..n);

win.consoleOpen(); --打开控制台窗口,用来支持print函数
tab = {"字符串", 123,"字符串2",23,56,78,99,123,0}

local n = table.maxn(tab);--获取数组大小
for i=1,n,1 do --按数字索引循环读取数组元素
print(i,tab[i]); -->显示: 数字索引,数组元素的值
end;

win.consoleOpen();--打开控制台窗口,用来支持print函数
tab = {"字符串", 123,"字符串2",23,56,78,99,123,0,

test=123};--

tab.test不是数组元素

for i,v in ipairs(tab) do
--i为键,v是匹配的值,在这里键值对有序的出现。
print(i,v); -->显示: 数字索引,数组元素的值
end;

三、多维数组、矩阵

什么是矩阵?

local tab = {} --创建一个新的短阵
local m,n = 10,20;

for i=1,m do
    tab[i] = {}   --行
    for j=1,n do
        tab[i][j] = 0 --列
    end
end

--用同样的方法建立三角矩阵(节省一半的内存空间)

local tab = {} --创建一个新的短阵
local m,n = 10,20;

for i=1,m do
    tab[i] = {}   --行
    for j=1,i do
        tab[i][j] = 0 --列
    end
end

local tab = {} --创建一个新的短阵
local m,n = 10,20;

for i=1,m do
    for j=1,n do
        tab[i*m + j] = 0
    end
end

local tab = {} --创建一个新的短阵
local m,n = 10,20;

for i=1,m do
    for j=1,n do
        tab[i..'\0'..j] = 0
    end
end

这在其他编程语言中是一个难题,但是table先天就是具有稀疏的特性:

local tab = {}
tab[1000]=110; --仅分配一个元素的内存,而不是1000个元素的内存

了解这个特性就可以用前面介绍的几种方法建立稀疏矩阵了,这不需要任何复杂的技术.

--[[初始化二维表]]
function table.mk2(m,n)
   tab={};
   for i=1,m,1 do
      tab[i]={};
      for j=1,n,1 do
         tab[i][j]=j;
      end;
   end;

   return tab;
end;

--[[在控制台显示二维表]]
function table.dir2(tab)
    for i,tab2 in ipairs(tab) do --遍历数组tab
        print(unpack(tab2)); --展开tab2，作为print的多个参数显示一行多列
    end;
end;

tab=table.mk2(3,4); --制作一张3行4列的表格
--table.save(tab,"c:\\xx.xml") --用xml文件保存制作的表格数据

win.consoleOpen();
table.dir2(tab); --在控制台显示二维表

四、链表

五、双端队列

队列作为特定的数据结构，最先进入的元素最先释放(先进先出)

首先,我们定义队列结构.

namespace("queue")--创建新的名字空间queue

new = function()
    local q = {first = 0, last = -1};--创建一个新的队列
    _G.setmetatable(q,{__index = _M});--让q继承queue名字空间的所有成员
    return q;--返回新的队列
end

function pushleft (qe, value) --左端添加一个元素
    local first = qe.first - 1; --开始索引减1;
    qe.first = first --修改开始索引
    qe[first] = value; --插入新的成员在开始
end

function pushright (qe, value) --右端添加一个元素
    local last = qe.last + 1 --结束索引加1;
    qe.last = last --修改结束索引
    qe[last] = value --插入新的成员在结束
end

function popleft (qe) --左端弹出一个元素
    _G.assert(qe.first <= qe.last,("queue is empty"));

    local first = qe.first
    local value = qe[first]
    qe[first] = nil      -- 清除开始位置元素，允许垃圾回收
    qe.first = first + 1 --开始索引加1
    return value
end

function popright (qe) --右端弹出一个元素
    _G.assert(qe.first <= qe.last,("queue is empty"));

    local value = qe[qe.last]
    qe[qe.last] = nil       -- 清除结束位置元素，允许垃圾回收 qe.last = qe.last - 1 --结束索引减1
    return value
end

namespace("_G");--回到默认的全局名字空间

q = queue.new();
q:pushleft("字符串1");
q:pushleft("字符串2");

str = q:popright();
win.messageBox(str);-->显示"字符串1",先进先出

str = q:popright();
win.messageBox(str);-->显示"字符串2",先进先出

--已经没有元素了,弹出错误
str = q:popright();

六、字符串缓冲、高效的字符串连接

LAScript采用垃圾收集算法的并且字符串不可变的语言,与其他类似的语言一样在连接字符串时会比较占用资源.
因为每次连接都要创建新的字符串,

如果在一个循环中进行大量的连接操作,效率是很低下的.
因为随了不断的连接字符串变的越来越大,每次连接都要重新拷贝新的副本创建新的字符串。
Java、C#等提供StringBuffer来改善这种情况。

在LAScript中如果需要大量的连接,可以简单的把字符串按顺序添加到一个table数组中。
然后

使用table.concat(tab,"分隔符")来合并字符串. 使用这种方法连接字符串速度非常快。

table.concat(tab,sep,i,j);有四个参数,分别为table数组,分隔符,起始索引,结束索引。
后面的三个参数都可以省略。

我们还可以进一步的优化这种方法。将字符串添加到table数组中以后,检查较小的字符串进行合并.
遇到较大的字符串以后停止合并,这样可以避免生成太大的table数组。
这与经典的汉诺塔问题类似：位于栈下面的串肯定比上面的长，
只要一个较长的串入栈后比它下面的串长，就将两个串合并成一个新的更大的串
，新生成的串继续与相邻的串比较如果长于底部的将继续进行合并，循环进行到没有串可以合并或者到达栈底。

下面我们看示例代码:

--建立一个新的字符串缓冲区,chr为合并字符串时的分隔符(可省略);
string.buffer = function(chr)
    local buf = {"",chr=chr}; --创建一个新的缓冲区

    --转换为字符串,table.concat合并字符串速度很快
    function buf:tostring()
        return table.concat(self,self.chr,1,2)
    end;

    --这个函数添加一个字符串到缓冲区
    function buf:add(str)
        table.insert(self, str)    -- 添加新的字符串到缓冲区中

        for i=table.getn(self)-1, 1, -1 do --从顶端开始向下检查缓冲区
            if string.len(self[i]) > string.len(self[i+1]) then
                break;--直到遇到一个较小的字符串中断循环
            end

            --如果前面是一个较小的元素,将这个字符串与顶端的字符串连接,并移除顶端的字符串
            if(chr)then
                self[i] = self[i] ..chr..table.remove(self);
            else
                self[i] = self[i] .. table.remove(self);--table.remove弹出一个元素并返回其值
            end;
        end
    end

    --重载tostring操作符;
    buf.__tostring = buf.tostring;
    --重载字符串连接操作符
    buf.__concat = function(s,s2)
        if(type(s)=="table")then --操作数是不是字符串缓冲?
            s = s:tostring()
        end;
        if(type(s2)=="table")then --操作数是不是字符串缓冲?
            s2 = s2:tostring()
        end;
        return s..s2;
    end;

    --添加一个元表(自已作为自已的元表),重载tostring操作符
    setmetatable(buf,buf);

    return buf;
end

--下面是使用方法的示例
bf = string.buffer();

bf:add("字符串1");--压入缓冲，准备连接
bf:add("字符串2");--压入缓冲，准备连接
bf:add("字符串3");--压入缓冲，准备连接
bf:add("字符串4");--压入缓冲，准备连接
bf:add("字符串5");--压入缓冲，准备连接
bf:add("字符串6");--压入缓冲，准备连接

win.messageBox( tostring(bf) );--强制转换为字符串

数据结构

一、字典

二、动态数组

三、多维数组、矩阵 什么是矩阵?

四、链表

五、双端队列

六、字符串缓冲、高效的字符串连接

三、多维数组、矩阵

什么是矩阵?