如何为2D阵列动态分配连续的内存块

Question

如果我像这样分配一个2D数组[N] [N] ; 它将分配一个连续的内存块.

但是,如果我尝试动态这样做:

int **a = malloc(rows * sizeof(int*));
for(int i = 0; i < rows; i++) 
   a[i] = malloc(cols * sizeof(int));

这样可以在行中的元素之间保持单位跨度,但行之间可能不是这种情况.

一种解决方案是从2D转换为1D,除此之外,还有另一种方法吗？

Answer 1

如果在编译时已知数组维度:

#define ROWS ...
#define COLS ...

int (*arr)[COLS] = malloc(sizeof *arr * ROWS);
if (arr) 
{
  // do stuff with arr[i][j]
  free(arr);
}

如果在编译时未知数组维度,并且您使用的是C99编译器或支持可变长度数组的C2011编译器:

size_t rows, cols;
// assign rows and cols
int (*arr)[cols] = malloc(sizeof *arr * rows);
if (arr)
{
  // do stuff with arr[i][j]
  free(arr);
}

如果在编译时未知数组维度,并且您没有使用支持可变长度数组的C99编译器或C2011编译器:

size_t rows, cols;
// assign rows and cols
int *arr = malloc(sizeof *arr * rows * cols);
{
  // do stuff with arr[i * rows + j]
  free(arr);
}

Answer 2

事实上,n维数组(在堆栈上分配)实际上只是一维向量.多重索引只是语法糖.但是你可以编写一个访问器函数来模拟你想要的东西:

int index_array(int *arr, size_t width, int x, int y)
{
    return arr[x * width + y];
}

const size_t width = 3;
const size_t height = 2;
int *arr = malloc(width * height * sizeof(*arr));

// ... fill it with values, then access it:

int arr_1_1 = index_array(arr, width, 1, 1);

但是,如果你有C99支持,那么可以声明一个指向数组的指针,你甚至可以使用语法糖:

int (*arr)[width] = malloc(sizeof((*arr) * height);
arr[x][y] = 42;

Answer 3

假设您要动态分配ROWS行和COLS列的二维整数数组。然后，您可以先分配连续的ROWS * COLS整数块，然后手动将其拆分为ROWS行。没有语法糖，这读

int *mem = malloc(ROWS * COLS * sizeof(int));
int **A = malloc(ROWS * sizeof(int*));
for(int i = 0; i < ROWS; i++) 
   A[i] = mem + COLS*i;
// use A[i][j]

并且可以避免乘法来更高效地完成操作，

int *mem = malloc(ROWS * COLS * sizeof(int));
int **A = malloc(ROWS * sizeof(int*));
A[0] = mem;
for(int i = 1; i < ROWS; i++) 
   A[i] = A[i-1] + COLS;
// use A[i][j]

最后，可以完全放弃多余的指针，

int **A = malloc(ROWS * sizeof(int*));
A[0] = malloc(ROWS * COLS * sizeof(int));
for(int i = 1; i < ROWS; i++) 
   A[i] = A[i-1] + COLS;
// use A[i][j]

但是有一个重要的GOTCHA！您首先必须先释放A [0]，然后再释放A，

free(A[0]);
free(A);              // if this were done first, then A[0] would be invalidated

尽管代码会变得混乱，但相同的想法可以扩展到3维或更高维的数组。