表示此篇文章概述一下数据结构的主要知识点

——线性结构——

线性结构分为顺序表和链表
顺序表(即数组)：内存中一块连续的区域，紧密排列了若干个相同类型的数据。数据存储方式为顺序存储
这种设计需要事先知道同样的元素一共有多少，不然就无法开辟出合适的内存区域（即会存在浪费或者不足）

链表：为了解决数组这种元素数量不灵活的缺点而提出的方法。链表的基本单位是节点，每个节点拥有一个数据区和一个next指针，其中数据区用于存放数据，next指针指向下一个节点。

顺序表[数组]

顺序表构造
一个一个往里塞就行。在实践中，一般使用一个下标保存当前顺序表的结尾位置，插入元素时直接在这里插入，然后让下标向后移动

for(let i=0;i<len-1;i++)
    arr[i] = xxx;

顺序表插入： 假设在第i个位置（变量i假设合法）插入元素e
主要实现逻辑：将顺序表的第i个元素及其后面的所有元素都向右移动一个位置，腾出一个空位插入新元素e，顺序表长度增1

# 伪码
function ListInsert(arr, i , e) {
    for(let j = arr.length; j >= i; j--) {
        // 从表的末尾元素开始一直往后腾一位，直到位置i
        arr[j] = arr[j-1];
    }

    arr[i-1] = e;
    arr.length++;
}

删除同理，将第i个位置的及其以后的元素向前移动一位

数组更多相关知识点、经典题等

链表

单链表

为了操作的方便，通常在单链表的第一个节点之前附加一个节点，称为头结点。

let dummy = new ListNode();
dummy.next = head; // 指针域指向线性表的第一个元素节点
dummy.data = null;

引入头结点带来的优点：

• 开始节点的位置被存放在头结点的指针域里，因此链表的第一个位置的操作和表其他位置的操作是一致的，无需特殊处理
• 无论链表是否为空，头指针都指向头结点的非空指针（空表中头结点的指针域为空），空表与非空表的处理也因此统一；

单链表的构造**：链表一般分为头插法和尾插法
头插法**：每一个新的节点都直接插在链表的头部，这样构造出来的数据与输入数据的顺序是反序，适用于构造栈；

let s = new Node(x);
s.next = this.head.next;
this.head.next = s;

尾插法：将新结点插入到当前链表的尾部，需要额外的指针指向尾节点，适用于构造队列

let newcode = new Node(x);
this.rear.next = newcode;
this.rear = newcode;

单链表的结点插入

let p = getElem(index-1); // 找到链表中插入位置的前驱结点
s.next = p.next;
p.next = s;

单链表的结点删除

**

let p= getElem(i-1);// 找到链表中插入位置的前驱结点
let q = p.next; // q指向将被删除的结点
p.next = q.next; // 断开p
free(q);

双链表

单链表结点中只有一个指向其后继结点的指针，使得单链表只能从头结点依次顺序地向后遍历，若要访问某个结点的前继结点（插入、删除的操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(N)

双链表在单链表的基础上增加了一个前向指针previous，即对于每一个节点可以同时找到它的上一个和下一个节点
双链表仅在单链表的基础上新增前驱结点，因此按值查找和按索引查找的操作与单链表一致，但插入和删除的实现上，双链表需要保证修改过程中不断链，同时维护好前驱结点

双链表的结点插入

S.next = p.next;
p.next.prior = s;
s.prior = p;
p.next = s;

循环链表

循环单链表：循环单链表与单链表的区别仅在于，循环单链表最后一个结点的指针不是null，而是改为指向头结点，从而整个链形成一个环。

所以引出一个经典问题：如何判断链表是否有环？

同理，也有循环双链表，循环双链表最后一个节点.next指向头结点，且头结点的prior指针指向表尾节点

队列与栈

队列和栈是被特化了规则的线性结构，属于逻辑结构的范畴，并不拘泥于某种特定的物理结构实现。换句话说，任何满足先进先出（FIFO）的结构都可以被描述成队列，而任何满足后进先出（LIFO）的结构都可以被描述成栈。

「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。
用数组实现，就要处理扩容缩容的问题；
用链表实现，没有这个问题，但需要更多的内存空间存储节点指针

队列的顺序表实现使用顺序表构造队列需要一个头指针和一个尾指针。进入的元素在尾指针处插入，取出的元素从头指针处去除；
队列的链表实现使用链表构造队列需要使用尾插法，并从头部移除元素。

栈的顺序表实现
使用顺序表构造栈只需要一个栈顶指针。元素从栈顶指针处入栈（push），同样从栈顶指针处出栈（pop）

栈的链表实现
使用链表构造栈需要使用头插法，并从头部移除元素（此时指向链表头结点本身的指针即为栈顶指针）

散列表

「散列表」就是通过散列函数把键映射到一个大数组里。
而且对于解决散列冲突的方法：拉链法、线性探查法
拉链法需要链表特性，操作简单，但需要额外的空间存储指针；
线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些

——树状结构——

基本概念：
每一棵树有唯一的根节点，在此基础上向下生长
每一个节点的所有直接后代称为它的孩子节点，孩子的直接先代称为父亲节点
树中不能有环，每一个节点都必须有且仅有一个父亲节点（根节点除外）。
从根节点到叶子结点的最长路径称为树的度（或者深度）。

树一般使用链表实现，可以轻松cover住一个节点对应多个不等节点的情况（只需每个节点多几个节点索引即可，比如二叉树里node.left, node.right，如果是多叉树可能会有node.firsrtElement, node.secondXX,…., node.lastElemet等等）

这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉树、二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

二叉树

其中最基础的是：二叉树，而二叉树中比较特殊的二叉树又分为：完全二叉树、二叉搜索树
什么是二叉树呢？
每个非叶节点至多只有两个孩子的树称为二叉树。显然二叉树的深度介于log₂N与N之间。当深度为N时，二叉树退化为线性表。二叉树节点的两个孩子分别称为左孩子和右孩子

二叉树的链式存储：每个节点包含一个数据区和两个孩子指针。数据区用于存储数据，孩子指针分别指向两个孩子，如果没有孩子就悬空。二叉链表至少包含3个域：数据域data、左指针域、右指针域

二叉树的线性存储：将树上的节点依次从上到下、自左到右存储在数组中。
将二叉树保存在顺序表中。这种方式会成为堆排序的理论基础，并且在存储完全二叉树时有明显的优势，根据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，最大可能地节省存储空间，且可以利用数组元素的下标值确定节点在二叉树的位置及节点之间的关系。

二叉树的构建
建立一棵二叉树十分简单，一般有两种方式：从根向叶子和从叶子向根。
从根向叶子：大多数二叉树的构建方式
从叶子向根：哈夫曼树的构建

二叉树的访问
树的遍历：遍历二叉树即是以一定规则将二叉树的节点排列成线性序列，实质即是对非线性结构进行线性化操作。

• 前序遍历(递归与迭代实现
• 后序遍历
• 中序遍历
• 层序遍历

具体的遍历细节可以查看这里

扩展：对于多树，每个节点的记录不一定是.left,.right，有可能有多个节点，这个时候又怎么遍历呢？
比如dom树的api，比如一个普通的树状的json对象

扩展：根据前序遍历和中序遍历或后序遍历和中序遍历可以重建整棵树

几种常见的特殊二叉树：满二叉树、完全二叉树、二叉排序树、平衡二叉树

满二叉树

每个节点都含有左右子节点，如果高度为h，那么这棵树一定有2^h-1个节点。
如果对满二叉树按层序遍历进行编号，从根节点编号1开始，从上到下、自左到右。这样有个规律
对于编号为i的节点:
i的父节点：Math.floor(i/2)
i的左子节点：2i
i的右子节点：2i + 1

完全二叉树

如上图所示，满二叉与完全二叉的区别，完全二叉树的每个节点都与高度为h的满二叉树中编号为1-n的节点一一对应。
完全二叉树的叶子节点只可能出现在层次最大的两层上（最后两层）。对于最大层次的叶子节点，都依次排序在该层最左边位置上。
同理，完全二叉同满二叉一样用数组存储有较大优势。

堆

堆就是完全二叉树的一种应用，硬要说的话也属于反向生长。常用的堆分为大顶堆和小顶堆两种，前者满足父亲节点大于孩子节点，后者满足父亲节点小于孩子节点。根据递归我们可以推算出，大顶堆堆顶的元素是最大的，小顶堆堆顶的元素是最小的。堆排序就是在不断地重复建堆并移走堆顶元素的过程，显然平均复杂度是O(N*logN)，而且由于完全二叉树的性质

堆排序最神奇的地方就是它不需要借助一个链式的二叉树的辅助，而是直接在顺序表中操作元素，因此它的空间复杂度是O(1)级别

第一步，在逻辑上建堆。这一步要求我们根据实际情况（即数组下标从1或者0开始）来推演父亲节点与孩子节点真实的下标关系，在脑海中建立这个堆。> 第二步，满足堆的性质。这一步我们要对所有的非叶子节点从下到上进行调整，使其满足大顶堆或者小顶堆的性质。具体做法是找到第一个非叶子节点，并对它与它的孩子节点进行调整，使其满足堆的性质；然后从这个节点开始向前线性地调整每一个非叶子节点，直至根节点。此时整个堆都满足性质。

第三步，取得堆顶元素。这一步会把堆顶元素与堆内序号最大的元素进行交换，并且堆内元素数量减一。显然这个堆顶元素满足剩余未排序元素都比它小或比它大，而前面的已排序元素都比它大或比它小，因此它在已排序队列中的相对位置是确定的，即头或尾。 第四步，恢复堆的性质。由于刚才把一个无序元素插入了堆顶，导致堆的性质被破坏，接下来我们需要恢复它的性质。这一步不需要逆序遍历，而是从堆顶开始，将刚插入的元素逐步向下落，直至停在合适的位置。举例来讲，对于大顶堆，要保证堆顶元素是最大的，因此要把它分别与左右孩子进行比较，并且把三者中最大的一个升上堆顶。由于左右孩子在刚才的操作中都没有变动，因此各自满足在子树中是最大的的性质，此时若堆顶元素比他们两个都大，便能推理出堆顶元素是最大的。同理，升上去的三者中最大的元素也能满足这个推理。将堆顶元素向下落的操作要递归地进行到该元素不需要再进行交换为止，此时整个堆恢复性质。 第五步，重复第三步和第四步的操作，直至堆被清空。此时，整个数列有序。

重要应用: 堆排序，以及堆排序的变种问题（实时数据流中的第K大的元素

二叉排序(搜索)树

二叉排序树的定义是：每一个节点的左孩子小于它，而右孩子大于它（等于的情况事先声明一下放左还是放右就行，对于结果无实质影响）
特点：
1、左子树上所有节点均小于根节点
2、右子树上所有节点均大于根节点
3、左子树、右子树各自也是一棵二叉排序树
4、二叉排序树的中序遍历，即是将数据从小到大输出

二叉搜索树的构建：
在建立二叉排序树时只需要从根节点开始，递归地比较每一层元素，如果其比要插入的元素大则走向其左孩子，反之走向其右孩子，直至最终来到叶子结点，并把该元素插入。当全部的元素都被插入了，二叉排序树就建立完成了

二叉排序树的平均复杂度是O(N*logN)，其中的log就来自于二叉树的深度。当数组已经有序时二叉排序树会退化为O(N²)

使用二叉排序树排序尽管复杂度较低，而且十分容易理解，但是需要O(N)级别的辅助空间（即需要建立树而不是直接线性存储，因为二叉搜索树并不满足完全二叉树的特性）

了解:平衡二叉树

树上任一节点的左子树和右子树的高度之差不超过1

了解:哈夫曼树

正常的树都是从根向叶子生长，所以逆生长的哈夫曼树就显得比较特别。哈夫曼树一般用于压缩算法，可以用来生成前缀码。前缀码指的是，在一套编码体系中，任何一个字的密文都不是其他字的密文的前缀，或者说对于任何一个字的密文，从头开始连续截取任意长度，得到的结果都不能构成另外一个字的密文

1、哈夫曼树的第一步就是从统计字频开始的。这一步只需要遍历文本流就可以
2、建树: 由于哈夫曼树是逆生长树，采取的是合并子树的思想，所以最先被选择的一定是最深的子树。合并子树的方法如下：在最开始的时候，把每一个节点都视为一棵只有一个根节点的树。每一次迭代，选取频率最低的两棵子树进行合并，直到最后只剩下一棵树为止。举例来说，假设刚开始有a，b，c三棵子树，频率分别是0.1，0.2，0.7，那么第一次迭代就会选择0.1跟0.2进行合并，得到一棵频率为0.3的新子树，然后再把这棵新子树与0.7合并完成建树。显然，从根节点开始，寻找c只需要一步，而寻找a和b各需要两步，平均字长为1.3

建立哈夫曼树的目的是为了进行哈夫曼编码。前文也提到了，这是一种压缩算法。压缩的过程就是建立上述的哈夫曼树，然后遍历哈夫曼树写出每个字的密文，再按照查字典的方式把每个字转换过去。而解压缩的时候，则需要先重建哈夫曼树，再一位一位对照密文从树根开始向下寻找，找到叶子结点就可以认为解码出了一个字，然后下一位回到树根重新寻找

多叉树

多叉树相对于二叉树来讲没有孩子数量一定的限制，因此通常用一个孩子列表来保存全部的孩子节点，这一种应用在网页的DOM中尤其广泛，倒不如说整个XML规范文档以及JSON规范都可以抽象成多叉树。操作系统的目录树也属于这一应用范畴

了解:多元化的存储结构：除了二叉树里常见的左右子节点链式存储、基于层次遍历的顺序存储。还有一些其他存储结构，我们一起开开眼界

名称	图示	存储结构	优劣
双亲表示法			利用每个节点（除双亲节点）都有唯一双亲的性质 优：可快速得到双亲 劣:求节点的孩子时需遍历整个树
孩子表示法	是不是很像图的邻接表存储~		将每个节点的孩子节点用单链表链接成一个线性结构，n个节点就有n个孩子链表； 优：寻找子女十分直接 劣：寻找双亲需要遍历n个节点中孩子指针域指向的n个孩子链表
孩子兄弟表示法			存储灵活 优：方便实现将树转换为二叉树，易于查找节点的孩子节点 劣：查找节点的双亲比较麻烦。（不过为每个节点再增设一个parent的域可解决）

与Dom树最接近的存储方式即是孩子兄弟表示法、双亲表示法，一个dom的node节点有用的访问api有：

# 父节点
el.parentNode
# 兄弟节点 
el.previousElementSibling
el.nextElementSibling
# 孩子
el.children
el.firstElementChild
el.lastElementChild

了解:B+树

B+树是一种极其鬼畜的多叉树，结构复杂但是十分有效，极其常用于索引的建立，包括数据库索引、目录树索引等等
B+树的主要难点在于节点的分裂与合并，非叶节点与叶子结点的大小的上界与下界，以及树深度的伸缩，属于研究生课程的范畴，我不打算深入去讲，因为非常抽象并且不好实现，甚至比AVL树的四种旋转还要难理解。在设计B+树时需要考量节点大小，而这个大小一般是由计算机的一些物理性质决定的，缺乏计组的基础我觉得我也给你说不明白。总之，这东西很有用，但是不考。

并查集

树的应用—并查集
并查集是一种简单的集合表示，支持一下3种操作：
1、Union(S, Root1, Root2): 把集合S中的子集合Roo2并到子集合Root1中
2、Find(S, x)：查找集合S中单元素x所在的子集合，返回集合名字
3、Initial(S)：将集合S每个元素初始化为只有一个单元素的子集合

通常使用树的双亲表示法作为并查集的存储结构，每个子集合以一棵树表示，所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组里。

（未完待续…

——网状结构——

最后一部分是网状结构，也就是图论相关的东西

基本概念：首先，图是由顶点和边组成的，根据边的方向性又可以分为有向图和无向图（这一点看地图上的单行路就明白了）。如果在一个有向图中任意两个顶点可以相互到达，则称这张图为强连通图；反之，若不满足强连通图的定义，但是将所有的有向边修改为无向边后原有向图能构成连通图，则称该有向图为弱连通图。由于不像树一样要求唯一的父亲，图是允许有环的，并以此分为有环图和无环图

图的存储

邻接表就是链表，比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵
邻接矩阵就是二维数组，判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间
通常存储图有两种方式，即集合的方式和矩阵的方式。
~~
集合的方式：维护两个集合，即一个顶点集合V和一个边集合E。顶点集合中保存了所有顶点的信息以及序号，边集合保存了被一条边连通的两个顶点的序号以及边的代价（无权图可认为每一条边代价都是一样的）。由于稀疏图占了日常生活中的图的绝大多数，因此集合的方式是保存图的主要方式

邻接表：集合的方式这边也拿出了邻接表来进行快速查找。邻接表就是很简单的使用链表，为每一个节点建立一个链式的出度表，从而达到快速查找的目的。如果需要统计入度，那么应同时维护一张逆邻接表来对入度建立索引。当然，无向图可以把出度和入度混在一起记录，反正是无向的。

为了克服需要同时维护两张表的缺陷，人们发明了十字链表和邻接多重表，分别用于处理有向图和无向图

矩阵的方式：矩阵的方式取消了边集合，改用一个矩阵保存每两个顶点之间的代价。显然，顶点与自己的代价是0，与邻居的代价已知，与不直接相连的顶点代价为无穷大。只有在绝大多数顶点都彼此直接相连的情况下，矩阵的方式才能更节省空间。

邻接矩阵的链式存储
为了节省矩阵的空间开销，矩阵的链式存储应运而生。这种方法只关心矩阵中存在的元素，而忽略不存在的元素。每一个矩阵会被存储为一个行数组和一个列数组，以及一系列节点。两个数组中的每个元素各带有一个指针，指向该行或该列的第一个元素；每个节点保存了行号和列号，同时带有两个指针，分别指向该行的直接后继和该列的直接后继。使用这种结构的矩阵平衡了空间和时间的开销，对于稀疏矩阵提升尤其明显，但是随着矩阵中元素数量的增加效率会降低。

图的遍历

遍历就是从一个顶点出发，沿某一种规则访问全部的顶点，并且每个顶点只访问一次。遍历主要分为深度优先遍历和广度优先遍历两种

深度优先遍历在诸如迷宫求解的时候应用较好，如果途中有环则需要记录已经访问过的顶点，否则不需要；广度优先遍历适合浅层的关系，比如AI寻路（作为A*算法的基础），比如通过社交关系网查询两个用户之间的距离

图的最小生成树

图的最小生成树的作用是去除图中的环，同时使整体代价尽可能的小。
最小生成树算法可以应用于网络布设中，使用最低成本达到连通所有节点的目的。但是，这种做法并不能保证任意两个节点之间的距离都是最短的，同样也容易造成星型布局，并使得上游节点遭受随之而来的带宽压力。但这种做法可以使总成本最低。

常用算法包括普里姆算法（Prim）和克鲁斯卡尔算法（Kruskal）
**

图中两顶点的最短距离

**如果需要求某一个顶点到所有顶点的最短路径，常用的算法是迪杰斯特拉算法（Dijkstra

迪杰斯特拉算法在计算机网络中有大量应用（OSPF协议），也就是在路由器估计网络拥塞状况并智能选择更空闲的路径

AOV网-拓扑排序

拓扑排序用于清理AOV网（Activity On Vertex）。比如某一系列课程的复杂的前置关系就可以看成是一个AOV网，它是一个有向无环图。拓扑排序负责从其中找出一个顺序，可以在不违反所有前置课程条件的情况下完成对每一门课程的学习。拓扑排序每一次移除一个入度为0的顶点，然后移除该顶点的所有出度边，重复此操作直至最后移除全部的顶点。拓扑排序亦可用于复杂关系网的死锁检测。这是十分工业而且贴近管理的东西，一般不会在代码项目中遇到。

**

参考

数据结构和算法学习指南
不吃鱼的喵酱-数据结构笔记整理