前几天在笔试的时候遇到了一些指针的问题，关于指针的问题总是一知半解的，于是阅读研究了 《深入理解C指针》，希望可以通过笔记与总结的形式来理清楚C指针的知识。
这是一篇关于 C 指针与数组的博客，其他关于C指针的文章将在本专栏中持续更新。
数组是能用索引访问的同质元素的连续集合。这里所说的连续指的是数组中元素在内存中的位置是相邻的，中间不存在空隙，而同质指的是元素都是同一类型的。
数组的声明使用的是方括号 []。数组的长度是固定的，当我们声明数组时，需要决定数组有多大。如果指定过多的元素就会造成空间浪费，而指定过少的元素就会限制能够处理的元素数量。C 中的 realloc 函数和 C11 \texttt{C11} C11 标准中提供了应对长度需要变化的数组的技术；C++ 中则是提供容器对数组进行动态扩容。这些将会在后续小节中进行说明。
常见的数组有一维数组和二维数组，还有多维数组的存在，接下来将对这三种数组一一进行介绍。
一维数组是线性结构，使用 索引 来访问成员，也可以使用 指向数组首元素的指针的偏置 来访问数组元素，这将在第 3 节中进行介绍。下面的代码声明一个长度为 5 的整数数组，即数组内有 5 个整型数据。
int vector[5];
数组的索引从 0 开始，到声明的长度减 1 结束。在绝大多数的程序语言中，下标都是从 0 开始的。图 1-1 说明了数组的内存是如何分配的，int 类型的数据占据 4 个字节，因此数组的内存分配有如 图 1-1 所示的 +4 操作。该图中内存里的内容用 … 表示，因为我们只对一维数组声明还未进行初始化。
printf("%d\n", sizeof(vector) / sizeof(int));
可以通过一个块语句初始化一维数组，下面的代码把数组中的元素初始化为从 1 开始到 5 结束的自然数：
int vector[5] = {1, 2, 3, 4, 5};
二维数组使用行和列来标识数组元素，这类数据需要映射为内存中的一维地址空间。下面声明了一个2行3列的二维数组，用块语句进行初始化。图 1-2 说明了二维数组的内存分配，该图中不再将内存地址中的元素用 … 表示，因为我们在声明二维数组之后就初始化二维数组。
int matrix[2][3] = {
{1, 2, 3},
{4, 5, 6};
};
我们可以将二维数组当做数组的数组，也就是说，只用一个下标访问二维数组得到的是下标对应的行的首地址，利用 sizeof() 得到的字节数是下标对应的行的所有元素占据的字节数。下面的代码说明了这个概念，它会打印出每行的地址和长度（每一行占据的字节数）:
for (int i = 0; i < 2; ++i) {
printf("&matrix[%d]: %p sizeof(matrix[%d]): %d\n", i, &matrix[i], i, sizeof(matrix[i]));
}
下面的输出假设数组位于地址 100，因为每行有 3 个元素，每个元素占据 4 个字节，所以二维数组的一行占据 12 个字节：
// 输出
&matrix[0]: 100 sizeof(matrix[0]): 12
&matrix[1]: 112 sizeof(matrix[1]): 12
多维数组具有两个或两个以上的维度。对于多维数组，需要使用多组括号来定义数组的类型和长度。多维数组的三个维度依次被称为 行-列-阶。下面的例子中定义了一个具有 3 行、2 列、4 阶的三维数组。
int arr3d[3]][2][4] = {
{{1, 2, 3, 4}, {5, 6, 7, 8}},
{{9, 10, 11, 12}, {13, 14, 15, 16}},
{{17, 18, 19, 20}, {21, 22, 23, 24}}
};
元素按照 行-列-阶 的顺序连续分配内存，如图 1-3 所示。
前面一节介绍了 定长数组 的声明方式，这里的定长指的是数组一旦声明之后可容纳同质元素的数量不可以改变，除非使用 relloc() 函数重新分配内存空间。与定长数组相对应的就是可变长数组， C11 \texttt{C11} C11 和 C++11 \texttt{C++11} C++11 中都引入了可变长数组，这里主要讲述的 C++11 \texttt{C++11} C++11 中的可变长数组—— vector 容器。
首先看一下，vector 容器的声明：
#include <vector>
vector<int> nums;
标准库容器 vector 表示对象的集合，其中所有对象的类型都相同，这些对象可以 C++ 内置的数据类类型也可以是自己定义类对象。上面代码中容器内的对象集合的是整型数据。 声明 vector 容器需要包含头文件。
和任何数据类型一样，vector 容器有自己的定义和初始化方法。表 2-1 列出了定义 vector 对象的常用方法。
对 vector 对象来说，直接初始化的方式适应于三种情况：初始化值已知并且数量很少、初始化是另一个 vector 对象的副本、所有元素的初始值都一样。然后更常见的情况是创建的 vector 对象并不清楚实际所需的个数以及元素的值也不确定。还有些时候，即使元素的初始值已知，但如果元素的总量很大且各不相同，那么在创建 vector 对象的时候执行初始化操作就会显得繁琐。
举个例子，现在要创建一个包含整型数据 0 - 9 的 vector 对象 nums \texttt{nums} nums，使用列表初始化方法很容易做到，代码如下所示：
vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8, 9};
但如果要初始化 vector 对象包含的元素是 0 - 99 或者是更多的数呢？这个时候使用一一罗列元素的方法进行初始化就不合适了。对于这样的需求，一个更好的处理方法是先声明一个空的 vector 对象，然后在运行时利用 vector 的成员函数 push_back \texttt{push\_back} push_back 向其中增加元素。 push_back \texttt{push\_back} push_back 负责将一个值当做是 vector 对象的尾元素压入到 vector 对象的尾部。例如：
vector <int> v2; // 空 vector 对象
// 向空的容器对象中压入值 0-99
for (int i = 0; i < 100; ++i) {
v2.push_back(i);
}
在上例中一开始将 vector 初始化为空对象，通过 for 循环迭代向空 vector 对象中 push 新的元素。
同样的，如果知道运行时才知道 vector 对象中的元素，也可以使用这种方法创建 vector 对象并赋值，如下例是在运行时通过控制窗口输入字符串到 vector 对象中：
string str;
vetor<string> strs;
while (cin >> str) {
strs.push_back(str);
}
和上一个例子一样，一开始创建一个空的 vector 对象，然后通过 while 循环迭代向空 vector 对象中 push 新的元素。
首先通过表 2-2 来看一下 vector 支持的一些操作。
表 2-2 中的一些操作说明已经表述的很清楚了，这里主要提一个用下标添加元素问题和关系运算符。
在声明了一个空的 vector 对象时，不能使用下标形式增加元素。因为 vector 对象的下标运算符只能访问已经存在的元素，而不能添加元素。
关系运算符按照字典顺序进行比较：如果两个 vector 对象的容量不同，但是在相同位置上的元素值都一样，则元素较少的 vector 对象小于元素较多的 vector 对象；若元素值不同，则 vector 对象的顺序由第一对不同的元素值大小决定。
指针在处理数组是很有用的，我们可以用指针指向已有的数组，也可以从堆上分配内存然后把这块内存当做一个数组使用，这些数组可以是一维的也可以是多维的。
单独使用数组名字时会返回数组地址。我们可以把地址赋给指针，如下所示：
int vector[5] = {1, 2, 3, 4, 5};
int *pv = vector;
指针变量 pv 指向数组的第一个元素而不是数组本身。给 pv 赋值是把数组的第一个元素的地址赋值给 pv。使用数组的名字可以表示数组的首地址，即达到 &vector[0] 的效果。以下代码输出的结果是一样的，输出的结果都是数组的首地址。
printf("%p", vector);
printf("%p", &vector[0]);
有时候会使用 &vector 这个表达式获取数组的地址，不同于其他表达式，这么做返回的是整个数组的指针，其他两种情况返回的是整数指针。
我们可以把数组下标用在指针上，例如 pv[i]，pv 指向的是数组的首元素，那么它包含首元素的地址，方括号表示会取出 pv 中包含的地址，用指针算术运算把索引 i 加上，然后解引新地址返回其内容，返回的内容是数组的第 i+1 个元素的值。这里的给地址加上一个整数会将地址增加这个整数和数据类型长度的乘积，这一点对于数组名字上加上整数也适用，因为此时的数组名表示的是地址。 比如这里的 pv 指向的是整型对象，那么 +1 操作实际上就是 + 1 * sizeof(int)。
pv[i] 表达式等价于 vector[i]、*(pv+i)、*(vector + i) 这些表达式。 假设 vector 位于地址 100，pv 位于地址 96，表 1-1 和 图 1-4 说明了如何利用数组下标和指针算术运算分别从数组名字和指针得到不同的值。
下面的代码展示的是遍历一维数组的数组表示法和指针表示法。
// ① 数组下标法
for (int i = 0; i < n; ++i) {
printf("%d\n", vector[i]);
}
// ② 指针表示法
for (int i = 0; i < n; ++i) {
printf("%d\n", *(vector + i));
}
vector[i] 表示法生成的机器码从位置 vector 开始，移动 i 个位置，取出内容。而 *(vector + i) 表示法生成的机器码则是从 vector 首地址开始，在地址上增加 i，然后取出这个地址的内容。
首先我们声明并初始化一个二维数组，如下所示：
int matrix[2][5] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10}
};
现在打印数组元素的地址和值：
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 5; ++j) {
printf("matrix[%d][%d] Address: %p Value: %d\n", i, j, &matrix[i][j], matrix[i][j]);
}
}
// 输出
matrix[0][0] Address: 100 Value: 1
matrix[0][1] Address: 104 Value: 2
matrix[0][2] Address: 108 Value: 3
matrix[0][3] Address: 112 Value: 4
matrix[0][4] Address: 116 Value: 5
matrix[1][0] Address: 120 Value: 6
matrix[1][1] Address: 124 Value: 7
matrix[1][2] Address: 128 Value: 8
matrix[1][3] Address: 132 Value: 9
matrix[1][4] Address: 136 Value: 10
二维数组是按照 行-列 顺序存储的，也就是说，将第一行按顺序存入内存，然后是第二行按顺序存入内存。内存分配如图 1-5 所示。
现在我们想用指针表示法访问二维数组的第二个元素，首先看一下下面的代码：
printf("%p\n", matrix);
printf("%p\n", matrix + 1);
// 输出
// 100
// 120
上面代码的输出结果显示 matrix 返回的是数组第一个元素的地址；matrix + 1 返回的地址不是从数组开头偏移了 4，而是偏移了第一行的长度 20 字节。
要想访问数组的第二个元素，也就访问数组第一行的第二个元素，我们需要知道第一行第一个元素的地址，然后利用指针算术运算的方法 +1 便可以得到第二个元素的地址，解地址即可得到第二个元素的值。具体代码如下所示：
printf("%p %d\n", matrix[0] + 1, *(matrix[0] + 1));
// 输出
// 104 2
图 1-6 中表明 matrix[0] 指向二维数组中第一行第一个元素，matrix[1] 指向二维数组中第二行第一个元素。
matrix：二维数组名，代表的是二维数组首行元素的地址。
matrix[0]：指向二维数组中第一行第一个元素，即表示的是二维数组中第一行第一个元素的地址。
matrix[1]：指向二维数组中第二行第一个元素，即表示的是二维数组中第二行第一个元素的地址。
还可以通过数组指针的方法，遍历二维数组中的任意一个元素。如下所示是数组指针的声明与初始化：
int (*p)[5] = matrix;
(*p)[5] 表达式声明了一个数组指针，初始化后它的指向的是一个包含 5 个整数的一维数组即二维数组首行的一维数组。因为在前面对二维数组名字的分析中我们知道，二维数组名表示的是二维数组首行元素的地址，所以数组指针 p 指向的是二维数组第一行的一维数组。通过对地址解引即 *p 操作可以获得首行的首地址。
这里数组指针需要和指针数组进行区分，把上述声明中数组指针的括号去掉后，表达式即是指针数组，指针数组的数组元素是指针。
接下来将对 p[i][j]、*(*(p+1)+1)、*(p[1]+1)、(*p)[3] 几个表达式逐一解读。
p[i][j]
p 指向的是二维数组第一行数组，那么它包含首元素的地址，第一个方括号表示会取出 p 中包含的行地址，用指针算术运算把索引 i 加上得到新的行地址，第二个方括号表示会取出 p 中包含的列地址，用指针算术运算把索引 i 加上得到新的列地址，最后解引新的地址返回内容。因此，p[i][j] 表示的是二维数组第 i+1 行第 j+1 列的元素。
*(*(p+1)+1)
p 指向的是二维数组首行的一维数组，利用指针算术运算 +1 操作，(p+1) 指向的就是二维数组第 2 行的一维数组，*(p+1) 即可得到第 2 行一维数组的首地址，*(p+1)+1 指向的第 2 行中第 2 个元素，*(*(p+1)+1) 表示拿到二维数组第 2 行的第 2 个元素值 7。
*(p[1]+1)
p[1] 操作和上述的 *(p+1) 效果一致指向的都是二维数组第二行的一维数组，最终 *(p[1]+1) 表示的是二维数组第 2 行第 2 个元素值 7。
(*p)[3]
*p 操作可以获得首行的首地址，中括号表示取出 *p 中包含的地址， 用指针算术运算把索引 i 加上得到新该行第 4 列的地址，最后解引用返回 4，因此该表达式表示的是二维数组第 1 行第 4 个元素值。
在堆上分配一块内存并将地址赋值给一个指针，那么就可以对指针使用数组下标进行访问，这块内存也就是一个数组。下面的代码表示的是在内存上申请一块可以容纳 5 个整型数据的空间作为数组。指针 pv 指向的就是申请的内存空间，对 pv 使用数组下标访问数组并赋初值。图 1-7 是代码对应的内存分配示意图。
int *pv = (int*)malloc(5 * sizeof(int));
for (int i = 0; i < 5; ++i) {
pv[i] = i + 1;
}
为二维数组动态分配内存涉及到分配的内存是否要求连续的问题，据此可以将动态内存分配分为分配可能不连续的内存和分配连续的内存。
分配可能不连续的内存
下面的代码演示了如何创建一个内存可能不连续的二维数组。对 “外层” 和 “内存” 数组用 malloc() 进行内存分配。
int rows = 2;
int cols = 5;
int **matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; ++i) {
matrix[i] = (int *)malloc(cols * sizeof(int));
}
因为分别用 malloc() 分配内存，所以内存不一定是连续的。如图1-8 所示。实际的分配情况取决于堆管理器和堆的状态，内存也有可能是连续的。
分配连续的内存
分配连续的内存有两种方法，第一种首先分配外层的内存，然后在第一行分配所有元素需要的内存，接着将第一行分配内存的剩下部分（被被占用的部分）赋值给其他行使用；第二种方法是直接一次性分配好所有的内存。
首先来看第一种内存的分配方法：
int rows = 2;
int cols = 5;
int **matrix = (int **)malloc(rows * sizeof(int *));
matrix[0] = (int *)malloc(rows * cols * sizeof(int));
for (int i = 1; i < rows; ++i) {
matrix[i] = matrix[0] + i * cols;
}
分配的情况如图 1-9 所示。
接着看一下第二种方法一次性分配好所有的内存。
int *matrix = (int *)malloc(rows * cols *sizeif(int));
分配的情况如图 1-10 所示。
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
*(arr + (i*cols) + j) = i + j;
}
}
将一维数组作为参数传递给函数实际是通过值来传递数组的地址，这样传递消息就很高效，因为我们不需要传递整个数组，从而也不需要在栈上分配内存。这样意味着需要传递数组的长度，否则在函数看来只有数组的地址却不知道数组的长度。
除非数组内部有信息告诉我们数组的边界，否则就需要在传递数组的同时传递数组的长度信息。因为通常一维数组的传递是传递地址的，缺少数组的边界信息，因此还要传递一个数组的长度。如果数组传递的是字符串信息，由于字符串本身字符串终止符 NUL 字符，这时可以不用传递数组长度。
关于一维数组的传递，我们可以使用以下两种表示法之一：数组表示法和指针表示法。
下面的例子将一个整数数组和数组的长度传递给函数，并打印其内容：
void displayArray1(int arr[], int size) {
for (int i = 0; i < n; ++i) {
printf("%d", arr[i]);
}
}
void displayArray2(int arr[], int size) {
for (int i = 0; i < n; ++i) {
printf("%d ", *(arr+i));
}
}
int vector[5] = {1, 2, 3, 4, 5};
displayArray1(vector, 5); // 输出 1 2 3 4 5
displayArray2(vector, 5); // 输出 1 2 3 4 5
在声明函数的时候使用的是数组表示法，在函数体内部既可以使用数组表示法也可以使用指针表示法遍历数组，因为函数传递一维数组参数的本质是用值传递的方式传递数组的地址，函数体内部都可以使用 [] 或者 * 解引出相应的值。
声明函数的数组参数也可以使用指针表示法，如下所示：
void displayArray3(int *arr, int size) {
for (int i = 0; i < n; ++i) {
printf("%d", arr[i]);
}
}
void displayArray4(int *arr, int size) {
for (int i = 0; i < n; ++i) {
printf("%d ", *(arr+i));
}
}
void main() {
int vector[5] = {1, 2, 3, 4, 5};
displayArray3(vector, 5); // 输出 1 2 3 4 5
displayArray4(vector, 5); // 输出 1 2 3 4 5
}
在声明函数的时候使用的是指针表示法，在函数体内部既可以使用数组表示法也可以使用指针表示法遍历数组。
多维数组不同于一维数组，一维数组只可能是一行，而多维数组可能是有有限行的二维数组，还可能是包含了 行-列-阶 的三维数组等等。因此在传递多维数组的时候，最重要的一件事是传递信息中要包含多维数组的形态即维度信息。
这里以二维数组为例。首先看两种传递方法：
void display2DArray(int arr[][5], int rows) {}
void display2DArray(int (*arr)[5], int rows) {}
以上的两种写法都指明了数组的列数，因为这是二维数组，编译器需要知道每行有几个元素。并且需要传递一个表示行数的信息。
在上面的第一种写法中，arr[] 是数组指针的一个隐式声明，而第二种写法 (*arr) 是数组指针的一个显示声明。接下来补全显示的数组指针的函数：
void display2DArray(int (*arr)[5], int rows) {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < 5; ++j) {
// ① ② 等价，选用一个即可
printf("%d ", arr[i][j]); // ①
// printf("%d ", *(*(arr+i)+j)); // ②
}
}
}
void main() {
int matrix[2][5] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10}
};
display2DArray(matrix, 2);
}
在函数体内部既可以使用数组表示法也可以使用指针表示法遍历数组，即 ① ② 处输出结果一致。
目前我遇到的最常见的传递方法是这样的：
void display2DArray(int **arr, int rows, int cols) {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
// ① ② 等价，选用一个即可
printf("%d ", arr[i][j]); // ①
// printf("%d ", *(*(p+i)+j)); // ②
}
}
}
void main() {
int rows = 2;
int cols = 5;
int **matrix = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; ++i) {
matrix[i] = (int *)malloc(cols * sizeof(int));
}
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
matrix[i][j] = i + j;
}
}
display2DArray(matrix, rows, cols);
return 0;
}
这种利用二级指针来传参的方法和数组指针类似，二级指针指向指针的指针，外层指针指向的是数组的行，解引即可得到行的一维数组，内层指针指向的是一维数组，解引即可得到一维数组首元素。
还有可能遇到下面这种函数，接受的参数是一个指针和行列数：
void display2DArrayUnknownSize(int *arr, int rows, int cols) {
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
printf("%d ", *(arr + (i*cols) + j)); // ①
// 等价于 printf("%d ", (arr+i)[j]); // ②
}
}
}
void main() {
int matrix[2][5] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10}
};
display2DArrayUnknownSize(&matrix[0][0], 2, 5);
}
将二维数组的第 1 行的第 1 个元素传递给函数，说明二维数组的存储是按照一维数组的在内存中的顺序存储方式进行存储的，通过 ① 或者 ② 处代码输出所有元素。为什么只能使用一个下标如 ② 中所示？因为编译器不知道一维的长度，只能用数组内部的偏移移动到相应的行。