这个问题的目的是提供有关如何在C中动态正确分配多维数组的参考。即使在某些C编程书籍中，这也是一个经常被误解且很少解释的主题。因此，即使是经验丰富的C程序员也很难做到这一点。
从我的编程老师/书/教程中得知，动态分配多维数组的正确方法是使用指针到指针。
但是，SO上的一些高级用户现在告诉我，这是错误的做法。他们说指针对指针不是数组，我实际上不是在分配数组，我的代码不必要地慢。
这是教我分配多维数组的方法：
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
int** arr_alloc (size_t x, size_t y)
{
int** pp = malloc(sizeof(*pp) * x);
assert(pp != NULL);
for(size_t i=0; i<x; i++)
{
pp[i] = malloc(sizeof(**pp) * y);
assert(pp[i] != NULL);
}
return pp;
}
int** arr_fill (int** pp, size_t x, size_t y)
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
pp[i][j] = (int)j + 1;
}
}
return pp;
}
void arr_print (int** pp, size_t x, size_t y)
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
printf("%d ", pp[i][j]);
}
printf("\n");
}
}
void arr_free (int** pp, size_t x, size_t y)
{
(void) y;
for(size_t i=0; i<x; i++)
{
free(pp[i]);
pp[i] = NULL;
}
free(pp);
pp = NULL;
}
int main (void)
{
size_t x = 2;
size_t y = 3;
int** pp;
pp = arr_alloc(x, y);
pp = arr_fill(pp, x, y);
arr_print(pp, x, y);
arr_free(pp, x, y);
return 0;
}
输出量
1 2 3
1 2 3
这段代码很好用！怎么可能错了？
最佳答案
为了回答这个问题，我们首先要弄清楚一些概念。什么是数组，如何使用？如果不是数组，问题中的代码是什么？
什么是数组？
数组的正式定义可在C标准ISO 9899：2011 6.2.5 / 20类型中找到。
数组类型描述了连续分配的非空集
具有特定成员对象类型（称为元素类型）的对象。
用简单的英语来说，数组是相邻存储单元中连续分配的相同类型项的集合。
例如，将在内存中分配3个整数int arr[3] = {1,2,3};的数组，如下所示：
+-------+-------+-------+
| | | |
| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
那么多维数组的形式定义又如何呢？实际上，它与上面引用的定义非常相同。它递归地应用。
如果我们要分配2D数组，则
int arr[2][3] = { {1,2,3}, {1,2,3} };会像这样在内存中分配：+-------+-------+-------+-------+-------+-------+
| | | | | | |
| 1 | 2 | 3 | 1 | 2 | 3 |
| | | | | | |
+-------+-------+-------+-------+-------+-------+
在此示例中，我们实际上是一个数组数组。一个有2个项目的数组，每个项目都是3个整数的数组。
数组是其他类型
C语言中的数组通常遵循与常规变量相同的类型系统。如上所示，您可以拥有一个数组数组，就像您可以拥有任何其他类型的数组一样。
您还可以在n维数组上应用与普通一维数组相同的指针算术。对于常规的一维数组，应用指针算法应该很简单：
int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.
for(size_t i=0; i<3; i++)
{
printf("%d ", *ptr); // print contents.
ptr++; // set pointer to point at the next element.
}
这是通过“阵列衰减”实现的。在表达式中使用
arr时，它会“衰减”为指向第一个元素的指针。类似地，我们可以使用相同类型的指针算法，通过使用数组指针来遍历数组数组：
int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.
for(size_t i=0; i<2; i++)
{
printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
ptr++; // set pointer to point at the next element
}
再次出现阵列衰减。类型为
arr的变量int [2][3]衰减为指向第一个元素的指针。第一个元素是int [3]，指向该元素的指针声明为int(*)[3]-数组指针。为了使用多维数组，必须了解数组指针和数组衰减。
在更多情况下，数组的行为就像常规变量一样。
sizeof运算符对（非VLA）数组的作用与常规变量的作用相同。 32位系统的示例：int x; printf("%zu", sizeof(x));打印4。int arr[3] = {1,2,3}; printf("%zu", sizeof(arr));打印12（3 * 4 = 12）int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr));打印24（2 * 3 * 4 = 24）像任何其他类型一样，数组可以与库函数和通用API一起使用。由于数组满足连续分配的要求，因此我们可以例如使用
memcpy安全地复制它们：int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));
连续分配也是
memset，strcpy，bsearch和qsort之类的其他类似标准库功能起作用的原因。它们旨在处理连续分配的阵列。因此，如果您具有多维数组，则可以有效地对其进行搜索并使用bsearch和qsort对其进行排序，从而省去了执行二进制搜索和快速进行自我排序的麻烦，从而为每个项目重新发明了轮子。数组和其他类型之间的所有上述一致性是我们要利用的一件非常好的事情，尤其是在进行通用编程时。
如果不是数组，指针对指针是什么？
现在回到问题中的代码，该代码使用带有指针到指针的不同语法。没有什么神秘的。它是指向类型的指针，不多也不少。它不是数组。它不是二维数组。严格来说，它不能用于指向数组，也不能用于指向2D数组。
但是，可以使用指针指向指针指向指针数组的第一个元素，而不是指向整个数组。这就是问题中使用它的方式-一种“模拟”数组指针的方式。在问题中，它用于指向2个指针的数组。然后，使用2个指针中的每一个指向3个整数的数组。
这称为查找表，它是一种抽象数据类型（ADT），与普通数组的下层概念有所不同。主要区别在于查找表的分配方式：
+------------+
| |
| 0x12340000 |
| |
+------------+
|
|
v
+------------+ +-------+-------+-------+
| | | | | |
| 0x22223333 |---->| 1 | 2 | 3 |
| | | | | |
+------------+ +-------+-------+-------+
| |
| 0xAAAABBBB |--+
| | |
+------------+ |
|
| +-------+-------+-------+
| | | | |
+->| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
本例中的32位地址是虚构的。
0x12340000框表示指针到指针。它包含指向指针数组中第一项的地址0x12340000。该数组中的每个指针依次包含一个指向整数数组中第一项的地址。问题就从这里开始。
查询表版本存在问题
查找表分散在整个堆内存中。它不是在相邻单元中连续分配的内存，因为每个对
malloc()的调用都提供了一个新的存储区域，不一定与其他区域相邻。这又给我们带来了许多问题：我们不能按预期使用指针算法。尽管我们可以使用某种形式的指针算术来索引和访问查找表中的项目，但不能使用数组指针来做到这一点。
我们不能使用sizeof运算符。在指针指向上使用时，它将为我们提供指针指向的大小。习惯于指向的第一项，它将为我们提供指针的大小。它们都不是数组的大小。
除了数组类型（
memcpy，memset，strcpy，bsearch，qsort等）之外，我们不能使用标准库函数。所有这些功能都假定获取数组作为输入，并连续分配数据。使用我们的查询表作为参数调用它们会导致未定义的行为错误，例如程序崩溃。重复调用
malloc分配多个段会导致堆fragmentation，这反过来会导致RAM内存使用不足。由于内存分散，因此在遍历查找表时，CPU无法利用高速缓存。有效使用数据缓存需要从上到下迭代的连续内存块。这意味着根据设计，查找表的访问时间比真正的多维数组要慢得多。
对于每次对
malloc()的调用，管理堆的库代码都必须计算出可用空间。同样，对于每个free()调用，都必须执行开销代码。因此，出于性能考虑，通常最好是尽可能少地调用这些函数。查询表是否都不好？
如我们所见，基于指针的查找表存在很多问题。但是，它们并不全都不好，它是与其他工具一样的工具。它只是必须用于正确的目的。如果您要寻找一个多维数组，应该将其用作数组，则查找表显然是错误的工具。但是它们可以用于其他目的。
当您需要所有尺寸分别具有完全可变的尺寸时，查找表是正确的选择。例如，在创建C字符串列表时，这样的容器可能很方便。因此，通常有理由考虑采取上述执行速度性能损失以节省内存。
此外，查找表的优点是您可以在运行时重新分配表的各个部分，而无需重新分配整个多维数组。如果需要经常执行此操作，则在执行速度方面，查询表甚至可能优于多维数组。例如，在实现链式哈希表时，可以使用类似的查找表。
那么如何动态地适当分配多维数组呢？
现代C语言中最简单的形式是简单地使用可变长度数组（VLA）。
int array[x][y];其中，x和y是在运行时，在先数组声明中给定值的变量。但是，VLA具有本地作用域，并且不会在程序的整个过程中持续存在-它们具有自动存储的持续时间。因此，尽管VLA可以方便快捷地用于临时阵列，但它并不是问题中查询表的通用替代品。为了真正地动态分配多维数组，以便为其分配存储时间，我们必须使用
malloc() / calloc() / realloc()。我在下面举一个例子。在现代C语言中，您将使用指向VLA的数组指针。即使程序中没有实际的VLA，也可以使用此类指针。与普通的
type*或void*相比，使用它们的好处是提高了类型安全性。使用指向VLA的指针还可以使您将数组尺寸作为参数传递给使用数组的函数，从而使其既可变又可以类型安全。不幸的是，为了利用拥有指向VLA的指针的好处，我们不能将该指针作为函数结果返回。因此，如果我们需要将指向数组的指针返回给调用方，则必须将其作为参数传递（出于Dynamic memory access only works inside function中所述的原因）。这是使用C的好习惯，但会使代码难以阅读。它看起来像这样：
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
assert(*aptr != NULL);
}
虽然这种带有指向数组指针的指针的语法可能看起来有些奇怪和令人生畏，但即使我们添加了更多的维度，它也不会比这更复杂：
void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
*aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
assert(*aptr != NULL);
}
现在，将该代码与为查询表版本添加一个维度的代码进行比较：
/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
int*** ppp = malloc(sizeof(*ppp) * x);
assert(ppp != NULL);
for(size_t i=0; i<x; i++)
{
ppp[i] = malloc(sizeof(**ppp) * y);
assert(ppp[i] != NULL);
for(size_t j=0; j<y; j++)
{
ppp[i][j] = malloc(sizeof(***ppp) * z);
assert(ppp[i][j] != NULL);
}
}
return ppp;
}
现在，这是“三星级编程”的一团糟。而且甚至不考虑4个维度...
使用真实2D数组的版本的完整代码
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
assert(*aptr != NULL);
}
void arr_fill (size_t x, size_t y, int array[x][y])
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
array[i][j] = (int)j + 1;
}
}
}
void arr_print (size_t x, size_t y, int array[x][y])
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
printf("%d ", array[i][j]);
}
printf("\n");
}
}
int main (void)
{
size_t x = 2;
size_t y = 3;
int (*aptr)[x][y];
arr_alloc(x, y, &aptr);
arr_fill(x, y, *aptr);
arr_print(x, y, *aptr);
free(aptr); // free the whole 2D array
return 0;
}
关于c - 正确分配多维数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59353465/