无法理解这种转换。我想递归地将 2D NxN 矩阵转换为其 z 顺序版本。
例如给定数组:
[ 1 2 ]
[ 3 4 ]
Z 阶是
[ 1 2 3 4]
z 顺序转换的递归步骤是什么?
无法理解这种转换。我想递归地将 2D NxN 矩阵转换为其 z 顺序版本。
例如给定数组:
[ 1 2 ]
[ 3 4 ]
Z 阶是
[ 1 2 3 4]
z 顺序转换的递归步骤是什么?
递归方式很简单:
在代码中
#include <iostream>
template<typename M, typename CBACK>
void zorder(const M& m, int y0, int x0, int size,
CBACK cback)
{
if (size == 1) {
// Base case, just one cell
cback(m[y0][x0]);
} else {
// Recurse in Z-order
int h = size/2;
zorder(m, y0, x0, h, cback); // top-left
zorder(m, y0, x0+h, h, cback); // top-right
zorder(m, y0+h, x0, h, cback); // bottom-left
zorder(m, y0+h, x0+h, h, cback); // bottom-right
}
}
void print(int x) {
std::cout << x << " ";
}
int main(int argc, const char *argv[]) {
int x[][4] = {{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9, 10, 11, 12},
{13, 14, 15, 16}};
zorder(x, 0, 0, 4, print);
std::cout << std::endl;
return 0;
}
该程序的输出是
1 2 5 6 3 4 7 8 9 10 13 14 11 12 15 16
请注意,还有另一种非递归方法:要以 z 顺序访问元素,您只需遍历一个计数器并将奇数位作为 y,将偶数位作为 x(从 0 开始计数):
int zorder_x_of(int index) {
int x = 0;
for (int b=0,k=0; (1<<b) <= index; b+=2,k++) {
x += ((index & (1<<b)) != 0) << k;
}
return x;
}
int zorder_y_of(int index) {
return zorder_x_of(index>>1);
}
template<typename M, typename CBACK>
void zorder2(const M& m, int size, CBACK cback)
{
for (int i=0; i<size*size; i++) {
cback(m[zorder_y_of(i)][zorder_x_of(i)]);
}
}
笔记:
在上面的代码示例中,我创建了一个函数,该函数接受一个“回调”(名为cback
),该函数将使用矩阵的元素,一次一个,以 z 顺序调用。
为了允许将任何支持双[]
索引和任何可以调用的东西用作矩阵和回调,我使用了 C++ 模板。
在作为矩阵的主程序中,我使用了一个二维整数数组和一个函数,但是代码甚至会编译,例如使用std::vector< std::vector< double > >
as 矩阵和提供operator()(double)
回调的类的对象实例。
二维矩阵在内部表现为一维数组,即它已经处于“Z 顺序”。
只需遍历指向第一个元素的指针,直到NxM
其中N
的列M
数和行数。
例子:
int arr[2][2] = {{2,4},{3,5}};
for (int i=0; i<2 * 2; ++i){
std::cout << *(&arr[0][0] + i); // or *(arr + i)
}