数据结构-多维数组的超平面视角：从索引到地址的映射
数据结构-多维数组的超平面视角：从索引到地址的映射
核心思想
多维数组在逻辑上是嵌套的子空间结构，在物理上是一段连续的内存。
寻址的本质：每一维的索引跳过若干个完整的子空间；未满的那个子空间，进入下一维继续定位，直到 0 维。
什么是多维数组？
多维数组是一个定义在离散笛卡尔积上的函数：
A:D→VA: D \to VA:D→V
其中：
D={0,...,b1−1}×{0,...,b2−1}×...×{0,...,bn−1}D = \{0,...,b_1-1\} \times \{0,...,b_2-1\} \times ... \times \{0,...,b_n-1\}D={0,...,b1−1}×{0,...,b2−1}×...×{0,...,bn−1}（定义域）
VVV = 数据类型的值域（如 int, float）
- bmb_mbm = 第 mmm 维的大小（该维度拆出的子空间个数）
- 维数 = 笛卡尔积的阶数（坐标分量的个数）
- 元素由一个 nnn 元组 (i1,i2,...,in)(i_1, i_2, ..., i_n)(i1,i2,...,in) 唯一确定
逻辑结构：降维切片
几何图解（三维）
k轴 (b₃=4) ↑ │ ┌─────────┐ │ ╱ ╱│ │ ╱ 平面1 ╱ │ │┌─────────┐ │ A[2][3][4] ││ 平面0 │ │ ││ │ │ 总共 2×3×4 = 24 个元素 ││ │ ╱ 连续存放在内存中 │└─────────┘ └──────────→ j轴 (b₂=3) ╱ ╱ i轴 (b₁=2) 降维过程：每次固定一个轴，维度降低一级
对于 A[b₁][b₂][b₃]，访问 A[i][j][k] 的过程：
第1步：固定 i（选第几个平面）— 3维 → 2维
i=0 → 取第0个平面（12个元素） i=1 → 取第1个平面（12个元素） 跳过 i 个完整的 (n-1)维 子空间 [3][4] 第 i+1 个平面未满 → 进入内部继续定位 第2步：固定 j（选第几行）— 2维 → 1维
j=0 → 取第0行（4个元素） j=1 → 取第1行（4个元素） j=2 → 取第2行（4个元素） 跳过 j 个完整的 (n-2)维 子空间 [4] 第 j+1 行未满 → 进入内部继续定位 第3步：固定 k（选第几个元素）— 1维 → 0维
k=0,1,2,3 → 跳过 k 个 (n-3)维 子空间（单个元素） → 到达 0 维，定位完成 数学表述
D3={0,...,b1−1}×{0,...,b2−1}×{0,...,b3−1}(3维)D_3 = \{0,...,b_1-1\} \times \{0,...,b_2-1\} \times \{0,...,b_3-1\} \quad \text{(3维)}D3={0,...,b1−1}×{0,...,b2−1}×{0,...,b3−1}(3维)
↓ 固定 i=i0\downarrow \text{ 固定 } i = i_0↓ 固定 i=i0
D2={0,...,b2−1}×{0,...,b3−1}(2维平面)D_2 = \{0,...,b_2-1\} \times \{0,...,b_3-1\} \quad \text{(2维平面)}D2={0,...,b2−1}×{0,...,b3−1}(2维平面)
↓ 固定 j=j0\downarrow \text{ 固定 } j = j_0↓ 固定 j=j0
D1={0,...,b3−1}(1维行)D_1 = \{0,...,b_3-1\} \quad \text{(1维行)}D1={0,...,b3−1}(1维行)
↓ 固定 k=k0\downarrow \text{ 固定 } k = k_0↓ 固定 k=k0
D0={⋅}(0维标量)D_0 = \{·\} \quad \text{(0维标量)}D0={⋅}(0维标量)
每次索引 = 固定一个坐标轴 = 超平面切片 = 维度降低一级
物理存储：连续线性内存
所有元素在内存中连续存储，没有任何"分界"：
内存布局（行优先）： [a₀₀₀][a₀₀₁][a₀₀₂][a₀₀₃][a₀₁₀][a₀₁₁]...[a₁₀₀][a₁₀₁]... “平面”、"行"只是逻辑标签，物理上是一串连续的字节。
地址计算公式
核心逻辑：逐层跳过 + 逐层细化
以 A[2][3][4] 访问 A[1][2][3] 为例。
每一维的索引，跳过若干个完整的子空间；未满的那个子空间，进入下一维继续定位，直到 0 维：
第1步：i=1 跳过 1 个完整的 (n-1)维 子空间 [3][4] → 第 2 个平面未满，进入内部继续定位 第2步：j=2 跳过 2 个完整的 (n-2)维 子空间 [4] → 第 3 行未满，进入内部继续定位 第3步：k=3 跳过 3 个完整的 (n-3)维 子空间（单个元素） → 到达 0 维，定位完成 偏移量 = 每一步跳过的子空间个数 × 该子空间的大小，逐层累加：
偏移 = i × size(n-1维子空间) + j × size(n-2维子空间) + k × size(n-3维子空间) = 1 × (3×4) + 2 × (4) + 3 × (1) = 12 + 8 + 3 = 23 个元素 转成字节：LOC=LOC0+23×L=LOC0+92LOC = LOC_0 + 23 \times L = LOC_0 + 92LOC=LOC0+23×L=LOC0+92
子空间大小的递推
每一级子空间的大小 = 下一级的个数 × 下一级的大小：
| 子空间维度 | 大小（元素数） | 递推关系 | 具体值 |
|---|---|---|---|
| 0维（元素） | 1 | 基础单位 | 1 |
| 1维（行） | b3×1=b3b_3 \times 1 = b_3b3×1=b3 | b3b_3b3 个元素 | 4 |
| 2维（平面） | b2×b3b_2 \times b_3b2×b3 | b2b_2b2 个行 | 12 |
转成字节就是权重系数 cmc_mcm（乘以 LLL）：
c3=1×L=4,c2=b3×c3=16,c1=b2×c2=48c_3 = 1 \times L = 4, \quad c_2 = b_3 \times c_3 = 16, \quad c_1 = b_2 \times c_2 = 48c3=1×L=4,c2=b3×c3=16,c1=b2×c2=48
三维公式
LOC=LOC0+i×c1+j×c2+k×c3LOC = LOC_0 + i \times c_1 + j \times c_2 + k \times c_3LOC=LOC0+i×c1+j×c2+k×c3
每一项的含义：该维索引（跳过几个子空间） × 该维子空间的字节大小 = 跳过的字节数。
推广到 n 维
对于 A[b₁][b₂]...[bₙ]，访问 A[i₁][i₂]...[iₙ]：
LOC=LOC0+∑m=1ncm⋅imLOC = LOC_0 + \sum_{m=1}^{n} c_m \cdot i_mLOC=LOC0+m=1∑ncm⋅im
展开权重：
LOC=LOC0+∑m=1n(∏p=m+1nbp)⋅im⋅LLOC = LOC_0 + \sum_{m=1}^{n} \left( \prod_{p=m+1}^{n} b_p \right) \cdot i_m \cdot LLOC=LOC0+m=1∑n(p=m+1∏nbp)⋅im⋅L
mmm 是求和的循环变量（从第 1 维遍历到第 nnn 维），不是数组索引 jjj 或 kkk。
∏p=m+1nbp\prod_{p=m+1}^{n} b_p∏p=m+1nbp 就是第 mmm 维子空间的大小（元素个数），乘以 LLL 得到字节数。
逻辑始终不变：从最外层到最内层，每层跳过 imi_mim 个完整子空间，未满的进入下一层继续定位。
权重系数 cmc_mcm（递推形式）
定义 cmc_mcm = 第 mmm 维走一步跳过的字节数：
cn=L,cm=bm+1×cm+1(m=n−1,n−2,...,1)c_n = L, \quad c_m = b_{m+1} \times c_{m+1} \quad (m = n-1, n-2, ..., 1)cn=L,cm=bm+1×cm+1(m=n−1,n−2,...,1)
其中 bm+1b_{m+1}bm+1 是第 mmm 维的子空间内部有多少个下一级子空间，cm+1c_{m+1}cm+1 是每个下一级子空间的字节大小。
bmb_mbm 与 cmc_mcm 的关系
| 符号 | 含义 | 类比（书架） |
|---|---|---|
| bmb_mbm | 第 mmm 维有几个子空间（结构形状） | 第 mmm 级有几格 |
| cmc_mcm | 第 mmm 维走一步跳多少字节（寻址步长） | 第 mmm 级一格有多宽 |
| imi_mim | 第 mmm 维选第几个（具体索引） | 第 mmm 级选第几格 |
| LLL | 递推起点，最底层单个元素的字节大小 | 每本书的厚度 |
具体例子：A[2][3][4]，sizeof(int) = 4
计算权重（从内往外推）：
c3=L=4（1个元素 = 4字节）c_3 = L = 4 \quad \text{（1个元素 = 4字节）}c3=L=4（1个元素 = 4字节）
c2=b3×c3=4×4=16（1行有 b3=4 个元素 = 16字节）c_2 = b_3 \times c_3 = 4 \times 4 = 16 \quad \text{（1行有 $b_3=4$ 个元素 = 16字节）}c2=b3×c3=4×4=16（1行有 b3=4 个元素 = 16字节）
c1=b2×c2=3×16=48（1层有 b2=3 行 = 48字节）c_1 = b_2 \times c_2 = 3 \times 16 = 48 \quad \text{（1层有 $b_2=3$ 行 = 48字节）}c1=b2×c2=3×16=48（1层有 b2=3 行 = 48字节）
计算 A[1][2][3] 的地址：
LOC=LOC0+1×48+2×16+3×4=LOC0+48+32+12=LOC0+92LOC = LOC_0 + 1 \times 48 + 2 \times 16 + 3 \times 4 = LOC_0 + 48 + 32 + 12 = LOC_0 + 92LOC=LOC0+1×48+2×16+3×4=LOC0+48+32+12=LOC0+92
分解理解：
- 1×481 \times 481×48：跳过 1 个完整平面
[3][4]（进入第1层） - 2×162 \times 162×16：平面未满，跳过 2 整行
[4]（进入第2行） - 3×43 \times 43×4：行未满，跳过 3 个元素（到达目标）
子空间的计数公式
k 维子空间的个数
N(k维子空间)=∏i=1n−kbiN(\text{k维子空间}) = \prod_{i=1}^{n-k} b_iN(k维子空间)=i=1∏n−kbi
含义：从第 1 维到第 (n−k)(n-k)(n−k) 维依次固定，第 iii 维沿轴跨越 bib_ibi 个位置，可以固定在 000 到 bi−1b_i-1bi−1 的任意一个位置，所有组合的总数就是 ∏i=1n−kbi\prod_{i=1}^{n-k} b_i∏i=1n−kbi。
每个 k 维子空间的大小
Size(k维子空间)=∏i=n−k+1nbiSize(\text{k维子空间}) = \prod_{i=n-k+1}^{n} b_iSize(k维子空间)=i=n−k+1∏nbi
含义：固定前 (n−k)(n-k)(n−k) 维后，剩下的后 kkk 维自由变化，元素总数 = 后 kkk 个维度大小之积。下标从 n−k+1n-k+1n−k+1 开始是因为取的是后 kkk 个维度。
验证关系
Nk×Sizek=∏i=1nbi=总元素数✓N_k \times Size_k = \prod_{i=1}^{n} b_i = \text{总元素数} \quad \checkmarkNk×Sizek=i=1∏nbi=总元素数✓
示例：A[2][3][4]
| 维度 | 子空间个数 | 每个大小 | 总元素数 |
|---|---|---|---|
| 3维（整体） | 1 | 2×3×4=242 \times 3 \times 4 = 242×3×4=24 | 24 |
| 2维（平面） | b1=2b_1 = 2b1=2 | b2×b3=3×4=12b_2 \times b_3 = 3 \times 4 = 12b2×b3=3×4=12 | 24 |
| 1维（行） | b1×b2=2×3=6b_1 \times b_2 = 2 \times 3 = 6b1×b2=2×3=6 | b3=4b_3 = 4b3=4 | 24 |
| 0维（点） | b1×b2×b3=24b_1 \times b_2 \times b_3 = 24b1×b2×b3=24 | 1 | 24 |
与混合进制数系统的类比
数组地址计算本质上是**混合进制（Mixed-radix）**的位置表示。
十进制数 253（每位基数都是 10）：
253=2×102+5×101+3×100253 = 2 \times 10^2 + 5 \times 10^1 + 3 \times 10^0253=2×102+5×101+3×100
数组偏移 A[i][j][k]（每维"基数"不同：b1,b2,b3b_1, b_2, b_3b1,b2,b3）：
offset=i×(b2×b3)+j×b3+k×1offset = i \times (b_2 \times b_3) + j \times b_3 + k \times 1offset=i×(b2×b3)+j×b3+k×1
给定偏移量反推索引（类似进制转换）：
i=⌊offset / (b2×b3)⌋i = \lfloor offset \;/\; (b_2 \times b_3) \rfloori=⌊offset/(b2×b3)⌋
j=⌊(offset mod (b2×b3)) / b3⌋j = \lfloor (offset \bmod (b_2 \times b_3)) \;/\; b_3 \rfloorj=⌊(offsetmod(b2×b3))/b3⌋
k=offset mod b3k = offset \bmod b_3k=offsetmodb3
代码实现
//// Created by elliot on 2/16/26.//#ifndefDATA_STRUCTURE_LEARN_SEQ_ARRAY_HPP#defineDATA_STRUCTURE_LEARN_SEQ_ARRAY_HPP#include<cstdint>#include<memory>#include<stdexcept>#include<vector>#include<initializer_list>// N维数组 - 顺序存储（行优先，一维扁平数组）template<typenameT>classSeqArray{public:// InitArray - 构造n维数组，bounds为各维长度// 例: SeqArray<int>({3, 4, 5}) 构造 3x4x5 的三维数组explicitSeqArray(std::initializer_list<uint64_t> bounds);explicitSeqArray(const std::vector<uint64_t>& bounds);// DestroyArray - unique_ptr 自动销毁~SeqArray()=default;// Value - 根据下标取值// 例: arr.get({1, 2, 3}) 取第[1][2][3]个元素const T&get(std::initializer_list<uint64_t> indices)const;// Assign - 根据下标赋值// 例: arr.set({1, 2, 3}, value)voidset(std::initializer_list<uint64_t> indices,const T& value);// 维数[[nodiscard]]uint64_tdimensions()const;// 第i维的长度[[nodiscard]]uint64_tbound(uint64_t dim)const;//最多能够存储的元素个数[[nodiscard]]uint64_ttotal_size()const;private: std::unique_ptr<T[]> _data;// 扁平一维数组 std::vector<uint64_t> _bounds;// 各维长度 {b1, b2, ..., bn} std::vector<uint64_t> _constants; // 映射常量 ci = b(i+1)*b(i+2)*...*bn, cn=1 uint64_t _total; // 总元素数 = b1*b2*...*bn// 根据多维下标计算一维偏移量// offset = j1*c1 + j2*c2 + ... + jn*cnuint64_t_offset(const std::vector<uint64_t>& indices)const;// 初始化 _constants 和 _total void _init_constants();};// ==================== 实现 ====================template<typenameT>SeqArray<T>::SeqArray(std::initializer_list<uint64_t> bounds):SeqArray(std::vector<uint64_t>(bounds)){}template<typenameT>SeqArray<T>::SeqArray(const std::vector<uint64_t>& bounds):_bounds(bounds){_init_constants(); _data = std::make_unique<T[]>(_total);}template<typenameT>const T&SeqArray<T>::get(std::initializer_list<uint64_t> indices)const{return _data[_offset(indices)];}template<typenameT>voidSeqArray<T>::set(std::initializer_list<uint64_t> indices,const T& value){ _data[_offset(indices)]= value;}template<typenameT>uint64_tSeqArray<T>::dimensions()const{return _bounds.size();}template<typenameT>uint64_tSeqArray<T>::bound(uint64_t dim)const{return _bounds[dim];}template<typenameT>uint64_tSeqArray<T>::total_size()const{return _total;}template<typenameT>uint64_tSeqArray<T>::_offset(const std::vector<uint64_t>& indices)const{if(indices.size()!= _bounds.size())throw std::invalid_argument("维度不匹配");uint64_t offset =0;for(uint64_t i =0; i < indices.size();++i){if(indices[i]>= _bounds[i])throw std::out_of_range("索引越界"); offset += indices[i]* _constants[i];}return offset;}template<typenameT>voidSeqArray<T>::_init_constants(){// _constants[i] = b(i+1) * b(i+2) * ... * bn// _constants[n-1] = 1 uint64_t n = _bounds.size(); _constants.resize(n); _constants[n -1]=1;//从n-1维到0维for(uint64_t i = n -1; i >0;--i){ _constants[i -1]= _bounds[i]* _constants[i];} _total = _bounds[0]* _constants[0];}#endif//DATA_STRUCTURE_LEARN_SEQ_ARRAY_HPP
