数据结构是一种在计算机中组织和存储数据的专门方法,使我们可以更有效地对存储的数据执行操作。数据结构在计算机科学和软件工程领域有着广泛而多样的使用范围。
几乎所有已开发的程序或软件系统都在使用数据结构。此外,数据结构属于计算机科学和软件工程的基础知识。当涉及到软件工程面试问题时,这是一个关键话题。因此,作为开发人员,我们必须对数据结构有很好的了解。
在这篇文章中,我将简要解释每个程序员都必须了解的 8 种常用数据结构。
数组是一种固定大小的结构,可以容纳相同数据类型的项。它可以是整数数组、浮点数数组、字符串数组甚至数组的数组(例如二维数组)。数组是有索引的,这意味着可以进行随机访问。
由于数组的大小是固定的,因此无法立即向数组插入元素和从数组中删除元素。如果要将元素插入数组,首先必须创建一个大小增加的新数组(当前大小 + 1),复制现有元素并添加新元素。对于删除尺寸减小的新数组也是如此。
链表是一种顺序结构,由一系列按线性顺序相互链接的项目组成。因此,您必须顺序访问数据,而随机访问是不可能的。链接列表提供了动态集的简单而灵活的表示。
让我们考虑以下有关链表的术语。
以下是可用的各种类型的链接列表。
堆栈是一种LIFO(后进先出 - 最后放置的元素可以首先访问)结构,在许多编程语言中都很常见。这种结构被命名为“堆栈”,因为它类似于现实世界中的堆栈——一堆盘子。
下面给出了可以在堆栈上执行的 2 个基本操作。
此外,还为堆栈提供了以下附加函数以检查其状态。
队列是一种FIFO(先进先出——先放置的元素可以先访问)结构,在许多编程语言中都很常见。这种结构被命名为“队列”,因为它类似于现实世界的队列——人们在队列中等待。
下面给出了可以在队列上执行的 2 个基本操作。
哈希表是一种存储值的数据结构,这些值具有与每个值关联的键。此外,如果我们知道与值关联的键,它就可以有效地支持查找。因此,无论数据大小如何,插入和搜索都非常有效。
直接寻址在表中存储时使用值和键之间的一对一映射。但是,当存在大量键值对时,这种方法会出现问题。该表将非常庞大,包含如此多的记录,并且考虑到典型计算机上的可用内存,可能不切实际甚至不可能进行存储。为了避免这个问题,我们使用哈希表。
称为散列函数(h)的特殊函数用于克服直接寻址中的上述问题。
在直接访问中,具有键k的值存储在槽k中。使用哈希函数,我们计算每个值所在的表(槽)的索引。使用哈希函数对给定键计算出的值称为哈希值,它指示该值映射到的表的索引。
h(k) = k % m
考虑哈希函数h(k) = k % 20,其中哈希表的大小为 20。给定一组键,我们要计算每个键的哈希值,以确定它在哈希表中应位于的索引。考虑我们有以下键、哈希和哈希表索引。
从上面给出的最后两个示例中,我们可以看到,当哈希函数为多个键生成相同的索引时,可能会出现冲突。我们可以通过选择合适的哈希函数 h 并使用链接和开放寻址等技术来解决冲突。
树是一种层次结构,其中数据按层次结构组织并链接在一起。这种结构与链表不同,而在链表中,项目以线性顺序链接。
在程序的应用中,为了适应某些应用并满足某些限制,已经开发了各种类型的树木。一些例子是二叉搜索树、B树、treap、红黑树、splay树、AVL树和n叉树。
二叉搜索树(BST),顾名思义,是一种二叉树,其中数据以层次结构组织。该数据结构按排序顺序存储值。
二叉搜索树中的每个节点都包含以下属性。
二叉搜索树具有区别于其他树的独特属性。该属性称为二叉搜索树属性。
令x为二叉搜索树中的一个节点。
堆是二叉树的一种特殊情况,其中父节点与其子节点的值进行比较,并进行相应的排列。
让我们看看如何表示堆。堆可以使用树和数组来表示。下面两张图显示了如何使用二叉树和数组来表示二叉堆。
图由一组有限的顶点或节点以及一组连接这些顶点的边组成。
图的阶数是图中顶点的数量。图的大小是图中边的数量。
如果两个节点通过同一条边相互连接,则称它们是相邻的。
如果图G的所有边都具有指示起始顶点和终止顶点的方向,则称图 G 是有向图。
我们说(u, v)是从顶点u入射或离开顶点u ,并且是从顶点 v 入射或进入顶点v。
自循环:从顶点到自身的边。
如果图G的所有边都没有方向,则称其为无向图。它可以在两个顶点之间双向移动。
如果一个顶点没有连接到图中的任何其他节点,则称该顶点是孤立的。
还有很多种数据结构,其实都是基于以上数据结构变种生成的,数据结构是每个程序员都要掌握的,无论是工作中还是面试都必不可少的知识储备。