查看“︁数组”︁的源代码

[[分类:线性表]]
[[分类:存储结构]]
{{InfoBox
|name=数组存储结构
|eng_name=array
|aliases=顺序存储结构
}}
{{InfoBox
|name=索引
|eng_name=index
|aliases=下标,subscript
}}
{{InfoBox
|name=元素
|eng_name=element
|aliases=分量,component
}}
{{#seo:
|keywords=顺序存储结构
|description=介绍了数组存储结构，或顺序存储结构，即元素按顺序排列，可以从索引使用下标公式直接得到元素地址的存储结构。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2025-7-18
}}
'''数组'''存储结构('''array''')是最基础的存储结构，也称为'''顺序'''存储结构，经常被简称为'''数组'''；数组一词也常用于代指一种基础的逻辑结构（正式术语为[[线性表]]）。尽管绝大多数情况下，这两方面是密不可分的，“数组”指既使用这种存储结构，又使用这种逻辑结构的数据结构（正式术语也称'''顺序表'''），包括[[静态数组]]和[[动态数组]]。

数组存储结构容纳一系列的'''元素'''，这些元素由给定的顺序编号，称为'''索引'''/'''下标'''。

数组也指代一种寻址方式。数组中的元素在内存中以相等大小紧密排列（严格地说，相等地址差即可）。这种排列方式决定了对任意给定，都可通过计算得到指定顺序元素的内存地址。这种寻址方式有时可能不要求连续而是按某种“公式”进行规律排列，因此有时被称为'''数组寻址'''或'''公式化寻址'''；也有人称'''线性寻址'''，但线性寻址一词一般只要求连续而不要求大小相同。

有时，如果一个数据结构使用数组存储结构，或使用线性表逻辑结构，或使用数组寻址方式，都可能被统称数组，也被会命名为某某数组。

<blockquote>
“数组”也是大多数[[编程语言]]中具体[[数据类型]]的名字，而且通常会实现这一数据结构。见[[数组（数据类型）]]。
</blockquote>

如果数组的元素也是数组，也就是一系列的紧密排列之间紧密排列，这与其元素直接紧密排列在存储上没有本质区别，但是要按照多个层次上的一组索引得到元素地址，通常称为[[多维数组]]，其存储方式也视为一种数组。

数组作为抽象数据结构时，见[[线性表]]。

== 定义 ==

=== 存储结构 ===

'''数组'''/阵列('''array''')是一种存储结构。数组包括一段连续的内存空间，依次排列着开始位置有相同间隔（大多数情况是，元素内存大小相同且之间无间隔）的对象，称为'''元素'''('''element''')或分量(component)。数组中的元素用一系列连续的整数标记，称为'''索引'''('''index''')或'''下标'''('''subscript''')。

数组的元素可以是数组，此时称为[[多维数组]]，并根据是数组的层数称其为几维数组；相对地，元素不是数组的普通情况，就称为一维数组。有时一维数组也称为向量(vector)<ref>但是数组与数学上的[[向量]]逻辑上不等价，逻辑上数组更接近数学上的[[元组]]。特别是数的元组也可以简称数组，通常翻译成数组而不是“array”一词更字面的“阵列”可能也是这个原因。</ref>，二维数组也称为矩阵(matrix)。

根据不同编程语言的习惯，数组索引范围有不同的规定。即使抛开编程语言抽象地谈问题时，不同人也会有不同的习惯。但是总体说来数组索引有三种，从 0 开始(zero-based indexing)、从 1 开始(one-based indexing)和自定义(n-based indexing)。如果允许自定义的话，就允许其他连续的整数（也就是说允许出现负数）。一般地，索引的开始值称为索引的'''下界'''('''lower bound''')，结束值称为索引的'''上界'''('''upper bound''')。

在存储具体地址方面，数组中元素开始地址间隔称为'''地址增量'''('''address increment''')或'''stride'''，因为大多数情况下是无间隔的相同元素，也可以称为元素'''大小'''('''size''')。整个数组的开始地址称为'''基址'''('''base address''')，记为 <math>b</math> 。

=== 寻址方式 ===

若基址为 <math>b</math> ，地址间隔为 <math>c</math> ，索引的下界和上界为 <math>l</math> 和 <math>u</math> ，则对任意索引为 <math>i</math> 的元素，其索引偏移量是 <math>i-l</math> ，起始地址偏移量是 <math>c(i-l)</math> ，起始地址为 <math>\mathrm{LOC}(a_i) = b + c(i-l)</math> 。

注：由于 <math>l=0</math> 可以简化寻址计算，编程语言索引从 0 开始的情况更常见。当然抛开编程语言的时候人们使用三种都不少见。


{{数据结构}}