《JavaScript数据结构算法》读书笔记
2018-08-17 16:44:42 31 举报AI智能生成
笔记：《JavaScript数据结构&算法》
作者其他创作
大纲/内容
数组
删除数组元素: splice 、 pop 或 shift
特点：数据元素的插入&删除会改变其他元素位置
栈
后进先出（LIFO）原则的有序集合
队列
队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）
优先队列
循环队列——击鼓传花
JavaScript 任务队列
MacroTask
setTimeout, setInterval, setImmediate, I/O, UI rendering
MicroTask
process.nextTick, Promise, MutationObserver
链表
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个
元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成
元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成
特点：添加或者移除元素时，不需要移动其他元素；链表需要使用指针，访问链表元素需要从表头开始迭代列表
现实例子：康加舞队、寻宝游戏
双向链表
循环链表
集合
集合是由一组无序且唯一（即不能重复）的项组成的
集合操作
并集
交集
子集
差集
字典和散列表
字典
字典则是以[键，值]的形式来存储元素。也称作映射
散列表
散列算法
散列集合
处理散列表冲突
创建更好的散列表
Map
弱化版本WeatMap
Set
弱化版本WeatSet
WeakSet 或 WeakMap 类没有 entries 、 keys 和 values 等方法，为了提高性能
树
术语：根节点、子节点、叶节点；深度
二叉树
两个子节点：一个是左侧子节点，另一个是右侧子节点
二叉搜索树（BST）
左侧节点存储（比父节点）小的值，
在右侧节点存储（比父节点）大（或者等于）的值
在右侧节点存储（比父节点）大（或者等于）的值
树的遍历
中序遍历
也就是以从最小到最大的顺序访问所有节点
对树进行排序操作
先序遍历
优先于后代节点顺序访问每个节点
一种应用是打印一个结构化的文档
后序遍历
先访问节点的后代节点，再访问节点本身
一种应用是计算一个目录和它的子目录中所有文件所占空间的大小
搜索树种的值
搜索最大值和最小值
搜索一个指定值
移除一个节点
自平衡树
Adelson-Velskii-Landi 树（AVL 树）
图
术语：一个图G = (V, E)
V：一组顶点
E：一组边，连接V中的顶点
相邻顶点
路径
环、无环的、连通的
有向图和无向图
强连通的
加权的、未加权的
图的表示
邻接矩阵
邻接表
关联矩阵
图的遍历
广度优先搜索
深度优先搜索
最短路径算法
Dijkstra 算法
Floyd-Warshall 算法
最小生成树MST
Prim 算法
Kruskal 算法
排序和搜索算法
排序算法
冒泡排序
选择排序
插入排序
归并排序
快排序
堆排序
技术排序、桶排序、基数排序
搜索算法
顺序搜索
二分搜索
算法模式
递归
JavaScript 调用栈大小的限制
斐波那契数列
动态规划
最少硬币找零问题
分数背包问题
最长公共子序列
矩阵链相乘
贪心算法
最少硬币找零问题
分数背包问题
函数式编程
算法复杂度O
收藏
0 条评论
下一页
