算法之道（3）数据结构

一、概述

数据结构是指相互之间存在着一种或多种关系的数据元素的集合。

程序 = 数据结构 + 算法 。数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界，首先二者表现为不可分割的关系。

数据结构与算法关系：数据结构是底层，算法是高层。数据结构为算法提供服务，算法围绕数据结构操作。

数据结构看分为逻辑结构和物理结构（存储结构）。逻辑结构是指数据对象中数据元素之间的相互关系。物理结构：是指数据的逻辑结构在计算机中的存储形式。逻辑结构分为：集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储和链式存储。

常用的数据结构有：

• 数组（Array）
• 链表（Linked List）
• 栈（Stack）
• 队列（Queue）
• 树（Tree）
• 堆（Heap）
• 图（Graph）
• 散列表（哈希表）（Hash）

二、数组和链表

线性表（线性的数据结构）是最常用且最简单的一种数据结构，它是n个数据元素的有限序列。实现线性表的方式有两种：数组和链表（有时也称列表）。

数组（顺序存储结构）

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

数组的空间是从栈中分配的。

优点：

• 随机访问效率很高，时间复杂度可以达到O(1)。数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问。

缺点：

• 数组只能存储一种类型的数据
• 数组需要预留空间，数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小。导致数组空间的利用率低
• 在数组头部插入数据和删除数据效率低。后面的元素都需要向前或向后搬移，时间复杂度为O(N) 。
• 当数组空间不够使用的时候需要扩容，由于创建后大小不能改变，因此只能创建一个新的大的数组来替换当前数组。

适用场景：

频繁查询，对存储空间要求不大，较少进行增删操作。

链表（链式存储结构）

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。

链表的空间是从堆中分配的。

根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

优点：

• 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
• 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加删除操作很快，时间复杂度为O(1) 。

缺点：

• 含有大量的指针域，占用空间较大；
• 查找元素需要遍历链表来查找，非常耗时，时间复杂度为O(N)。

适用场景：

数据量较小，需要频繁增加，删除操作的场景。

java

• Vector、Array、ArrayList都是以数组的形式存储在内存中，所以查询效率高，新增和删除效率不高，但是Vector被Synchronized修饰，所以线程是安全的，ArraryList线程不安全。
• LinkedList则以链表的形式进行存储，所以查询效率底，新增和删除效率高，并且线程不安全。

三、栈和队列

通常称，栈和队列是限定插入和删除只能在表的”端点”进行的线性表。

栈

栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。

栈有自己的结构特性：栈是后进先出的线性表，栈的插入和删除操作只能在这个线性表的表尾进行。对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

队列

队列的本质也是一个线性表，则队列也可以用数组和链表两种方式来实现。

队列有自己的结构特性：队列是先进先出的线性表，它同时维护表的两端，但只能在表尾进行插入，在表头进行删除操作。

java

• Stack
• Queue

四、树

树不在是一对一的数据结构，而是一对多的非线性连接。其中常用的包括二叉树、二叉搜索树、2-3树、红黑树等等。

相关术语

• 根结点：最顶部的结点是根结点，只多只有一个根结点
• 子结点/父结点：结点的直接后继称为该结点的子结点。结点的直接前驱称为父结点，两者是相对的
• 叶子结点：没有子结点的结点，又称为终端结点，简称叶子。
• 深度/高度：树中结点最大层次称为树的深度或高度。
• 度：树的结点包含一个数据及若干指向子树的分支，结点拥有的子树数目称为结点的度。树的度定义为所有结点中度的最大值。
• 森林：n棵互不相交的树

二叉树

• 二叉树的每个结点至多只有2棵子树
• 二叉树的子树有左右之分，次序不能颠倒。
• 二叉树的第i层至多有2^(i-1)个结点。
• 深度为k的二叉树至多有2^k-1个结点。

对于任何一棵非空的二叉树,如果叶结点个数为n0，度数为2的结点个数为n2，则有: n0 = n2 + 1。

证明如下：

在一棵二叉树中，除了叶子结点（度为0）之外，就剩下度为2(n2)和1(n1)的结点了。则树的结点总数为T = n0+n1+n2;在二叉树中结点总数为T，而连线数为T-1.所以有：n0+n1+n2-1 = 2*n2+n1;最后得到n0 = n2+1;

二叉树遍历

二叉树遍历采用递归方式，先中后的序列表示的是根结点的访问顺序。

• 先序遍历：按照 根结点->采用先序递归遍历左子树->采用先序递归遍历右子树 的顺序访问。
• 中序遍历：按照 中序递归遍历左子树->根结点->中序递归遍历右子树 的顺序访问，中序遍历可采用中序投影法。
• 后序遍历：按照 后序递归遍历左子树->后序递归遍历右子树->根结点 的顺序访问。

满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。

• 叶子只能出现在最下一层。
• 非叶子结点度一定是2.
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。
• 高度为h，由2^h-1个结点构成的二叉树就是满二叉树

完全二叉树

对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。

• 叶子结点只能出现在最下一层（满二叉树继承而来）
• 最下层叶子结点一定集中在左部连续位置。
• 倒数第二层，如有叶子结点，一定出现在右部连续位置。
• 同样结点树的二叉树，完全二叉树的深度最小。

具有n的结点的完全二叉树的深度为[lgn]+1。

二叉查找树（Binary Search Tree）

二叉查找树，又称为是二叉排序树或二叉搜索树。

二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉查找树；
• 没有键值相等的结点。

当添加结点时，从二叉查找树最顶端结点开始，小于该值时向左走，大于该值时向右走。
当删除结点时，如结点没有子结点，可直接删除。如结点有一个子结点，将子结点替换到该位置。如结点有两个子结点，需要从删除结点的左子树中找到最大的结点替换到该位置。

对于二叉查找树而言，其深度的平均值是lgn，这将大大降低查找时的时间复杂度。

二叉查找树的性质：对二叉查找树进行中序遍历，即可得到有序的数列。

二叉平衡树（Balanced Binary Search Tree）

二叉树的一个性质是一颗平均二叉树的深度要比及结点个数N小得多，其深度的平均值是lgN，这将大大降低查找时的时间复杂度。

二叉树在运用得不好的情况下的情况下是有严重的问题的，比如只有左子树或者只有右子树，深度会大到N-1，被称为不平衡树。

为了维持二叉树的平衡，提出了各种实现的算法，AVL树（平衡二叉查找树）、结点大小平衡树（SBT）、红黑树等。

对于AVL树来说，它的平衡必须满足：每个结点的左子树和右子树深度最多差1。

可以证明,AVL树的确是适度平衡的——也就是说 一棵规模为N的AVL树高度在渐近意义下是不超过lgN的。

红黑树（Red-Black Tree）

红黑树是一种具有红色和黑色结点的平衡查找树，同时满足：

• 每个结点都是红色或者黑色
• 根结点是黑色的，每片叶子都是黑色的
• 如果一个结点是红色的，则它的两个子结点都是黑色的，即一条路径上不能出现相邻的两个红色结点。
• 从任意一个结点到其每个叶子的所有路径都包含着相同数目的黑色结点，即黑色平衡。

这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果就是这棵树大致上是平衡的，因为插入、删除和查找某个值得最坏情况时间都要求与树的高度成比例，这个高度理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树，最终保证了红黑树能够以O(logN) 的时间复杂度进行搜索、插入、删除。

HashMap与LinkedHashMap，它们保证了以O(1)的时间复杂度进行增、删、改、查，从存储角度考虑，这两种数据结构是非常优秀的。

但它们的统计（或排序）性能时间复杂度为O(N)，可以使用红黑树的典型实现TreeMap来用于排序。

详细参考：https://mp.weixin.qq.com/s/2KW31256VhsOWAnprG3tRw

B+Tree

动态查找树说了以上3种：二叉查找树，平衡二叉查找树，红黑树。其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

但是在大规模数据存储（数据库、磁盘）中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的，这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。因此一般平衡多路查找树（B-Tree），不是二叉的。

B树（即B-Tree）的定义一棵m阶（可理解为度）的B树满足下列条件：

• 树中每个结点至多有m个孩子。
• 除根结点和叶子结点外，其它每个结点至少有m/2个孩子。根结点至少有2个孩子（如果B树只有一个结点除外）。
• 所有叶结点在同一层，B树的叶结点可以看成一种外部节点，不包含任何信息。
• 有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子

总结：

• 二叉树：每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
• B树（或B-tree）：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
• B+树(B+-tree)：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；MySQL的InnoDB等引擎使用的就是B+树。
• B*树（B*-tree，或B~Tree）：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。

霍夫曼树

五、散列表（哈希表）

散列表，是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），散列表通常使用数组来存放记录。

好的散列函数：

• 计算简单
• 散列地址分布均匀

常用的散列函数构造方法：

• 直接定址法：取关键字的某个线性函数值为散列地址
• 平方取中法
• 除留余数法

处理散列冲突的方法：

• 开放定址法：一旦发生冲突，寻找下一个空的散列地址。
• 再散列函数法：准备多种不同的散列函数，发生冲突就换散列函数。
• 链地址法：将散列地址相同的记录存储在一个单链表中，当有冲突，在当前位置给单链表增加结点。
• 公共溢出区法：专门开辟公共溢出区，存储有冲突的数据。

六、图（Graph）

图是由结点和他们之间连线的集合。图是由顶点的有穷非空集合和顶点之间边的集合组成。表示为G(V,E)，其中G表示图，V是顶点的集合，E是边的集合。

结构	对应关系	数据元素	能否为空	数据元素的关系
线性表	一对一	元素	空表	线性关系
树	一对多	结点	空树	层次关系
图	多对多	顶点（Vertex）	顶点有穷非空	边（Edge）

术语

• 按照有无方向分类：无向图和有向图。无向图有顶点和边构成，有向图由顶点和弧构成。无向边用无序偶对（vi,vj）来表示。有向边用有序偶<vi,vj>表示，vi为弧尾，vj为弧头。
• 按照边或弧的多少，分为稀疏图和稠密图。如果任意两个顶点之间都存在边，叫完全图。含有n个顶点的无向完全图有n(n-1)/2条边。含有n个顶点的有向完全图有n(n-1)条弧。
• 简单图：图中，不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
• 权（Weight）：与图的边或弧相关的数叫权。
• 网（Network）:带权的图称为网。
• 子图(Subgraph)：有两个图G(V,E)和G’(V’,E’)，如果V’包含于V且E’包含于E，则称G’为G的子图。
• 度：无向图顶点的边数叫做度，有向图顶点分为入度和出度。
• 连通图：顶点间存在路径则说明是连通的，路径最终回到起始点的称为环，当中不重复叫简单路径。如任意两顶点都连通则叫连通图，有向则称为强连通图。

存储结构

1、邻接矩阵：用两个数组来表示图，一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。其中，有向图是对称矩阵。如果顶点多边少，会造成存储空间浪费。
2、邻接表：是数组和链表相结合的存储方法，对边或弧（实际是对邻接点）进行链式存储。有向图的邻接表有缺陷，只能选择邻接表或逆邻接表，关心了出度，想计算入度就必须遍历整个图。
3、十字链表：整合邻接表和逆邻接表，容易求顶点的出度和入度。
4、邻接多重表：在十字链表基础上，针对无向的边做优化，只保留一个结点，方便更新。
5、边集数组：由两个一维数组构成，边数组每个数据元素由边的起点下标、终点下标和权组成。

图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这一过程就叫图的遍历。

1、深度优先遍历（Depth First Search,DFS），和树的前序遍历类似。
2、广度优先遍历（Breadth First Search,BFS），和树的层序遍历类似。

最小生成树（Minimum Cost Spanning Tree）

构造连通网的最小代价生成树，称为最小生成树。

实际案例：线路互通成本。

1、普里姆(Prim)算法，时间复杂度O(n^2)，n为顶点数。走一步看一步，逐步生成最小生成树。
2、克鲁斯卡尔(Kruskal)算法，时间复杂度O(elge)，e为边数。从图中最短权值的边入手，找出最小生成树。

最短路径

对网图来说，最短路径，是指两顶点（源点和终点）之间经过的边上权值之和最少的路径。

实际案例：地铁或路网的导航。

1、迪杰斯特拉（Dijkstra）算法，思路简单，算法代码复杂。
2、弗洛伊德（Floyd）算法，应用矩阵变换，原理理解有难度，算法编写简洁。