将二维数组转换为一维数组并不难，但如何将超过二维的多维数组转换为一维数组呢？例如，假设我有 int [5][5][5] x 和 int [125] y，并且我想将 x[3][4][2] 的值放在 y 中的正确位置上，应该怎么做呢？
希望这样说得清楚了。
5个回答
40
这里已经有一些技术上不错的答案了，但以下是更直观的理解方式...
好的，所以你知道如何从一维情况转到二维情况。
一个一维数组看起来像这样：
int [5] :
+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | 3 | 4 |
| | | | | |
+-----+-----+-----+-----+-----+
一个二维数组看起来像这样：
int [5][5] :
+-----+-----+-----+-----+-----+
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
| | | | | |
+-----+-----+-----+-----+-----+
| 1,0 | 1,1 | 1,2 | 1,3 | 1,4 |
| | | | | |
+-----+-----+-----+-----+-----+
| 2,0 | 2,1 | 2,2 | 2,3 | 2,4 |
| | | | | |
+-----+-----+-----+-----+-----+
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |
| | | | | |
+-----+-----+-----+-----+-----+
| 4,0 | 4,1 | 4,2 | 4,3 | 4,4 |
| | | | | |
+-----+-----+-----+-----+-----+
你可以将转换为相应的一维数组想象成这样：
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - -
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 | 1,0 | 1,1 | 1,2 | 1,3 | 1,4 | etc.
| | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - -
vvv
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - -
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | etc.
| | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+- - -
但是另一种思考方式是将原始数组重新标记，就像这样：
int [5][5] :
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 | | 0 | 1 | 2 | 3 | 4 |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1,0 | 1,1 | 1,2 | 1,3 | 1,4 | | 5 | 6 | 7 | 8 | 9 |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2,0 | 2,1 | 2,2 | 2,3 | 2,4 | => | 10 | 11 | 12 | 13 | 14 |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 | | 15 | 16 | 17 | 18 | 19 |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4,0 | 4,1 | 4,2 | 4,3 | 4,4 | | 20 | 21 | 22 | 23 | 24 |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
2-D array index [i][j] => 1-D array index [i*5 + j]
......如果你这样考虑，三维情况只是遵循同样的原则（对于更高的维度也是如此——只是越来越难以可视化！）：
int [5][5][5] :
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
|+-----+-----+-----+-----+-----+ |+-----+-----+-----+-----+-----+
||+-----+-----+-----+-----+-----+ ||+-----+-----+-----+-----+-----+
|||+-----+-----+-----+-----+-----+ |||+-----+-----+-----+-----+-----+
||||1,0,0|1,0,1|1,0,2|1,0,3|1,0,4| |||| 25 | 26 | 27 | 28 | 29 |
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+
|||+---|0,0,0|0,0,1|0,0,2|0,0,3|0,0,4| |||+---| 0 | 1 | 2 | 3 | 4 |
||||1,1| | | | | | |||| 30| | | | | |
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+
|||+---|0,1,0|0,1,1|0,1,2|0,1,3|0,1,4| |||+---| 5 | 6 | 7 | 8 | 9 |
||||1,2| | | | | | |||| 35| | | | | |
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+
|||+---|0,2,0|0,2,1|0,2,2|0,2,3|0,2,4|=>|||+---| 10 | 11 | 12 | 13 | 14 |
||||1,3| | | | | | |||| 40| | | | | |
|||| +-----+-----+-----+-----+-----+ |||| +-----+-----+-----+-----+-----+
+||+---|0,3,0|0,3,1|0,3,2|0,3,3|0,3,4| +||+---| 15 | 16 | 17 | 18 | 19 |
+||1,4| | | | | | +|| 45| | | | | |
+| +-----+-----+-----+-----+-----+ +| +-----+-----+-----+-----+-----+
+---|0,4,0|0,4,1|0,4,2|0,4,3|0,4,4| +---| 20 | 21 | 22 | 23 | 24 |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
3-D array index [i][j][k] => 1-D array index [i*5*5 + j*5 + k]
- Matthew Slattery
3
1谢谢！很好的阐述方式！ - user436390
3对于 int[dimX][dimY][dimZ] 的更多细节：1-D 数组索引为 [i * dimY*dimZ + j * dimZ + k]。 - Steven Muhr
这个例子启发了我理解多项式方程和数组（向量）之间的关系。 - Hariharan
6
m0,m1,.. are dimensions
A(i,j,k,...) -> A0[i + j*m0 + k*m0*m1 + ...]
一个有用的C语言技巧:
double *A;
size_t m;
#define A(i,j) A[(i) + (j)*m];
- Anycorn
3
实际上，有一种非常酷的方式可以思考这个问题，这里还没有人发布过。
在最简单的情况下，您可以将X、Y、Z坐标想象为您创建的虚数系统中的数字。这些数字被写成XYZ，因此您的示例[3] [4] [2]将被写成：342
我们习惯于以八进制和十六进制思考，这意味着不是三百、四十二，而是三个64、四个8和两个1，或者是三个256、四个16和两个1。
这实际上就是您的虚数系统需要做的事情，但是每个数字都是该数组相应侧面长度的基数，乘以下一个较低的基数（除非没有，此时为1）。此计算中不使用最后一个数组长度，而仅用于限制循环。此计算中的排序基于您希望将侧面长度转换为线性元素的方式。
对于5x5x5数组，这很容易：
25s | 5s | 1s * 3 | 4 | 2 ----+----+--- 75 + 20 + 2 = 97
其他基数可能更复杂，特别是具有非均匀大小的情况，但这只是解决问题的另一种方式。
这是一个非均匀的565示例：
30s | 5s | 1s * 3 | 4 | 2 ----+----+--- 90 + 20 + 2 = 102
在最简单的情况下，您可以将X、Y、Z坐标想象为您创建的虚数系统中的数字。这些数字被写成XYZ，因此您的示例[3] [4] [2]将被写成：342
我们习惯于以八进制和十六进制思考，这意味着不是三百、四十二，而是三个64、四个8和两个1，或者是三个256、四个16和两个1。
这实际上就是您的虚数系统需要做的事情，但是每个数字都是该数组相应侧面长度的基数，乘以下一个较低的基数（除非没有，此时为1）。此计算中不使用最后一个数组长度，而仅用于限制循环。此计算中的排序基于您希望将侧面长度转换为线性元素的方式。
对于5x5x5数组，这很容易：
25s | 5s | 1s * 3 | 4 | 2 ----+----+--- 75 + 20 + 2 = 97
其他基数可能更复杂，特别是具有非均匀大小的情况，但这只是解决问题的另一种方式。
这是一个非均匀的565示例：
30s | 5s | 1s * 3 | 4 | 2 ----+----+--- 90 + 20 + 2 = 102
- SplinterReality
1
您可以有不同的方法将多维数组映射到线性数组中。关键是您必须选择一种约定。让我们采用以下约定。第一个索引指定块容器，第二个指定先前容器中的块，最后第三个索引是块内的偏移量。您可以轻松地将其推广到多维度，但让我们在此示例中保持为3：
#include <cstddef>
std::size_t linear_index
(std::size_t f,
std::size_t s,
std::size_t t,
std::size_t f_width,
std::size_t s_width)
{
return (f*f_width + s)*s_width + t;
}
- Khaled Alshaya
-1
你可以在 C# 中进行以下操作。
public class ArrayIndexer
{
private readonly int[] _bounds;
private readonly int[] _sum;
public ArrayIndexer(params int[] bounds)
{
_bounds = bounds;
// Pre-compute bounds sums for speed.
_sum = new int[bounds.Length - 1];
for (int i = 1, sum = _bounds[i - 1]; i < _bounds.Length; ++i, sum *= _bounds[i - 1])
_sum[i-1] = sum;
}
public T Index<T>(T[] array, params int[] indices)
{
if (indices.Length != _bounds.Length)
throw new ArgumentException("There should be as many indices as bounds", "indices");
var index = indices[0];
for (int i = 1, sum = _bounds[i - 1]; i < indices.Length; ++i, sum *= _bounds[i - 1])
index += sum * indices[i];
return array[index];
}
public T FastIndex<T>(T[] array, params int[] indices)
{
if (indices.Length != _bounds.Length)
throw new ArgumentException("There should be as many indices as bounds", "indices");
var index = indices[0];
for (int i = 1; i < indices.Length; ++i)
index += _sum[i-1] * indices[i];
return array[index];
}
}
或将其转换为 n 维数组。
public static class ArrayExtensions
{
public static Array CreateArray<T>(this T[] array1d, params int[] bounds)
{
var arrayNd = Array.CreateInstance(typeof(T), bounds);
var indices = new int[bounds.Length];
for (var i = 0; i < array1d.Length; ++i)
{
arrayNd.SetValue(array1d[i], indices);
for (int j = 0; j < bounds.Length; ++j)
{
if (++indices[j] < bounds[j])
break;
indices[j] = 0;
}
}
return arrayNd;
}
}
并进行测试。
int[] array3d =
new[]
{
0, 1, 2, 3,
4, 5, 6, 7,
8, 9, 10, 11,
12, 13, 14, 15,
16, 17, 18, 19,
20, 21, 22, 23
};
var copied3d = (int[, ,])array3d.CreateArray(4, 3, 2);
var indexer3d = new ArrayIndexer(4, 3, 2);
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 3; ++j)
{
for (int k = 0; k < 2; ++k)
{
var x = indexer3d.FastIndex(array3d, i, j, k);
var y = copied3d[i, j, k];
Debug.Print("Array[{0},{1},{2}] = {3} and {4} match = {5}", i, j, k, x, y, x == y);
}
}
}
- Rob Blackbourn
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接