内容简介:最近的工作涉及了大量 JSON 操作,用到了一些之前做过的算法题中的知识,深刻感觉到,传统数据结构与算法在前端开发中的应用也挺多的。所以,想借此文记录总结一番。深度优先搜索(Depth-First-Search,DFS)是一种用于遍历或搜索树或者图的算法。顾名思义,它的搜索的规则是深度优先:先访问根结点,如果有孩子节点(或者邻居节点)就优先访问孩子节点,并对孩子节点也进行上述递归访问。
最近的工作涉及了大量 JSON 操作,用到了一些之前做过的算法题中的知识,深刻感觉到,传统数据结构与算法在前端开发中的应用也挺多的。所以,想借此文记录总结一番。
深度优先搜索简介
深度优先搜索(Depth-First-Search,DFS)是一种用于遍历或搜索树或者图的算法。顾名思义,它的搜索的规则是深度优先:先访问根结点,如果有孩子节点(或者邻居节点)就优先访问孩子节点,并对孩子节点也进行上述递归访问。
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 中每个节点都被遍历到了。
DFS 用于构建无限递归表单
只需要更改上述 dfs
函数的参数,就可以渲染 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}}}});
所以,还可以通过指针来将路径与它所需要的结构进行互转。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- NULL 指针、零指针、野指针
- 将数组和矩阵传递给函数,作为C中指针的指针和指针
- C语言指针数组和数组指针
- python(函数指针和类函数指针)
- C++ 基类指针和派生类指针之间的转换
- golang的值类型,指针类型和引用类型&值传递&指针传递
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!