内容简介:本文转载自公众号“读芯术”(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解决数据结构与算法问题(三):线性数据结构之栈
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Android 源码设计模式解析与实战
何红辉、关爱民 / 人民邮电出版社 / 2015-11 / 79.00元
本书专门介绍Android源代码的设计模式,共26章,主要讲解面向对象的六大原则、主流的设计模式以及MVC和MVP模式。主要内容为:优化代码的首步、开闭原则、里氏替换原则、依赖倒置原则、接口隔离原则、迪米特原则、单例模式、Builder模式、原型模式、工厂方法模式、抽象工厂模式、策略模式、状态模式、责任链模式、解释器模式、命令模式、观察者模式、备忘录模式、迭代器模式、模板方法模式、访问者模式、中介......一起来看看 《Android 源码设计模式解析与实战》 这本书的介绍吧!