快速介绍8种常用数据结构
数据结构是一种特殊的组织和存储数据的方式,可以使我们可以更高效地对存储的数据执行操作。数据结构在计算机科学和软件工程领域具有广泛而多样的用途。
几乎所有已开发的程序或软件系统都使用数据结构。此外,数据结构属于计算机科学和软件工程的基础。当涉及软件工程面试问题时,这是一个关键主题。因此,作为开发人员,我们必须对数据结构有充分的了解。
在本文中,我将简要解释每个程序员必须知道的8种常用数据结构。
1.数组
数组是固定大小的结构,可以容纳相同数据类型的项目。它可以是整数数组,浮点数数组,字符串数组或什至是数组数组(例如二维数组)。数组已建立索引,这意味着可以进行随机访问。
Fig 1. Visualization of basic Terminology of Arrays
数组运算
数组的应用
2.链表
链表是一种顺序结构,由相互链接的线性顺序项目序列组成。因此,您必须顺序访问数据,并且无法进行随机访问。链接列表提供了动态集的简单灵活的表示形式。
让我们考虑以下有关链表的术语。您可以通过参考图2来获得一个清晰的主意。
Fig 2. Visualization of basic Terminology of Linked Lists
以下是可用的各种类型的链表。
· 循环链接列表—链接列表,其中头的上一个指针指向尾部,尾号的下一个指针指向头。
链表操作
链表的应用
3.堆栈
堆栈是一种LIFO(后进先出-最后放置的元素可以首先访问)结构,该结构通常在许多编程语言中都可以找到。该结构被称为"堆栈",因为它类似于真实世界的堆栈-板的堆栈。
Image Source: pixabay
堆栈操作
下面给出了可以在堆栈上执行的2个基本操作。请参考图3,以更好地了解堆栈操作。
Fig 3. Visualization of basic Operations of Stacks
此外,为堆栈提供了以下附加功能,以检查其状态。
堆栈的应用
4.队列
队列是一种FIFO(先进先出-首先放置的元素可以首先访问)结构,该结构通常在许多编程语言中都可以找到。该结构被称为"队列",因为它类似于现实世界中的队列-人们在队列中等待。
Image Source: pixabay
队列操作
下面给出了可以在队列上执行的2个基本操作。请参考图4,以更好地了解堆栈操作。
Fig 4. Visualization of Basic Operations of Queues
队列的应用
5.哈希表
哈希表是一种数据结构,用于存储具有与每个键相关联的键的值。此外,如果我们知道与值关联的键,则它有效地支持查找。因此,无论数据大小如何,插入和搜索都非常有效。
当存储在表中时,直接寻址使用值和键之间的一对一映射。但是,当存在大量键值对时,此方法存在问题。该表将具有很多记录,并且非常庞大,考虑到典型计算机上的可用内存,该表可能不切实际甚至无法存储。为避免此问题,我们使用哈希表。
哈希函数
名为哈希函数(h)的特殊函数用于克服直接寻址中的上述问题。
在直接访问中,带有密钥k的值存储在插槽k中。使用哈希函数,我们可以计算出每个值都指向的表(插槽)的索引。使用给定键的哈希函数计算的值称为哈希值,它表示该值映射到的表的索引。
Fig 5. Representation of a Hash Function
从上面给出的最后两个示例中,我们可以看到,当哈希函数为多个键生成相同的索引时,就会发生冲突。我们可以通过选择合适的哈希函数h并使用链接和开放式寻址等技术来解决冲突。
哈希表的应用
6.树
树是一种层次结构,其中数据按层次进行组织并链接在一起。此结构与链接列表不同,而在链接列表中,项目以线性顺序链接。
在过去的几十年中,已经开发出各种类型的树木,以适合某些应用并满足某些限制。一些示例是二叉搜索树,B树,红黑树,展开树,AVL树和n元树。
二叉搜索树
顾名思义,二进制搜索树(BST)是一种二进制树,其中数据以分层结构进行组织。此数据结构按排序顺序存储值,我们将在本课程中详细研究这些值。
二叉搜索树中的每个节点都包含以下属性。
二叉搜索树具有独特的属性,可将其与其他树区分开。此属性称为binary-search-tree属性。
令x为二叉搜索树中的一个节点。
Fig 6. Visualization of Basic Terminology of Trees.
树的应用
7.堆
堆是二叉树的一种特殊情况,其中将父节点与其子节点的值进行比较,并对其进行相应排列。
让我们看看如何表示堆。堆可以使用树和数组表示。图7和8显示了我们如何使用二叉树和数组来表示二叉堆。
Fig 7. Binary Tree Representation of a Heap
Fig 8. Array Representation of a Heap
堆可以有2种类型。
堆的应用
8.图
一个图由一组有限的顶点或节点以及一组连接这些顶点的边组成。
图的顺序是图中的顶点数。图的大小是图中的边数。
如果两个节点通过同一边彼此连接,则称它们为相邻节点。
有向图
如果图形G的所有边缘都具有指示什么是起始顶点和什么是终止顶点的方向,则称该图形为有向图。
我们说(u,v)从顶点u入射或离开顶点u,然后入射到或进入顶点v。
自环:从顶点到自身的边。
无向图
如果图G的所有边缘均无方向,则称其为无向图。它可以在两个顶点之间以两种方式传播。
如果顶点未连接到图中的任何其他节点,则称该顶点为孤立的。
Fig 9. Visualization of Terminology of Graphs
图的应用
2021年3月24日,主题为《数据的世界,世界的数据》的星环科技2021春季新品发布会...
建站 什么 虚拟主机 够用?这要看搭建的是什么类型的网站。比如个人博客类型的网...
前提条件 请您在购买前确保已完成注册和充值。详细操作请参见 如何注册公有云管...
Docker生成新镜像版本的两种方式 There are two ways Docker can generate new m...
本文整理自直播《Hologres 数据导入/导出实践-王华峰(继儒)》 视频链接: https:/...
从 10.0.0 版开始,异步迭代器就出现在 Node 中了,在本文中,我们将讨论异步迭...
摘要 元旦期间 订单业务线 告知 推送系统 无法正常收发消息,作为推送系统维护者...
在Python语言中有如下3种方法: 成员方法 类方法(classmethod) 静态方法(staticm...
信息化2.0时代提出开展智慧教育创新发展行动。2019年2月,中共中央、国务院印发...
【51CTO.com快译】 数据可视化工具不断发展,提供更强大的功能,同时改善可访问...