学习数据结构与算法

栈是一个后进先出(LIFO)的数据结构。JavaScript的内置对象Array实现了栈的push、pop等相关方法。

队列是一个先进先出(FIFO)的数据结构。JavaScript事件循环中有一个事件队列，按照先进先出的规则来处理各种异步事件。

链表是一个动态的数据结构，可以任意增删元素，按需扩容。

• 数组的存储有缺陷，增删元素时需要移动元素，效率较低。而链表在内存中的放置不是连续的，元素通过next属性指向下个元素，因此链表的增删只需更改next指向。

集合是一种无序且唯一的数据结构。JavaScript中已经实现了集合类Set。

字典是一种以键值对的形式存储唯一值的数据结构。JavaScript中已经实现了字典类Map。

• 一个对象通常都有自己的原型(prototype)，不过，通过map = Object.create(null)来创建一个没有原型的对象。
• 一个对象的键只能是字符串或者Symbols，而Map可以是任意值。
• Map具有size方法，可以获取键值对个数，对象不具备直接获取长度的方法。

散列表也是一种以键值对存储数据的数据结构，但是它的键是通过散列函数生成的位置或索引。散列表可以更快地访问某个值，其查找复杂度为O(1)，其他顺序数据结构如栈、队列、链表需要遍历，查找复杂度都为O(n)。

• 散列函数
  • 散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。
  • 散列函数构造方法：直接定址法、数字分析法、平方取中法、折叠法、随机数法、保留余数法等。
  • 保留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。p一般取素数或m。
  • 解决冲突：当多个键得到同样的散列地址时就会产生冲突，此时就需要解决冲突。
    • 分离链表法：散列表中存入一个链表，所有散列地址冲突的存入同一个列表。
    • 线性探查法：当散列地址冲突时，就设置在下一个位置，继续冲突，则继续向后查找，直到找到空位。

树是一种分层数据的抽象模型。

• 二叉树：树中的每个节点最多只能有两个子节点。
• 二叉搜索树：二叉树的一种，只允许在左侧节点存储比父节点小的值，右侧节点存储比父节点大于等于的值。
• AVL树：一种自平衡二叉搜索树，树中任何一个节点左右两侧子树的高度之差最多为1。
• 红黑树：也是一种自平衡二叉搜索树，每个节点都带有颜色属性的二叉搜索树。
  • 节点是红色或者黑色。
  • 根是黑色。
  • 所有叶子都是黑色。
  • 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
  • 从任一节点到其每个叶子的所有简单路径（一个没有重复节点的路径）都包含相同数目的黑色节点。
• 堆积树：二叉树的一种，若父节点小于子节点，则称之为最小堆积树，若父节点大于子节点，则称之为最大堆积树。

图是网络结构的抽象模型，是一组由边连接的节点（顶点）。

• 图按照有无方向分为无向图和有向图。无向图由顶点和边组成，有向图由顶点和弧构成。弧有弧尾和弧头之分，带箭头一端为弧头。
• 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫做完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边叫简单图。
• 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度。有向图顶点分为入度和出度。
• 图上的边或弧带有权则成为网。
• 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复的叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称为强连通图。
• 图的展现方式：
  • 邻接矩阵：矩阵的行列都是图的顶点，数字代表是否连接。
  • 邻接表：由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表、甚至是散列表或是字典来表示相邻顶点列表。
  • 关联矩阵：矩阵的行表示顶点，列表示边，数字代表是否连接。
• 图的遍历：

  • 广度优先遍历：先广后深来遍历图中的顶点。（先遍历相邻顶点，再遍历非相邻顶点）

    

  • 深度优先遍历：先深后广来遍历图中的顶点。