常见数据结构

参考文档
数据结构中的树
Bit-map空间压缩和快速排序去重
浅谈算法和数据结构: 七 二叉查找树
Java遍历树（深度优先+广度优先）
DFS（深度优先搜索）和BFS(广度优先搜索)
二叉树遍历(先序、中序、后序)
B树、B-树、B+树、B*树详解

动态演示：
Data Structure Visualizations
VisuAlgo
演示

一、数组

数组是有序的元素集合，数组在内存中为一段连续内存，数组有固定的大小

二、链表

表是有序的元素集合，储存为分散的节点(node)，每个节点包含有一个元素，以及一个指向下一个(或者上一个)元素的指针。

表的每个节点占据的内存可以是离散的。在表中，我们必须沿着指针联系起的长链，遍历查询元素。表可以根据运行情况插入或者删除节点，动态的更改大小。表插入节点时需要从进程空间的堆中开辟内存空间，用以储存节点。删除节点可以将节点占据的内存归还给进程空间。

• 单向链表

  
  

• 双向链表

  
  

• 循环链表

  
  

• 双向循环链表

  
  

三、栈

栈(stack)是简单的数据结构，但在计算机中使用广泛。它是有序的元素集合。栈最显著的特征是LIFO (Last In, First Out, 后进先出)。

栈中的每个元素称为一个frame。而最上层元素称为top frame。栈只支持三个操作， pop, top, push。

栈最经典的计算机应用是函数调用。每个进程都会有一个栈，每个frame中记录了调用函数的参数，自动变量和返回地址。当该函数调用一个新的函数时，栈中会 push一个frame。当函数执行完毕返回时，该frame会pop，从而进入调用该函数的原函数，继续执行。

由于栈是限定了操作的有序的元素集合，所以既可以在数组的基础上来实现栈，也可以在表的基础上来实现栈。

四、队列

队列(queue)是一个简单而常见的数据结构。队列也是有序的元素集合。队列最大的特征是First In, First Out (FIFO，先进先出)，即先进入队列的元素，先被取出。这一点与栈(stack)形成有趣的对比。

队列支持两个操作，队首的元素离开队列(dequeue)，和新元素加入队尾(enqueue)。

队列在计算机中应用很广泛。一个经典的应用是消息队列，实际上就是利用队列来分配有限的进程。还有FIFO文件(哦，你可以看到，这种文件叫做FIFO，肯定是和队列有关)，用以实现管道传输。再比如，我们将多个打印任务发送给打印机，打印机也是使用队列来安排任务的顺序。

和栈相似，队列也可以有多种实现方式，这里是基于单链表的实现。

五、堆

堆(heap)又被为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。回忆一下，在队列中，我们可以进行的限定操作是dequeue和enqueue。dequeue是按照进入队列的先后顺序来取出元素。而在堆中，我们不是按照元素进入队列的先后顺序取出元素的，而是按照元素的优先级取出元素。

Linux内核中的调度器(scheduler)会按照各个进程的优先级来安排CPU执行哪一个进程。计算机中通常有多个进程，每个进程有不同的优先级(该优先级的计算会综合多个因素，比如进程所需要耗费的时间，进程已经等待的时间，用户的优先级，用户设定的进程优先程度等等)。内核会找到优先级最高的进程，并执行。如果有优先级更高的进程被提交，那么调度器会转而安排该进程运行。优先级比较低的进程则会等待。“堆”是实现调度器的理想数据结构。

(Linux中可以使用nice命令来影响进程的优先级)

堆的一个经典的实现是完全二叉树(complete binary tree)。这样实现的堆称为二叉堆(binary heap)。

完全二叉树是增加了限定条件的二叉树。假设一个二叉树的深度为n。为了满足完全二叉树的要求，该二叉树的前n-1层必须填满，第n层也必须按照从左到右的顺序被填满，比如下图:

• 左倾堆

左倾堆则是维持一种不平衡的结构: 它的左子树节点往往比右子树有更多的节点。，左倾堆可以相对高效的实现合并(merge)操作。

左倾堆利用不平衡的节点分布，让右侧路径保持比较短的状态，从而提高合并的效率。

在合并过程，通过左右互换，来恢复左倾堆的性质。

六、哈希表

哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系，而且集合A的某个元素只能对应集合B中的一个元素。但反过来，集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素，这样的映射被称为一一映射。

hash冲突, open hashing, closed hashing

七、树

树的遍历：

• 广度优先遍历：层次遍历
• 深度优先遍历：

前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点

树(Tree)是元素的集合。

树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。

树成员关系图：

• 二叉树
  二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：
  

  

• 二叉搜索树
  二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。
  

  

• AVL树
  AVL树要求: 任一节点的左子树深度和右子树深度相差不超过1
  

  

平衡，单旋转，双旋转。

• 红黑树（RBTree）

红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。

红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：
任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。

除了具备该特性之外，红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树。

• 伸展树（splay tree）
  它对于m次连续搜索操作有很好的效率。
  具体来说，在查询到目标节点后，伸展树会不断进行下面三种操作中的一个，直到目标节点成为根节点 （注意，祖父节点是指父节点的父节点）

1. zig: 当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。

2. zig-zag: 当目标节点、父节点和祖父节点成"zig-zag"构型时，进行一次双旋转，将目标节点调整到祖父节点的位置。

3. zig-zig：当目标节点、父节点和祖父节点成"zig-zig"构型时，进行一次zig-zig操作，将目标节点调整到祖父节点的位置。

八、图

图(graph)是一种比较松散的数据结构。它有一些节点(vertice)，在某些节点之间，由边(edge)相连。节点的概念在树中也出现过，我们通常在节点中储存数据。边表示两个节点之间的存在关系。在树中，我们用边来表示子节点和父节点的归属关系。树是一种特殊的图，但限制性更强一些。

有向图，无向图。

一种简单的实现图的方法是使用二维数组。让数组a的每一行为一个节点，该行的不同元素表示该节点与其他节点的连接关系。如果(u,v)∈E，那么a[u][v]记为1，否则为0。

更经济的实现方式是使用邻接表(adjacency list)，即记录每个节点所有的相邻节点。对于节点m，我们建立一个链表。对于任意节点k，如果有(m,k)∈E，就将该节点放入到对应节点m的链表中。邻接表是实现图的标准方式。

• 拓扑排序 (topological sort)

• 最短路径(shortest path)与贪婪

最短路径是寻找最优解的算法。在复杂的网络中，简单的实现方式无法运行，必须求助于精心设计的算法，比如这里的Dijkstra算法。利用贪婪的思想，我们不断的优化结果，直到找到最优解。

---

总结优缺点