可思数据-人工智能媒体资讯平台！
应对程序员面试，你必须知道的八大数据结构
|
|
瑞士计算机科学家Niklaus Wirth在1976年写了一本书，名为《算法+=编程》。 40多年后，这个等式仍被奉为真理。这就是为什么在面试过程中，需要考察软件工程师对的理解。 几乎所有的问题都需要面试者对有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业)，还是拥有几十年经验的职场老鸟。 有些面试题会明确提及某种数据结构，例如，“给定一个二叉树。”而另一些则隐含在面试题中，例如，“我们希望记录每个作者相关的书籍数量。” 即便是对于一些非常基础的工作来说，学习数据结构也是必须的。那么，就让我们先从一些基本概念开始入手。 什么是数据结构? 简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。 为什么我们需要数据结构? 数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。 无论你以何种方式解决何种问题，你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单，还是只是简单的电话簿问题。 数据需要根据不同的场景，按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。 常见的数据结构 首先列出一些最常见的数据结构，我们将逐一说明：
• 数组 数组 数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素(1，2，3和4)的简单数组，数组长度为4。
每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。 以下是数组的两种类型：
• 一维数组(如上所示) 数组的基本操作
• Insert——在指定索引位置插入一个元素 面试中关于数组的常见问题
• 寻找数组中第二小的元素 栈 著名的撤销操作几乎遍布任意一个应用。但你有没有思考过它是如何工作的呢?这个问题的解决思路是按照将最后的状态排列在先的顺序，在内存中存储历史工作状态(当然，它会受限于一定的数量)。这没办法用数组实现。但有了栈，这就变得非常方便了。 可以把栈想象成一列垂直堆放的书。为了拿到中间的书，你需要移除放置在这上面的所有书。这就是LIFO(后进先出)的工作原理。 下图是包含三个数据元素(1，2和3)的栈，其中顶部的3将被最先移除：
栈的基本操作
• Push——在顶部插入一个元素 面试中关于栈的常见问题
• 使用栈计算后缀表达式 队列 与栈相似，队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO(后进先出)，而队列是FIFO，即先进先出。 一个完美的队列现实例子：售票亭排队队伍。如果有新人加入，他需要到队尾去排队，而非队首——排在前面的人会先拿到票，然后离开队伍。 下图是包含四个元素(1，2，3和4)的队列，其中在顶部的1将被最先移除：
移除先入队的元素、插入新元素 队列的基本操作
• Enqueue() —— 在队列尾部插入元素 面试中关于队列的常见问题
• 使用队列表示栈 链表 链表是另一个重要的线性数据结构，乍一看可能有点像数组，但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。 链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。 链表一般用于实现文件系统、哈希表和邻接表。 这是链表内部结构的展示： 
链表包括以下类型：
• 单链表(单向) 链表的基本操作：
• InsertAtEnd - 在链表的末尾插入指定元素 面试中关于链表的常见问题
• 反转链表 图 图是一组以网络形式相互连接的节点。节点也称为顶点。 一对节点(x，y)称为边(edge)，表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y所需的成本。
图的类型
• 无向图 在程序语言中，图可以用两种形式表示：
• 邻接矩阵 常见图遍历算法
• 广度优先搜索 面试中关于图的常见问题
• 实现广度和深度优先搜索 树 树形结构是一种层级式的数据结构，由顶点(节点)和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。 树形结构被广泛应用于人工智能和复杂算法，它可以提供解决问题的有效存储机制。 这是一个简单树的示意图，以及树数据结构中使用的基本术语：
• Root - 根节点 以下是树形结构的主要类型：
• N元树 其中，二叉树和二叉搜索树是最常用的树。 面试中关于树结构的常见问题：
• 求二叉树的高度 字典树(Trie) 字典树，也称为“前缀树”，是一种特殊的树状数据结构，对于解决字符串相关问题非常有效。它能够提供快速检索，主要用于搜索字典中的单词，在搜索引擎中自动提供建议，甚至被用于IP的路由。 以下是在字典树中存储三个单词“top”，“so”和“their”的例子：
这些单词以顶部到底部的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“theirs”的底部。 面试中关于字典树的常见问题
• 计算字典树中的总单词数 哈希表 哈希法(Hashing)是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引(称为“键(key)”)中的过程。因此，对象以键值对的形式存储，这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构，但最常用的数据结构是哈希表。 哈希表通常使用数组实现。 散列数据结构的性能取决于以下三个因素：
• 哈希函数 下图为如何在数组中映射哈希键值对的说明。该数组的索引是通过哈希函数计算的。
面试中关于哈希结构的常见问题：
• 在数组中查找对称键值对 以上是在编程面试之前你应该知晓的八大数据结构。 |
时间:2018-08-20 23:22 来源: 转发量:次
声明：本站部分作品是由网友自主投稿和发布、编辑整理上传，对此类作品本站仅提供交流平台，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，不为其版权负责。如果您发现网站上有侵犯您的知识产权的作品，请与我们取得联系，我们会及时修改或删除。
