每个程序员必知!必须掌握的8种数据结构
每个程序员必知!必须掌握的8种数据结构
数据结构是一种特定的计算机组织与存储数据的技术,它使得我们能够更高效地对数据进行操作。这种技术在计算机科学与软件工程领域中应用广泛,且种类繁多。
众多已开发的程序与软件系统普遍采用了数据结构这一概念。同时,数据结构构成了计算机科学与软件工程领域的基础理论。在软件工程面试中,这一议题往往占据核心位置。鉴于此,对于开发者而言,对数据结构的深入理解至关重要。
本文将对我将简要阐述的八个程序员必备的常用数据结构进行概述。
1. 数组()
数组是一种具有固定规模的集合,能够存放具有相同数据类型的多个元素。它包括整数数组、浮点数数组、字符串数组,甚至可以包含数组自身的数组,如二维数组。数组具有索引功能,这使得我们能够实现对其元素的随机访问。
数组运算
数组容量固定,故无法直接向其添加或移除元素。若需向数组中添加元素基本数据结构,需先构建一个比原数组多一个位置的全新数组,接着将原数组中的所有元素复制至新数组,并将新增元素加入其中。删除元素时,亦需采取类似步骤,创建一个容量减少的新数组,并将原数组中除被删除元素外的所有元素复制至新数组。
数组的应用
2. 链表( Lists)
链表是一种基于线性顺序的排列结构,它由若干个项目按照顺序相互连接而成。这就意味着在处理数据时,我们必须遵循一定的顺序进行访问,而无法像在数组中那样进行随机的读取。链接列表则能够以简洁和灵活的方式,实现对动态集合的有效表示。
让我们考虑以下有关链表的术语。
以下是可用的各种类型的链接列表。
链表操作
链表的应用
3. 堆栈()
堆栈是一种遵循LIFO原则(即后进先出,最后放入的元素最先被访问)的数据结构,这种结构在众多编程语言中普遍存在。之所以被称为“堆栈”,是因为其运作原理与现实生活中的堆叠盘子极为相似。
堆栈操作
下面给出了可以在堆栈上执行的 2 个基本操作。
此外基本数据结构,还为堆栈提供了以下附加函数以检查其状态。
栈的应用
4. 队列()
队列是一种遵循FIFO(即先进先出,即最先放置的元素将最先被访问)原则的结构,这种结构在众多编程语言中均有广泛应用。之所以将其称为“队列”,是因为其运作方式与现实生活中的排队场景颇为相似——人们通常会在队列中依次等待。
队列操作
下面给出了可以在队列上执行的 2 个基本操作。
队列的应用
5. 哈希表(Hash )
哈希表是一种专门用于存储带有相应键值的数据结构,每个存储的值都与其对应的键紧密相连。除此之外,只要我们掌握了与值对应的键,就能高效地实现数据的查找。因此,不论数据量的大小,无论是插入还是搜索,都能展现出极高的效率。
直接寻址法在存储时,通过值与键的对应关系进行记录。然而,当键值对数量庞大时,这种方法的弊端显现。表的大小将急剧膨胀,记录数量众多,加之常规计算机内存的局限性,这种存储方式可能既不现实,甚至根本无法实现。为此,我们转而采用哈希表来规避这一难题。
哈希函数
称为散列函数(h)的特殊函数用于克服直接寻址中的上述问题。
在直接访问过程中,键k对应的值被保存在槽k里。借助哈希函数,我们可以计算出每个值应归属的表(即槽)的具体位置。这个由哈希函数计算出的对应于特定键的值,我们称之为哈希值,它明确指出了该值应映射至的表索引。
h(k) = k % m
以哈希函数h(k) = k % 20为基准每个程序员必知!必须掌握的8种数据结构,该函数的参数为键k,而哈希表的总容量为20。面对一组特定的键,我们需要计算每个键对应的哈希值每个程序员必知!必须掌握的8种数据结构,进而确定它们在哈希表中的具体索引位置。下面展示了这些键、它们对应的哈希值以及它们在哈希表中的索引。
观察上述两个示例,我们发现,若哈希函数对多个键值产生相同的索引,便会产生所谓的索引冲突。对此,我们可以通过挑选恰当的哈希函数h,并运用链表链接和开放寻址等方法来有效处理这些冲突。
哈希表的应用
6. 树(Trees)
树木构成了一个层级化的架构基本数据结构,其中的信息依照层级顺序排列并相互连接。这种组织形式与链表相异,链表中的元素则是按照一条直线顺序相连的。
在程序应用领域,为了满足特定需求并应对各种限制条件,研究人员已经设计并实现了多种树木结构。其中,二叉搜索树、B树、treap、红黑树、splay树、AVL树以及n叉树等都是典型的代表。
二叉搜索树
二叉搜索树,简称BST,正如其名所示,是一种二叉树形式,其数据按照层级结构进行排列。这种数据结构中的数值是按照一定的排序规则进行存储的。
二叉搜索树中的每个节点都包含以下属性。
节点内保存的数据被称为键值。指向其左侧子节点的引用称作左指针。指向其右侧子节点的引用称作右指针。指向其父节点的引用称为父指针。
二叉搜索树独树一帜,它所拥有的特性被称作二叉搜索树特性。
令x为二叉搜索树中的一个节点。
树的应用
7. 堆(Heaps)
堆作为一种特殊的二叉树结构,其特点在于父节点会与子节点的数值进行对比,并据此进行有序排列。
让我们探究堆的表示方法。堆可以通过树形结构和数组形式来展现。接下来的两张图将具体展示如何用二叉树和数组来具体表示二叉堆。
堆可以有两种类型
最小堆中,每个父节点的键值都不超过其子节点的键值,这一特性被称为最小堆性质。因此,堆的根节点将存储整个堆中的最小值。而在最大堆中,父节点的键值总是大于或等于其子节点的键值,这一特性称为最大堆性质。因此,最大堆的根节点将包含堆中的最大值。
堆的应用
8.图表()
图由一组有限的顶点或节点以及一组连接这些顶点的边组成。
图的阶数是图中顶点的数量。图的大小是图中边的数量。
如果两个节点通过同一条边相互连接,则称它们是相邻的。
有向图
若图G中的每一条边均标明了其起点和终点的指向,那么这样的图G便被定义为有向图。
我们谈论的(u, v)这一对顶点,指的是光线从顶点u射入或离开,同时亦是从顶点v射入或进入。
自循环:从顶点到自身的边。
无向图
若图G中所有边均不具备方向性,那么该图便被定义为无向图。在这种图中,顶点间的移动是可逆的,即可以在两个顶点之间进行双向通行。
若一个顶点与图中其他节点无任何连线,那么该顶点便被视为孤立。
图的应用
总结
众多数据结构实际上均源自上述结构的演变,它们是每位程序员必须精通的技能,无论是在日常工作中还是在求职面试中,这些知识都是不可或缺的储备。