集团主站
欢迎来到成都达内官方网站!达内—美国上市公司 亿元级外企IT培训企业!
成都it培训哪家好
成都it培训哪家好
全国服务监督电话:15023458194  |   联系客服   |
当前位置:主页 > 培训课程 > 大数据 >

成都大数据学习:你必须知道的八大数据结构

发布者: 成都大数据工程师     浏览次数:     发布时间:2018-09-26 16:52:18

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

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


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

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


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

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


什么是数据结构?

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


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


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

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


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


常见的数据结构

成都大数据工程师
首先列出一些最常见的数据结构,我们将逐一说明:


数组





队列


链表








字典树(这是一种高效的树形结构,但值得单独说明)


散列表(哈希表)


数组

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


应对程序员面试,你必须知道的八大数据结构


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


以下是数组的两种类型:


一维数组(如上所示)


多维数组(数组的数组)


数组的基本操作


Insert——在指定索引位置插入一个元素


Get——返回指定索引位置的元素


Delete——删除指定索引位置的元素


Size——得到数组所有元素的数量


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


寻找数组中第二小的元素


找到数组中第一个不重复出现的整数


合并两个有序数组


重新排列数组中的正值和负值





著名的撤销操作几乎遍布任意一个应用。但你有没有思考过它是如何工作的呢?这个问题的解决思路是按照将最后的状态排列在先的顺序,在内存中存储历史工作状态(当然,它会受限于一定的数量)。这没办法用数组实现。但有了栈,这就变得非常方便了。


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


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


应对程序员面试,你必须知道的八大数据结构


栈的基本操作


Push——在顶部插入一个元素


Pop——返回并移除栈顶元素


isEmpty——如果栈为空,则返回true


Top——返回顶部元素,但并不移除它


面试中关于栈的常见问题


使用栈计算后缀表达式


对栈的元素进行排序


判断表达式是否括号平衡


队列


与栈相似,队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO(后进先出),而队列是FIFO,即先进先出。


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


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


应对程序员面试,你必须知道的八大数据结构


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


队列的基本操作


Enqueue()?——?在队列尾部插入元素


Dequeue()?——移除队列头部的元素


isEmpty()——如果队列为空,则返回true


Top()?——返回队列的第一个元素


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


使用队列表示栈


对队列的前k个元素倒序


使用队列生成从1到n的二进制数


链表


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


链表就像一个节点链,其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针,它指向链表的第一个元素,但当列表为空时,它指向null或无具体内容。


链表一般用于实现文件系统、哈希表和邻接表。


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


应对程序员面试,你必须知道的八大数据结构


链表包括以下类型:


单链表(单向)


双向链表(双向)


链表的基本操作:


InsertAtEnd - 在链表的末尾插入指定元素


InsertAtHead - 在链接列表的开头/头部插入指定元素


Delete? - 从链接列表中删除指定元素


DeleteAtHead - 删除链接列表的第一个元素


Search? - 从链表中返回指定元素


isEmpty - 如果链表为空,则返回true


面试中关于链表的常见问题


反转链表


检测链表中的循环


返回链表倒数第N个节点


删除链表中的重复项





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


应对程序员面试,你必须知道的八大数据结构


图的类型


无向图


有向图


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


邻接矩阵


邻接表


常见图遍历算法


广度优先搜索


深度优先搜索


面试中关于图的常见问题


实现广度和深度优先搜索


检查图是否为树


计算图的边数


找到两个顶点之间的最短路径





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


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


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


应对程序员面试,你必须知道的八大数据结构


Root - 根节点


Parent - 父节点


Child - 子节点


Leaf - 叶子节点


Sibling - 兄弟节点


以下是树形结构的主要类型:


N元树


平衡树


二叉树


二叉搜索树


AVL树


红黑树


2-3树


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


面试中关于树结构的常见问题:


求二叉树的高度


在二叉搜索树中查找第k个最大值


查找与根节点距离k的节点


在二叉树中查找给定节点的祖先节点


字典树(Trie)


字典树,也称为“前缀树”,是一种特殊的树状数据结构,对于解决字符串相关问题非常有效。它能够提供快速检索,主要用于搜索字典中的单词,在搜索引擎中自动提供建议,甚至被用于IP的路由。


以下是在字典树中存储三个单词“top”,“so”和“their”的例子:


应对程序员面试,你必须知道的八大数据结构


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


面试中关于字典树的常见问题


计算字典树中的总单词数


打印存储在字典树中的所有单词


使用字典树对数组的元素进行排序


使用字典树从字典中形成单词


构建T9字典(字典树+ DFS )


哈希表


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


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


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


哈希函数


哈希表的大小


碰撞处理方法


下图为如何在数组中映射哈希键值对的说明。该数组的索引是通过哈希函数计算的。


应对程序员面试,你必须知道的八大数据结构


面试中关于哈希结构的常见问题:


在数组中查找对称键值对


追踪遍历的完整路径


查找数组是否是另一个数组的子集


检查给定的数组是否不相交


以上是在编程面试之前你应该知晓的八大数据结构。
(责任编辑:陈老师)
最新开班
  • 成都Java培训班
    免费试听名额发放中...
  • 成都C++培训班
    免费试听名额发放中...
  • 成都PHP培训班
    免费试听名额发放中...
  • 成都网络工程培训班
    免费试听名额发放中...
  • 成都Unity3D培训班
    免费试听名额发放中...
  • 成都大数据培训班
    免费试听名额发放中...
  • 成都uid培训班
    免费试听名额发放中...
  • 成都会计培训班
    免费试听名额发放中...
  • 成都Python培训班
    免费试听名额发放中...
  • 成都嵌入式培训班
    免费试听名额发放中...
  • 成都web培训班
    免费试听名额发放中...
  • 成都软件测试培训班
    免费试听名额发放中...
在线留言
提交

校区地址:绵阳市涪城区临园路东段68号富临大都会7栋3单元9层12号

联系电话:15023458194

公交路线:富乐路口凯德广场(10路;29路;3路;15路;11路;15a路;71路)

校区地址:成都市锦江区东大街紫东楼段35号明宇金融广场19楼1903室

联系电话:15023458194

公交路线:芷泉街(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:东门大桥站(地铁2号线)

校区地址:成都市高新区奥克斯广场蜀锦路209号一楼商铺

联系电话:15023458194

公交路线:益州大道锦城大道口(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:孵化园(地铁1号线)

校区地址:成都锦江区东大街芷泉街229号东方广场C座3楼303

联系电话:15023458194

公交路线:芷泉街(188路;115路;515路;236路;505路;501路;84路 ) 地铁路线:东门大桥站(地铁2号线)

校区地址:成都市武侯区佳灵路3号红牌楼广场2号写字楼11楼1115号

联系电话:15023458194

公交路线:红牌楼东(11路;92路;100路;111路;139路;g28路;快速公交K1/K2) 地铁路线:红牌楼站(地铁3号线)

校区地址:成都市锦江区红星路二段70号四川日报大厦502-2

联系电话:15023458194

公交路线:市二医院站(6路;49路;102路;5路;37路;g92路;) 地铁路线:地铁市二医院(地铁3号线)

校区地址:成都市锦江区东大街紫东段35号明宇广场2306

联系电话:15023458194

公交路线:芷泉街(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:东门大桥站(地铁2号线)

校区地址:四川省成都市武侯区高新科技孵化园9号园区E座7楼

联系电话:15023458194

公交路线:益州大道锦城大道口(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:孵化园(地铁1号线)

校区地址:成都市成华区建设路10号万科钻石广场B座5楼

联系电话:15023458194

公交路线:建设路中(6路;14路;42路;72路;76路;1010路;)

校区地址:成都市高新区奥克斯广场B座1708

联系电话:15023458194

公交路线:益州大道锦城大道口(18路;21路;43路;48路;104路;152路;335路 ) 地铁路线:孵化园(地铁1号线)

了解达内动态
关注成都达内教育公众号

首页 | 关于达内 | 课程中心 | 专家师资 | 视频教程 | 学员空间 | 校企合作 | 新闻资讯 | 就业指导 | 网站地图

2016-2025 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56