使用JavaScript学习数据结构和算法（2） | 小册免费学

系列文章

• 使用JavaScript学习数据结构和算法（1）| 小册免费学
• 使用JavaScript学习数据结构和算法（2）| 小册免费学
• 使用JavaScript学习数据结构和算法（3）| 小册免费学
• 使用JavaScript学习数据结构和算法（4）| 小册免费学

字典

字典和集合很相像，集合是以[值, 值]的形式储存的。字典则是以[键, 值]的形式来储存元素的，字典也称为 “映射”
字典储存的是[键, 值]对，其中键名是用来查询特定元素的。
EACAScript 6 中的 Map 数据结构就是字典的一种实现，它类似对象。

散列表（散列映射 Hash）

• 散列算法：尽可能快得在数据结构中找到一个值。
• 处理散列表中的冲突（冲突原因：同一个位置只能存放一个值）
  • 分离链接：为散列表的每一个位置都创建一个链表并将元素存放在里面。
  • 线性探查：当新元素加入列表时，如果索引为 index 的位置已被占据，则尝试 index+1 的位置，依次类推，已找到空位置未知。
  • 双散列法
• 更好的散列函数 djb2

let djb2HashCode = function(key) {
  let hash = 5371;
  for (let i = 0; i < key.length; i++) {
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
};
复制代码

树

树是一种非顺序数据结构，它对于储存需要快速查找的数据非常有用。
树是一种分层的抽象模型，如：家谱，公司组织架构图等。

每个树都有一个根节点以及多个子节点构成，节点分为内节点和外节点，至少有一个节点的的节点被称为内部节点，没有子元素的节点被称为外部节点。
树的高度，取决于所有节点深度的最大值。

二叉树和二叉树搜索树

• 二叉树：最多只能有两个节点，一个是左侧子节点，一个是右侧子节点。

• 二叉树搜索树：二叉树搜索树是二叉树的一种，但是它只允许你在左侧节点储存（比父节点）小的值，在右侧节点储存（比父节点）大（或者等于）的值。

二叉树遍历

假如在保证“左子树一定先于右子树遍历”这个前提

• 先序遍历：根节点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根节点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根节点

图

图是一种非线性数据结构。图是一种网络抽象模型，它是一组由边连接的节点（或顶点），任何二元关系都可以用图来表示。

特点

• 有环或者无环的
• 有向图或者无向图
• 加权或者未加权的
• 是否是强连接的

图的表示

• 邻接矩阵：是使用二维数组（矩阵）来描述图
• 领接表：使用动态数据结构（链表、数组、字典）来描述图
• 关联矩阵：矩阵的行表示顶点，列表示边

图的遍历

广度优先搜索（BFS）

• 队列实现：通过将顶点存入队列，最先入队列的顶线先被搜索。
• 简单理解：就是一层一层的访问遍历，走完为止。

深度优先搜索（DFS）

• 栈实现：通过将顶点粗存入栈中，顶点沿着路径被探索的，存在新的相邻顶点就去访问。
• 简单理解：先从一条边走到头，然后在走下一条边，走完为止。

参考

• 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

来自九旬的原创：博客原文链接

本文正在参与「掘金小册免费学啦！」活动, 点击查看活动详情