数组

LUA中数组的实现

Lua中使用整数作为table的索引即可实现数组

Lua中数组的索引由1开始

local t = {}
for i = 1, 1000 do    --完整数组的初始化
t[i] = 0
end
print(#t)                        --使用#table获得数组的长度

Lua中矩阵和多维数组的实现

方法一：不规则数组

即数组的数组，table中的元素是别的table

local t = {}
local M, N = 5, 5        --创建M×N的矩阵
for i = 1, M do
  local row = {}    --创建临时table用于储存行
  t[i] = row            --将储存行的table的地址赋值给列
  for j = 1, N do
      row[j] = 0
  end
end

方法二：合并索引

该方法与哈希表类似，使用一个公式将两个索引合并成一个，这样储存的时候就可以使用一维数组储存多维数组
- 如：5×6的数组，在table的1~6储存第一行，7~12储存第二含行。。。（总行-1）×总列+当前列
```
local t = {}
local M, N = 5, 5
for i = 1, M do
local locate = (i - 1) * M        --使用公式，让多维数组能够储存在一维数组中
for j = 1, N do
   t[locate + j] = 0
end
end
```
  处理稀疏矩阵
稀疏矩阵：矩阵中大多是0或nil。
- 在使用邻接矩阵来表示图时，(m,n)处元素的值为x代表：图中的m和n节点相连，权重为x。如果不使用稀疏矩阵，则会照成大量空间的浪费
Lua中的table本质上就是稀疏矩阵，只有非nil元素才占用空间，因此很少用到稀疏矩阵的技巧

处理原理
- 计算矩阵的常见算法（a[M,K]*b[K,N]=c[M,N]） ```lua local M, N, K local a, b, c = {}, {}, {}

for i = 1, M do for j = 1, N do c[i][j] = 0 for k = 1, K do c[i][j] = c[i][j] + a[i][k] * b[k][j] end end end


   - 由于每轮遍历存在遍历列，因此不适合使用pairs进行遍历，因此进行修改
```lua
for i = 1, M do
    for k = 1, K do
        for j = 1, N do
            a[i][j] = (a[i][j] or 0) + a[i][k] * b[k][j]
        end
    end
end

--[[
修改算法之后，    替换了最内层循环和中层循环的位置，
原本的算法中：    每次最内层循环都将a[i][j]的结果算出，也就是每次完成一个位置的矩阵运算，
修改后的算法：    最内层循环中的每次运算，只进行了该位置会进行的1次运算，
                            然后与下一轮的最中层循环进行叠加，完成一轮中层循环，
                            才代表结果矩阵的一行全部完成计算
--]]

最终的处理稀疏矩阵算法

function mult(a, b)
local c = {}
for i = 1, #a do
   local resultLine = {}
   for k, va in pairs(a[i]) do
       for j, vb in pairs(b[k]) do
           local result = (resultLine[j] or 0) + va * vb
           resultLine[j] = (result ~= 0) and result or nil
                   --如果计算结果为0则填充nil，不为0则田填充result
       end
   end
   c[i] = resultLine
end
return c
end

链表

由于table是动态对象，因此将每个节点使用table来表示，链接则table内含指向其他table的引用的简单字段
- 双向表、环形表也是用该方式实现，但由于可以用更简单的方式实现，所以Lua中很少使用 ```lua list=nil —初始化表为nil list={next=list,value=”1”} —插入一个节点，由于=是左结合的，所以会想进行table构造器的运算 list={next=list,value=”2”}

local l=list while l do print(l.value) l=l.next end

<a name="GfnzA"></a>
# 队列及双端队列
<a name="QXeCo"></a>
### 队列模型

- 只允许在**一端插入（対尾）**数据操作，**在另一端进行删除（对头）**数据操作的特殊线性表。
   - **初始化**：最初时，队头指针与队尾指针指向同一位置
   - **入队**：队尾加入元素，队尾指针+1
   - **出队**：取出元素，队头指针+1
   - **队空**：队头等于队尾

![未命名文件.png](https://cdn.nlark.com/yuque/0/2021/png/422971/1638965524255-7f4c0190-6de0-49ac-b7bd-7061c84d9cfe.png#clientId=uab297ab3-68d1-4&crop=0&crop=0&crop=1&crop=1&from=drop&height=387&id=uff8104d1&margin=%5Bobject%20Object%5D&name=%E6%9C%AA%E5%91%BD%E5%90%8D%E6%96%87%E4%BB%B6.png&originHeight=539&originWidth=771&originalType=binary&ratio=1&rotation=0&showTitle=true&size=19600&status=done&style=stroke&taskId=u7ad3d154-f560-41fc-855a-8debeff52fd&title=%E5%87%BA%E5%85%A5%E9%98%9F%E6%B5%81%E7%A8%8B%E5%9B%BE&width=554 "出入队流程图")
<a name="DBERk"></a>
# 双端队列

- 在队列**两头**都可进行**加入**和**删除**操作
   - **初始化**：队头为0，队尾为-1
   - **队头**：
      - 入队：队头指针-1，储存元素
      - 出队：取出元素，队头指针+1
   - **队尾**：
      - 入队：队尾指针+1，储存元素
      - 出队：取出元素，队尾指针-1
   - **队空**：队头 > 队尾
```lua
function listNew()
    return {first = 0, last = -1}
end

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

function pushLast(list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
end

function popFirst(list)
    local first = list.first
    if first > list.last then
        error("list is empty")
    end
    local value = list[first]
    list[first] = nil --让垃圾回收器来释放空间
    list.first = list.first + 1
    return value
end

function popLast(list)
    local last = list.last
    if list.first > last then
        error("list is empty")
    end
    local value = list[last]
    list[last] = nil --让垃圾回收器来释放空间
    list.last = last - 1
    return value
end

反向表

将table中的键值对进行位置的互换 ```lua local days = {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”,
```
                    "Friday", "Satuarday"}
```

local revDays = {} for k, v in pairs(days) do revDays[v] = k end


<a name="pZGrf"></a>
# 集合与包
<a name="ECgJF"></a>
### 集合

- 如一个**字符串** 或 **整数**组成**的集合**
- Lua中将**集合元素作为索引储存**在**table**中
   - 将**table对应索引赋true**值，这样如果**查询table[元素]**的**结果不为true**，则**不在集合**中
```lua
function Set(list)      --将list转换为集合储存
    local set = {}
    for k, v in pairs(list) do
        set[v] = true   --将集合中的元素，赋true值，用于之后辨别是否在集合中
    end
    return set
end

local id = {}
local str = "this is a function string end"
local reserved = Set({"while", "end", "function", "local"}) --储存集合

for i in string.gmatch(str, "[%a_][%w_]*") do
    if not reserved[i] then --不在集合中，则储存到标识符集合id中
        id[i] = true
    end
end

包

也称为多重集合，不同在于元素可以出现多次
- 每一个键都对应一个计数器，
  - 插入元素：递增其计数器
  - 删除元素：递减其计数器，计数器大于0则保留 ```lua function insert(bag, element) —插入元素
    bag[element] = (bag[element] or 0) + 1 end

function remove(bag, element) —删除元素 local count = bag[element] bag[element] = (count and count > 1) and count - 1 or nil —如果计数器存在且为不0，则-1,；不存在或为0则删除 end ```

Lua实现数据结构

数组

LUA中数组的实现

Lua中矩阵和多维数组的实现

方法一：不规则数组

方法二：合并索引

处理稀疏矩阵

处理原理

链表

反向表

包