数据结构

栈

一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端
为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈也被用在编程语言的编译器和内存中保存变变量、方法调用。

队列

与上相反，一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。

优先队列

实现优先队列，有两种选择：
设置优先级，然后在正确的位置添加元素
入列操作添加元素，然后按照优先级移除他们

循环队列

充分利用向量空间，客服‘假溢出’现象
将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中队列被称为循环队列
循环队列可以以单链表、队列的方式来时机变成应用中来实现

链表

存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的；每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针/链接）组成。
好处：添加或移除元素的时候不需要移动其他元素

注意：链表需要使用指针，因此实现链表时需要额外注意

链表想要访问中间的一个元素，需要从起点 (表头) 开始迭代列表直到找到所需的元素

双向链表

在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，一个链向上一个元素
双向链表可以从头到尾，或者从尾到头

循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。
循环链表和链表之间的区别：最后一个元素指向下一个元素的指针不是引用 null，而是指向第一个元素

链表的优点：无需移动链表中的元素，就能轻松地添加和移除元素

集合

由一组无序且唯一（即不能重复）的项组成；这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。

并集

对于给定的两个集合，返回一个包含两个集合中所有元素的新集合

交集

对于给定的两个集合，返回一个包含两个集合中共有元素的新集合

差集

对于给定的两个数组，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合

子集

求证一个给定集合是否是另一个集合的子集

字典

以 [键，值] 对为数据形态的数据结构，其中键名用来查询特定元素，类似于 Javascript 中的Object。
集合、字典、散列表都可以存储不重复的数据。字典和我们上面实现的集合很像，上面的集合中我们以 { value: value } 的形式存储数据，而字典是以 { key: value } 的形式存储数据，字典也称作映射。

散列

根据关键码值（Key value）直接进行访问的数据结构；它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度；这个映射函数叫做散列函数，存放记录的数组叫做散列表。
HashTable 类，也叫 HashMap 类，是 Dictionary 类的一种散列表实现方式。
散列算法的作用是尽可能快地在数据结构中找到一个值。

散列集合

散列集合由一个集合构成，但是插人、 移除或获取元素时，使用的是散列函数。我们可以重用上面实现的所有代码来实现散列集合， 不同之处在于，不再添加键值对，而是只插入值而没有键。例如，可以使用散列集合来存储所有 的英语单词（不包括它们的定义)。和集合相似，散列集合只存储唯一的不重复的值。

处理散列表中的冲突

分离链接

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的 最简单的方法，但是它在 HashTable 实例之外还需要额外的存储空间。

继性探查

当想向表中某个位置加人一个新元素的时候，如果索引为 index 的位置已经被占据了，就尝试 index+1的位置。如果index+1 的位置也被占据了，就尝试 index+2 的位置，以此类推。

树

由 n（n>=1）个有限节点组成一个具有层次关系的集合；把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，基本呈一对多关系，树也可以看做是图的特殊形式。

  • 节点
    • 根节点
    • 内部节点：非根节点、且有子节点的节点
    • 外部节点/页节点：无子节点的节点
  • 子树：就是大大小小节点组成的树
  • 深度：节点到根节点的节点数量
  • 高度：树的高度取决于所有节点深度中的最大值
  • 层级：也可以按照节点级别来分层

    二叉树

    二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这些定 义有助于我们写出更高效的向/从树中插人、查找和删除节点的算法。

    二叉搜索树

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

    树的遍历

    遍历一棵树是指访问树的每个节点并对他们进行某种操作的过程
    访问树的所有节点有三种方式：中序、先序、后序

    中序遍历

    中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以从最小到最大的顺序访 问所有节点。中序遍历的一种应用就是对树进行排序操作。

    先序遍历

    先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

    后序遍历

    后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小。

    遍历顺序

    先序遍历：节点本身 => 左侧子节点 => 右侧子节点
    中序遍历：左侧子节点 => 节点本身 => 右侧子节点
    后序遍历：左侧子节点 => 节点本身 => 右侧子节点

    图

    图是网络结构的抽象模型；图是一组由边连接的节点（顶点）；任何二元关系都可以用图来表示，常见的比如：道路图、关系图，呈多对多关系。

    邻接矩阵

    每个节点都和一个整数相关联，该整数将作为数组的索引。我 们用一个二维数组来表示顶点之间的连接。如果索引为 i 的节点和索引为 j 的节点相邻，则 array[ i ][ j ] ===1，否则 array[ i ][ j ] === 0

    邻接表

    邻接表由图中每个顶点的相邻顶 点列表所组成。存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表，甚至是 散列表或是字典来表示相邻顶点列表。

    关联矩阵

    在关联矩阵中，矩阵的行表示顶点，列表示边。如下图所 示，我们使用二维数组来表示两者之间的连通性，如果顶点 v 是边 e 的入射点，则 array[v][e] === 1; 否则，array [v][e] === 0。

    图的遍历

    图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环等。

    广度优先搜索

    队列，通过将顶点存入队列中，最先入队列的顶点先被探索
    广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访 问图的一层。简单说，就是先宽后深地访问顶点

    广度优先搜索

    深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶 点被访问了，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点

    算法

    冒泡排序

    比较任何两个相邻的项，如果第一个比第二个大，则交换它们；元素项向上移动至正确的顺序，好似气泡上升至表面一般，因此得名。
    1. Array.prototype.bubbleSort = function() {
    2. for (let i = 0; i < this.length; i++) {
    3.   for (let j = 0; j < this.length - 1 - i; j++) {
    4.     if (this[j] > this[j + 1]) {
    5.       let aux = this[j]
    6.       this[j] = this[j + 1]
    7.       this[j + 1] = aux
    8.     }
    9.   }
    10. }
    11. }

    选择排序

    每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，以此循环，直至排序完毕。
    1. Array.prototype.selectionSort = function() {
    2. let indexMin
    3. for (let i = 0; i < this.length - 1; i++){
    4.   indexMin = i
    5.   for (var j = i; j < this.length; j++){ 
    6.     if(this[indexMin] > this[j]) {
    7.       indexMin = j
    8.     }
    9.   } 
    10.   if (i !== indexMin){
    11.     let aux = this[i]
    12.     this[i] = this[indexMin]
    13.     this[indexMin] = aux
    14.   }
    15. }
    16. return this
    17. }

    插入排序

    将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，此算法适用于少量数据的排序，时间复杂度为 O(n^2)。

    归并排序

    将原始序列切分成较小的序列，只到每个小序列无法再切分，然后执行合并，即将小序列归并成大的序列，合并过程进行比较排序，只到最后只有一个排序完毕的大序列，时间复杂度为 O(n log n)。

    快速排序

    通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行上述递归排序，以此达到整个数据变成有序序列，时间复杂度为 O(n log n)。

搜索算法

##顺序搜索：

让目标元素与列表中的每一个元素逐个比较，直到找出与给定元素相同的元素为止，缺点是效率低下。

二分搜索：

在一个有序列表，以中间值为基准拆分为两个子列表，拿目标元素与中间值作比较从而再在目标的子列表中递归此方法，直至找到目标元素。

其他

贪心算法：

在对问题求解时，不考虑全局，总是做出局部最优解的方法。

动态规划：

在对问题求解时，由以求出的局部最优解来推导全局最优解。

复杂度概念：

一个方法在执行的整个生命周期，所需要占用的资源，主要包括：时间资源、空间资源。