1. 数据结构与算法/

数据结构和算法-数组

·179 字·1 分钟· loading
数据结构与算法 数据结构和算法 数组
demo007x
作者
demo007x

数据结构和算法-数组
#

什么是数组?
#

数组是存储在连续内存位置相同变量类型的项目的集合。它是最流行和最简单的数据结构之一,通常用于实现其他数据结构。数组中的每个项目都从 0 开始索引。

每个程序员的梦想不仅是成为一名优秀的程序员,而且成为一名伟大的程序员。我们都想实现我们的目标,为了实现我们的目标,我们必须有一个伟大的计划。

Arrays 面试准备完整指南

我们可以通过索引值直接访问数组元素。

数组的基本术语
#

  • **数组索引:**在数组中,元素由其索引来标识。数组索引从0开始。
  • **数组元素:**元素是存储在数组中的项目,可以通过其索引进行访问。
  • **数组长度:**数组的长度由它可以包含的元素数量决定。

数组的表示
#

数组的表示可以通过其声明来定义。声明意味着为给定大小的数组分配内存。

array

数组可以用不同的语言以不同的方式声明。为了更好地说明,下面是一些特定于语言的数组声明。

img

然而,上面的声明是静态编译时内存分配,这意味着数组元素的内存是在程序编译时分配的。这里只会分配固定大小(即方括号**[]**中提到的大小)的内存用于存储,但是我们不认为这不会与我们知道数组的大小相同的情况每次,可能会出现我们不知道数组大小的情况。如果我们声明较大的大小并存储较少数量的元素,将导致内存浪费,或者是我们声明较小的大小的情况,那么我们将不会获得足够的内存来存储其余元素。在这种情况下,静态内存分配不是首选。

为什么需要数组数据结构?
#

假设有一个班有五名学生,如果我们必须记录他们的考试成绩,我们可以通过声明五个变量并跟踪记录来做到这一点,但如果学生人数变得非常多,那会怎样?操纵和维护数据具有挑战性。

这意味着,当我们有少量对象时,我们可以使用普通变量(v1,v2,v3,..)。但如果我们想要存储大量实例,用普通变量来管理它们就变得很困难。数组的想法是在一个变量中表示许多实例..

需要数组

数组类型:
#

数组主要有两种类型:

一维数组

一维数组

  • 二维数组: 2-D多维数组可以被视为数组的数组,也可以被视为由行和列组成的矩阵。

二维阵列

二维阵列

  • 三维数组: 3-D多维数组包含三个维度,因此可以将其视为二维数组的数组。

3D阵列

数组运算的类型:
#

  • 遍历:遍历数组的元素。
  • 插入:在数组中插入一个新元素。
  • 删除:从数组中删除元素。
  • 搜索:在数组中搜索元素。
  • 排序:保持数组中元素的顺序。

使用数组的优点:
#

  • 数组允许随机访问元素。这使得按位置访问元素变得更快。
  • 数组具有更好的缓存局部性,这在性能上有很大的差异。
  • 数组使用单个名称表示相同类型的多个数据项。
  • 数组存储多个具有相同名称的相似类型的数据。
  • 数组数据结构用于实现其他数据结构,如链表、堆栈、队列、树、图等。

数组的缺点:
#

  • 由于数组的大小是固定的,一旦分配了内存,就无法增加或减少,因此无法在需要时存储额外的数据。固定大小的数组称为静态数组。
  • 为数组分配少于所需的内存会导致数据丢失。数组本质上是同构的,因此单个数组不能存储不同数据类型的值。
  • 数组将数据存储在连续的内存位置,这使得删除和插入非常难以实现。通过实现链表可以克服这个问题,链表允许顺序访问元素。

数组的应用、优点与缺点
#

数组数据结构的应用:
#

  • 存储和访问数据:数组用于按特定顺序存储和检索数据。例如,数组可用于存储一组学生的分数,或气象站记录的温度。
  • **排序:**数组可用于按升序或降序对数据进行排序。冒泡排序、合并排序和快速排序等排序算法严重依赖数组。
  • 搜索:可以使用线性搜索和二分搜索等算法在数组中搜索特定元素。
  • 矩阵:数组用于表示数学计算中的矩阵,例如矩阵乘法、线性代数和图像处理。
  • **栈和队列:**数组作为底层数据结构来实现栈和队列,常用于算法和数据结构中。
  • :数组可用于表示计算机科学中的图。数组中的每个元素代表图中的一个节点,节点之间的关系由数组中存储的值表示。
  • 动态编程:动态编程算法通常使用数组来存储子问题的中间结果,以解决更大的问题。

数组的实时应用:
#

  • **信号处理:**数组在信号处理中用于表示随时间收集的一组样本。这可用于语音识别、图像处理和雷达系统等应用。
  • **多媒体应用:**数组用于多媒体应用,例如视频和音频处理,用于存储像素或音频样本。例如,可以使用数组来存储图像的 RGB 值。
  • **数据挖掘:**数组在数据挖掘应用程序中用于表示大型数据集。这可以实现高效的数据访问和处理,这在实时应用程序中非常重要。
  • 机器人技术:机器人技术中使用数组来表示 3D 空间中物体的位置和方向。这可用于运动规划和对象识别等应用。
  • **实时监控系统:**实时监控系统中使用阵列来存储传感器数据和控制信号。这可以实现实时处理和决策,这在工业自动化和航空航天系统等应用中非常重要。
  • **财务分析:**数组在财务分析中用于存储历史股票价格和其他财务数据。这可以实现高效的数据访问和分析,这在实时交易系统中非常重要。
  • **科学计算:**数组在科学计算中用于表示数值数据,例如实验和模拟的测量结果。这可以实现高效的数据处理和可视化,这对于实时科学分析和实验非常重要。

数组数据结构的优点:
#

  • **高效访问元素:**数组提供对集合中任何元素的直接高效访问。访问数组中的元素是一个 O(1) 操作,这意味着访问元素所需的时间是恒定的,并且不依赖于数组的大小。
  • **快速数据检索:**数组允许快速数据检索,因为数据存储在连续的内存位置中。这意味着可以快速有效地访问数据,而不需要复杂的数据结构或算法。
  • **内存效率:**数组是一种节省内存的数据存储方式。由于数组的元素存储在连续的内存位置中,因此数组的大小在编译时已知。这意味着可以在一个块中为整个数组分配内存,从而减少内存碎片。
  • **多功能性:**数组可用于存储多种数据类型,包括整数、浮点数、字符,甚至对象和指针等复杂的数据结构。
  • **易于实现:**数组易于实现和理解,使其成为初学者学习计算机编程的理想选择。
  • **与硬件的兼容性:**数组数据结构与大多数硬件架构兼容,使其成为在各种环境下进行编程的通用工具。

数组数据结构的缺点:
#

  • **固定大小:**数组具有在创建时确定的固定大小。这意味着,如果需要增加数组的大小,则必须创建一个新数组,并且必须将数据从旧数组复制到新数组,这可能非常耗时且占用内存。
  • **内存分配问题:**分配大型数组可能会出现问题,特别是在内存有限的系统中。如果数组的大小太大,系统可能会耗尽内存,从而导致程序崩溃。
  • 插入和删除问题:从数组中插入或删除元素可能效率低下且耗时,因为插入或删除点之后的所有元素都必须移动以适应更改。
  • **浪费的空间:**如果数组未完全填充,则为该数组分配的内存中可能会出现浪费的空间。如果内存有限,这可能是一个问题。
  • **有限的数据类型支持:**数组对复杂数据类型(例如对象和结构)的支持有限,因为数组的元素必须全部具有相同的数据类型。
  • **缺乏灵活性:**与链表和树等其他数据结构相比,固定大小和对复杂数据类型的有限支持可能使数组缺乏灵活性。

结构体相对于数组的优点:
#

  • 结构体可以存储不同类型的数据,而数组只能存储相似的数据类型。
  • 结构不像数组那样有大小限制。
  • 结构元素可能会也可能不会存储在连续位置,但数组元素会存储在连续位置。
  • 在结构中,可以实例化对象,而在数组中则不可能实例化对象。

使用数组的常见问题
#

  • 为什么从数组中获取值的复杂度是 O(1)?

数组是一种线性数据结构。在数组中,获取值的操作需要常数时间,即 O(1)。由于数组在内存中连续分配,因此通过数组索引获取值是一种算术运算。所有算术运算都在恒定时间内完成,即O(1)

第 i个索引的地址= 基址 + 偏移量 = 第 0个索引的地址 + i ×(一个元素的大小)

例子:

img

数组中的内存分配

在数组A[] = {8, 6, 7, 13, 8, 19}中

要获取索引 4 处的值,我们需要存储该索引值的内存地址。该地址可以通过进行算术运算来获得,即

索引 4 处的值的地址 = 索引 0 处的值的地址 + 4 × int的大小= 108 + 4 × 4 字节 索引 4 处的值的地址 = 124 A[4] = 地址 124 处的值 = 8

  • 什么时候应该使用数组而不是列表?

当在 Java 中使用数组而不是列表时:

  • 当我们需要多维结构来存储数据时,我们使用数组而不是列表,因为列表只能是一维的。
  • 如果我们需要固定长度和静态分配,则使用数组而不是列表。
  • 当需要更快地处理数据时,可以使用数组而不是列表。
  • 原始数据类型可以直接存储在数组中,但不能存储在列表中,因此,我们使用数组而不是列表。

当在 Python 中使用数组而不是列表时:

  • 我们在 python 中使用数组而不是列表,因为它需要更少的内存。
  • python 中数组比列表快。
  • 数组可以直接处理算术运算,而列表则不能。所以我们使用数组而不是列表。
  • 对于较长的数据项序列,数组优于列表。

Related

docker-swarm 教程:部署篇
docker devops
docker-swarm 教程:部署篇
2023年软件开发人员的 10 大 Docker 替代品
devops
想象一下,您努力创建一个具有各种库和依赖项的应用程序。该应用程序在您的系统上平稳高效地运行。如果要将应用程序发送到其他人的系统,该怎么办?该人需要对应用程序进行大量设置才能运行它。即使在设置之后,代码和配置中的单个更改也可能会中断任一系统上的整个应用程序,或者在最坏的情况下会中断两个系统上的整个应用程序。
生产环境中使用Docker的最佳实践
docker devops
近几年Docker的使用不断增长📈,上至公司团队,下至普通开发者。 但是并不是每个团队(或者个人)在使用 Docker 的时候都能做到 Docker 的最佳实践 👀, 本文将从以下几个方面来聊聊 Docker 工程化实践中的最佳方案.