提示

原文：https://www.jianshu.com/p/6b03035bbd19

什么是数据结构？

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

上面是百度百科的定义，通常情况下，我们说的数据结构可以理解成是指一组数据的存储结构。

如上图所示，数据是存储在计算机的内存里的，在存储时，决定了数据顺序和位置关系的便是“数据结构”。存储结构的顺序和位置关系就是“数据结构”。选择合适的数据结构，不但可以提高内存的使用率，也可以提高查找的效率。查找效率就是指算法，数据结构是为算法而生。

数据结构分类

数据结构分为逻辑结构和物理结构。

• 逻辑结构：指数据元素之间逻辑关系的数据结构，这里的逻辑关系是指数据元素之间的前后间关系，与数据在计算机中的存储位置无关。
• 物理结构：指数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构，也叫做存储结构。

数据的逻辑结构

数据的逻辑结构主要分为线性结构和非线性结构。

• 线性结构：

  • 数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点

  • 线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的 ，链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地 址信息

  • 线性结构是一个有序数据元素的集合

  • 常用的线性结构有：线性表，栈，队列，双队列，串(一维数组)

    这两点结合起来一句话就是：有序的一维数组（线性表，栈，队列，双队列）

  • 特点

    • 集合中必存在唯一的一个”第一个元素”，可以理解为：12345... 必须只能有1，不能是11。如112345..
    • 集合中必存在唯一的一个”最后的元素”，可以理解为：12345.... 必须只有5，不能是55，如123455....
    • 除最后元素之外，其它数据元素均有唯一的”后继”，这个 “后续” 是指后面一个元素
    • 除第一元素之外，其它数据元素均有唯一的”前驱”，这个 “前驱” 是指前面一个元素

• 非线性结构：各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点。

  • 关于广义表、数组(高维)，是一种非线性的数据结构。
  • 常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图
  • 这两点结合起来一句话就是：无序的多维数组（二维数组，广义表，树(二叉树等)，图）
  • 特点
    • 一个结点元素可能有多个直接前驱和多个直接后继。

数据的物理结构(存储结构)

数据的物理结构（以后我都统一称存储结构），表示数据元素之间的逻辑关系，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有：

• 顺序存储：存储顺序是连续的，在内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。
• 链式存储：在内存中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。
• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。
• 散列存储：又称Hash存储，由节点的关键码值决定节点的存储地址。

顺序表

逻辑结构顺序和物理结构顺序相同的的线性表被称为顺序表，是把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元中，用这种方法存储的线性表称为顺序表，一般情况下采用数组存储。在数组上完成数据的增删查改。

简单来说，顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改，顺序表也是线性表。

**所以，顺序表对储存物理空间有很强的要求：**顺序表存储数据时，会提前申请一整块足够大小的连续的物理空间，然后将数据依次存储起来。

并且，顺序表通过是否有固定大小空间可以分为：静态顺序表和动态顺序表

静态：

动态：

常用的数据结构

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

线性表

数组（Array）

数组是最简单、使用最频繁的一种数据结构。它一种线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据。

如上图所示，数据是按照顺序存储在内存的连续空间内，arr后面的[]代表下标，由于数据是存储在连续空间内的，所以每个数据的内存地址(在内存上的位置)都可以通过数组下标计算出来，从而可以直接访问目标数据，达到随机访问的目的。

队列（Queue）

队列也是一种非常基础的数据结构，其特点是先入先出，也就是我们常听到的FIFO（First in First Out），即操作数据是从两端进行的。

画一个入队列，出队列的示意图

链表（Linked List）

链表是一种物理存储单元上非连续，非顺序的存储结构。链表有一系列节点组成，所谓节点就是指链表中的每一个元素，每个节点包含两个数据，一个是存储元素的数据域（值），另一个是存储下一个节点地址的指针域。

通俗点说，链表数据一般都是分散存储于内存中 的，无须存储在连续空间内。画一张图：

假设上图中100-108是一块内存中连续地址的内存分布，假设101、103、106、107这几个内存地址都已经存储数据了，那剩下的100、102、104、105、108是不是就浪费呢，答案是否定的，我们可以使用链表的方式存储数据。

栈（Stack）

栈也是一种数据呈线性排列的数据结构，和上面的队列相反，栈的特点先进后出、后进先出，就是常说的LIFO（Last in First Out）。

非线性表

树（Tree）

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。

数的结构特点是：

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

我们平时用到最多的就是二叉树，我也以二叉树来为例，先看一下树结构：

二叉树有几下特点：

• 每个结点最多有两颗子树，结点的度最大为2。
• 左子树和右子树是有顺序的，次序不能颠倒。
• 即使某结点只有一个子树，也要区分左右子树。
• 个结点的值均大于其左子树上任意一个结点的值。比如 点的值。结点100大于其左子树上的30，18和16。
• 每个结点的值均小于其右子树上任意 一个结点的值。比如结点 100 小于其右子树上的 120、130 和 135。

散列表（Hash）

散列表又叫哈希表，存储的是由键(key)和值(value)组 成的数据，根据键直接访问存储在内存存储位置的数据结构。

从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。**哈希表查找数据的公式为：记录的存储位置=f(key)**这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

堆（Heap）

堆比较特殊，是一种图的树形结构。被用于实现“优先队列”(priority queues)，优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺 序取出。在堆的树形结构中，各个顶点被称为“结点”(node)，数据就存储在这些结点中。

只要满足下面两个特点的树形结构就是堆：

• 堆是一个完全二叉树（所谓完全二叉树就是除了最后一层其他层的节点个数都是满的）。
• 堆中每一个节点的值都必须大于等于或者小于其子树中每一个节点的值。

下面我们看一下堆的结构：

上面其实叫大顶堆，如果每一个节点小于子树中每个节点的值，那就叫小顶堆。

图（Graph）

图是相对复杂的一种数据结构，由顶点和连接每对顶点的边所构成的图形就是图。

我们先来看图：

上图中的圆圈叫作“顶点”(Vertex，也叫“结点”)，连接顶点的线叫作“边”（Edge）。也就是说，由顶点和连接每对顶点的边所构成的图形就是图。 图按照顶点指向的方向可分为无向图和有向图，像我上面的就叫无向图。 图在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。常见的图遍历算法就是广度优先算法和深度优先算法。