[数据结构与算法]数组和指针

首先看一维数组的定义和使用

int array[5] = {1, 2, 3, 4, 5};

array是具有5个整型元素的一维数组，5个元素连续存放在以数组名array为起始的内存空间中。

用数组名访问：

访问数组array中的元素，可以直接用数组名访问，例如array[0]代表数组中的第一个元素，array[3]代表数组中的第4个元素；

array和array[0]的地址是一样的，都代表这个数组的起始地址。

#include <stdio.h>

int main()
{
    int array[5] = {1, 2, 3, 4, 5};
    printf("array[3] is %d\n", array[3]);
    printf("the address of array is 0x%x\n", array);
    printf("the address of array[0] is 0x%x\n", &array[0]);
}

运行结果：

array[3] is 4
the address of array is 0x4379d40
the address of array[0] is 0x4379d40

用指针方式访问：

定义一个指针int *p = array; p指向了数组array（也可以通过p = &array[0]来进行赋值），此时*p的值为array中第一个元素的值，访问第4个元素可以通过*(p+3)进行；也可以通过p[0]或p[3]访问数组。

#include <stdio.h>

int main()
{
    int array[5] = {1, 2, 3, 4, 5};
    int *p;
    p = array;
    printf("*p is %d\n", *p);
    printf("*(p+3) is %d\n", *(p+3));
    printf("p[0] is %d\n", p[0]);
    printf("p[3] is %d\n", p[3]);
}

运行结果如下：

*p is 1
*(p+3) is 4
p[0] is 1
p[3] is 4

从一维数组的访问上来说，无论通过array[3]还是p[3]的形式访问，编译器都转换成类似于 array+3或p+3的地址，然后通过指针的方式访问。

需要注意的是p作为指针变量是可以进行自加之类的运算，但是array的自加运算或赋值都是非法的，这是因为array在编译后就是一个确定的值，永远指向数组array，不能再次被改变，这个特性类似于const指针（int *const p = array，p不能再次被赋值）。例如：

array++

此时编译器会报下面错误：

/usercode/file.cpp: In function 'int main()':
/usercode/file.cpp:7:46: error: lvalue required as increment operand

下面讨论一维数组作为函数参数的情况：

由于数组名也是指针，所以函数的入参应该也是指针的形式。入参有两种形式：

一种是 f(int *p)，另一种是f(int p[])

从下面的示例中可以发现，上面两种形式没有任何区别，怀疑编译器会把 *p和p[]视为等同，甚至对于入参p[]，中括号中写成几都会被编译器所忽略，例f(int p[3])

#include <stdio.h>
void showArray(int *p);
void showArrayP(int p[0]);
int main()
{
    int array[5] = {1, 2, 3, 4, 5};
    showArray(array);
    showArrayP(array+1);
}

void showArray(int *p)
{
    printf("%d\n", *p);
}

void showArrayP(int p[1])
{
    printf("%d\n", p[1]);
}

运行结果?分别为1和3

上面例子中，showArray函数的定义和声明中的参数都不一致，也没有报任何错误。

在数组中有一种特殊的数组是指针数组，指针数组中的每个元素都是指针。例：

int *p[5]? ?定义了一个包含5个元素的指针数组p，数组p中的每一个元素都是指针，指向一个int的整型值。

下面例子验证了数组只是指针的一种异化情况，也就是编译器在处理array[2]完全是按照指针来处理的。

#include <stdio.h>
int main()
{
    int d = 5;
    int *p = &d;
    printf("%d\n", p[0]);
    printf("0x%x\n", p);
    printf("0x%x\n", &p[0]);
}

程序的运行结果为：

5
0x1b089604
0x1b089604

上面例子中指针p指向了一个整型变量，但是却使用了类似数组的形式取元素，此时仍然能够正确的得到整型变量的值。?

延伸到二维数组上，例如定义a[2][3]，当用a[0][0]来取值时在编译器看来?a是一个指向指针的指针，a[0]先取到了第1个行向量的首地址，行向量相当于一个一维数组，含有3个元素；然后a[0][0]是接着取这个行向量的第一个元素。对于a[1][1]来讲，a[1]指的是第二个行向量的地址，a[1][1]取得是第二个行向量的第二个元素。

下面例子验证了二维数组的情形

#include <stdio.h>
int main()
{
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    printf("0x%x\n", a);
    printf("0x%x\n", *a);
    printf("0x%x\n", a[0]);
    printf("0x%x\n", a[1]);
}

运行结果为

0x8b8ad0e0
0x8b8ad0e0
0x8b8ad0e0
0x8b8ad0ec

所以数组只是一种利用指针构造的数据结构。

用指针访问二维数组：

从上面的讲解中，不免思考数组名a到底是一个什么样的指针？首先有一点是明确的，这个指针的类型是int型，即指针指向的是一个int型的数据；那么它是 int *p吗，显然不是，如果是这样，那么p[0]就能直接取到数组的值，但明显指向这个数组名的指针p的p[0]指向的应该是第一个行向量的首地址；那么是int **p指针吗，也不是，因为此时p[1]指向的p[0]的下一个位置即p + 4，而正确定义的指针p的p[1]指向的应该是下一个行向量的首地址，即p+12（因为每个行向量中包含3个int型元素）。

所以可以得出，正确定义的指针p，要满足：p[0]取到的是第一个行向量的地址，p[1](也就是p++)指向的是下一个行向量的首地址。所以我们引出这个指针数组的定义：

int (*p)[3]? = a;

首先p是一个指针，它指向一个具有3个int型元素的数组。这时p++就是 p[0]+12，如果用sizeof得到大小的话可以发现它占据的是12个字节的空间。

另外一种角度，对比int a[2][3] 和int (*p)[3]，其实对于指针的定义就是把a[2]替换成了(*p)，所以*p发挥的作用和a[0] 或 a[1]是一样的，只是用一个变量p来指向不同的数组地址。*p = a[0]，那么p = &a[0]; （这个一维数组的情况是一样的，在一维中，int a[2]; int *p; p = &a[0];）而&a[0]等同于数组名a。

#include <stdio.h>
int main()
{
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int (*p)[3];
    p = a;
    //p = &a[0];
    printf("a is 0x%x\n", a);
    printf("&a[0] is 0x%x\n", &a[0]);
    printf("a[0] is 0x%x\n", a[0]);
    printf("a[1] is 0x%x\n", a[1]);
    
    printf("p[0] is 0x%x\n", p[0]);
    printf("p[1] is 0x%x\n", p[1]);
    printf("p[0][0] is %d\n", p[0][0]);
    printf("p[1][1] is %d\n", p[1][1]);
}

运行结果为

a is 0x5d165170
&a[0] is 0x5d165170
a[0] is 0x5d165170
a[1] is 0x5d16517c
p[0] is 0x5d165170
p[1] is 0x5d16517c
p[0][0] is 1
p[1][1] is 5

作为函数入参：

和一维数组的情况一样，二维数组作为函数入参可以直接用数组名，也可以用数组指针。

int showArray2D(int array[2][3])? 或?int showArray2D(int array[1][3]) 或?int showArray2D(int array[][3])? 但不能是改变列的大小例：

int showArray2D(int array[2][2])，因为此时array指向的不再是3个含有元素的行向量，编译器会报如下错误：

error: cannot convert 'int (*)[3]' to 'int (*)[2]'

指针形式传参如下，即指明了二维数组的类型：

int showArray2D(int (*p)[3])

下面是具体示例：

#include <stdio.h>
void showArray2D(int (*p)[3]);
int main()
{
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    showArray2D(a);
}

void showArray2D(int (*p)[3])
{
    printf("p is %d\n", p[1][1]);
}

总结：

牢记数组也是指针，不同维数的数组对应不同的指针。

推广到3维数组也是类似的情况，例如

int array[2][2][3] = {{{1, 2, 3}, {4, 5 ,6}}, {{-1, -2, -3}, {-4, -5, -6}}};? 对应的指针定义就是一个指向具有2行3列的二维数组指针，即：int (*p)[2][3];