使用malloc进行多维数组的分配，其中每一行长度不同

Question

我有以下的 C 代码：

int *a;
size_t size = 2000*sizeof(int);
a = malloc(size);

这个代码运行良好。但是如果我有以下代码：

char **b = malloc(2000*sizeof *b);

假设每个元素的长度都不同，那么如何对b执行与 a 相同的操作？即以下代码是否正确？

char *c;
size_t size = 2000*sizeof(char *);
c = malloc(size);

- asel

Answer 1

首先，您需要分配指针数组，如 char **c = malloc( N * sizeof( char* ))，然后为每个行分别调用malloc来进行分配，可能需要在循环中进行：

/* N is the number of rows  */
/* note: c is char** */
if (( c = malloc( N*sizeof( char* ))) == NULL )
{ /* error */ }

for ( i = 0; i < N; i++ )
{
  /* x_i here is the size of given row, no need to
   * multiply by sizeof( char ), it's always 1
   */
  if (( c[i] = malloc( x_i )) == NULL )
  { /* error */ }

  /* probably init the row here */
}

/* access matrix elements: c[i] give you a pointer
 * to the row array, c[i][j] indexes an element
 */
c[i][j] = 'a';

如果您知道元素的总数（例如 N*M），您可以进行单个分配。

- Nikolai Fetissov

---

如果您在单个操作中分配了NM字节，则需要手动填充所有的c[i]：c[i] = p + Mi; - Tadeusz A. Kadłubowski

这取决于c的类型 - 如果它是char **，那么是的，如果它是char *，那么索引会改变：element [i] [j] 〜 c [i * M + j]。 - Nikolai Fetissov

@Nikolai N Fetissov，代码中有很多malloc，如何通过使用for循环来释放它们？ - e19293001

@e19293001 是的，每个 malloc 都有一个 free。您需要循环遍历 char* 变量并释放它们，然后释放 char**。 - erickrf

我在一本书中看到过同样的内容，它说：“……内存不保证是连续的。” - dud3

Answer 2

动态分配类型为T的NxM数组的典型形式为：

T **a = malloc(sizeof *a * N);
if (a)
{
  for (i = 0; i < N; i++)
  {
    a[i] = malloc(sizeof *a[i] * M);
  }
}

如果数组的每个元素长度不同，则用该元素的适当长度替换M；例如：

T **a = malloc(sizeof *a * N);
if (a)
{
  for (i = 0; i < N; i++)
  {
    a[i] = malloc(sizeof *a[i] * length_for_this_element);
  }
}

- John Bode

---

如果我知道我需要的整数总数，但不知道它们应该分配到每个数组中的数量，我该如何继续？ - dietbacon

非常清晰的答案，谢谢！您能否添加一个描述，以正确的顺序“释放”分配的内存？ - Kagaratsch

@Kagaratsch：通常来说，你需要按照分配的相反顺序进行释放 - 也就是先释放每个a[i]，然后再释放a。 - John Bode

Answer 3

char a[10][20] 的等效内存分配如下所示。

char **a;

a=malloc(10*sizeof(char *));

for(i=0;i<10;i++)
    a[i]=malloc(20*sizeof(char));

我希望这看起来简单易懂。

- Ramesh

Answer 4

另一种方法是分配一个连续的内存块，其中包括指向行的指针的头块和存储实际数据的主体块。然后只需通过在每行基础上将主体内存中的地址分配给头块中的指针来标记内存。它看起来像下面这样：

int** 2dAlloc(int rows, int* columns) {    
    int header = rows * sizeof(int*);

    int body = 0;
    for(int i=0; i<rows; body+=columnSizes[i++]) {  
    }
    body*=sizeof(int);

    int** rowptr = (int**)malloc(header + body);

    int* buf  = (int*)(rowptr + rows);
    rowptr[0] = buf;
    int k;
    for(k = 1; k < rows; ++k) {
        rowptr[k] = rowptr[k-1] + columns[k-1];
    }
    return rowptr;
}

int main() {
    // specifying column amount on per-row basis
    int columns[] = {1,2,3};
    int rows = sizeof(columns)/sizeof(int);
    int** matrix = 2dAlloc(rows, &columns);

    // using allocated array
    for(int i = 0; i<rows; ++i) {
        for(int j = 0; j<columns[i]; ++j) {
            cout<<matrix[i][j]<<", ";
        }   
            cout<<endl;
    }

    // now it is time to get rid of allocated 
    // memory in only one call to "free"
    free matrix;
}

这种方法的优势在于优雅地释放内存，并能够使用类似数组的符号来访问生成的二维数组中的元素。

- Dmitry Aleks

---

需要注意的是：相对于其他一行一行分配的方法，这种解决方案通常在缓存一致性方面表现更好，因为每个单独的行都保证是连续的，可能会导致矩阵的组成部分散布在高度碎片化的堆中。 - Max DeLiso

遗憾的是，这也会导致非指针大小类型无法保证对齐。例如：一个具有32位指针和64位双精度浮点数以及奇数行数的系统将在double的第一列行上开始一个未对齐的边界。这一点非常重要，需要加以考虑，因为不正确的数据对齐可能会导致总线错误。通用解决方案应确保数据行从8字节边界开始，并在将行指针分配给主指针段时进行额外分配空间并相应地进行调整。 - WhozCraig

@DmitryAleks：你在哪里声明columnSizes[]？ - user2284570

Answer 5

如果b中的每个元素长度都不同，则需要进行以下操作：

int totalLength = 0;
for_every_element_in_b {
    totalLength += length_of_this_b_in_bytes;
}
return malloc(totalLength);

- plinth

---

它不为一个字符指针的一维数组分配内存。 - Tadeusz A. Kadłubowski

Answer 6

我认为采用两步方法是最好的，因为C 2D 数组只是数组的数组。第一步是分配单个数组，然后循环通过分配每列的数组来进行。此文章提供了很好的细节。

- zdav

Answer 7

2-D 数组动态内存分配

int **a,i;

// for any number of rows & columns this will work
a = malloc(rows*sizeof(int *));
for(i=0;i<rows;i++)
    *(a+i) = malloc(cols*sizeof(int));

- Sridhar T

Answer 8

malloc不会在特定边界上分配内存，因此必须假定它在字节边界上进行分配。

如果将返回的指针转换为其他类型，则不能使用该指针，因为访问该指针可能会导致CPU发生内存访问冲突，并且应用程序将立即关闭。

- Vendicar Decarian