每个程序员都必须知道的8种常见数据结构。数据结构在计算机科学和软件工程中有着广泛而多样的用途。几乎所有开发的程序或软件系统都使用数据结构。此外，数据结构属于计算机科学和软件工程的基础。当涉及到软件工程面试问题时，这是一个关键主题。因此，作为开发人员，我们必须对数据结构有扎实的了解。在这篇文章中，我将简要解释8个每个程序员都必须知道的常用数据结构。1.数组数组是固定大小的结构，可以容纳相同数据类型的项。它可以是整数数组、浮点数数组、字符串数组甚至是数组数组（例如二维数组）。数组是有索引的，这意味着可以进行随机访问。图1.数组基本术语的可视化数组操作遍历：遍历所有元素并打印。插入：向数组中插入一个或多个元素。删除：从数组中删除一个元素搜索：在数组中搜索一个元素。您可以通过其值或索引搜索元素更新：应用值数组更新给定索引处的现有元素用作构建其他数据结构如数组列表、堆、哈希表、向量的基础和矩阵。用于不同的排序算法，如插入排序、快速排序、冒泡排序和归并排序。2.链表链表是一种顺序结构，由相互链接的线性顺序的项目序列组成。因此，必须顺序访问数据，随机访问是不可能的。链接列表提供了动态集的简单而灵活的表示。让我们考虑以下关于链表的术语。参考图2就可以很清楚了。链表中的元素称为节点。每个节点都包含一个键和一个指向其后继节点（称为下一个）的指针。名为head的属性指向链表的第一个元素。链表的最后一个元素称为尾。图2.链表基本术语的可视化下面是可用的各种类型的链表。单向链表——只能向前遍历项。双链表-项目可以向前和向后两个方向遍历。节点由一个名为previous的附加指针组成，指向前一个节点。循环链表——头部的前一个指针指向尾部，尾部的下一个指针指向头部的链表。链表操作搜索：通过简单的线性搜索在给定的链表中找到第一个键为k的元素，并返回指向该元素的指针插入：向链表中插入一个键。插入可以通过3种不同的方式完成；在列表的开头插入，在列表的末尾插入，然后在列表的中间插入。删除：从给定的链表中删除元素x。您不能单步删除节点。可以通过3种不同的方式进行删除；从列表开头删除，从列表末尾删除，然后从列表中间删除。链表的应用用于编译器设计中的符号表管理。用于使用AltTab在程序之间切换（使用循环链表实现）。3.堆栈堆栈是一种LIFO（后进先出-最后放置的元素可以最先访问）结构，这在许多编程语言中都很常见。这种结构被称为“堆栈”，因为它类似于现实世界中的堆栈——一堆木板。堆栈操作下面给出了可以在堆栈上执行的2个基本操作。请参考图3以更好地理解堆栈操作。Push：在栈顶插入一个元素。Pop：移除最顶层的元素并返回。图3.堆栈基本操作的可视化此外，还为堆栈提供了以下附加功能以检查其状态。Peep：返回栈顶元素而不移除它。isEmpty：检查堆栈是否为空。isFull：检查堆栈是否已满。堆栈的应用程序用于表达式评估（例如：用于解析和评估数学表达式的调车场算法）。用于实现递归编程中的函数调用。4.队列队列是一种FIFO（先进先出-先放置的元素先被访问）结构，在许多编程语言中都很常见。该结构被称为“队列”，因为它类似于现实世界中的队列——人们在队列中等待。队列操作下面给出了可以在队列上执行的2个基本操作。请参考图4以更好地理解堆栈操作。入队：在队尾插入一个元素。出队：从队列的开头移除一个元素。图4.队列基本操作可视化应用队列用于管理多线程中的线程。用于实现排队系统（例如：优先级队列）。5.哈希表哈希表是一种数据结构，它存储值和与每个键相关联的键。此外，如果我们知道与值关联的键，它会有效地支持查找。因此，无论数据大小如何，插入和搜索都非常有效。当存储在表中时，直接寻址使用值和键之间的一对一映射。但是，当存在大量键值对时，这种方法会出现问题。这张表将有很多记录，而且非常大，考虑到典型计算机上的可用内存，它可能不切实际甚至不可能存储。为了避免这个问题，我们使用哈希表。哈希函数一个名为哈希函数（h）的特殊函数用于克服直接寻址中的上述问题。在直接访问中，具有键k的值存储在槽k中。使用哈希函数，我们可以计算每个值指向的表（槽）的索引。使用散列函数为给定键计算的值称为散列值，它表示该值映射到的表的索引。h：散列函数k：要确定其散列值的键m：散列表的大小（可用槽的数量）。不接近2的精确幂的素数是m的不错选择。图5.哈希函数的表示1→1→15→5→523→23→363→63→3从上面给出的最后两个例子可以看出，当哈希函数为multi时会发生冲突两个键生成相同的索引。我们可以通过选择合适的散列函数h并使用链接和开放寻址等技术来解决冲突。哈希表的应用是用来实现数据库索引的。用于实现关联数组。用于实现“设置”数据结构。6.树树是一种层次结构，其中数据按层次组织并链接在一起。这种结构不同于链表，链表中的项目以线性顺序链接。在过去的几十年里，已经开发出各种类型的树来适应特定的应用并满足特定的限制。一些示例是二叉搜索树、B树、红黑树、splay树、AVL树和n叉树。二叉搜索树顾名思义，二叉搜索树（BST）是一种二叉树，其中数据以层次结构组织。这种数据结构按排序顺序存储值，我们将在本课程中详细研究。二叉搜索树中的每个节点都包含以下属性。key：存储在节点中的值。left：指向左孩子的指针。右：指向正确孩子的指针。p：指向父节点的指针。二叉搜索树具有区别于其他树的独特属性。此属性称为二叉搜索树属性。令x为二叉搜索树中的一个节点。如果y是x的左子树中的节点，则y.key≤x.key如果y是x的右子树中的节点，则y.key≥x.key图6.树的基本术语可视化。二叉树的应用：用于实现表达式解析器和表达式求解器。二叉搜索树：用于许多连续输入和输出数据的搜索应用程序。堆：由JVM（Java虚拟机）用来存储Java对象。陷阱：用于无线网络。7.堆堆是二叉树的一种特殊情况，其中比较父节点及其子节点的值并进行相应排列。让我们看看如何表示堆。堆可以用树和数组表示。图7和图8显示了我们如何使用二叉树和数组来表示二叉堆。图7.堆的二叉树表示图8.堆的数组表示可以有2种类型的堆。最小堆-父项的密钥小于或等于子项的密钥。这称为最小堆属性。根将包含堆的最小值。最大堆计数-父项的密钥大于或等于子项的密钥。这称为最大堆属性。根将包含堆的最大值。堆的应用用于实现优先级队列，因为优先级值可以根据堆属性进行排序。队列功能可以在O(logn)时间内使用堆实现。用于查找给定数组中的k个最小（或最大）值。对于堆排序算法。8.图一个图由一组有限的顶点或节点，以及一组连接这些顶点的边组成。图的阶是图中的顶点数。图的大小是图中边的数量。如果两个节点通过同一条边相互连接，则它们称为相邻节点。有向图如果图G的所有边都有方向指示起始顶点和结束顶点，则图G称为有向图。我们说(u,v)在顶点u处入射或远离顶点u，然后入射或进入顶点v。自环：从顶点到自身的边。无向图如果图G的所有边都没有方向，则称图G是无向的。它可以在两个顶点之间以两种方式传播。如果一个顶点没有连接到图中的任何其他节点，则称该顶点是孤立的。图9.图形术语可视化在表示社交媒体网络中的应用。每个用户都是一个顶点，当用户连接时会创建一条边。用于表示搜索引擎的网页和链接。Internet上的网页通过超链接相互链接。每个页面都是一个顶点，两个页面之间的超链接是一条边。用于Google中的页面排名。用于表示GPS中的位置和路线。位置是顶点，连接位置的路线是边。用于计算两个位置之间的最短路径。
