深度优先搜索和链表指针在 JSON 操作中的应用

最近的工作涉及了大量 JSON 操作，用到了一些之前做过的算法题中的知识，深刻感觉到，传统数据结构与算法在前端开发中的应用也挺多的。所以，想借此文记录总结一番。

深度优先搜索简介

深度优先搜索（Depth-First-Search，DFS）是一种用于遍历或搜索树或者图的算法。顾名思义，它的搜索的规则是深度优先：先访问根结点，如果有孩子节点（或者邻居节点）就优先访问孩子节点，并对孩子节点也进行上述递归访问。

dfs

DFS 可谓是 LeetCode 中考察最多的知识点了，另外由于动态规划算法可以和 DFS 算法相互转换（就像是所有的递归都可以用“栈”来改写一样），所以 DFS 的题目简直不能更多。

使用深度优先搜索打印 JSON

那么 DFS 在 JSON 操作中有什么用处呢？假如你想在网页上渲染一个 JSON，甚至想渲染出一个表单来编辑这个 JSON，那么就要用到 DFS 了。思路也很简单，先访问一个 JSON 的根结点，然后访问它的所有 key（也就是孩子节点），并对 key 也进行上述递归。

示例代码：

1
2
3
4
5
6
7
8
const json = { a: { b: 'hello' }, c: [1, 2] };
const dfs = (n) => {
  console.log(n);
  if(String(n) === '[object Object]' || Array.isArray(n)){
    Object.keys(n).forEach(k => { dfs(n[k]); });
  }
}; 
dfs(json);

结果如下：

打印 JSON

可以发现 JSON 中每个节点都被遍历到了。

DFS 用于构建无限递归表单

只需要更改上述 dfs 函数的参数，就可以渲染 JSON 树中的任意一项了，也可以渲染表单项来编辑它们。比如之前做的递归表单组件：

递归表单

链表指针简介

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。

链表遍历及操作也是 LeetCode 考察非常多的题目。通常我们会定义一个变量作为指针，然后在循环里让它遍历链表的多个 next。比如：

1
2
3
4
let p = linkedList;
// 某个循环中
p = p.next;

使用链表指针获取 JSON 中的叶子节点的值

那么链表指针在 JSON 操作中有什么用呢？我们可以把 JS 中 Object 的 key 当作链表中的 next。那么如果知道一个叶子节点的路径，我们就可以用指针像遍历链表那样遍历到 JSON 的叶子节点处。比如：

1
2
3
4
5
6
const json = { a: { b: 'hello' }, c: [1, 2] };
const path = ['a', 'b'];
let point = json;
path.forEach(key => { point = point[key] });
// point 为 'hello'，即 json.a.b 的值。
console.log(point);

上述代码中，json 是我们要查找的 JSON 对象，path 是叶子节点的路径，point 是指针，通过遍历，point 最后指向了指定的叶子节点的值。

使用链表指针构造 immutibility-helper 所需要的数据结构

另外，由于 React Redux 的风行，不可变数据结构在前端用的非常多，有个不可变数据工具包叫 immutibility-helper ，它经常用到这样的结构来“不可变”地改变数据：

1
update(obj, {a: {b: {c: {$set: 1}}}});

所以，还可以通过指针来将路径与它所需要的结构进行互转。

结语

本文讲述的算法都非常简单，在 LeetCode 上应该属于 Easy 中的 Easy 级别的，但是将算法应用到实际工作中也是一件有趣的事情，故记录下来，作为总结，也抛砖引玉，分享给大家。

本文作者：
发布时间： 2019年1月23日 - 16时01分
版权声明： 本文由 原创，采用 保留署名-非商业性使用-禁止演绎 4.0-国际许可协议
转载请保留以上声明信息！