正确分配多维数组
Correctly allocating multi-dimensional arrays
这个问题的目的是提供一个关于如何在C中正确动态分配多维数组的参考。这是一个经常被误解的主题,即使在一些C编程书籍中也解释得不好。因此,即使是经验丰富的 C 程序员也很难做到正确。
我从编程中学到 teacher/book/tutorial 动态分配多维数组的正确方法是使用指向指针的指针。
但是,现在 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 Types.
An array type describes a contiguously allocated non-empty set of
objects with a particular member object type, called the element type.
用简单的英语来说,数组是在相邻存储单元中连续分配的相同类型项目的集合。
例如,一个包含 3 个整数的数组 int arr[3] = {1,2,3};
将像这样在内存中分配:
+-------+-------+-------+
| | | |
| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
那么 multi-dimensional 数组的正式定义呢?实际上,它与上面引用的定义完全相同。它递归地应用。
如果我们分配一个二维数组,int arr[2][3] = { {1,2,3}, {1,2,3} };
它会像这样在内存中分配:
+-------+-------+-------+-------+-------+-------+
| | | | | | |
| 1 | 2 | 3 | 1 | 2 | 3 |
| | | | | | |
+-------+-------+-------+-------+-------+-------+
我们在这个例子中得到的实际上是一个数组数组。一个包含 2 个项目的数组,每个项目都是 3 个整数的数组。
数组和其他类型一样
C 中的数组通常遵循与常规变量相同的类型系统。如上所示,您可以拥有一个数组数组,就像您可以拥有任何其他类型的数组一样。
您还可以在 n 维数组上应用与普通 one-dimensional 数组相同的指针算法。对于常规 one-dimensional 数组,应用指针算法应该是微不足道的:
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.
}
这是通过 "array decay" 实现的。当在表达式中使用 arr
时,它 "decayed" 变成指向第一个元素的指针。
类似地,我们可以使用相同类型的指针算法来遍历数组数组,方法是使用 数组指针:
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
}
再次出现数组衰减。 int [2][3]
类型的变量 arr
退化为指向第一个元素的指针。第一个元素是 int [3]
并且指向此类元素的指针被声明为 int(*)[3]
- 数组指针。
了解数组指针和数组衰减对于使用 multi-dimensional 数组是必要的。
在更多情况下,数组的行为就像常规变量一样。 sizeof
运算符对 (non-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
工作的原因。它们旨在处理连续分配的数组。因此,如果你有一个 multi-dimensional 数组,你可以有效地搜索它并使用 bsearch
和 qsort
对其进行排序,从而节省你自己实现二进制搜索和快速排序的麻烦,从而 re-inventing 每个项目的轮子。
数组和其他类型之间的上述所有一致性是我们想要利用的好东西,尤其是在进行泛型编程时。
如果不是数组,pointer-to-pointer是什么?
现在回到问题中的代码,它使用了带有 pointer-to-pointer 的不同语法。这没有什么神秘的。它是指向类型指针的指针,不多也不少。它不是数组。它不是二维数组。严格来说不能用来指向数组,也不能用来指向二维数组。
然而,A pointer-to-pointer 可用于指向指针数组的第一个元素,而不是指向整个数组。这就是它在问题中的使用方式 - 作为 "emulate" 数组指针的一种方式。在问题中,它用于指向 2 个指针的数组。然后 2 个指针中的每一个都用于指向 3 个整数的数组。
这被称为 look-up table,它是一种抽象数据类型 (ADT),与普通数组的底层概念不同。主要区别在于 look-up table 的分配方式:
+------------+
| |
| 0x12340000 |
| |
+------------+
|
|
v
+------------+ +-------+-------+-------+
| | | | | |
| 0x22223333 |---->| 1 | 2 | 3 |
| | | | | |
+------------+ +-------+-------+-------+
| |
| 0xAAAABBBB |--+
| | |
+------------+ |
|
| +-------+-------+-------+
| | | | |
+->| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
本例中的32位地址为made-up。 0x12340000
框代表 pointer-to-pointer。它包含指向指针数组中第一项的地址 0x12340000
。该数组中的每个指针依次包含一个指向整数数组中第一项的地址。
这就是问题的开始。
look-uptable版本有问题
look-up table 散落在堆内存中。它不是在相邻单元格中连续分配的内存,因为每次调用 malloc()
都会提供一个新的内存区域,不一定与其他内存区域相邻。这反过来又给我们带来了很多问题
我们不能按预期使用指针运算。虽然我们可以使用一种指针算法来索引和访问 look-up table 中的项目,但我们不能使用数组指针来这样做。
我们不能使用 sizeof 运算符。用在 pointer-to-pointer 上,它会给我们一个 pointer-to-pointer 的大小。习惯于第一个指向的项目,它会给我们一个指针的大小。它们都不是数组的大小。
我们不能使用数组类型除外的标准库函数 (memcpy
, memset
, strcpy
, bsearch
, qsort
等等)。所有这些函数都假定获取数组作为输入,数据是连续分配的。使用我们的 look-up table 作为参数调用它们会导致未定义的行为错误,例如程序崩溃。
重复调用malloc
分配多个段导致堆fragmentation,进而导致RAM内存使用不当。
由于内存是分散的,CPU在遍历look-uptable时无法利用缓存内存。数据高速缓存的有效使用需要从上到下迭代的连续内存块。这意味着 look-up table 在设计上的访问时间比真正的 multi-dimensional 数组慢得多。
每次调用 malloc()
,管理堆的库代码必须计算哪里有空闲 space。类似地,对于 free()
的每次调用,都有必须执行的开销代码。因此,为了性能,尽可能少地调用这些函数通常是可取的。
look-uptable都不好吗?
正如我们所看到的,pointer-based look-up table 有很多问题。但它们并不都是坏的,它是一种与其他任何工具一样的工具。它只需要用于正确的目的。如果你正在寻找一个 multi-dimensional 数组,它应该被用作一个数组,look-up tables 显然是错误的工具。但它们可以用于其他目的。
A look-up table 当您需要所有维度都具有完全可变的大小时,table 是正确的选择。例如,在创建 C 字符串列表时,这样的容器会很方便。为了节省内存,采取上述执行速度性能损失往往是合理的。
此外,look-up table 的优点是您可以 re-alloce run-time 中的 table 部分而不需要 re-allocate 整个 multi-dimensional 数组。如果这是需要经常做的事情,look-up table 甚至可能在执行速度方面优于 multi-dimensional 数组。例如,在实现链式哈希 table.
时可以使用类似 look-up tables
如何动态分配multi-dimensional数组?
现代 C 中最简单的形式是简单地使用 variable-length 数组 (VLA)。 int array[x][y];
其中 x
和 y
是在数组声明之前 run-time 中给定值的变量。但是,VLA 具有本地作用域并且不会在整个程序期间持续存在 - 它们具有自动存储持续时间。因此,虽然 VLA 可以方便快捷地用于临时数组,但它并不是问题中 look-up table 的通用替代品。
要真正动态分配一个multi-dimensional数组,使其获得分配的存储持续时间,我们必须使用malloc()
/calloc()
/realloc()
。下面我举一个例子。
在现代 C 中,您将使用指向 VLA 的数组指针。即使程序中没有实际的 VLA,您也可以使用此类指针。使用它们比普通 type*
或 void*
的好处增加 type-safety。使用指向 VLA 的指针还允许您将数组维数作为参数传递给使用该数组的函数,使其同时具有变量和类型安全性。
不幸的是,为了利用指向 VLA 的指针的好处,我们不能 return 该指针作为函数结果。所以如果我们需要 return 一个指向数组的指针给调用者,它必须作为参数传递(原因在 中描述)。这在 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);
}
现在将该代码与为 look-up table 版本增加一维的代码进行比较:
/* 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;
}
现在 是 "three-star programming" 的一团乱七八糟的东西。甚至不考虑 4 个维度...
使用真正二维数组的版本的完整代码
#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 没有多维数组(作为原始 数据类型)。但是您可以拥有数组数组(或其他聚合数组)和指针数组。
一种可能的方法是与一些abstract data type (perhaps using flexible array members, which is one implementation trick, and you could use other approaches) like in 推理。
我们不能建议任何抽象数据类型,因为这取决于您的作业文本,而我们没有。您需要设计您的抽象数据类型(在一张纸上),然后再实现它。
一旦您(在纸上或板上)列出了 ADT 所需的所有操作,实施它们就很简单了。
This code works just fine! How could it be wrong?
那句话不一致(错w.r.t。什么规格?)...
我建议使用所有警告和调试信息进行编译(例如 with gcc -Wall -Wextra -g
with GCC), to improve your code till you get no warnings, to use the debugger gdb
(to understand what is happening in your program) and other tools like valgrind。
这个问题的目的是提供一个关于如何在C中正确动态分配多维数组的参考。这是一个经常被误解的主题,即使在一些C编程书籍中也解释得不好。因此,即使是经验丰富的 C 程序员也很难做到正确。
我从编程中学到 teacher/book/tutorial 动态分配多维数组的正确方法是使用指向指针的指针。
但是,现在 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 Types.
An array type describes a contiguously allocated non-empty set of objects with a particular member object type, called the element type.
用简单的英语来说,数组是在相邻存储单元中连续分配的相同类型项目的集合。
例如,一个包含 3 个整数的数组 int arr[3] = {1,2,3};
将像这样在内存中分配:
+-------+-------+-------+
| | | |
| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
那么 multi-dimensional 数组的正式定义呢?实际上,它与上面引用的定义完全相同。它递归地应用。
如果我们分配一个二维数组,int arr[2][3] = { {1,2,3}, {1,2,3} };
它会像这样在内存中分配:
+-------+-------+-------+-------+-------+-------+
| | | | | | |
| 1 | 2 | 3 | 1 | 2 | 3 |
| | | | | | |
+-------+-------+-------+-------+-------+-------+
我们在这个例子中得到的实际上是一个数组数组。一个包含 2 个项目的数组,每个项目都是 3 个整数的数组。
数组和其他类型一样
C 中的数组通常遵循与常规变量相同的类型系统。如上所示,您可以拥有一个数组数组,就像您可以拥有任何其他类型的数组一样。
您还可以在 n 维数组上应用与普通 one-dimensional 数组相同的指针算法。对于常规 one-dimensional 数组,应用指针算法应该是微不足道的:
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.
}
这是通过 "array decay" 实现的。当在表达式中使用 arr
时,它 "decayed" 变成指向第一个元素的指针。
类似地,我们可以使用相同类型的指针算法来遍历数组数组,方法是使用 数组指针:
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
}
再次出现数组衰减。 int [2][3]
类型的变量 arr
退化为指向第一个元素的指针。第一个元素是 int [3]
并且指向此类元素的指针被声明为 int(*)[3]
- 数组指针。
了解数组指针和数组衰减对于使用 multi-dimensional 数组是必要的。
在更多情况下,数组的行为就像常规变量一样。 sizeof
运算符对 (non-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
工作的原因。它们旨在处理连续分配的数组。因此,如果你有一个 multi-dimensional 数组,你可以有效地搜索它并使用 bsearch
和 qsort
对其进行排序,从而节省你自己实现二进制搜索和快速排序的麻烦,从而 re-inventing 每个项目的轮子。
数组和其他类型之间的上述所有一致性是我们想要利用的好东西,尤其是在进行泛型编程时。
如果不是数组,pointer-to-pointer是什么?
现在回到问题中的代码,它使用了带有 pointer-to-pointer 的不同语法。这没有什么神秘的。它是指向类型指针的指针,不多也不少。它不是数组。它不是二维数组。严格来说不能用来指向数组,也不能用来指向二维数组。
然而,A pointer-to-pointer 可用于指向指针数组的第一个元素,而不是指向整个数组。这就是它在问题中的使用方式 - 作为 "emulate" 数组指针的一种方式。在问题中,它用于指向 2 个指针的数组。然后 2 个指针中的每一个都用于指向 3 个整数的数组。
这被称为 look-up table,它是一种抽象数据类型 (ADT),与普通数组的底层概念不同。主要区别在于 look-up table 的分配方式:
+------------+
| |
| 0x12340000 |
| |
+------------+
|
|
v
+------------+ +-------+-------+-------+
| | | | | |
| 0x22223333 |---->| 1 | 2 | 3 |
| | | | | |
+------------+ +-------+-------+-------+
| |
| 0xAAAABBBB |--+
| | |
+------------+ |
|
| +-------+-------+-------+
| | | | |
+->| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
本例中的32位地址为made-up。 0x12340000
框代表 pointer-to-pointer。它包含指向指针数组中第一项的地址 0x12340000
。该数组中的每个指针依次包含一个指向整数数组中第一项的地址。
这就是问题的开始。
look-uptable版本有问题
look-up table 散落在堆内存中。它不是在相邻单元格中连续分配的内存,因为每次调用 malloc()
都会提供一个新的内存区域,不一定与其他内存区域相邻。这反过来又给我们带来了很多问题
我们不能按预期使用指针运算。虽然我们可以使用一种指针算法来索引和访问 look-up table 中的项目,但我们不能使用数组指针来这样做。
我们不能使用 sizeof 运算符。用在 pointer-to-pointer 上,它会给我们一个 pointer-to-pointer 的大小。习惯于第一个指向的项目,它会给我们一个指针的大小。它们都不是数组的大小。
我们不能使用数组类型除外的标准库函数 (
memcpy
,memset
,strcpy
,bsearch
,qsort
等等)。所有这些函数都假定获取数组作为输入,数据是连续分配的。使用我们的 look-up table 作为参数调用它们会导致未定义的行为错误,例如程序崩溃。重复调用
malloc
分配多个段导致堆fragmentation,进而导致RAM内存使用不当。由于内存是分散的,CPU在遍历look-uptable时无法利用缓存内存。数据高速缓存的有效使用需要从上到下迭代的连续内存块。这意味着 look-up table 在设计上的访问时间比真正的 multi-dimensional 数组慢得多。
每次调用
malloc()
,管理堆的库代码必须计算哪里有空闲 space。类似地,对于free()
的每次调用,都有必须执行的开销代码。因此,为了性能,尽可能少地调用这些函数通常是可取的。
look-uptable都不好吗?
正如我们所看到的,pointer-based look-up table 有很多问题。但它们并不都是坏的,它是一种与其他任何工具一样的工具。它只需要用于正确的目的。如果你正在寻找一个 multi-dimensional 数组,它应该被用作一个数组,look-up tables 显然是错误的工具。但它们可以用于其他目的。
A look-up table 当您需要所有维度都具有完全可变的大小时,table 是正确的选择。例如,在创建 C 字符串列表时,这样的容器会很方便。为了节省内存,采取上述执行速度性能损失往往是合理的。
此外,look-up table 的优点是您可以 re-alloce run-time 中的 table 部分而不需要 re-allocate 整个 multi-dimensional 数组。如果这是需要经常做的事情,look-up table 甚至可能在执行速度方面优于 multi-dimensional 数组。例如,在实现链式哈希 table.
时可以使用类似 look-up tables如何动态分配multi-dimensional数组?
现代 C 中最简单的形式是简单地使用 variable-length 数组 (VLA)。 int array[x][y];
其中 x
和 y
是在数组声明之前 run-time 中给定值的变量。但是,VLA 具有本地作用域并且不会在整个程序期间持续存在 - 它们具有自动存储持续时间。因此,虽然 VLA 可以方便快捷地用于临时数组,但它并不是问题中 look-up table 的通用替代品。
要真正动态分配一个multi-dimensional数组,使其获得分配的存储持续时间,我们必须使用malloc()
/calloc()
/realloc()
。下面我举一个例子。
在现代 C 中,您将使用指向 VLA 的数组指针。即使程序中没有实际的 VLA,您也可以使用此类指针。使用它们比普通 type*
或 void*
的好处增加 type-safety。使用指向 VLA 的指针还允许您将数组维数作为参数传递给使用该数组的函数,使其同时具有变量和类型安全性。
不幸的是,为了利用指向 VLA 的指针的好处,我们不能 return 该指针作为函数结果。所以如果我们需要 return 一个指向数组的指针给调用者,它必须作为参数传递(原因在
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);
}
现在将该代码与为 look-up table 版本增加一维的代码进行比较:
/* 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;
}
现在 是 "three-star programming" 的一团乱七八糟的东西。甚至不考虑 4 个维度...
使用真正二维数组的版本的完整代码
#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 没有多维数组(作为原始 数据类型)。但是您可以拥有数组数组(或其他聚合数组)和指针数组。
一种可能的方法是与一些abstract data type (perhaps using flexible array members, which is one implementation trick, and you could use other approaches) like in
我们不能建议任何抽象数据类型,因为这取决于您的作业文本,而我们没有。您需要设计您的抽象数据类型(在一张纸上),然后再实现它。
一旦您(在纸上或板上)列出了 ADT 所需的所有操作,实施它们就很简单了。
This code works just fine! How could it be wrong?
那句话不一致(错w.r.t。什么规格?)...
我建议使用所有警告和调试信息进行编译(例如 with gcc -Wall -Wextra -g
with GCC), to improve your code till you get no warnings, to use the debugger gdb
(to understand what is happening in your program) and other tools like valgrind。