如何交换数组元素以将数组从列式表示转换为行式表示

Question

例如：数组

a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3

代表下表

a1, b1, c1, d1
a2, b2, c2, d2
a3, b3, c3, d3

现在我喜欢将数组变成以下形式

a1, b1, c1, d1, a2, b2, c2, d2, a3, b3, c3, d3

是否存在一种算法，它将数组（来自第一种形式）和表的维度作为输入参数，并将数组转换为第二种形式？ 我想到了一种不需要分配额外内存的算法，相反我认为应该可以通过元素交换操作来完成这项工作。

Answer 1

您正在寻找的术语是就地矩阵转置，这是实现。

Answer 2

维基百科专门写了一篇文章来介绍这个过程，称为就地矩阵转置。

http://en.wikipedia.org/wiki/In-place_matrix_transposition

Answer 3

这只不过是一个就地矩阵转置。一些伪代码：

for n = 0 to N - 2
    for m = n + 1 to N - 1
        swap A(n,m) with A(m,n)

如您所见，您需要 2 个索引来访问一个元素。这可以通过将

(n,m)

转换为

nP+m

来完成，其中

P

是列数。

Answer 4

何苦呢？ 如果它们排列在一个一维数组中，并且您知道逻辑行/跨度中有多少个元素，那么您可以通过一些算术按顺序获得任何索引。

int index(int row, int col, int elements)
{
  return ((row * elements) + col);
}

int inverted_index(int row, int col, int elements)
{
  return ((col * elements) + row);
}

然后，当您访问元素时，您可以说...

array[index(row, col, elements)];
array[inverted_index(row, col, elements)];

我大部分基本的数组操作都是这样进行的，正是因为我可以通过不同的索引来转置矩阵，而无需任何内存改组。 这也是您可以用计算机完成的最快的事情。

您可以遵循相同的原则，并使用您自己的一些算术来满足最终示例的需求，从而对第一个数组进行寻址。