在结构中需要一个 "variable" 大小的二维数组

Question

我正在尝试实现一个单元格网格，类似于 Conway 的生命游戏。

虽然每个单独的网格在两个维度上都应具有固定大小，但我想要一个允许在两个维度上具有任意大小的网格结构。

这类似于数组可以是任意大小，但数组一旦初始化就具有固定大小。

这是我目前拥有的：

typedef struct Cell {
    int data;
    // stuff to be added later
} Cell;

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell cell[][];
} Grid;

Grid initGrid(unsigned width, unsigned height) {
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc( sizeof(Cell)*width*height );
    return g;
}

但是我得到以下编译时错误：

main.c|12|note: declaration of `‘cell’ as multidimensional array must have bounds for all dimensions except the first|

How can I define a Grid data type with flexible size?

Post scriptum：作为一个 C 新手，我认为下面的方法可行：

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell cell[width][height];
} Grid;

Post post scriptum: 每当我使用malloc时，我总是感到不安。我在这里做（或试图做）什么可怕的错误吗？

Answer 1

你不能用 C 中的双索引 (cell[x][y]) 来做到这一点，没有办法表示每行要跳转的字节数是动态的。

所以，最好的（在我看来）方法是使用 one-dimensional 数组手动进行索引。

放个平原：

Cell *cell;

在 struct 中（保持 width 和 height）然后索引如下：

set_cell(Grid *g, unsigned int x, unsigned int y, Cell value)
{
  g->cell[y * g->width + x] = value;
}

编译器不太可能将其内联，而且会非常紧凑。可能比使用更多内存和另一层间接的锯齿状数组”方法更快。

分配简单：

Grid initGrid(unsigned int width, unsigned int height)
{
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc(width * height * sizeof *g.cell);
    // add assert or error here, can't return NULL for value type
    return g;
}

如果你也想 heap-allocate Grid，你可以 co-allocate 它的元素。

是的，您需要在完成分配后 free() 分配，以免内存泄漏。严格来说，在现代系统上，OS 无论如何都会在程序结束时释放所有资源，但无论如何释放都是一种很好的形式：

void destroyGrid(Grid g)
{
  free(g.cell);
}

Answer 2

你在这里很不走运，因为在 C 中没有办法在 struct 定义中使用可变数组长度。你可以做的是：

typedef struct Grid {
    unsigned width, height;
    void* cell_internal;    //Type: Cell(*)[height]
} Grid;

#define cell(myGrid) ((Cell(*)[(myGrid).height])(myGrid).cell_internal)

//in the constructor of Grid
newGrid->width = ...;
newGrid->height = ...;
cell(*newGrid) = malloc(newGrid->width*sizeof(*cell(*newGrid)));
for(unsigned x = 0; x < newGrid->width; x++) {
    for(unsigned y = 0; y < newGrid->height; y++) {
        cell(*newGrid)[x][y] = ...;
    }
}

这是一个肮脏的小 hack，但它应该可以正常工作。最酷的部分是，您可以简单地使用 cell(aGrid)[x][y] 来处理您的网格单元格。缺点是，它确实完全掩盖了实际发生的事情。而真正能读懂cell()宏的作用的人并不多。（提示：它只是将 void* 转换为指向列数组 Cell(*)[myGrid.height] 的指针，无论 myGrid.height 在那个时间点可能是什么。）

当然，你可以更明确一点：

typedef struct Grid {
    unsigned width, height;
    void* cell_internal;    //Type: Cell(*)[height]
} Grid;

//in the constructor of Grid
newGrid->width = ...;
newGrid->height = ...;
Cell (*cells)[newGrid->height] = malloc(newGrid->width*sizeof(*cells));
newGrid->cell_internal = cells;
for(unsigned x = 0; x < newGrid->width; x++) {
    for(unsigned y = 0; y < newGrid->height; y++) {
        cells[x][y] = ...;
    }
}

这种方法的缺点是，您需要在使用

处理单元格数据的每个函数中为 cell_internal 指针显式创建别名指针

Cell (*cells)[myGrid->height] = myGrid->cell_internal;

可能这是更好的方法，因为它似乎可以被更多人阅读。

Answer 3

使用灵活的数组。使用两个 malloc() 调用是微不足道的，如果您想要突破对齐限制或严格别名的限制，或者想要编写代码来强制 [=12] 的部分对齐，则可以只使用一个调用=]用于存储Cell结构。

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell[];
} Grid;

Grid *initGrid(unsigned width, unsigned height )
{
    // the Grid structure itself
    size_t bytesNeeded = sizeof( Grid );

    // space for pointers
    bytesNeeded += height * sizeof( Cell * );

    Grid *g = malloc( bytesNeeded );
    g->width = width;
    g->height = height;

    // get all the data needed with one malloc call
    g->cell[ 0 ] = malloc( width * height * sizeof( Cell ) );

    // fill in the pointers
    for ( unsigned ii = 1; ii < height; ii++ )
    {
        g->cell[ ii ] = g->cell[ 0 ] + ii * width;
    }

    return g;
}

void freeGrid( Grid *g )
{
    free( g->cell[ 0 ] );
    free( g );
}

如果您不介意突破严格别名的限制，您可以使用灵活的数组和对 malloc() 的一次调用来做到这一点（它留作 reader 的练习强制数据部分的对齐，这样就没有潜在的对齐问题——这绝对是可能的）：

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell[];
} Grid;

Grid *initGrid(unsigned width, unsigned height )
{
    // the Grid structure itself
    size_t bytesNeeded = sizeof( Grid );

    // space for pointers
    bytesNeeded += height * sizeof( Cell * );

    // space for data
    bytesNeeded += width * height * sizeof( Cell );

    Grid *g = malloc( bytesNeeded );
    g->width = width;
    g->height = height;

    // fill in the pointers
    // (technically a strict-aliasing/alignment violation as it assumes
    // that &(g->cell[ height ]) is suitable to store a Cell...)
    for ( unsigned ii = 0; ii < height; ii++ )
    {
        g->cell[ ii ] = ( Cell * ) &(g->cell[ height ]) +
            ii * width;
    }

    return g;
}

Answer 4

关注这个优秀的post： How do I work with dynamic multi-dimensional arrays in C? 阅读@JensGustedt post 并关注他的 link variable length arrays (VLAs)

其实是有办法的——我跟着他post写了一个小测试程序来验证：

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

int main(int argc, char ** argv)
{
    unsigned int height = 100;
    unsigned int width = 10;

    int (*array)[width] = malloc (sizeof(int[height][width]));

    array[90][2] = 1231;
    printf("%d", array[90][2]);
}

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

int main(int argc, char ** argv)
{
    unsigned int height;
    unsigned int width;
    int i,j;

    printf("enter width: ");
    scanf("%d", &width);
    printf("enter height: ");
    scanf("%d", &height);
    int (*array)[width] = malloc (sizeof(int[height][width]));

    for (i = 0; i < height; i++ )
        for (j = 0; j < width; j++ )
            array[i][j] = i;

    for (i = 0; i < height; i++ ) {
        for (j = 0; j < width; j++ )
            printf("%d ", array[i][j]);
        printf("\n");
    }
}

和控制台：

enter width: 10
enter height: 6
0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 2 
3 3 3 3 3 3 3 3 3 3 
4 4 4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5

我承认这令人惊讶 - 我不知道这存在...

编辑 - 使用结构：

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

typedef struct Cell {
    int data;
    // stuff to be added later
} Cell;

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell;
} Grid;

Grid initGrid(unsigned width, unsigned height) {
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc( sizeof(Cell[height][width]) );
    return g;
}
int main(int argc, char ** argv)
{
    unsigned int height;
    unsigned int width;
    int i,j;
    Grid test;

    printf("enter width: ");
    scanf("%d", &width);
    printf("enter height: ");
    scanf("%d", &height);
    test = initGrid (width, height);
    Cell (*array)[width] = test.cell;

    for (i = 0; i < height; i++ )
        for (j = 0; j < width; j++ )
            array[i][j].data = i;

    for (i = 0; i < height; i++ ) {
        for (j = 0; j < width; j++ )
            printf("%d ", array[i][j].data);
        printf("\n");
    }
}

控制台输出：

enter width: 20
enter height: 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

有一个铸造警告，我没有时间解决，但可以实现这个想法 - 只需干净地做......再次强调，这是一个 POC，而不是一个实际的程序

在结构中需要一个 "variable" 大小的二维数组

Need a two-dimensional array of "variable" size in a struct

c

arrays

struct

multidimensional-array

dynamic-memory-allocation