再论指针

多维数组的内存布局

C语言并未像其他语言所要求的那样定义了详细的运行时程序来支持这个特性。对于某些结构如动态数组，我们必须使用指针显示的分配和操纵内存，而不是由编译器自动完成。另外还有一些结构（作为参数的多维数组），在C语言中并没有一般的形式来表达。

如果我们有以下声明：

char pea[4][6];

有人把二维数组看作是排列在一张表格中的一行行的一维数组，事实上系统绝不允许程序按照这种方式存储数据。单个元素的存储和引用实际上是以线性形式顺序排列在内存中的。

数组下标的规则告诉我们如何计算左值pea[i][j]，首先找到pea[i]的位置，然后根据偏移量[j]取得字符。因此，pea[i][j]将被编译器解析为：

*(*(pea + i) + j)

pea[i]的意思随pea定义的不同而变化。

指针数组

首先看一下C语言中最常见最重要的数据结构：指向字符串一维指针数组。

可以通过声明一个一维指针数组，其中每个指针指向一个字符串来取得类似二维字符数组的效果，这种形式的声明如下：

char *pea[4];

注意char *pea[4]把pea声明为一个具有4个元素的数组，每个元素的类型是一个指向字符串（或字符）的指针。

在分析C语言的声明（1）里详细介绍了数组指针与指针数组的定义与区别。

这种数组必须用指向为字符串而分配的内存的指针进行初始化，可以在编译时用一个常量初始值，也可以在运行时用下面这样的代码进行初始化：

for(j=0;j<4;j++){
	pea[j] = (char *)malloc(10 * sizeof(char));
}

另一种方法是一次性的用malloc分配整个x * y个数据的数组：

(char *)malloc(row_size * column_size * sizeof(char));

然后，使用一个循环，用指针指向这块内存的各个区域。整个数组保证能够存储在连续的内存中，即按C用于分配静态数组的次序。它减少了调用malloc的维护性开销，但缺点是当处理完一个字符串时无法单独将其释放。

两个下标的二维数组和一维指针数组所存在的一个问题是：
当你看到pea[i][j]这样的引用形式时，你并不知道pea是怎样被声明的
这有点类似于在函数内部无法分辨传递给函数的实参究竟是一个数组还是一个指针。

int pea[4][6]; //int型的二维数组
int *pea[4]; //4个int型的指针的数组
int **pea; //int类型的指针的指针

在上面几种定义中，都可以使用如pea[i][j]这样的形式，尽管在不同的情况中访问的实际类型并不相同。

与二维数组一样，一个指针数组（char *pea[4]）中的单个字符也是使用两个下标来引用数组中的元素(如pea[i][j])。指针下标引用的规则告诉我们pea[i][j]被编译器解释为：

*(*(pea + i) + j)

是不是觉得很熟悉？它和一个二维数组引用的分解形式完全一样，在许多C语言书中就是这样解释的。然而，这里存在一个很大的问题，尽管这两种下标形式在源代码里看上去是一样的，而且被编译器解释为同一种指针表达式，但它们在各自的情况下所引用的实际类型并不相同。

二维数组char pea[4][6]

char pea[4][6]的定义表示pea是一个包含4个元素的数组，每个元素是一个char类型的数组（长度为6）。
假设在编译器符号表中，pea的地址为9980，pea[i][j]引用时步骤：

• 1.取i的值，把它的长度调整为一行的宽度（这里是6），然后加到9980上。
• 2.取j的值，把它的长度调整为一个元素的宽度（这里是1），然后加到前面所得出的结果上。
• 3.从地址（9980 + i*scale-factor1 + j*scale-factor2）中取出内容。

指针数组char *pea[4]

char *pea[4]的定义表示pea是一个包含4个元素的数组，每个元素为一个指向char的指针。
假设在编译器的符号表中，pea的地址为4624，pea[i][j]引用时步骤：

• 1.取i的值，乘以指针的宽度（4个字节），并把结果加到4624上。
• 2.从地址（4624 + i*4）取出内容，为5081。
• 3.取j的值，乘以元素的宽度（这里是1个字节），并把结果加到5081上。
• 4.从地址（5081 + j*1）取出内容。

除非指针已经指向字符（或字符数组），否则查找过程无法完成，假定每个指针都给定了一个值，那么查寻过程先找到数组的第i个元素（每个元素均为指针），取出指针的值，加上偏移量j，以此为地址，取出地址的内容。

指针数组的一个应用场景是：存储各行长度不一的表以及在一个函数调用中传递一个字符串数组。
如果需要存储50个字符串，每个字符串的最大长度可以达到255个字节，可以声明下面的二维数组：

char carrot[50][256];

它声明了50个字符串，其中每一个都保留256字节的空间，即使有些字符串的实际长度只到一两个字节。如果经常这样做，内存的浪费很大。一种替代方法就是使用字符串指针数组，所有第二级数组并不需要长度都相同。如果声明一个字符串指针数组，并根据需要为这些字符串分配内存，将会大大节省系统资源。字符串指针可以直接使用现有的，也可以通过分配内存创建一份现有字符串的拷贝。

char *carrot[50];
char my_string[] = "your message here";
carrot[i] = &my_string[0];
carrot[j] = (char *)malloc((strlen(my_string) + 1)*sizeof(char));
strcpy(carrot[j],my_string);

只要有可能，尽量不要选择拷贝整个字符串的方法。如果需要从两个不同的数据结构访问它，拷贝一个指针比拷贝整个数组快的多，空间也节省很多。另一个可能影响性能的因素是指针数组可能会使字符串分配于内存中不同的页面中。这就违反了局部引用的规则（一次读写的数据位于同一页面上），并导致更加频繁的页面切换，具体如何取决于怎样访问数据以及访问的频率。

数组和指针参数是如何被编译器修改的

“数组名被改写成一个指针参数”的规则并不是递归定义的。数组的数组会被改写为数组的指针，而不是指针的指针。

实参	解释	所匹配的形参	解释
char c[8][10];	数组的数组	char (*c)[10];	数组指针
char *c[15];	指针数组	char **c;	指针的指针
char (*c)[64];	数组指针	char (*c)[64];	不改变
char **c;	指针的指针	char **c;	不改变

之所以能在main()函数中看到char **argv这样的参数，是因为argv是一个指针数组（即char *argv[]）。这个表达式被编译器改写为指向数组第一个元素的指针，也就是一个指向指针的指针。如果argv参数事实上被声明为一个二维数组（也就是char argv[10][15]）,它将被编译器改写为char (*argv)[15]（也就是一个字符数组指针），而不是char **argv。

向函数传递一个一维数组

在C语言中，任何一维数组均可以作为函数的实参。形参被改写为指向数组第一个元素的指针，所以需要一个约定来提示数组的长度。一般有两个基本方法：

• 增加一个额外的参数，表示元素的数目（argc就是起这个作用）。
• 赋予数组最后一个元素一个特殊的值，提示它是数组的尾部（字符串结尾的’\0’字符就是起这个作用）。这个特殊值必须不会作为正常的元素值在数组中出现。

二维数组的情况要复杂一些，数组被改写为指向数组第一行的指针。
现在需要两个约定，其中一个用于提示每行的结束，另外一个用于提示所有行的结束。
提示单行结束可以使用一维数组所用的两种方法，提示所有行结束也可以这样。

我们所接收的是一个指向数组第一个元素的指针。每次当对指针执行自增操作时，指针就指向数组中下一行的起始位置，但怎么知道指针到达了数组的最后一行了呢？

• 我们可以增加一个额外的行，行内所有元素的值都是不可能在数组正常元素中出现的，能够提示数组超出了范围。当对指针进行自增操作时，要对它进行检查，看看它是否到达了那一行。
• 另一种方法是，定义一个额外的参数，提示数组的行数。

使用指针向函数传递一个多维数组

使用上面所描述的笨拙方法，可以解决标记数组范围这个难题。但还存在一个问题，就是如何在函数内部声明一个二维数组参数，这才是真正的麻烦所在。C语言没有办法表达“这个数组的边界在不同的调用中可以变化”这个概念。C编译器必须要知道数组的边界，以便为下标引用产生正确的代码。

在C语言中，没有办法向函数传递一个通用的多维数组，这是因为我们需要知道每一维的长度，以便为地址运算提供正确的单位长度。因此，你必须提供除了最左边一维以外的所有维的长度。这样就把实参限制为除最左边一维外所有维都必须与形参匹配的数组。

我们能够采取的最好方法就是放弃传递二维数组，把array[x][y]这样的形式改写为一个一维数组array[x+1],它的元素类型是指向array[y]的指针。这样就改变了问题的性质（传递的是一个指针数组），而改变后的问题是我们已经解决了的。在数组最后的那个元素array[x+1]里存储一个NULL指针，提示数组的结束。

向函数传递多维数组参数的方法

方法一：

my_func(int my_array[10][20]);

尽管这是最简单的方法，但同时也是作用最小的。因为它迫使函数只处理10行20列的int型数组。我们想要的是一个确定更为普通的多维数组形参的方法，使函数能够操作任意长度的数组。

注意，多维数组最主要的一维的长度（最左边一维）不必显示写明。所有的函数都必须知道数组其他维的确切长度和数组的基地址。有了这些信息，它就可以一次跳过一个完整的行，到达下一行。

方法二：
我们可以合法的省略第一维的长度：

my_func(int my_array[][20]);

但这样做法仍不够充分，因为每一行都必须正好是20个整数的长度。
函数也可以类似的声明为：

my_func(int (*my_array)[20]);

参数列表中(*my_array)周围的括号是绝对需要的，这样可以确保它被翻译为一个指向20个元素的int数组的指针，而不是一个20个int指针元素的数组。同样，我们对最右边一维的长度必须为20而感到不快。

方法三：
我们可以采取的第三种方法是放弃二维数组，把它的结构改为一个数组指针。也就是说，创建一个一维数组，数组中的元素是指向其他东西的指针。可以简单的传递一个指向数组参数的第一个元素的指针，如下所示（用于二维数组）：

my_func(char **my_array);

注意：只有把二维数组改为一个指向二维数组每行的指针数组的前提下才可以这样做！
指针数组这种数据结构的美感在于：它允许任意的字符串指针数组传递给函数，但必须是指针数组，而且必须是指向字符串的指针数组。这是因为字符串和指针都有一个显示的越界值（分别为NUL和NULL），可以作为结束标记。至于其他类型，并没有一种类似的通用且可靠的值，所以并没有一种内置的方法知道何时到达数组某一维的结束位置。即使是指向字符串的指针数组，通常也需要一个计数参数argc，记录字符串的数量。

方法四：
我们可以采取的最后一种方法也是放弃多维数组的形式，提供自己的下标方式。例如若多维数组各维的长度都是一个相同的固定值，那么可以定义为一个一维数组，而在引用时采取如下的方式：

char_array[row_size * i + j] = ...

总结：

• 一维数组——没有问题，但需要包括一个计数值或者是一个能够标识越界位置的结束符。被调用的函数无法检测数组参数的边界。
• 二维数组——不能直接传递给函数，但可以把二维数组改写为一个一维的指针数组，并使用相同的下标表示方法。对于字符串来说，这样做是可以的，对于其他类型，需要增加一个记数值或者能够标识越界位置的结束符。同样，它依赖于调用函数和被调用函数之间的约定。
• 三维或更多维的数组——都无法使用。必须把它分解为几个维数更少的数组。

使用指针从函数返回一个数组

严格的说，无法直接从函数返回一个数组。但是，可以让函数返回一个指向任何数据结构的指针，当然也可以是一个指向数组的指针。

记住，声明必须在使用之前。一个声明的例子是：

int (*paf())[20];

这里，paf是一个函数，它返回一个指向包含20个int元素的数组的指针。
它的定义可能如下：

int (*paf())[20]{
	int (*pear)[20];
	pear = malloc(20*sizeof(int));
	return pear;
}

可以用这样的方法来调用函数：

int (*result)[20];
result = paf();
(*result)[3] = 12;

或者玩个花样，定义一个结构体(利用结构体可以整体赋值的特性)；

struct a_tag{
	int array[20];
}x,y;
struct a_tag my_func(){... return y;}
x = y;
x = my_func();
x.array[i] = 38;

千万要注意，不能从函数中返回一个指向函数的局部变量的指针

使用指针创建和使用动态数组

当预先并不知道数据的长度时，可以使用动态数组。其基本思路就是使用malloc()库函数来得到一个指向一大块内存的指针。然后，像引用数组一样引用这块内存，其机理就是一个数组下标访问可以改写为一个指针加上偏移量。

动态数组对于避免预定义的限制也是非常有用的。这方面的经典例子是在编译器中。我们不想把编译器符号表的记录数量限制在一个固定的数目上。，但也不想一开始就建立一个非常巨大的固定长度的表，这样会导致其他操作的内存空间不够。

我们真正需要实现的是使表具有根据需要自动增长的能力，这样它的唯一限制就是内存的总容量。如果你不是直接声明一个数组，而是在运行时在堆上分配数组的内存，这可以实现这个目标。有一个库函数realloc()，它能够对一个现在的内存块大小进行重新分配（通常是使之扩大），同时不会丢失原先内存块的内容。当需要在动态表中增长一个项目时，可以进行如下操作：

• 1.对表进行检查，看看它是否真的已满。
• 2.如果确实已满，使用realloc()函数扩展表的长度。并进行检查，确保realloc()操作成功进行。
• 3.在表中增加所需要的项目。

realloc()使用的注意点：

• 1.在实践中，不要把realloc()函数的返回值直接赋值给当前指针。如果realloc()函数失败，它会使该指针的值变成NULL，这样就无法对现有的表进行访问。
• 2.当一个大型表突然需要增长时，系统的运行速度可能会慢下来，而且这在什么时候发生是无法预测的。内存分配成倍增长是最关键的原因。
• 3.重分配操作很可能把原先的整个内存块移到一个不同的位置，这样表中元素的地址便不再有效。为避免麻烦，应该使用下标而不是元素的地址。
• 4.所有的“增加“和”删除”操作都必须通过函数来进行，这样才能维持表的完整性。只是这样一来，修改表所涉及到的东西就比仅仅使用下标要多得多。
• 5.如果表的项目数量减少，可能应该缩小表并释放多余的内存。这样内存收缩的操作对程序的运行速度有很大的影响。每次收缩表时，编译器最好能够知道任一时刻表的大小。
• 6.当某个线程对表进行内存重新分配时，你可能想锁住表，保护表的访问，防止其他线程读取表。对于多线程代码，这种锁总是必要的。

数据结构动态增长的另一种方法是使用链表，但链表不能进行随机访问。你只能线性的访问链表（除非你把频繁访问的链表元素的地址保存在缓冲区内），而数组则允许随机访问，这可能在性能上造成很大的差别。