javascript基础|前端必看js数据结构与算法(队列,链表,集合,字典,树,图,堆) 算法|链表|数据结构

队列队列简介

一个先进先出的数据结构
js中没有队列,但是可以用Array实现对队列的所有功能

javascript基础|前端必看js数据结构与算法(队列,链表,集合,字典,树,图,堆)

文章图片

使用数组模拟先进先出的场景

const queue = [] // 进队列 queue.push(1) queue.push(2)// 出队列 const itme1 = queue.shift() const itme2 = queue.shift()

什么时候用

食堂排队打饭
所有先进先出的场景
js 异步中的任务队列
一个leetcode题第933题

链表链表是什么

多个元素组成的列表
匀速存储不连续, 用next指针连在一起

文章图片

数组 vs 链表

数组:增删非收尾元素是往往需要移动元素
链表:增删非收尾元素,不需要移动元素,只需要更改next指针即可

js中的链表

js没有链表的数据结构
可以用Object模拟链表

const a = { val: 'a' } const b = { val: 'b' } const c = { val: 'c' } const d = { val: 'd' } a.next = b b.next = c c.next = d// 遍历 let point = a while (point) {console.log(point.val) point = point.next }// 插入 (c-d)中插入dconst e = { val:'e'} c.next = e e.next = d// 删除 (删除e) c.next = d

leetcode练习:第83题-删除链表重复元素

var deleteDuplicates = function(head) {// 定义链表的一个头部的指针 let p = head while(p && p.next) {if(p.val === p.next.val) {// 删除链表的一项 p.next = p.next.next }else {// 不相同的时候再移动指针 p = p.next } } return head };

前端原型链的链表 JavaScript 一文搞定理解原型与原型链
手写一个instanceof

function myInstanceof (A, B) {// 遍历链表 let p =A while (p) {p = p.__proto__ // B的 prototype 属性是否出现在A实例对象的原型链上 if (p === B.prototype) {return true }} return false } function Foo () { } var f = new Foo() console.log(myInstanceof(f, Foo)); // true console.log(myInstanceof(f, Object)); // true

集合集合简介

一种无序且唯一的数据结构
ES6中有集合, 名为Set
集合常用操作: 去重,判断某元素是否在集合中,求交集

// 去重 const arr = [1,1,2,3,4,3] const arr2 = [...new Set(arr)]// 判断元素是否在集合中 let set = new Set(arr)// add 方法 set.add(1) set.add('text') set.add({ a:1,b:2})// has方法 const has =set.has(3)// delete方法 set.delete(1)// 获取size 方法 console.log(set.size) // 求交集 const set2 = new Set([2,3]) const set3 new Set([...set]).filter(item => set2.has(item))// 求差集 const set2 = new Set([2,3]) const set4 = new Set([...set]).filter(item => !set2.has(item))// 数组转为set set2 = new Set([1,2,3])// 迭代方法 fot ..of for (let item of set) console.log(item) for (let item of set.keys())) console.log(item) for (let item of set.values()) console.log(item) for (let item of set.entrise()) console.log(item)

补充说明迭代
内置迭代器:
可迭代的对象，都内置以下3种迭代器
entries(): 返回一个迭代器，值为键值对
values(): 返回一个迭代器, 值为集合的值
keys(): 返回一个迭代器，值为集合中的所有键

let userList = [ 'ghostwu', '悟空', '八戒' ]; for ( let name of userList.entries() ) {console.log( name ); }let set = new Set( [ 10, 20, 30 ] ); for ( let num of set.entries() ){console.log( num ); }let map = new Map( [ [ 'name', 'ghostwu' ], [ 'age', 22 ] ] ); for ( let detail of map.entries() ){console.log( detail ); }

【javascript基础|前端必看js数据结构与算法(队列,链表,集合,字典,树,图,堆)】

文章图片

字典字典简介

与集合相似, 字典也是一种存储为一值的数据结构, 但他是以键值对的形式存储
ES6中有字典–>Map(映射)
常见操作增(set) 删(delete) 改(set) 查(get)

const m = new Map()//增 m.set('a','aaa')// 删 m.delete('a') m.clear()// 改 m.set('a','aaaaa')// 查 m.get('a')

使用Map取两个数组的交集

var intersection = function(nums1, nums2) {// new Set(nums1) 去重 return[...new Set(nums1)].filter(item => nums2.includes(item)) };

树树简介

一种分层数据的抽象模型
前端工作中常见的树包括:DOM树,级联选择,树形控件…
js中没有树,但是可以用Array 和Object构建树
树的常用操作: 深度/广度优先遍历 , 先中后序遍历

树的深度/广度优先遍历

深度优先遍历：尽可能深的搜索树的分支:递归
1. 访问根节点
2. 对根节点的children挨个进行深度优先遍历
  
  文章图片

const tree = {val: 'a', children: [ {val: 'b', children: [ {val: 'd', children: [] }, {val: 'e', children: [] } ] }, {val: 'c', children: [ {val: 'f', children: [] }, {val: 'g', children: [] } ] } ] } const dfs =(root) => {console.log(root.val) root.children.forEach(dfs) }dfs(tree)

打印结果

文章图片

广度优先遍历:先访问离根节点最近的节点
1. 新建一个队列, 把根节点入队
2. 把对头出队并访问
3. 把对头的children挨个入队
4. 重复第二,第三,直到队列为空

文章图片

const bfc = (root) => {const q = [root] while (q.length > 0) {const n = q.shift() console.log(n.val) n.children.forEach(child => {q.push(child) }) } }

打印结果:

文章图片

二叉树的先中后序遍历二叉树是什么?

文章图片

树中每个节点最多只能有两个子节点
在js中通常用Object来模拟二叉树

const binaryTree = {val: 1, left: {val:2, left: null, right: null }, right: {val:3, left: null, right: null } }

先序遍历算法

访问根节点
对根节点的左子树进行先序遍历
对根节点的右子树进行先序遍历

遍历顺序如图

文章图片

定义一棵树

const binaryTree = { val: 1, left: {val: 2, left: {val: 4, left: null, right: null, }, right: {val: 5, left: {val: 7, left: null, right: null, }, right: null, }, }, right: {val: 3, left: null, right: {val: 6, left: null, right: null, }, }, };

递归版:

const preorder = root => {if (!root) return; console.log(root.val); preorder(root.left); preorder(root.right); }; preorder(binaryTree);

非递归(栈特性):

const preorder = root => {if (!root) return; const stack = [root]; while (stack.length) {const n = stack.pop(); console.log(n.val); n.right && stack.push(n.right); n.left && stack.push(n.left); } }; preorder(binaryTree);

打印结果:

文章图片

中序遍历算法

对根节点的左子树进行中序遍历
访问根接节点
对根节点的右子树进行中序遍历

遍历顺序如图

文章图片

还是使用binaryTree这个树
递归版实现:

const inorder = root => {if(!root) return inorder(root.left) console.log(root.val) inorder(root.right) } inorder(binaryTree)

非递归版实现:

const inorder = root => {if (!root) return; const stack = []; let p = root; while (stack.length || p) {while (p) {stack.push(p); p = p.left; } const n = stack.pop(); console.log(n.val); p = n.right; } } inorder(binaryTree)

打印结果:

文章图片

后序遍历算法

对根节点的左子树进行中序遍历
对根节点的右子树进行中序遍历
访问根接节点

文章图片

还是使用binaryTree这个树
递归版实现:

const postorder = (root) => {if (!root) return; postorder(root.left); postorder(root.right); console.log(root.val); }; postorder(binaryTree);

非递归版实现:

const inorder = root => {if (!root) return; const outputStack = []; const stack = [root]; while (stack.length) {const n = stack.pop(); outputStack.push(n); if (n.left) stack.push(n.left); if (n.right) stack.push(n.right); } while (outputStack.length) {const n = outputStack.pop(); console.log(n.val); } } inorder(binaryTree)

打印结果:

文章图片

前端与树遍历JSON的所有节点值
使用深度优先遍历

const json = {a: { b: { c: 1 } }, d: [1, 2], }; // 深度优先遍历 const dfs = (n, path) => {console.log(n, path); Object.keys(n).forEach((k) => {dfs(n[k], path.concat(k)); }); }; dfs(json, []);

打印结果

文章图片

图图是什么

图是网络结构的抽象模型, 是一组由边连接的节点
图可以表示任何二元关系, 比如路,航班
js没有图, 可以用Array Object模拟

文章图片

图的表示法邻接矩阵

文章图片

文章图片

邻接表

文章图片

文章图片

图的遍历

深度优先遍历: 尽可能深的搜索图的分支

访问根节点
对根节点的没访问过得相邻节点挨个进行深度优先遍历

文章图片

定义一个图

const graph = {0:[1,2], 1:[2], 2:[0,3], 3:[3] }

使用深度优先遍历

const visited = new Set() const dfs = n => {console.log(n) visited.add(n) graph[n].forEach(c => {if(!visited.has(c)) {dfs(c) } }) } dfs(2)

打印结果

文章图片

广度优先遍历: 先访问离根节点最近的节点

新建一个队列, 把根节点入队
把队头出队并访问
把队头的没访问过得相邻节点入队
重复第二三步, 直到队列为空

文章图片

const bfs = node => {const visited = new Set() visited.add(node) const q = [node] while (q.length) {const n = q.shift() console.log(n) graph[n].forEach(c => {if(!visited.has(c)) {q.push(c) visited.add(c) } }) } } bfs(2)

打印结果: