面试常见基础数据结构

原文链接:https://segmentfault.com/a/1190000018019127

常用的数据结构

我们首先列出最常用的数据结构,然后再挨个讲解:

  • 数组(Array)
  • 栈(Heap, Stack)
  • 队列(Queue)
  • 链表(Linked List)
  • 树(Tree)
  • 图(Graph)
  • 字典树(Dictoinary Tree)
  • 哈希表(Hash Table)

数组

数组是一种最简单和最广泛使用的数据结构,其它数据结构比如栈和队列都源自数组。

下图是一个大小为 4 的简单数组,包含几个元素( 1 , 2 , 3,4)。

每个数据元素会被分配一个正的数值,叫作“索引”,它对应该元素在数组中的位置。大部分编程语言都将初始索引定义为 0.

以下是两种数组:

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

数组的基本操作:

  • Insert——在给定索引位置插入一个元素
  • Get——返回给定索引位置的元素
  • Delete——删除给定索引位置的元素
  • Size——获取数组内所有元素的总数

常问的数组面试问题:

  • 找到数组中第二小的元素
  • 找到数组中第一个没有重复的整数
  • 合并两个分类数组
  • 重新排列数组中的正值和负值

我们都熟悉很有名的撤销(Undo)选项,它几乎存在每个应用程序中。有没有想过它是如何工作的?其思路就是,按照最后的状态排列在先的顺序将工作的先前状态(限于特定数字)存储在内存中。这只用数组是无法实现的,因此栈就有了用武之地。

可以把栈看作一堆垂直排列的书籍。为了获得位于中间位置的书,你需要拿掉放在它上面的所有书籍。这就是 LIFO(后进先出)方法的工作原理。

这是一个包含三个数据元素(1,2 和 3)的栈图像,其中3位于顶部,首先把它删除:

栈的基本操作:

  • Push——在顶部插入元素
  • Pop—— 从栈中删除后返回顶部元素
  • isEmpty——如果栈为空,则返回 true
  • Top ——返回顶部元素,但不从栈中删除

常见的栈面试问题:

  • 使用栈计算后缀表达式
  • 对栈中的值进行排序
  • 检查表达式中的括号是否平衡

队列

与栈类似,队列是另一种线性数据结构,以顺序方式存储元素。栈和队列之间唯一的显着区别是,队列不是使用 LIFO 方法,而是应用 FIFO 方法,这是 First in First Out(先入先出)的缩写。

队列的完美现实例子:一列人在售票亭等候。如果有新人来,他们是从末尾加入队列,而不是在开头——站在前面的人将先买到票然后离开队列。

下图是一个包含四个数据元素(1,2,3 和 4)的队列,其中 1 位于顶部,首先把它删除:

队列的基本操作:

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

常问的队列面试问题:

  • 使用队列来实现栈
  • 颠倒队列中前 k 个元素的顺序
  • 使用队列生成从 1 到 n 的二进制数

链表

链表是另一个重要的线性数据结构,刚一看可能看起来像数组,但在内存分配,内部结构以及如何执行插入和删除的基本操作方面有所不同。

链表就像一个节点链,其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针,指向链表的第一个元素,如果列表是空的,那么它只指向 null 或不指向任何内容。

链表用于实现文件系统,哈希表和邻接表。下图是链表内部结构的直观展示:

下面是几种类型的链表:

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

链表的基本操作:

  • InsertAtEnd —— 在链表末尾插入指定元素
  • InsertAtHead —— 在链表头部插入指定元素
  • Delete —— 从链表中删除指定元素
  • DeleteAtHead —— 删除链表的第一个元素
  • Search —— 返回链表中的指定元素
  • isEmpty —— 如果链表为空,返回 true

常问的链表面试问题:

  • 翻转列表
  • 检测链表中的循环
  • 返回链表中倒数第 n 个节点
  • 移除链表中的重复值

图就是一组节点,以网络的形式互相连接。节点也被称为顶点(vertices)。一对(x,y)就叫做一个边,表示顶点 x 和顶点 y 相连。一个边可能包含权重/成本,显示从顶点 x 到 y 所需的成本。

图的类型:

  • 无向图
  • 有向图

在编程语言中,图可以表示为两种形式:

  • 邻接矩阵
  • 邻接列表

常见的图遍历算法:

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

常问的图面试问题:

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

树是一种层级数据结构,包含了连接它们的顶点(节点)和边。树和图很相似,但二者有个很大的不同点,即树中没有循环。

树广泛应用在人工智能和复杂的算法中,为解决各种问题提供高效的存储机制。

下图是一个简单的树,以及在树型数据结构中所用的基本术语:

下面是几种类型的树:

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

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

常问的树面试问题:

  • 找到一个二叉树的高度
  • 找到一个二叉搜索树中第 k 个最大值
  • 找到距离根部“k”个距离的节点
  • 找到一个二叉树中给定节点的祖先(ancestors)

字典树

字典树,也叫“前缀树”,是一种树形结构,在解决字符串相关问题中非常高效。其提供非常快速的检索功能,常用于搜索字典中的单词,为搜索引擎提供自动搜索建议,甚至能用于IP路由选择。
下面展示了“top”“thus”和“their”这三个词是如何存储在字典树中的:

这些单词以从上到下的方式存储,其中绿色节点“p”,“s”和“r”分别表示“top”,“thus”和“their”的末尾。

常见的字典树面试问题:

  • 计算字典树中的总字数
  • 打印存储在字典树中的所有单词
  • 使用字典树对数组的元素进行排序
  • 使用字典树从字典中形成单词
  • 构建一个T9字典

哈希表

散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构,但最常用的数据结构是哈希表。

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

哈希数据结构的性能取决于以下三个因素:

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

下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。

常问的哈希面试问题:

  • 找到数组中的对称对
  • 追踪遍历的完整路径
  • 查看一个数组是否为另一个数组的子集
  • 检查给定数组是否不相交
  • 以上就是你在准备编程面试前需要掌握的8种数据结构。