数组

概述

数组 是一个固定(有限)长度的、存储相同数据类型元素(元素大小固定)的集合。数组：一组数(

数组 这个概念本身是模糊的，既可以视作 ADT, 又可以视作具体的实现，下列叙述默认将数组视为具体实现

简单图示(C++)

代码定义

char a[10];
int b[2][3];
// ...

特性

• 数组层面
  • 顺序存储 —— 存储空间连续：数组内所有元素存储在一段连续的内存空间中
  • 随机存取 —— 有索引：由于存储的位置是连续的，可以通过指针等直接取址定位
  • 长度/容量固定：数组创建后长度固定，不可扩展压缩(若需要扩展，需要重新申请一个更大的数组)(压缩的话，可以自定义一个末指针，指定所需位置)
  • 批处理：在申请以及释放资源方面，数组一般是成批处理的
• 元素层面
  • 改变元素方式为覆盖，不可直接将元素删除。交换元素时只能交换元素的数值，其本身的位置信息(地址)无法交换

复杂度分析(部分操作)

操作	时间复杂度	空间复杂度
随机访问	O(1)	O(1)
查找元素(遍历)	O(n)	O(1)
插入数据	O(n)/O(1)(插入末尾，元素未满)	O(1)
删除数据	O(n)/O(1)(末尾)	O(1)
扩容	O(n)	O(n)

拓展：多维数组

参考内容: 代码随想录

在C++中，定义一个二维数组：

char a[10][10];

在内存中连续分布：即a[2][1]存储在以a为起始地址起后21字节的位置

在其它编程语言中未必也是连续分布的，似乎在java中存在这种多维数组结构：

在python中，a = [1,2,3,...] 所定义的结构并非数组，而是列表。python数组需要引入特定的package

发散/随想/自身理解(?)

• 数组本身是相当简单的数据结构，但如果天马行空一点的话，运用起来也能组建出很复杂的结构和算法，一般是作为 载体/容器 的形式存在(即数据结构的 具体实现)
• 数组在检索数据方面快，但是长度固定，元素类型固定，不太好处理涉及到数据不定长变换或数据本身类型不一致等情况