数组（数据类型）

数组
术语名称	数组
英语名称	array
别名	串

数组(array)是计算机科学领域及编程语言中处理多个相同类型数据的数据类型，可以字面理解为“相同数据构成的元组”。

本文描述的字符串是计算机科学及编程语言中的数据类型，对于数组指静态数组、动态数组，或泛指数组存储结构的数据结构，或泛指线性表的情况，见相应条目。

数组这一数据类型在不同编程语言中有不同处理。部分语言中，数组是静态数组，此时数组是固定数量（一到多个）的相同类型元素构成的元组；部分语言中，数组是动态数组，此时其内容是不固定数量的相同类型元素构成的元组。无论那种场景下，都是其元素构成的线性表。在部分语言中，也允许指定下标范围，从 0 开始的下标可以从起始地址直接加下标得到新地址，而其他下标范围都可以看成是在此基础上增加一个偏移量。

定义

对数据集合 [math]\displaystyle{ T }[/math] ，集合上长度为 [math]\displaystyle{ n }[/math] 的元组 [math]\displaystyle{ t = (t_0, t_1, t_2, \dots, t_n) \in T^n }[/math] 称为集合 [math]\displaystyle{ \Sigma }[/math] 上的字符串(string over [math]\displaystyle{ \Sigma }[/math] )，其中的每个序列元素称为字数组的元素(element)或分量(component)。

数组总是使用数组存储结构，其中的元素被连续排列在内存中。

数据类型

逻辑结构

数组的逻辑结构是线性表的结构，其中元素按照一个特定的、线性的顺序排列。每个元素在数组中都有一个确定的位置具体到数组类型，则包括一个首地址和一个索引范围。

数组中的元素用一系列连续的整数标记，称为索引(index)或下标(subscript)。数组索引的开始值称为索引的下界(lower bound)，结束值称为索引的上界(upper bound)。
数组的元素个数，也就是上下界的距离 + 1 ，称为数组的大小(size)或长度(length)。
数组指定下标范围，或者指定开始和长度，会得到一个“子数组”，称为数组的切片。
通常允许直接获取数组的指定下标元素，以及首元素、尾元素，以及基于这些的其他操作，按下标获取或设置应该当是一种高效随机访问（[math]\displaystyle{ O(1) }[/math]）。
经典情况下，数组是固定大小，而现代常见扩展为动态大小，这时会增加改变大小相关的操作。

实际差异

数组的实际实现在不同语言中可能有差别。最常见的实现是将元素放置在连续的内存空间中，但是也存在数组中存放元素引用的情况。