内容简介:本文转载自公众号“读芯术”(ID:AI_Discovery)就当是一场梦,醒了还是很悲痛,还是难以忘记被数据结构折磨的惨痛。当你打开一本数据结构和算法的教科书时,里面总是充满复杂的数学,令人望而生畏。对于那些不太喜欢这门学科的人来说,这就是一场噩梦。然而现实是,想要通过编程面试,必须求解算法,这就离不开数据结构。别害怕,一旦了解了数据结构,就会发现它们其实没有看上去那么难了。
本文转载自公众号“读芯术”(ID:AI_Discovery)
就当是一场梦,醒了还是很悲痛,还是难以忘记被数据结构折磨的惨痛。当你打开一本数据结构和算法的教科书时,里面总是充满复杂的数学,令人望而生畏。对于那些不太喜欢这门学科的人来说,这就是一场噩梦。
然而现实是,想要通过编程面试,必须求解算法,这就离不开数据结构。别害怕,一旦了解了数据结构,就会发现它们其实没有看上去那么难了。
本文将会简化和总结这些最基本的数据结构,帮你搞定数据结构。
什么是数据结构?
数据结构是一种在计算机中组织数据以便高效使用的特殊方式:
“在计算机科学中,数据结构是一种数据组织、管理和存储的格式,其允许高效地访问和修改。更准确地说,数据结构是数据值,数据值之间的关系,以及可应用于数据的函数或操作的集合。”
我们必须将数据存储到某种数据结构中,选择正确的数据结构至关重要。
值得注意的是,数据结构没有好坏之分,每种数据结构都有其优缺点。有很多方法可以用来衡量一种数据结构,这些也被称为大O符号,这是衡量操作可伸缩性的一个指标。
现在来讨论一下不同类型的数据结构。
链表
链表的单位被称为“节点”,一个节点包含一个值和一个指针(Pointer)。值只是一个数字,如12,而指针将该值链接到链中的下一个节点。这就是链表的连接部分,链表中的第一个节点被称为头,最后一个没有指针的节点被称为尾。
- 优点:添加删除节点很方便,只需要更改指针指向的地址即可。
- 缺点:不擅长检索节点,尽管有索引或搜索功能。因为每个节点只知道相邻节点的信息。
散列表(哈希表)
哈希映射或哈希表,也是一种关键的数据结构。它类似于JavaScript中的对象和 Python 中的字典,在这种类型的数据结构中,用户为散列表提供一个单词或者键,它将检索定义或值。
其工作原理很像一个数组,该键通过名为“散列函数(哈希函数)”的函数运行,该函数会找出键对应的内存地址。
不同之处在于,这些位置在内存中不需要相邻,而是可以在任意位置。因此,大小的增加不会存在问题。
但是,存在一个不同问题——根据使用的散列函数,两个键可能会指向同一个内存地址。这就是所谓的“冲突”,有很多种办法可以解决这个问题,但是这一切都隐藏在函数内。
- 优点:正如已提及的,散列函数(哈希函数)非常适合添加和读取。
- 缺点:可能会导致键值冲突。
栈和队列
这两种结构彼此非常相似,都是在数组的基础上构建了一些附加功能。
栈是后进先出的数据结构。这类似于堆叠在一起的托盘,顶部的托盘在放入时是最后一个,在取出时是第一个。
将一个元素添加到栈顶称为入栈,而从栈顶取出一个元素称为出栈。每种语言都通过称为调用堆栈的方式跟踪已调用的函数。栈对于称为深度优先搜索(DFS)的算法非常重要。
另一方面,队列是一种先进先出的结构,就像公共汽车站的排队,最后一个排队的人最后上车。在末尾添加元素的操作称为入队,从队首删除元素称为出队。队列被用于称为广度优先搜索(BFS)的重要算法中。
- 优点:两种结构在添加和删除元素时都非常有效。
- 缺点:与其他的数据结构相比,它们的用例数量有限。
数组
数组在所有的编程语言中都很常见,它是计算机内存中连续的单元块。
下面的示例表示了一个具有12个元素的整数数组。数组的索引从0开始,因此包含12个元素的数组具有从0到11的索引。
- 优点:数组擅于检索项,但前提是数组较小。
- 缺点:随着数组规模不断增大,会占用内存中的其他项来运行。因此,数组的添加操作效率很低,因为可能需要将数组移动到内存中的一个新位置以适应其长度。
幸运的是,这种情况出现在高级语言中,比如JavaScript和Python。若在底层语言中,必须要事先声明数组的大小。
图和树
计算机语言中有一个专门的部分叫做“图论”,图类似于链表有着指向其它节点的节点,只是这些指针被称为“边”,边可以有权重或者被赋予编号。
有一种特殊的层图称为“树”,其中的数据向一个方向拓展。它们可以用于指代很多事物,例如“家谱”,或者用于表示网络。与数组、链表、栈和队列这样的线性数据结构不同,树是分层数据结构。
- 优点:树提供了高效的插入和搜索能力,而且树的数据格式非常灵活,允许以最小的工作量来移动子树。
- 缺点:缺点在于,修改列表和检索的时间长度为O(log n)。
入门算法求解离不开这些数据结构,关键在于不要畏难。搏一搏,噩梦变美梦。祝你早日掌数据结构。
【责任编辑:赵宁宁 TEL:(010)68476606】
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 有了这篇文章, Python 中的编码不再是噩梦
- 开发者噩梦:欧盟希望过滤上传到互联网的所有代码
- AI速配爱情,单身狗的福音还是有情人的噩梦?
- 拯救开发者噩梦的NVIDIA云端神器!2万家企业已经受益
- 数据结构 – 用于构建文件系统的数据结构?
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Practical Algorithms for Programmers
Andrew Binstock、John Rex / Addison-Wesley Professional / 1995-06-29 / USD 39.99
Most algorithm books today are either academic textbooks or rehashes of the same tired set of algorithms. Practical Algorithms for Programmers is the first book to give complete code implementations o......一起来看看 《Practical Algorithms for Programmers》 这本书的介绍吧!