Rayjun

数据结构简明教程

数据结构的重要性无需多说，本文总结了常用的数据结构及其特点和适用场景，具体有：

  • 数组
  • 链表
  • 栈
  • 队列
  • 跳表
  • 散列表
  • 树
  • 图

数组

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

数组有两个特点：

  • 数据线性排列，每个数据最多有前和后两个方向
  • 有着连续的内存空间和相同类型的数据

这两个特点带来随机访问的特性，根据下标随机访问的时间复杂度为 $O(1)$，但是为了保持内存数据的连续性，会导致插入和删除这两个操作比较低效，因为需要不断去移动数据。

随机访问实际上是通过寻址公式来实现的，为了让寻址公式可以正常运行，那么要求数据中存储的数据类型必须要一样。

寻址公式:

a[i]_address = base_address + i * data_type_size

链表

链表是通过引用（指针）将零碎的内存块串联起来。每一个内存块称之为结点。

常见的链表类型有：

  • 单链表
  • 双向链表
  • 循环联表

链表的第一个结点叫头结点，最后一个节点叫尾节点，尾节点的 next 指向 NULL。

链表结点的结构如下：

class Node {        
     Node next; // 记录下一个结点
     Node prev; // 记录上一个结点，双向链表才会有
     int data; // 存储数据
}

链表与数组的不同之处：

  • 数组内存连续，链表内存不连续
  • 数组本身不支持动态扩容，链表本身支持动态扩容

链表和数组的性能对比：

时间复杂度 数组 链表
插入、删除 $O(N)$ $O(1)$
随机访问 $O(1)$ $O(n)$

栈

栈是一种操作受限的线性表，只允许在一段插入和删除数据，后进者先出，先进者后出。

栈的实现方式：

  • 使用数组实现的栈称之为顺序栈
  • 使用链表实现的栈称之为链式栈

栈的时间复杂度和空间复杂度都是 O(1)。顺序栈 本身是不支持扩容的，但是可以通过将其全部元素拷贝到另一个更大的数组中实现扩容。在扩容的过程中，使用摊还分析可以得出平均的时间复杂度为 O(1)。

栈的应用：

  • 函数调用栈
  • 表达式求值
  • 括号匹配

队列

队列也是一种操作受限的线性表。特点是先进者先出

队列和栈非常相似，只有两个操作，入队（enqueue）和出队（dequeue）两个操作。

队列的实现方式：

  • 使用数组实现的顺序队列
  • 使用链表实现的链式队列

数组实现队列的时候会有数据搬移的问题，如果为了彻底解决这个问题，可以通过实现 循环队列 的方式来解决问题。

队列的应用：

  • 使用数组实现的循环队列
  • 阻塞队列（生产者-消费模型）
  • 并发队列

跳表

通过对链表添加索引，就可以支持“二分”查找

跳表可以支持快速的插入、删除、查找操作，在一些场景下甚至可以替代红黑树。

跳表的实现：

跳表其实就是在有序链表的基础上，每隔 k 个节点提取一个节点到上一级，抽出来的那一层就是索引层。
加了一层索引之后，查找一个节点需要遍历的节点就少了，查找效率也就提高了。而且这个索引可以添加多层。

链表的时间复杂度：

跳表的高度是logmn，每隔 m 节点建立一个索引，n 为节点总数，可以适当增大 m 来减小跳表的时间复杂度。 跳表查询的时间复杂度为 O(logn), 空间复杂度为 O(n)。

跳表索引的更新：

在往跳表中插入数据的过程中，需要更新索引，如果不更新，将会使跳表退化成链表，链表的更新是通过一个随机函数来更新的，比如随机函数生成 k，那么就将数据更新到 1 ~ k 级索引中。

跳表的应用：

  • redis

散列表

散列表也称之为哈希表。

散列表是用数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

散列表的实现

散列表的结构与数组类似，访问元素的时间复杂度也是 O(1)。散列表通过散列函数（哈希函数）将散列表中每个元素的键（关键字）映射成散列值。在查询的过程中，使用相同的散列函数将键转化成散列值并且快速访问到数据。

所以对于一个散列表来说，散列函数（hash(key)）是最为关键的一点，hash就是哈希函数，key是键或者关键字。构建哈希函数有三个要点：

1. 散列函数计算得到的散列是一个非负整数
2. 如果 key1 == key2，那么 hash(key1) == hash(key2)
3. 如果 key1 != key2，那么 hash(key1) != hash(key2)

但是如果实现一个完全满足第三个条件的散列表基本是不可能的。这种情况称之为散列冲突。

散列冲突

解决散列冲突有两种方法：开放寻址法 和 链表法

开放寻址法：
开放寻址法的核心思想是如果出现了散列冲突么，那么我们就找一个新的空闲位置将数据插入。找到新的空闲位置有如下三种方法：

  • 线性探测
  • 二次探测
  • 双重散列

线性探测就是沿着冲突的位置一直往下找，直到找到空闲的位置，查找的时候类似，如果找到空闲位置还灭有找到，说明元素在散列表中不存在。删除的时候要注意将元素标记为已删除标记，否则会影响查找。

线性探测是每次将下标加1，而二次探测则是将下标每次都加当前下标的二次方（hash(key)+ 0, hash(key1) + 1^2， hash(key2) + 2^2）。而双重散列就是使用两个散列函数，第一个散列函数冲突的时候就会使用第二个散列函数。

当链表中空闲位置很少的时候，冲突的概率就会增大不少。空位的多少使用装载因子来表示：

装载因子 = 散列表中元素的个数 / 散列表的长度

装载因子越大，说明空闲位置越少，冲突也就越多，散列表的性能就会下降。

链表法：

链表法就是在每个下标的位置挂上一条链表，所有散列值相同的元素就会存储在这个链表中。查找删除的时间复杂度是 O(k)，其中 k = n/m。n 表示散列表中数据的个数，m 表示散列表中链表的条数。

链表法更灵活，比如可以将链表换成红黑树等数据结构

工业级散列表的设计方法

如果哈希表的散列函数设计的不好或者装载因子过高，都有可能导致发生哈希碰撞的可能，使查询效率降低。

所以设计散列表会考虑一下三个方面：

散列函数的设计:

  • 散列函数的设计不能太复杂
  • 散列函数生成的值要尽可能随机并且分部均匀

装载因子与扩容:

  • 装载因子需要控制在合理的范围内，如果装载因子过大，就需要动态扩容
  • 动态扩容需要视情况而定，不能简单的一次性扩容，可以新建一个散列表，直接插入数据到新的散列表，通过一点点将老散列表的数据迁移过去。

冲突解决方法：

  • 开放寻址法： 数据量小，装载因子小时适合
  • 链表法：比较适合存储大对象，大量数据的散列表

散列表和链表经常在一起使用，这两者组合使用其实就是结合了数组和链表的优势，规避两者的不足。

树

树结构与现实生活中树的结构非常类似。树中的每个元素称之为节点，用连线连接的两个节点，我们称之为父子关系。连接同一个父节点的元素我们称之为兄弟节点，在树中，所有的兄弟节点是不能相互连接的。没有父子节点的元素称之为根节点。没有子节点的元素称之为叶子节点。

树中还有几个关键的概念:

  • 节点的高度：节点到叶子节点的最长路径（边数）
  • 节点的深度：根节点到这个节点所经历的边的个数
  • 节点的层数：节点的深度 + 1
  • 树的高度：根节点的高度

二叉树

树的结构有多种，但是最常用的还是二叉树，二叉树的每个节点最多两个子节点。

满二叉树：

叶子节点都在最底层，除了叶子节点外，每个节点都有左右两个节点，这种树称之为满二叉树

完全二叉树：
叶子节点在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种树称之为完全二叉树

树的存储方式

链式存储法：

节点使用链表节点表示，每个节点都有一个 left 指针和一个 right 指针，大部分二叉树都是这种结构来实现的

顺序存储法：

节点 x 存储的位置为 i，那么左子节点的位置就是 2 * i，右子树的位置就是 2 * i + 1。一般为了计算方便，根节点存储的位置为 1。

通过顺序存储的方式，一颗完全二叉树仅仅浪费一个下标为0的存储位置，如滚是非完全二叉树，就会浪费比较多的存储空间。

一棵完全二叉树，使用数组存储是最省内存的方式。

二叉树的遍历

三种遍历方式的顺序是相对于根节点来说的，首先遍历根节点就叫前序，在中间顺序遍历根节点就叫中序，最后遍历根节点就叫后序。

  • 前序遍历：对树中的任意节点来说，先打印这个节点，再打印它的左子树，然后打印它的右子树
  • 中序遍历：对树中的任意节点来说，先打印它的左子树，然后打印这个节点，最后打印它的右子树
  • 后序遍历：对树中的任意节点来说，先打印它的左子树，然后打印它的右子树，最后打印这个节点

遍历树的时间复杂度为 O(n)。

实际上这三种遍历方式就是一个递归的过程

二叉搜索树

支持动态数据聚合的快速插入、删除和查找操作。

二叉搜索树中的任意一个节点的左子树的值又要小于这个节点的值，右子树的值都要大于这个节点的值。

二叉搜索树中序遍历可以输出一个有序数据的序列，二叉搜索树也称之为二叉排序树。

二叉搜索树的操作性能与树的高度是成正比的，左右子树高度相差不大时，时间复杂度为 O(logn)，如果左右子树的高度相差过大，那么时间复杂度就会退化为 O(n)。

平衡二叉搜索树

平衡二叉树是为了解决普通二叉树在频繁的插入、删除等动态操作中，出现时间复杂度退化的情况，从 $O(logN)$ 退化到 $O(N)$

  • AVL 树
  • R-B tree（红黑树）
  • Splay Tree（伸展树）
  • Treap（树堆）

二叉树的严格定义是：二叉树中任意一个节点的左右子树的高度相差不能大于一（大多数情况下并不会严格遵守）

平衡二叉搜索树中平衡是指左子树和右子树的高度相对来说相差不大，这样整棵树的查找、插入和删除的效率就要高一些。

递归树

递归树用于分析时间复杂度。

堆

堆是一种特殊的树，本质上就是一棵完全二叉树

  • 堆是一棵完全二叉树
  • 堆中的每一个节点的值都必须大于（或小于等于）其子树中每个节点的值

堆的应用：

  • 优先级队列
    • 合并有序小文件
    • 高性能定时器
  • 求海量数据中求 Top K
  • 求中位数问题

堆排序：

堆排序可以分成两个步骤，建堆和排序。

通过建立大顶堆，最大的元素就已经在堆顶了。然后每次都取堆顶的元素。依次取下来就排完序了。

图

图是一种比树更复杂的数据结构。

图的相关概念：

  • 图中的元素称之为顶点，图的顶点可以与其他任意顶点相连
  • 顶点与定点相连的关系称之为边
  • 边有方向的图称之为有向图，没有方向的图称之为无向图，还有一种边带权重的称之为带权图
  • 与顶点相连的边数称之为度，度分为入度和出度

图的存储方式：

  • 邻接矩阵存储
  • 邻接表

图的搜索算法：

  • 广度优先搜索
  • 深度优先搜索

(完)

  1. 极客时间数据结构与算法之美专栏
©2024 Rayjun    PowerBy Hexo