关于编程面试应了解的最重要的数据结构

瑞士计算机科学家尼克劳斯·沃思（Nicklaus Wirth）于1976年写了一本书，名为《 算法+数据结构=程序》 。

40多年后，此身份仍然有效。 这就是为什么想要成为程序员的求职者必须证明他们了解数据结构并能够应用它们。

在几乎所有任务中，候选人都需要对数据结构有深刻的理解。 同时，无论您是应届毕业生（大学毕业还是编程课程），还是拥有数十年的工作经验，都不是那么重要。

有时在面试问题中直接提到一个或另一个数据结构，例如“给定二叉树”。 在其他情况下，该任务的制定方式则更为笼统，例如，“您需要跟踪每位作者拥有多少本书”。

学习数据结构是一项必不可少的工作，即使您只是想在当前工作中进行专业改进。 让我们从基础开始。

翻译成Alconost

什么是数据结构？

简而言之，数据结构是一个容器，其中信息以特定方式排列。 由于这种“布局”，数据结构将在某些操作中有效，而在另一些操作中效率低下。 我们的目标是了解数据结构，以便您可以从中选择最适合解决您所面临的特定问题的数据结构。

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

由于数据结构用于有序存储信息，并且数据是计算机科学中最重要的现象，因此数据结构的真正价值显而易见。

无论要执行哪种任务，处理数据的方式都无关紧要，无论是员工的薪水，股票报价，到商店的产品清单还是常规的电话簿。

根据具体情况，数据必须以适当的格式存储。 我们拥有许多可以为我们提供各种格式的数据结构。

通用数据结构

首先，让我们列出最常见的数据结构，然后依次解析每个结构：

1. 数组
2. 堆栈
3. Queue列
4. 链表
5. 树木
6. 计数
7. Burs（本质上，它们也是树，但应分开考虑）。
8. 哈希表

数组

数组是最简单，最常见的数据结构。 其他数据结构（例如堆栈和队列）是从数组派生的。

此处显示的是大小为4的简单数组，其中包含元素（1、2、3和4）。

每个数据项都被分配一个称为索引的正数值，并且与该项在数组中的位置相对应。 在大多数编程语言中，数组中的元素从0开始编号。

有两种类型的数组：

• 一维（如上图所示）
• 多维（嵌入了其他数组的数组）

最简单的数组操作

• 插入-在具有给定索引的位置插入元素
• Get-返回具有给定索引位置的元素
• 删除-删除具有指定索引的项目
• 大小-获取数组中元素的总数

面试常见问题

• 找到第二个最小数组元素
• 在数组中查找非重复整数
• 合并两个排序的数组
• 重新排列数组中的正值和负值

堆栈

每个人都知道著名的“取消”选项，几乎所有应用程序都提供该选项。 有没有想过它是如何工作的？ 含义是这样的：工作的先前状态保存在程序中（保存状态的数量是有限的），并且它们按此顺序位于内存中：最后保存的元素排在最前面。 单靠数组不能解决这个问题。 这是堆栈派上用场的地方。

可以将一stack书与一大堆书进行比较。 如果您需要一本书位于书架中央附近，则必须首先移除上面的所有书。 这就是LIFO原理的工作方式（后进先出）。

它看起来像一个包含三个数据元素（1、2和3）的堆栈，其中3在最上面-因此将首先删除它：

最简单的堆栈操作：

• 推送-将项目推送到顶部的堆栈上
• 弹出-从堆栈中删除顶部项目后返回
• isEmpty-如果堆栈为空，则返回true
• 顶部-返回顶部项目而不将其从堆栈中移除

采访有关堆栈的常见问题

• 使用堆栈计算后缀表达式
• 在堆栈上对值排序
• 检查表达式中的平衡括号

Queue列

队列（如堆栈）是一种线性数据结构，其中的元素按顺序存储。 堆栈和队列之间的唯一显着区别是，在队列中，采用了FIFO原理（先来先得）代替了LIFO。

排队的理想现实示例-这是售票处的顾客排队。 一个新的买家在这条线的尽头，而不是一开始。 第一个排队的人将是第一个购买车票并离开的人。

这是具有四个数据元素（1、2、3和4）的队列的图像，其中1排在最前面，然后离开队列：

简单的队列操作

• 入队（）-将项目添加到队列的末尾
• 出队（）-从队列的前面删除项目
• isEmpty（）-如果队列为空，则返回true
• Top（）-返回队列中的第一项

面试常见问题

• 使用队列实现堆栈
• 支付队列中的前k个项目
• 使用队列生成从1到n的二进制数

链表

链表是另一个重要的线性数据结构，乍一看类似于数组。 但是，链表在内存分配，内部结构以及在其中执行基本插入和删除操作的方式方面与数组不同。

链表类似于一个节点链，每个节点都包含信息：例如，数据和指向链中下一个节点的指针。 在链接列表中有一个与第一个元素相对应的头指针，如果列表为空，则将其直接指向null（无）。

使用链接列表，可以实现文件系统，哈希表和邻接列表。

这是使链接列表的内部结构可视化的方式：


链接列表有几种类型：

• 单链接列表（单向）
• 双链表（双向）

链接列表最简单的操作是：

• InsertAtEnd-将指定的项目插入到链表的末尾。
• InsertAtHead-在链接列表的开头（从头开始）插入指定的元素
• 删除 -从链接列表中删除指定的项目。
• DeleteAtHead-删除链接列表中的第一项。
• 搜索 -从链接列表中返回指定的项目。
• isEmpty-如果链接列表为空，则返回true

面试常见问题：

• 支付链表
• 在链接列表中找到循环
• 从链接列表的顶部返回第N个节点
• 从链接列表中删除重复的值

计数

图是一组以网络形式相互连接的节点。 节点也称为顶点。 对 （x，y）称为边，这意味着顶点x连接到顶点y 。 边缘可以具有重量/成本-表示从顶点x到顶点y过渡的成本的指标。


图形类型：

• 无向图
• 定向图

在编程语言中，图可以分为两种类型：

• 邻接矩阵
• 邻接表

常见的图遍历算法：

• 广泛搜索
• 深度搜寻

面试常见问题：

• 进行广度和深度搜索
• 检查图是否为树
• 计算图中的边数
• 查找两个峰之间的最短路径

树木

树是由顶点（节点）和连接它们的边组成的分层数据结构。 树类似于图，但是树和图之间的主要区别在于：树中没有循环。

树木广泛用于人工智能领域和复杂算法中，可作为解决问题的有效信息存储库。

这是与此数据结构相关的简单树形图和基本术语：


存在以下类型的树：

• N树
• 平衡树
• 二叉树
• 二叉搜索树
• AVL树
• 红乌木
• 2-3棵

在以上树中，最常使用二叉树和二叉搜索树。

有关树木的常见采访问题：

查找二叉树的高度
在二分搜索树中找到第k个最大值
查找从根到“ k”的节点
在二叉树中找到给定节点的祖先

硼

硼，也称为“前缀树”，是一种树状数据结构，在解决字符串问题时特别有效。 它提供了快速的数据检索，最常用于在字典中搜索单词，在搜索引擎中自动完成，甚至用于IP路由。

这是林中存储“ top”（顶部）（top），“ thus”（因此）和“ their”（它们）这三个词的方式：


单词从上到下排列，绿色节点“ p”，“ s”和“ r”分别完成单词“ top”，“ thus”和“ their”。

有关Burs的常见访谈问题：

• 计算存储在松林中的单词总数
  
• 显示存储在林中的所有单词。
  
• 使用硼对数组元素进行排序
  
• 用硼建立词汇
  
• 创建T9字典
  

哈希表

散列是用于唯一标识对象并通过称为“键”的预先计算的索引存储每个对象的过程。 因此，将对象存储为键值，并将此类对象的集合称为字典。 每个对象都可以通过其关键字进行搜索。 有多种基于哈希原理的数据结构，但是最常见的是从此类结构中使用哈希表 。

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

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

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

下面显示了哈希如何映射到数组。 使用哈希函数计算该数组的索引。

面试常见哈希问题：

• 在数组中查找对称对
• 追踪完整路径
• 查找一个数组是否是另一个数组的子集
• 检查数组是否不相交

上面介绍了在进行编程面试之前您肯定需要了解的八个最重要的数据结构。

祝你好运，有趣的学习！ :)

关于翻译

这篇文章由Alconost翻译。

Alconost以68种语言本地化游戏 ， 应用程序和网站 。 母语翻译，语言测试，带有API的云平台，持续本地化，24/7项目经理，任何格式的字符串资源。

我们还制作广告和培训视频 -适用于销售，图像，广告，培训，预告片，专家，Google Play和App Store的预告片的网站。

更多细节