常用数据结构剖析

数据结构可以从两个方面分析：逻辑结构与物理结构(存储结构)。

其中逻辑结构指的是数据的组织方式，物理结构指的是数据在内存上的存储方式。

逻辑结构分为四种类型：集合结构，线性结构，树形结构，图形结构。

物理结构又叫存储结构，分为四种种，顺序存储结构、链式存储结构、索引结构、散列结构。

一、什么是数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

数据结构与算法的关系：

数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。
数据结构是为算法服务的，算法是要作用再特定的数据结构上的。

二、常用数据结构有哪些

2.1 基本数据结构

数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构。 集合结构:除了同属于一种类型外，别无其它关系 ；

线性结构:元素之间存在一对一关系常见类型有: 数组,链表,队列,栈,它们之间在操作上有所区别。例如:链表可在任意位置插入或删除元素, 而队列在队尾插入元素,队头删除元素,栈只能在栈顶进行插入,删除操作；

树形结构:元素之间存在一对多的关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等) 图形结构:元素之间存在多对多的关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。

2.2 常用数据结构 (逻辑结构）

2.2.1 数组（静态数组、动态数组）

在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中， 数组属于构造数据类型。
一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

2.2.2 线性表

线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。顺序表、链表（单向链表、双向链表、循环链表）

2.2.3 队列

栈隶属于线性表，是特殊的线性表，因为它对线性表中元素的进出做了明确的要求只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。即只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素 时，称为队空。

2.2.4 栈

栈隶属于线性表，是特殊的线性表，因为它对线性表中元素的进出做了明确的要求。栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。即先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，最后一 个数据被第一个读出来。

2.2.5 树（二叉树、查找树、平衡树、线索、堆）

树是一种典型的非线性结构，它是由 n（n>0）个有限节点组成的一个具有层次关系的集合。树形数据结构有以下这些特点：

• 每个节点都只有有限个子节点或无子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树。
  
  树的种类有很多种，常见的有：
• 无序树：树中任意节点的子节点之间没有顺序关系。
• 二叉树：每个节点最多含有两个子树。二叉树按照不同的表现形式又可以分为多种。
• 完全二叉树：对于一颗二叉树，假设其深度为 d（d > 1）。除了第 d 层，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。
• 平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。

平衡二叉树本质上也是一颗二叉查找树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于 1。
Java 中最常见的平衡二叉树就是红黑树，节点是红色或者黑色，通过颜色的约束来维持着二叉树的平衡：

1）每个节点都只能是红色或者黑色

2）根节点是黑色

3）每个叶节点（NIL 节点，空节点）是黑色的。

4）如果一个节点是红色的，则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。

5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

• 满二叉树：一颗每一层的节点数都达到了最大值的二叉树。有两种表现形式，第一种，像下图这样（每一层都是满的），满足每一层的节点数都达到了最大值 2。
• 二叉查找树：英文名叫 Binary Search Tree，即 BST，需要满足以下条件：

1.任意节点的左子树不空，左子树上所有节点的值均小于它的根节点的值；
2.任意节点的右子树不空，右子树上所有节点的值均大于它的根节点的值；
3.任意节点的左、右子树也分别为二叉查找树。

基于二叉查找树的特点，它相比较于其他数据结构的优势就在于查找、插入的时间复杂度较低，为 O(logn)。假如我们要从上图中查找 5 个元素，先从根节点 7 开始找，5 必定在 7 的左侧，找到 4，那 5 必定在 4 的右侧，找到 6，那 5 必定在 6 的左侧，找到了。

理想情况下，通过 BST 查找节点，所需要检查的节点数可以减半。

• B 树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树。数据库的索引技术里就用到了 B 树。
  

2.2.6 图(Graph)

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

上图共有 V0，V1，V2，V3 这 4 个顶点，4 个顶点之间共有 5 条边。

在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素（除第一个和最后一个外）均有唯一的“前驱”和“后继”；

在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素（父节点）及下一层的多个元素（子节点）相关；

而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。

2.2.7 堆 (Heap)

堆可以被看做是一棵树的数组对象，具有以下特点：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2.2.8 散列表(哈希表） (Hash)

哈希表（Hash Table），也叫散列表，是一种可以通过关键码值（key-value）直接访问的数据结构，它最大的特点就是可以快速实现查找、插入和删除。

数组的最大特点就是查找容易，插入和删除困难；而链表正好相反，查找困难，而插入和删除容易。哈希表很完美地结合了两者的优点， Java 的 HashMap 在此基础上还加入了树的优点。

哈希函数在哈希表中起着常关键的作，它可以把任意长度的输入变换成固定长度的输出，该输出就是哈希值。哈希函数使得一个数据序列的访问过程变得更加迅速有效，通过哈希函数，数据元素能够被很快的进行定位。

若关键字为 k，则其值存放在hash(k)的存储位置上。由此，不需要遍历就可以直接取得 k 对应的值。

对于任意两个不同的数据块，其哈希值相同的可能性极小，也就是说，对于一个给定的数据块，找到和它哈希值相同的数据块极为困难。再者，对于一个数据块，哪怕只改动它的一个比特位，其哈希值的改动也会非常的大——这正是 Hash 存在的价值！

尽管可能性极小，但仍然会发生，如果哈希冲突了，Java 的 HashMap 会在数组的同一个位置上增加链表，如果链表的长度大于 8，将会转化成红黑树进行处理——这就是所谓的拉链法（数组+链表）。

2.3 数据存储结构比较

• 顺序结构：一段连续的内存空间。
  优点：随机访问
  缺点：插入删除效率低，大小固定
• 链式结构：不连续的内存空间
  优点：大小动态扩展，插入删除效率高
  缺点：不能随机访问。
• 索引结构：为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。
  优点：对顺序查找的一种改进，查找效率高
  缺点：需额外空间存储索引表
• 散列结构：选取某个函数，数据元素根据函数计算存储位置。可能存在多个数据元素存储在同一位置，引起地址冲突。
  优点：查找基于数据本身即可找到，查找效率高。存取效率高
  缺点：存取随机，不便于顺序查找。

2.4 数据结构的操作

查询、删除、插入等

2.5 算法的空间复杂度与时间复杂度

大O复杂度表示法