c - C 中矩阵的迭代器和指针

Question

对于 JPEG 图像压缩，我以灰度级和 8 位像素处理图像

我有动态分配的这种类型的矩阵:

typedef char pixel_t;
pixel_t ** pix_matrix;

分配并填充它之后，我有一个二维数组，其中包含图片亮度的值(从-128到+127)。

对于 JPEG 压缩，我需要像这样以锯齿形迭代此数组:

所以我想为这种类型创建一个迭代器结构。该迭代器必须具有“当前”和“开始”成员，我希望这些成员是指向当前元素和矩阵第一个元素的指针。换句话说，我想存储地址而不是索引。但经过几个小时的测试、打印和研究，我找不到实现这一目标的方法。我必须使用什么类型的指针？如何让它指向我的矩阵的第一个地址？我的要求简单可行吗？

如果所有这些都是可能的，我怎样才能获取下一个元素以及当前元素的值？

Answer 1

您可以编写一个迭代器结构:

struct zigzag_t {
    int width;      // width, must be initialised
    int height;     // height, must be initialised
    int x;          // current x index
    int y;          // current y index
    int underway;   // dummy value to start at (0, 0)
};

您必须使用图像的宽度和高度进行初始化。编写一个迭代器函数，以便您可以像这样使用这个迭代器:

struct zigzag_t zz = {8, 8};

while (zigzag_next(&zz)) {
    printf("(%d, %d)\n", zz.y, zz.x);
}

迭代器本身并不太复杂:如果 x 和 y 索引的总和为奇数，则向西南方向行走，直到到达西边缘或南边缘。如果总和是偶数，你就向东北走，直到撞到北墙或东墙。如果您击中东北或西南边缘，则东边和南边优先。当您访问了 se 边缘后，迭代结束。

由于结构体以 x 和 y 均为零开始，因此第一个点是 (0, 1)。为了解决这个问题，使用了虚拟字段 underway，该字段也为零。

如果您想再次使用迭代器，则必须重置它。更好的是，定义并初始化一个新的迭代器。

迭代器函数:

int zigzag_next(struct zigzag_t *zz)
{
    int odd = (zz->x + zz->y) % 2;

    if (zz->underway == 0) {
        zz->x = zz->y = 0;
        zz->underway = 1;
        return 1;
    }

    if (odd) {
        /* walk southwest */

        int w_edge = zz->x == 0;
        int s_edge = zz->y == zz->height - 1;

        if (s_edge) {
            zz->x++;
            return zz->x < zz->width;
        } else if (w_edge) {
            zz->y++;
        } else {
            zz->x--;
            zz->y++;
        }
    } else {
        /* walk northeast */

        int e_edge = zz->x == zz->width - 1;
        int n_edge = zz->y == 0;

        if (e_edge) {
            zz->y++;
            return zz->y < zz->height;
        } else if (n_edge) {
            zz->x++;
        } else {
            zz->x++;
            zz->y--;
        }
    }

    return 1;
}

此解决方案返回 x 和 y 位置，您可以将其用作指向像素数据的双指针的索引。扩展该结构以保存指向像素数据的基指针并让迭代器函数返回指向像素的指针或NULL(如果迭代已用完)并不困难。

下面是一个带有指针的示例解决方案。

#include <stdlib.h>
#include <stdio.h>

typedef char pixel_t;

struct zigzag_t {
    pixel_t **p;    // base data
    int width;      // width, must be initialised
    int height;     // height, must be initialised
    int x;          // current x index
    int y;          // current y index
    int underway;   // dummy value to start at (0, 0)
};

pixel_t *zigzag_next(struct zigzag_t *zz)
{
    int odd = (zz->x + zz->y) % 2;

    if (zz->underway == 0) {
        zz->x = zz->y = 0;
        zz->underway = 1;
        return *zz->p;
    }

    if (odd) {
        /* walk southwest */

        int w_edge = zz->x == 0;
        int s_edge = zz->y == zz->height - 1;

        if (s_edge) {
            zz->x++;
            if (zz->x == zz->width) return NULL;
        } else if (w_edge) {
            zz->y++;
        } else {
            zz->x--;
            zz->y++;
        }
    } else {
        /* walk northeast */

        int e_edge = zz->x == zz->width - 1;
        int n_edge = zz->y == 0;

        if (e_edge) {
            zz->y++;
            if (zz->y == zz->height) return NULL;
        } else if (n_edge) {
            zz->x++;
        } else {
            zz->x++;
            zz->y--;
        }
    }

    return zz->p[zz->y] + zz->x;
}

int main()
{
    pixel_t *data[] = {
        "abcde", "fghij", "klmno", "pqrst", "uvwxy"
    };

    struct zigzag_t zz = {data, 5, 5};

    for (;;) {
        pixel_t *p = zigzag_next(&zz);

        if (p == NULL) break;
        putchar(*p);
    }
    putchar('\n');

    return 0;
}

该解决方案是 C 解决方案。没有 begin 成员函数；初始化是通过简单的结构初始化完成的。没有增量运算符，也没有 end 成员函数；向前移动迭代器并检查结尾是在一个普通的旧函数中完成的。

您已标记问题 C，但迭代器在 C++ 中更常见，它们可以作为类实现。上面的 C 示例可以作为此类实现的基础。