特殊交错存储规则下m×n 2D数组(i,j)元素地址表达式推导

前提约定 #

我们先明确所有前置条件：

• 数组规模为 m 行 × n 列，行索引i、列索引j均从0开始计数
• 单个元素占用内存大小为 s（按字节寻址时即为单元素字节数）
• 数组内存基地址为 base，也就是元素(0,0)的内存地址
• 存储规则如下：
  1. 从k=0开始逐层处理：先按行优先存储第k行所有未被存储过的元素，再按列优先存储第k列所有未被存储过的元素
  2. 循环执行直到所有元素存储完成

推导过程 #

步骤1：确定元素所属的处理层 #

任意元素(i,j)所属的处理层为 k = min(i,j)，即行号和列号的较小值：

• 如果i ≤ j，说明该元素属于第k=i行的存储段
• 如果j < i，说明该元素属于第k=j列的存储段

步骤2：计算前k层总存储元素数 #

每一层t（0 ≤ t < k）的存储元素数由两部分组成：第t行的n-t个元素，和第t列的m-t-1个元素，求和化简后可得前k层的总元素数为：
total_before = k * (m + n - k)

步骤3：计算当前层内的偏移量 #

分两种情况计算元素在当前k层内的偏移：

1. 当i ≤ j时（行存储段）：第k行从列号k开始存储，所以当前层偏移为 j - k
2. 当j < i时（列存储段）：当前层先存了n - k个行元素，列存储从行号k+1开始，所以当前层偏移为 (n - k) + (i - k - 1) = n + i - 2k - 1

步骤4：最终地址公式 #

总元素偏移量为前k层总元素数加当前层偏移，乘以单元素大小后加基地址，可得最终地址：

合并写法

addr = base + s * [ k*(m+n -k) + (i<=j ? (j -k) : (n + i - 2*k -1)) ]
其中 k = min(i,j)

分情况写法

• 若i ≤ j：addr = base + s * [ i*(m+n -i) + j - i ]
• 若j < i：addr = base + s * [ j*(m+n -j) + n + i - 2*j - 1 ]

验证示例 #

以3行4列（m=3，n=4）的数组为例，元素(2,1)的i=2>j=1，k=1：

• 前1层总元素数：1*(3+4-1)=6
• 当前层偏移：4 + 2 - 2*1 -1 =3
• 总偏移为6+3=9，和实际存储顺序完全匹配

内容的提问来源于stack exchange，提问作者Mihir Waykole