c++ - 给定2D数组，转换为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 > >作为矩阵，并使用提供operator()(double)作为回调的类的对象实例，该代码也可以进行编译。