数据结构

数据结构有：1.数组；2.栈；3.队列；4.链表（单链表、双向链表、循环链表）；5.数；6.散列表；7.堆；8.图。

一、数组

内存连续，可通过元素下标访问。

二、栈

先进后出

三、队列

先进先出

四、链表

物理存储不连续，因为存储了相邻元素的物理地址，所以逻辑上连续。

五、树

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。二叉树是树的特殊一种，具有如下特点：

每个结点最多有两颗子结点。

左子树和右子树是有顺序的，次序不能颠倒。

即使某结点只有一个子树，也要区分左右子树。

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。

二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等

六、散列表（哈希表）

是根据键和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。

散列表首先需要根据key来计算数据存储的位置，也就是数组索引的下标；

HashValue=hash(key)

散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

七、堆（Heap）

堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。堆有下列特点：

每个节点最多有两个子节点
排列顺序必须从上到下，同一行从左到右
堆中某个节点的值总是不大于或不小于其父节点的值；
存放数据时，一般会把新数据放在最下面一行靠左的位置。如果最下面一行没有多余空间时，就再往下另起一行，并把数据添加到这一行的最左端。

堆的性质：

• 堆是一个完全二叉树(从根结点到倒数第二层满足满二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。)
• 堆中某个结点的值总是不大于或不小于其父结点的值；

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
一棵深度为k 且有 2的k次方−1 个结点的二叉树称为满二叉树。也就是说除了叶子节点都有2个子节点，且所有的叶子节点都在同一层。

堆和普通树的区别 :

堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：

1.节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

2.内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。

3.平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

4.搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

8、图

图是一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。