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

[[分类:存储结构]]
{{InfoBox
|name=多维数组
|eng_name=multidimensional array
}}
{{#seo:
|keywords=多维数组
|description=介绍了多维数组，即嵌套多次的数组数据结构，描述了其抽象结构以及主序等差异。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2025-4-17
}}
'''多维数组'''('''multidimensional array''')指[[数组]]数据结构中元素也是数组，这种“嵌套”的数组称为多维数组。

有时，由于数组一词用于指[[线性表]]的逻辑结构，多维数组也可能指嵌套的线性表。

{{InfoBox
|name=行主次序
|eng_name=row-major order
|aliases=行主序
}}
{{InfoBox
|name=列主次序
|eng_name=column-major order
|aliases=列主序
}}
'''行主次序'''('''row-major order''')和'''列主次序'''('''column-major order''')指多维数组排列时先紧密排列靠前的维度还是先紧密排列靠后的维度，统称'''主序'''。

== 定义 ==

=== 存储结构 ===

'''数组'''存储结构中，多个元素被紧密（以固定间隔）排列，并以一个'''索引'''区分。如果元素本身也是数组，则构成元素之间紧密排列，但逻辑上有多层索引，这种情况称为'''多维数组'''('''multidimensional array''')。

{{InfoBox
|name=维数
|eng_name=dimension
}}
{{InfoBox
|name=一维数组
|eng_name=one-dimensional array
|aliases=向量,vector
}}
{{InfoBox
|name=二维数组
|eng_name=two-dimensional array
|aliases=矩阵,matrix
}}
{{InfoBox
|name=三维数组
|eng_name=three-dimensional array
}}
数组的嵌套层数，也是索引的数目，称为数组的'''维数'''('''dimension''')。普通元素的数组称为'''一维数组'''('''one-dimensional array''')或向量(vector)，普通元素的数组的数组称为'''二维数组'''('''two-dimensional array''')或矩阵(matrix)，普通元素的数组的数组的数组称为'''三维数组'''('''three-dimensional array''')，以此类推。

{{InfoBox
|name=内情向量
|eng_name=dope vector
}}
相对于一维数组的'''地址增量'''，多维数组的每一维都对应着等间隔的地址，因此每一维都有一个地址增量。将多维数组的每一维地址增量放在一起作为一个向量，就被称为多维数组的'''内情向量'''('''dope vector''')。

=== 寻址方式 ===

==== 线性公式 ====

朴素的多维数组就是逐层紧密排列的产物，其每层索引对应的层级有固定的地址间隔，因此：

若基址为 <math>b</math> ，每个维度地址间隔依次为 <math>c_1, c_2, \dots, c_n</math> ，索引的下界和上界依次为 <math>l_1, l_2, \dots, l_n</math> 和 <math>u_1, u_2, \dots, u_n</math> ，则对任意索引向量为 <math>i_1, i_2, \dots, i_n</math> 的元素，其第 <math>k</math> 维上的索引偏移量是 <math>i_k - l_k</math> ，起始地址偏移量是 <math>c_k(i_k-l_k)</math> ，因此起始地址为 <math>\mathrm{LOC}(a_{i_1,i_2, \dots,i_n}) = b + \sum_{k=1}^n c_k(i_k-l_k)</math> 。

==== 行主次序、列主次序 ====

内层数组作为元素被紧密排列在外层数组中时，可以看成一系列元素紧密排列，但是先排列内层数组，然后每个数组之间按照外层数组排列。因此当涉及多维数组、有多个索引上下界被指明时，默认按哪种顺序作为内层数据就会存在区别。

对于二维数组或者说矩阵，按照先排列一行中的元素，再把行排成整个矩阵，与先排列一列中的元素，再把列排成整个矩阵，分为两种顺序。前一种可以推广为先排列最后的索引，然后向前逐层进行排列；后一种是先排列最前的索引，然后向后逐层进行排列。由于习惯上矩阵元素下标先行后列，先紧密排列位于最前的索引，逐个向后，就称为'''行主次序'''('''row-major order''')；先紧密排列位于最后的索引，逐个向前，就称为'''列主次序'''('''column-major order''')。

如果元素是等大为 <math>c</math> 且行间、列间都没有间距，索引的下界和上界依次为 <math>l_1, l_2, \dots, l_n</math> 和 <math>u_1, u_2, \dots, u_n</math> ，则：
* 行主次序下， <math>c_i = c\prod_{m=i+1}^n (u_m - l_m)</math> ，且 <math>\mathrm{LOC}(a_{i_1,i_2, \dots,i_n}) = b + c\sum_{i=1}^n (i_k-l_k)\prod_{m=i+1}^n (u_m - l_m)</math> ，相当于这个元素是一个一维数组中索引为第 <math>\sum_{i=1}^n (i_k-l_k)\prod_{m=i+1}^n (u_m - l_m)</math> 的元素；
* 列主次序下， <math>c_i = c\prod_{m=1}^{i-1} (u_m - l_m)</math> ，且 <math>\mathrm{LOC}(a_{i_1,i_2,\dots,i_n}) = b + c\sum_{i=1}^n (i_k-l_k)\prod_{m=1}^{i-1} (u_m - l_m)</math> ，相当于这个元素是一个一维数组中索引为第 <math>\sum_{i=1}^n (i_k-l_k)\prod_{m=i+1}^n (u_m - l_m)</math> 的元素。

有时也将这个多维数组索引转化为一维数组索引的公式作为这个多维数组中索引转换的公式。

==== 非线性公式 ====

广义上，紧密排列且能够直接使用公式求出地址的就是数组，有时不要求数组元素的数组是同一大小的数组，而允许存在规律排列。比如允许[[下三角矩阵]]中的每一行被依次紧密排列。此时对应的公式不是上述乘法形式，但是也有类似的格式，通常视为也数组''类''存储结构，并且和多维数组一样可以存在一个索引转换的公式。


{{存储结构}}