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

栏目: C · 发布时间: 5年前

内容简介:最近的工作涉及了大量 JSON 操作,用到了一些之前做过的算法题中的知识,深刻感觉到,传统数据结构与算法在前端开发中的应用也挺多的。所以,想借此文记录总结一番。深度优先搜索(Depth-First-Search,DFS)是一种用于遍历或搜索树或者图的算法。顾名思义,它的搜索的规则是深度优先:先访问根结点,如果有孩子节点(或者邻居节点)就优先访问孩子节点,并对孩子节点也进行上述递归访问。

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

深度优先搜索简介

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

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

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

使用深度优先搜索打印 JSON

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

示例代码:

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 树中的任意一项了,也可以渲染表单项来编辑它们。比如之前做的递归表单组件:

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

链表指针简介

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

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

let p = linkedList;
// 某个循环中
p = p.next;

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

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

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 ,它经常用到这样的结构来“不可变”地改变数据:

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

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Algorithms in Java, Part 5

Algorithms in Java, Part 5

Robert Sedgewick / Addison-Wesley Professional / 2003-7-25 / USD 54.99

Algorithms in Java, Third Edition, Part 5: Graph Algorithms is the second book in Sedgewick's thoroughly revised and rewritten series. The first book, Parts 1-4, addresses fundamental algorithms, data......一起来看看 《Algorithms in Java, Part 5》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

随机密码生成器
随机密码生成器

多种字符组合密码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具