# 第四章 VimL 数据结构进阶

## 4.3 嵌套组合与扩展

VimL 虽然只提供了列表与字典两种数据结构，但通过列表与字典的合理组合，几乎能表
达任意复杂的数据结构。这与许多其他流行的脚本语言（如 python）的思想如出一辙。
本节就讨论在 VimL 中如何用列表与字典表示常用数据结构。

### 栈与队列

栈是所谓后进先出的结构，队列是先进先出的结构。这可以直接用一个 `list` 表示，
因为 `list` 相当于个动态数组，支持随意在两端增删元素。

如果只在列表尾部增删元素，那就实现了栈行为。如果尾部增加而在头部删除，就实现
了队列行为，如：
```vim
: function Push(stack, item)
:     call add(stack, item)
: endfunction

: function Pop(stack)
:     call remove(stack, -1)
: endfunction

: function Shift(queue)
:     call remove(stack, 0)
: endfunction
```
在这个示例中，用 `Push/Pop` 表示栈操作，用 `Push/Shift` 表示队列操作。这只为
简明地说明算法意图，实际应用中最好先检查 `stack/queue` 是否为 `list` 类型，以
及检查列表是否为空。

### 链表

在脚本语言中，其实根本不用实现链表，因为动态数组本身就可用于需要链表的场合。在
VimL 中，就直接用 `list` 表示线性链就够了。除非你真的需要很频繁地在一个很长的
`list` 中部增删元素，那么或可用字典来模拟链表的实现。

例如，以下代码构建了一个有 10 个结点的链表，每个结点是个字典，`value` 键表示存储
内容，`next` 表示指向下一个结点：
```vim
: let head = {}
: for value in range(10)
:   let node = {'value': value, 'next': head}
:   let head = node
: endfor
```
其实在上面的循环中，临时变量 `node` 可以省略。`head` 始终指向链表的起始结点，
可通过 `next` 键依次访问剩余结点，末尾结点的 `next` 键值是空字典。

这里的关键是，字典的值，或列表元素的值，不仅可以存储像数字与字串符的简单标量，
还可以存储另一个列表或字典（的引用）。基于这样的嵌套与组合，就可以表达更复杂的
数据结构了。

### 二维数组（矩阵）

如果列表的每个元素都是另一个列表，那就构成了一个二维数组。例如：
```vim
: let matrix = []
: for _ in range(10)
:   let row = range(10)
:   call add(matrix, row)
: endfor
```
构建了一个 `10x10` 大小的矩阵，其中每个行向量由 `range(10)` 生成。这样快速生成
的矩阵每一行都相同，或许不是很有趣，但是可以用以下两层循环重新赋值：

```vim
: for i in range(10)
:   for j in range(10)
:     let matrix[i][j] = i * j
:   endfor
: endfor
```

从数学意义上的矩阵讲，它应是规整的矩形，即每行的长度是一样的。但当在 VimL 中用
列表的列表表示时，其实并不能保证每一行都等长。例如：
```vim
: let text = getline(1, '$')
: for i in range(len(text))
:   let line = text[i]
:   let text[i] = split(line, '\s\+')
: endfor
```
在这里，首先用 `getline()` 获取当前 buffer 的所有行，保存在 `text` 这个列表变
量中，其中每个元素表示一行文本字符串。在随后的循环中，又将每行文本分隔成一个个
单词（空格分隔的字符串），将标量字符串元素转化为了另一个列表。因此，`text` 最
终结果就是列表的列表，即二维数组。而一般情况下，每行的单词数量是不等，所以这个
二维数组不是规整的矩阵。

事实上，这个示例的循环可以直接用 `map()` 函数代替：
```vim
: let text = getline(1, '$')
: call map(text, "split(v:val, '\\s\\+')")
```

### 树

以二叉树为例，也可用一个字典来表示树中某结点，除了需要一个键（如 `value`）来保
存业务数据，还用一个 `left` 键表示左孩子结点，`right` 表示右孩子结点，这两个应
该都是另一个具有相同结构的字典引用，如果缺失某个孩子，则可用空字典表示。

```vim
: let node = {}
: let node.value = 0
: let node.left = {}
: let node.right = {}
```

这样，只要有一个字典变量引用了这样的一个结点（不妨称之为根结点），就相当于引用
这一棵树，沿着结点的 `left` 与 `right` 键就能访问整棵树的所有结点。两个子结点
都是空字典时，该结点就是所谓的叶结点。

不过，由于每个结点含有两个方向的子结点，要遍历树可不是那么直观。有兴趣的读者请
参考相应的树算法。本节内容旨在说明 VimL 的字典用法，展示其表达能力。而算法其实
是与语言无关的。

在上述的树结点字典结构中，只能从一个结点访问其子结点，而无法从子结点访问父结点
。如果有这个需求，只要在每个结点字典中再加一个键引用父结点即可，如：
```vim
: let node.parent = {}
```
每个子结点都有父结点，即 `parent` 键非空。根结点没有父结点，那 `parent` 键应该
存个什么值呢？可以就用空字典表示，也可以引用它自身，这都可以将根结点与其他非根
结点区分开来。

我们知道，字典或列表变量都只是某个实体的引用。VimL 的自动垃圾回收机制主要是基
于计数引用的。如果某个字典或列表实体没有被任何变量引用了，即引用计数为 0 时，
（在变量离开作用域或显式 `:unlet` 时会减少引用计数）VimL 就认定该实体无法被访
问了，就会当作垃圾回收其所占用的内存。在大部分简单场合中，这套机制很好用。不过
考虑这里讨论的包含 `parent` 与 `left` `right` 键的树结点，在父、子结点之间形成
了环引用，它们的引用计数始终不会降到 0 。然而 VimL 另外也有一个算法检测环引用
，所以也尽可放心使用这个树结构，不必担心内存泄漏。只不过存在环引用时，垃圾回收
的时机可能相对滞后而已。

现在，让我们再考虑一种有任意多个孩子的树（任意叉树）。这种结构在实际应用中是存
在的，比如目录树，每个目录（结点）可以有很多个不确实数量的子目录或文件（叶结点
）。为表示这种结构，我们可以将所有子结点放在一个列表中，然后用一个键引用这个列
表，如下定义每个结点的字典结构：
```vim
: let node = {}
: let node.value = 0
: let node.parent = {}
: let node.child = []
```

与原来的二叉树相比，取消 `left` 与 `right` 键，而以统一的 `child` 键代替。每当
增加一个子结点时，就添加到 `child` 列表中，同时维护该子结点的 `parent` 键。如
果 `child` 键为空列表，就表示该结点为叶结点。

### 图

图是一些顶点与边的集合，常用 `G(V, E)` 表示，其中 `V` 是顶点集合，`E` 是边集合
，每条边连接着 `V` 中两个顶点。一般用 `|V|` 表示顶点的个数，`|E|` 表示边数。

用程序表示图，有两种常用的方式，邻接矩阵与邻接表。这里讨论一下如何用 VimL 的数
据结构表示图。

邻接矩阵很简单，就是一个 `|V| x |V|` 大小的矩阵，假设就用变量名 `graph` 表示这
个矩阵。前面小节已介绍，矩阵在 VimL 中就是列表的列表。如果顶点 `i` 与 `j` 之间
有一条边，就 `:let graph[i][j] = 1`，否则就用一个特殊值来表示这两个顶点之间没
有边，比如在很多情况下用 `0` 表示无边是可行的，`:let grapsh[i][j] = 0`。如果是
有权边，则可把边的权重保存在相应的矩阵位置中，如 `:let graph[i][j] = w`。如果
是无向图，则再对称赋值 `:let graph[j][i] = graph[i][j]`。

由于矩阵元素支持随机访问，用邻接矩阵表示图在某些应用中非常高效简便，尤其在边数
非常稠密的情况下（极限情况是每两个顶点之间都有边的完全连通图）。不过在边数很少
的情况下，这将是个稀疏矩阵，在内存空间使用上比较低效。

邻接表，首先它是包含所有顶点的列表；每个顶点是一个字典结构，它至少有个键 `edge`
来保存所有与本顶点相关的边，这应是一个边结构的列表；在边结构字典中则保存着权重
`weight`，以及它所连接的顶点（字典引用）。大致结构如下所示：

```vim
: let graph = [] " a list of vertex
: let vertex = {'edge': [], 'id':0, 'data': {}}
: let edge = {'weight':1, 'target': {}, 'source': {}}
```

如果只要求自上而下访问边结构，那这个字典中可以只保存一个顶点，另一个顶点就是它
被保存的顶点（由它的 `edge` 键访问到这个边）。这可以减少一些存储空间，不过顶点
也只是字典引用，保存双端点也浪费不了太多空间。

在实际的图应用中，肯定还会有具体的业务数据，这些数据一般是保存顶点结构中。比如
可以给每个顶点给个 `id` 编号或名字，如果有大量复杂的数据，可单独保存在另一个字
典引用中。

所以，邻接表虽然复杂，但灵活度高，易扩展业务数据。而邻接矩阵在矩阵元素中只能保
存一个值，扩展有些不方便。除非是业务数据是保存在边结构中，那么在矩阵中可以保存
另一个字典引用，而不是简单的权重数值。

### JSON

如果你了解 JSON，就会发现 VimL 的列表与字典的语法表示，正好也是符合 JSON 标准
的。一个有效的 JSON 字符串也是合适的 VimL 的表达式，可以直接用于 `:let` 命
令的赋值。

当然这有一个小小的限制，JSON 字符串不能有换行，因为 VimL 语言是按行解析的，且
续行符比较特殊（在下一行开头使用反斜杠）。如果是不太复杂的 JSON，在 Vim 编辑中
可以将普通命令 `J` 将多行字符串合并为一行，我不认为你会用其他编辑器写 VimL 脚
本。

此外，有个内置函数 `jsondecode()` 可将一个合法的 JSON 字符串（允许多行）解析为
VimL 值，以及反函数 `jsonencode()` 将一个 VimL 表达式转换为 JSON 字符串。

### 总结

在 VimL 中，用列表与字典的组合，可以表达很复杂很精妙的数据结构，几乎只有想不到
没有做不到。其实这也不必奇怪，因为目前大部分作为高级语言的动态脚本，其思想是相
通的。虽然 VimL 似乎只能用于 Vim，但它与其他流行的外部脚本语言，在某种程序上是
极其相似的。