当前位置:首页 > 市场动态 > 正文内容

每个程序员必知!必须掌握的8种数据结构

每个程序员必知!必须掌握的8种数据结构

每个程序员必知!必须掌握的8种数据结构 第1张

数据结构是一种特定的计算机组织与存储数据的技术,它使得我们能够更高效地对数据进行操作。这种技术在计算机科学与软件工程领域中应用广泛,且种类繁多。

众多已开发的程序与软件系统普遍采用了数据结构这一概念。同时,数据结构构成了计算机科学与软件工程领域的基础理论。在软件工程面试中,这一议题往往占据核心位置。鉴于此,对于开发者而言,对数据结构的深入理解至关重要。

本文将对我将简要阐述的八个程序员必备的常用数据结构进行概述。

1. 数组()

数组是一种具有固定规模的集合,能够存放具有相同数据类型的多个元素。它包括整数数组、浮点数数组、字符串数组,甚至可以包含数组自身的数组,如二维数组。数组具有索引功能,这使得我们能够实现对其元素的随机访问。

每个程序员必知!必须掌握的8种数据结构 第2张

数组运算

数组容量固定,故无法直接向其添加或移除元素。若需向数组中添加元素基本数据结构,需先构建一个比原数组多一个位置的全新数组,接着将原数组中的所有元素复制至新数组,并将新增元素加入其中。删除元素时,亦需采取类似步骤,创建一个容量减少的新数组,并将原数组中除被删除元素外的所有元素复制至新数组。

数组的应用

2. 链表( Lists)

链表是一种基于线性顺序的排列结构,它由若干个项目按照顺序相互连接而成。这就意味着在处理数据时,我们必须遵循一定的顺序进行访问,而无法像在数组中那样进行随机的读取。链接列表则能够以简洁和灵活的方式,实现对动态集合的有效表示。

让我们考虑以下有关链表的术语。

每个程序员必知!必须掌握的8种数据结构 第3张

以下是可用的各种类型的链接列表。

链表操作

链表的应用

3. 堆栈()

堆栈是一种遵循LIFO原则(即后进先出,最后放入的元素最先被访问)的数据结构,这种结构在众多编程语言中普遍存在。之所以被称为“堆栈”,是因为其运作原理与现实生活中的堆叠盘子极为相似。

每个程序员必知!必须掌握的8种数据结构 第4张

堆栈操作

下面给出了可以在堆栈上执行的 2 个基本操作。

每个程序员必知!必须掌握的8种数据结构 第5张

此外基本数据结构,还为堆栈提供了以下附加函数以检查其状态。

栈的应用

4. 队列()

每个程序员必知!必须掌握的8种数据结构 第6张

队列是一种遵循FIFO(即先进先出,即最先放置的元素将最先被访问)原则的结构,这种结构在众多编程语言中均有广泛应用。之所以将其称为“队列”,是因为其运作方式与现实生活中的排队场景颇为相似——人们通常会在队列中依次等待。

每个程序员必知!必须掌握的8种数据结构 第7张

队列操作

下面给出了可以在队列上执行的 2 个基本操作。

每个程序员必知!必须掌握的8种数据结构 第8张

队列的应用

5. 哈希表(Hash )

哈希表是一种专门用于存储带有相应键值的数据结构,每个存储的值都与其对应的键紧密相连。除此之外,只要我们掌握了与值对应的键,就能高效地实现数据的查找。因此,不论数据量的大小,无论是插入还是搜索,都能展现出极高的效率。

直接寻址法在存储时,通过值与键的对应关系进行记录。然而,当键值对数量庞大时,这种方法的弊端显现。表的大小将急剧膨胀,记录数量众多,加之常规计算机内存的局限性,这种存储方式可能既不现实,甚至根本无法实现。为此,我们转而采用哈希表来规避这一难题。

哈希函数

称为散列函数(h)的特殊函数用于克服直接寻址中的上述问题。

在直接访问过程中,键k对应的值被保存在槽k里。借助哈希函数,我们可以计算出每个值应归属的表(即槽)的具体位置。这个由哈希函数计算出的对应于特定键的值,我们称之为哈希值,它明确指出了该值应映射至的表索引。

h(k) = k % m

每个程序员必知!必须掌握的8种数据结构 第9张

以哈希函数h(k) = k % 20为基准每个程序员必知!必须掌握的8种数据结构,该函数的参数为键k,而哈希表的总容量为20。面对一组特定的键,我们需要计算每个键对应的哈希值每个程序员必知!必须掌握的8种数据结构,进而确定它们在哈希表中的具体索引位置。下面展示了这些键、它们对应的哈希值以及它们在哈希表中的索引。

观察上述两个示例,我们发现,若哈希函数对多个键值产生相同的索引,便会产生所谓的索引冲突。对此,我们可以通过挑选恰当的哈希函数h,并运用链表链接和开放寻址等方法来有效处理这些冲突。

哈希表的应用

6. 树(Trees)

树木构成了一个层级化的架构基本数据结构,其中的信息依照层级顺序排列并相互连接。这种组织形式与链表相异,链表中的元素则是按照一条直线顺序相连的。

在程序应用领域,为了满足特定需求并应对各种限制条件,研究人员已经设计并实现了多种树木结构。其中,二叉搜索树、B树、treap、红黑树、splay树、AVL树以及n叉树等都是典型的代表。

二叉搜索树

二叉搜索树,简称BST,正如其名所示,是一种二叉树形式,其数据按照层级结构进行排列。这种数据结构中的数值是按照一定的排序规则进行存储的。

二叉搜索树中的每个节点都包含以下属性。

节点内保存的数据被称为键值。指向其左侧子节点的引用称作左指针。指向其右侧子节点的引用称作右指针。指向其父节点的引用称为父指针。

二叉搜索树独树一帜,它所拥有的特性被称作二叉搜索树特性。

令x为二叉搜索树中的一个节点。

每个程序员必知!必须掌握的8种数据结构 第10张

树的应用

7. 堆(Heaps)

每个程序员必知!必须掌握的8种数据结构 第11张

堆作为一种特殊的二叉树结构,其特点在于父节点会与子节点的数值进行对比,并据此进行有序排列。

让我们探究堆的表示方法。堆可以通过树形结构和数组形式来展现。接下来的两张图将具体展示如何用二叉树和数组来具体表示二叉堆。

每个程序员必知!必须掌握的8种数据结构 第12张

每个程序员必知!必须掌握的8种数据结构 第13张

堆可以有两种类型

最小堆中,每个父节点的键值都不超过其子节点的键值,这一特性被称为最小堆性质。因此,堆的根节点将存储整个堆中的最小值。而在最大堆中,父节点的键值总是大于或等于其子节点的键值,这一特性称为最大堆性质。因此,最大堆的根节点将包含堆中的最大值。

堆的应用

8.图表()

图由一组有限的顶点或节点以及一组连接这些顶点的边组成。

图的阶数是图中顶点的数量。图的大小是图中边的数量。

如果两个节点通过同一条边相互连接,则称它们是相邻的。

有向图

若图G中的每一条边均标明了其起点和终点的指向,那么这样的图G便被定义为有向图。

我们谈论的(u, v)这一对顶点,指的是光线从顶点u射入或离开,同时亦是从顶点v射入或进入。

自循环:从顶点到自身的边。

无向图

若图G中所有边均不具备方向性,那么该图便被定义为无向图。在这种图中,顶点间的移动是可逆的,即可以在两个顶点之间进行双向通行。

若一个顶点与图中其他节点无任何连线,那么该顶点便被视为孤立。

每个程序员必知!必须掌握的8种数据结构 第14张

图的应用

总结

众多数据结构实际上均源自上述结构的演变,它们是每位程序员必须精通的技能,无论是在日常工作中还是在求职面试中,这些知识都是不可或缺的储备。

加入微信交流群:************ ,请猛戳这里→点击入群

扫描二维码推送至手机访问。

版权声明:本文由全景资讯网发布,如需转载请注明出处。

本文链接:https://www.qjnew.com/post/4102.html

分享给朋友:

“每个程序员必知!必须掌握的8种数据结构” 的相关文章

动植物的生存本领都是适应什么的结果

动植物的生存本领都是适应什么的结果

在广袤的大自然中,动植物们凭借着各自独特的生存本领,在残酷的环境中顽强地生存着,它们的故事充满了神奇与奥秘。让我们一起走进这个奇妙的世界,探寻动植物们的神奇生存本领。植物篇含羞草:害羞的防御机制含羞草,一种常见的观赏植物,它最为神奇的本领就是“害羞”。当你轻轻触碰含羞草的叶片时,它会迅速地合拢,仿佛...

董宇辉从东方甄选离职!俞敏洪回应:尊重选择

董宇辉从东方甄选离职!俞敏洪回应:尊重选择

在互联网的浪潮中,人事变动往往如同一颗颗石子投入平静的湖面,激起层层涟漪,引发广泛的关注与讨论。近日,董宇辉从东方甄选离职的消息,犹如一颗重磅,在商业和舆论的天空中炸开,引起了轩然。董宇辉,这位以才华横溢、知识渊博而闻名的主播,凭借着独特的直播风格和深厚的文化底蕴,在东方甄选的舞台上迅速崛起,成为了...

半导体行业产能扩张,芯片价格或将迎来调整

半导体行业产能扩张,芯片价格或将迎来调整

在当今的科技时代,半导体行业无疑是全球经济的重要支柱之一。随着信息技术的飞速发展,对半导体芯片的需求持续增长,而半导体行业的产能扩张也成为了业界关注的焦点。这一趋势不仅对半导体行业本身产生深远影响,也将对全球芯片价格带来重大调整。半导体行业的产能扩张是一个长期而复杂的过程。近年来,全球各大半导体厂商...

旅游旺季来临,热门景区门票预订量大幅增长

旅游旺季来临,热门景区门票预订量大幅增长

随着岁月的脚步悄然迈进,旅游的旺季如同一股炽热的浪潮,汹涌而来。在这个充满活力与的季节里,热门景区的门票预订量呈现出了令人瞩目的大幅增长态势,仿佛一场盛大的狂欢即将拉开帷幕。热门景区,宛如璀璨的明珠,在旅游的舞台上散发着无尽的光芒。它们以其独特的自然风光、深厚的历史文化底蕴或别具一格的建筑风格,吸引...

宠物经济市场规模扩大,相关服务需求增加

宠物经济市场规模扩大,相关服务需求增加

在当今社会,宠物已经不再仅仅是陪伴人们的伙伴,更是成为了许多家庭中不可或缺的一员。随着人们生活水平的不断提高和对宠物关注度的持续提升,宠物经济市场规模也在不断扩大,相关服务需求更是呈现出日益增长的趋势。宠物经济市场规模的扩大,首先得益于宠物数量的显著增加。越来越多的人选择将宠物带入自己的生活,无论是...

珠宝首饰市场消费回暖,个性化定制受追捧

珠宝首饰市场消费回暖,个性化定制受追捧

在当今的消费市场中,珠宝首饰领域呈现出一派令人瞩目的景象——消费逐渐回暖,而个性化定制更是成为了备受追捧的时尚潮流。珠宝首饰市场的消费回暖,并非是偶然的现象。随着人们生活水平的不断提高,对于美的追求和对自身形象的重视也与日俱增。珠宝首饰作为一种能够提升个人气质和彰显个性的配饰,自然受到了越来越多消费...