你必须知道的八大数据结构

前言

瑞士计算机科学家Niklaus Wirth在1976年写了一本书，名为《算法+数据结构=编程》。

40多年后，这个等式仍被奉为真理。这就是为什么在面试过程中，需要考察软件工程师对数据结构的理解。

几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵（刚从大学或者编程培训班毕业），还是拥有几十年经验的职场老鸟。

有些面试题会明确提及某种数据结构，例如，“给定一个二叉树。”而另一些则隐含在面试题中，例如，“我们希望记录每个作者相关的书籍数量。”

即便是对于一些非常基础的工作来说，学习数据结构也是必须的。那么，就让我们先从一些基本概念开始入手。

什么是数据结构？

数据结构：计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。

为什么我们需要数据结构？

数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。

无论你以何种方式解决何种问题，你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单，还是只是简单的电话簿问题。

数据需要根据不同的场景，按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

常见的数据结构

首先列出一些最常见的数据结构，我们将逐一说明：

• 数组
• 栈
• 队列
• 链表
• 树
• 图
• 字典树（这是一种高效的树形结构，但值得单独说明）
• 散列表（哈希表）

数组

所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。

数组是用于储存多个相同类型数据的集合。

数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素(1，2，3和4)的简单数组，数组长度为4。

image.png

每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。

以下是数组的两种类型：

• 一维数组(如上所示)
• 多维数组(数组的数组)

(1) 数组的基本操作

Insert——在指定索引位置插入一个元素
Get——返回指定索引位置的元素
Delete——删除指定索引位置的元素
Size——得到数组所有元素的数量

(2) 面试中关于数组的常见问题

• 寻找数组中第二小的元素
• 找到数组中第一个不重复出现的整数
• 合并两个有序数组
• 重新排列数组中的正值和负值

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底.

可以把栈想象成一列垂直堆放的书。为了拿到中间的书，你需要移除放置在这上面的所有书。这就是LIFO(后进先出)的工作原理。

下图是包含三个数据元素(1，2和3)的栈，其中顶部的3将被最先移除：

image.png

(1) 栈的基本操作

• Push——在顶部插入一个元素
• Pop——返回并移除栈顶元素
• isEmpty——如果栈为空，则返回true
• Top——返回顶部元素，但并不移除它

(2) 面试中关于栈的常见问题

• 使用栈计算后缀表达式
• 对栈的元素进行排序
• 判断表达式是否括号平衡

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

栈与队列的最大差别在于栈是LIFO(后进先出)，而队列是FIFO，即先进先出。

一个完美的队列现实例子：售票亭排队队伍。如果有新人加入，他需要到队尾去排队，而非队首——排在前面的人会先拿到票，然后离开队伍。

下图是包含四个元素(1，2，3和4)的队列，其中在顶部的1将被最先移除：

image.png

移除先入队的元素、插入新元素

(1) 队列的基本操作

• Enqueue() —— 在队列尾部插入元素
• Dequeue() ——移除队列头部的元素
• isEmpty()——如果队列为空，则返回true
• Top() ——返回队列的第一个元素

(2) 面试中关于队列的常见问题

• 使用队列表示栈
• 对队列的前k个元素倒序
• 使用队列生成从1到n的二进制数

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

这是链表内部结构的展示：

image.png

(1) 链表包括以下类型：

• 单链表(单向)
• 双向链表(双向)

(2) 链表的基本操作：

• InsertAtEnd - 在链表的末尾插入指定元素
• InsertAtHead - 在链接列表的开头/头部插入指定元素
• Delete  - 从链接列表中删除指定元素
• DeleteAtHead - 删除链接列表的第一个元素
• Search  - 从链表中返回指定元素
• isEmpty - 如果链表为空，则返回true

图

图是一组以网络形式相互连接的节点。节点也称为顶点(Vertex)。 一对节点(x，y)称为边(edge)，表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y所需的成本。

图是由顶点集合(Vertex)及顶点间的关系集合组成的一种数据结构：Graph＝( V, E )
V = {x | x ∈某个数据对象 } 是顶点的有穷非空集合；
E ={ (x, y) | x, y ∈V } 是顶点之间关系的有穷集合，也叫做边(Edge)集合。

image.png

(1) 图的类型

• 无向图
• 有向图

(2) 在程序语言中，图可以用两种形式表示：

• 邻接矩阵
• 邻接表

(3) 常见图遍历算法

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

(4) 面试中关于图的常见问题

• 实现广度和深度优先搜索
• 检查图是否为树
• 计算图的边数
• 找到两个顶点之间的最短路径

树

树形结构是一种层级式的数据结构，由顶点(节点)和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。

树形结构被广泛应用于人工智能和复杂算法，它可以提供解决问题的有效存储机制。

这是一个简单树的示意图，以及树数据结构中使用的基本术语：

image.png

• Root - 根节点
• Parent - 父节点
• Child - 子节点
• Leaf - 叶子节点
• Sibling - 兄弟节点

(1) 以下是树形结构的主要类型：

• N元树
• 平衡树
• 二叉树
• 二叉搜索树
• AVL树
• 红黑树
• 2-3树

其中，二叉树和二叉搜索树是最常用的树

(2) 面试中关于树结构的常见问题：

• 求二叉树的高度
• 在二叉搜索树中查找第k个最大值
• 查找与根节点距离k的节点
• 在二叉树中查找给定节点的祖先节点

字典树(Trie)

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

以下是在字典树中存储三个单词“top”，“thus”和“their”的例子：

image.png

这些单词以顶部到底部的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“theirs”的底部。

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

哈希表通常使用数组实现。

散列数据结构的性能取决于以下三个因素：

• 哈希函数
• 哈希表的大小
• 碰撞处理方法

以上是在编程面试之前你应该知晓的八大数据结构。