数组
| 数组存储结构 | |
|---|---|
| 术语名称 | 数组存储结构 |
| 英语名称 | array |
| 别名 | 线性结构, 线性存储结构 |
| 索引 | |
|---|---|
| 术语名称 | 索引 |
| 英语名称 | index |
| 别名 | 下标, subscript |
| 元素 | |
|---|---|
| 术语名称 | 元素 |
| 英语名称 | element |
| 别名 | 分量, component |
数组存储结构(array)是最基础的存储结构，也称为线性存储结构，经常被简称为数组；数组一词也常用于代指一种基础的逻辑结构（正式术语为线性表）。尽管绝大多数情况下，这两方面是密不可分的，“数组”指既使用这种存储结构，又使用这种逻辑结构的数据结构（正式术语也称顺序表），包括静态数组和动态数组。
数组存储结构容纳一系列的元素，这些元素在内存中以相等大小紧密排列（严格地说，相等地址差即可）。这种排列方式决定了对任意给定顺序编号，称为索引/下标，都可通过计算得到指定顺序元素的内存地址。这种寻址方式有时可能不要求连续而是按某种“公式”进行规律排列，因此有时被称为数组寻址或公式化寻址；也有人称线性寻址，但线性寻址一词一般只要求连续而不要求大小相同。
有时，如果一个数据结构使用数组存储结构，或使用线性表逻辑结构，或使用数组寻址方式，都可能被统称数组，也被会命名为某某数组。
如果数组的元素也是数组，也就是一系列的紧密排列之间紧密排列，这与其元素直接紧密排列在存储上没有本质区别，但是要按照多个层次上的一组索引得到元素地址，通常称为多维数组，其存储方式也视为一种数组。
数组作为抽象数据结构时，见线性表。
定义
存储结构
数组/阵列(array)是一种存储结构。数组包括一段连续的内存空间，依次排列着开始位置有相同间隔（大多数情况是，元素内存大小相同且之间无间隔）的对象，称为元素(element)或分量(component)。数组中的元素用一系列连续的整数标记，称为索引(index)或下标(subscript)。
数组的元素可以是数组，此时称为多维数组，并根据是数组的层数称其为几维数组；相对地，元素不是数组的普通情况，就称为一维数组。有时一维数组也称为向量(vector)[1]，二维数组也称为矩阵(matrix)。
根据不同编程语言的习惯，数组索引范围有不同的规定。即使抛开编程语言抽象地谈问题时，不同人也会有不同的习惯。但是总体说来数组索引有三种，从 0 开始(zero-based indexing)、从 1 开始(one-based indexing)和自定义(n-based indexing)。如果允许自定义的话，就允许其他连续的整数（也就是说允许出现负数）。一般地，索引的开始值称为索引的下界(lower bound)，结束值称为索引的上界(upper bound)。
在存储具体地址方面，数组中元素开始地址间隔称为地址增量(address increment)或stride，因为大多数情况下是无间隔的相同元素，也可以称为元素大小(size)。整个数组的开始地址称为基址(base address)，记为 [math]\displaystyle{ b }[/math] 。
寻址方式
若基址为 [math]\displaystyle{ b }[/math] ，地址间隔为 [math]\displaystyle{ c }[/math] ，索引的下界和上界为 [math]\displaystyle{ l }[/math] 和 [math]\displaystyle{ u }[/math] ，则对任意索引为 [math]\displaystyle{ i }[/math] 的元素，其索引偏移量是 [math]\displaystyle{ i-l }[/math] ，起始地址偏移量是 [math]\displaystyle{ c(i-l) }[/math] ，起始地址为 [math]\displaystyle{ \mathrm{LOC}(a_i) = b + c(i-l) }[/math] 。
注：由于 [math]\displaystyle{ l=0 }[/math] 可以简化寻址计算，编程语言索引从 0 开始的情况更常见。当然抛开编程语言的时候人们使用三种都不少见。