给定一个二维数组，将其转换为Z-Order。

Question

给定一个二维数组，将其转换为Z-Order。

3

我希望你能帮助我理解这个转换过程。我想要将一个二维NxN矩阵递归地转换成其z-order版本。

例如，给定数组：

[ 1  2 ]
[ 3  4 ]

Z-order是指元素在屏幕上的叠放顺序。

[ 1 2 3 4]

z-order转换的递归步骤是什么？

- Derptacos

1

这里不太清楚你在问什么。你能否澄清一下？ - luiscubal

@luiscubal，你到底觉得不清楚什么？ - Nilzone-

在这个上下文中，“z-order”是什么意思，例如为什么“递归”很重要。 - luiscubal

下面的解释提供了一些有关z序的隐含方式的见解。在这种情况下，Z顺序是指遍历矩阵的顺序。 - Derptacos

1

@Derptacos 在2x2的情况下，任何你尝试进行的并行化都会导致程序运行变慢。而且，无论如何，我也不明白将其递归化如何有助于解决这个问题。如果有什么作用的话，那只会让它更难以处理，因为像OpenMP这样的工具可以很好地处理循环，但是在递归方面则会失败。 - luiscubal

显示剩余3条评论

2个回答

0

一个 2D 矩阵在内部行为上表现为一个 1D 数组，即它已经处于 "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)
}

- Alexandru Barbarosie

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 6502 · Accepted Answer

递归方式很简单：

访问左上角
访问右上角
访问左下角
访问右下角

代码实现：

#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)]);
    }
}

注意：

在上面的代码示例中，我创建了一个函数来接受一个名为“callback”的回调函数，该函数将以z顺序逐个调用矩阵元素。

为了允许同时使用支持双[]索引和可调用的任何内容作为矩阵和回调函数，我使用了C++模板。

在主程序中，我使用了一个整数的二维数组和一个函数作为矩阵，但是即使使用std :: vector >作为矩阵并提供operator()（double）作为回调函数的类的对象实例，代码也会编译。