指针专题：指针及数组

2016-01-16

本文阐述指针及数组的之间的联系。

指针及数组

指针和数组是一样的吗？

经常可以看到

一维数组是一级指针
二维数组是二级指针
数组名是一个常量指针
数组名是一个指针常量

这些说法，但真的是这样吗？让我们先看一下指针和数组的定义。

指针与数组概念

博文数组与指针概念剖析对指针及数组的概念有很深刻的探讨，特整理如下（概念部分）。

指针：根据 C99 标准，指针的定义如下：

A pointer type may be derived from a function type or an object type, called the referenced type. A pointer type describes an object whose value provides a reference to an entity of the referenced type. A pointer type derived from the referenced type T is sometimes called “pointer to T”. The construction of a pointer type from a referenced type is called “pointer type derivation”.

指针是一种派生类型，它描述了这样一个对象，其值为对某种类型实体的引用。标准在这里所用的措词是指针类型描述了一个对象。

但我们再看一下取址运算符&的定义：

The unary & operator returns the address of its operand. If the operand has type “type”, the result has type “pointer to type”……. Otherwise, the result is a pointer to the object or function designated by its operand.

这个条款规定，& 运算符的结果是一个指针。但问题是，& 表达式的结果不是对象！标准自相矛盾了吗？当然不是，这说明的是，指针的实体有对象与非对象两种形态。

我们常说的指针变量只是指针实体的对象形态，但对象与非对象两种形态合起来，才是指针的完整涵义，就是说，无论是否对象，只要是一个具有指针类型的实体，都可以称之为指针，换言之，指针不一定是对象，也不一定是变量。

数组：数组的定义如下：

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. Array types are characterized by their element type and by the number of elements in the array. An array type is said to be derived from its element type, and if its element type is T , the array type is sometimes called “array of T”. The construction of an array type from an element type is called “array type derivation”.

数组类型同样是派生类型，它描述了某种对象的连续的非空集合，由其中元素类型和元素个数来刻画。

由指针和数组定义可以看出，指针和数组是完全不同的类型。这里还有另外一个问题。

数组名是指针吗？

根据《征服C指针》一书，数组名并不是指针，只不过在表达式中，数组名可以解读成“指向它的初始元素的指针”。

在另一篇博文数组名是一个指针常量吗？中，作者就分析的更加透彻：

数组名是一个指针常量这种观点来源于数组名在表达式计算中与指针的结果等效性。例如下面的代码：

1
2
3

int a[10], *p = a, *q;
q = a + 1;
q = p + 1;

在效果上看，a + 1 与 p + 1 是相同的，这很容易给人一种 a 就是 p 的假象，但，这仅仅是假象。

在《C与指针》一书中，作者用一个著名的例子阐述了数组名与指针的不同。在一个文件中定义：int a[10]; 然后在另一个文件中声明：extern int *a; 笔者不在这里重复其中的原理，书中的作者试图从底层操作上阐述数组名与指针的不同点，但笔者认为这个例子存在一些不足，a 在表达式中会转换为一个非对象的符号地址，而指针 a 却是一个对象，用一个非对象去跟一个对象比较，有“偷跑”的嫌疑，这个例子只是说明了数组名的非对象性质，只能证明对象与非对象实体在底层操作上的不同，事实上，如上一章所述，指针也有非对象形态。笔者认为，无须从底层的角度上花费那么多唇舌，仅仅从字面上的语义就可以推翻数组名是一个指针的观点。

首先，在C/C++中，数组类型跟指针类型是两种不同的派生类型，数组名跟指针是两种不同类型的实体，把数组类型的实体说成“是”另一个类型的实体，本身就是荒谬的；

其次，a + 1 在效果上之所以等同于 p + 1，是因为 a 进行了数组到指针的隐式转换，这是一个转换的过程，是 converted to 而不是 is a 的过程。如果是两个相同的事物，又怎会有转换的过程呢？当把 a 放在 a + 1 表达式中时，a 已经从一个数组名转换为一个指针，a 是作为指针而不是数组名参与运算的；

第三，a + 1 与 p + 1 是等效关系，不是等价关系。等价是相同事物的不同表现形式，而等效是不同事物的相同效果。把数组名说成是指针实际上把等效关系误解为等价关系。

因此，数组名不是指针，永远也不是，但在一定条件下，数组名可以转换为指针。

而根据《C和指针》一书的第 8 章 8.1 节，作者提到：“只有当数组名在表达式中使用时，编译器才会为它产生一个指针常量”。注意这个值是指针常量，而不是指针变量。我们不能修改常量的值。只有在两种场合下，数组名在表达式中不用指针常量来表示——就是当数组名作为 sizeof 操作符或单目操作符 & （如 &a[0]）的操作数时。sizeof 返回整个数组的长度，而不是指向数组的指针的长度。取一个数组名的地址所产生的是一个指向数组的指针，而不是一个指向某个指针常量值的指针。

综上所述，数组不是指针，数组名也只有在表达式中才会被当成一个指针常量。

下标运算符`[]`和数组有关系吗？

对于下标运算符，相信大家都再熟悉不过了，我们可用其方便快速访问数组中的元素。但它和数组有关系吗？先来看一个例子：

#include <iostream>
using namespace std;

int main()
{
    int p[10];
    for (int i = 0; i < 10; i++)
        p[i] = i + 1;

    cout << "*(p + i)\t" << "p[i]" << endl;
    for (int i = 0; i < 10; i++)
        cout << *(p + i) << "\t\t" << p[i] << endl;

    return 0;
}

程序输出如下：

所以，*(p + i) 跟 p[i] 的效果是一样的。根据《征服C指针》，p[i] 这种写法只不过是 *(p + i) 的简便写法。实际上，至少对于编译器来说，[] 这样的运算符完全可以不存在。[] 运算符是为了方便人们读写而引入的，是一种语法糖。

注意，认为[]和数组没有关系中的[]指的是表达式中出现的下标运算符，而不是声明中的[]。

题外话：判断机器大小端问题

从上边的分析，我们知道对数组元素的访问本质上是需要解引用的，如访问第 i 个元素需要采用 *(p + i) 的形式。这种做法跟指针的解引用一模一样。既然指针所指向的内存在堆（指针变量在栈）中，那数组的元素是不是应该存储在堆（数组名存储在栈）？答案是肯定的。具体可参考博文内存中的数组。数组在虚拟内存空间中的存储示意图如下（以上述程序为例）：

而对于大小端，他们的简单定义如下（以数字 0x12345678 在内存中的表示形式为例）：

小端就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。所以，对于数字 0x12345678 而言，它在内存中的存储顺序为：
低地址 —————> 高地址
0x78 | 0x56 | 0x34 | 0x12
大端就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。所以，对于数字 0x12345678 而言，它在内存中的存储顺序为：
低地址 —————> 高地址
0x12 | 0x34 | 0x56 | 0x78

综上，我们利用一下简单程序就可以判断出机器的大小端：

#include <stdio.h>
#include <stdlib.h>

void checkEndian()
{
    union
    {
        int s;
        char c[4];
    }u;

    u.s = 0x12345678;
    printf("%s\n", (0x12 == u.c[0]) ? "大端模式" : "小端模式");
}

int main()
{
    checkEndian();
    return 0;
}

sizeof 对指针和数组求得的不同结果

请看一小程序：

#include <iostream>
using namespace std;

void myFunc(int a[])
{
    cout << sizeof(a) << endl;
}

int main()
{
    int a[]{1, 2, 3, 4};
    int *p = a;
    cout << sizeof(a) << endl;
    cout << sizeof(p) << endl;
    myFunc(a);
    
    return 0;
}

在本人机器上的运行结果如下:

很明显，对于数组而言，sizeof 的结果是数组所占的所有字节数；而对于指针而言，sizeof 的结果是指针类型的大小。为什么呢？因为：

对于数组而言，它的大小是固定的和已知的，所以 sizeof 求到的结果是数组所占的所有字节数（虽然在表达式中数组名被当作指针处理）；
对于指针而言，sizeof 无法知道指针类型，也就无法确定指针所指向的内存的大小，所以要让 sizeof 返回指针所指向的内存大小是不现实的，而返回指针类型大小很简单，因为只跟系统位数相关。

注意：下边一小段这是个人以前说法，不正确，不过可以作为参照，以加深理解。

对于指针而言，我们只能知道它指向的内存的字节大小，而无法知道它知道它指向的连续内存的字节大小（因为不清楚在哪里结束），所以 sizeof 是无法返回指针所指连续内存的字节大小。在这种情况下，可能返回指针类型的大小可能较好。

另外，当把数组作为函数的参数进行传递时，该数组自动退化为同类型的指针。所以函数myFunc输出结果是4。

二级指针和指针数组

二级指针是指向指针的指针的简称，如下常见例子：

int **p;

而指针数组则是元素类型为指针的数组，如：

1	int *p[10];

二级指针和指针数组区别与联系

我们知道指针和数组是不一样的，当然二级指针和指针数组也是不一样的。那他们有什么联系呢？　　

下边请看一个例子：

对于main函数，常见的其中两种写法如下：

1	int main(int argc, char *argv[]);

或

1	int main(int argc, char **argv);

根据 Linux C 编程一站式学习说法，函数原型中的 [] 表示指针而不表示数组，等价于 char **argv。那为什么要写成 char *argv[] 而不写成 char **argv 呢？这样写给读代码的人提供了有用信息，argv 不是指向单个指针，而是指向一个指针数组的首元素。数组中每个元素都是 char * 指针，指向一个命令行参数字符串。

其实，就算在表达式中，它们也是等效的。

二级指针和指针数组如何表示二维数组？

在表达式中，二级指针和指针数组是等效的。所以我们下文可以只以二级指针来说明。

对于一个二级指针而言，第一级指针指向一个指针数组的首元素，因此利用下标运算符[]即可获得指针数组的每一个元素；而指针数组每个元素存储的是指针，可以再额外指向另一个数组。这样一来，我们就可以利用二级指针来实现一个二维数组了，如下例：

先看一个简单例子：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
    int i;
    for(i = 0; i < argc; i++)
    {
        printf("argv[%d]=%s\t", i, argv[i]);
        int len = strlen(argv[i]), j;
        for(j = 0; j < len; j++)
            printf("%s[%d]=%c ", argv[i], j, argv[i][j]);
        printf("\n");
    }
    return 0;
}

在Linux下编译执行：

二级指针妙用：删除单向链表

主要参考：

Two star programming
Linus：利用二级指针删除单向链表（有详细解释，非常值得参考！）

在删除单向链表（保留头指针head）时，我们可能会采用比较典型的做法：

typedef struct node
{
    struct node * next;
    ....
} node;

typedef bool (* remove_fn)(node const * v);

// Remove all nodes from the supplied list for which the 
// supplied remove function returns true.
// Returns the new head of the list.
node * remove_if(node * head, remove_fn rm)
{
    for (node * prev = NULL, * curr = head; curr != NULL; )
    {
        node * const next = curr->next;
        if (rm(curr))
        {
            if (prev)
                prev->next = next;
            else
                head = next;
            free(curr);
        }
        else
            prev = curr;
        curr = next;
    }
    return head;
}

但Linus大婶就要说这样子写的人了：“This person doesn’t understand pointers”。那对于Linus大婶来说，怎样做才是最好的？那就是利用二级指针，具体如下：

void remove_if(node ** head, remove_fn rm)
{
    for (node** curr = head; *curr; )
    {
        node * entry = *curr;
        if (rm(entry))
        {
            *curr = entry->next;
            free(entry);
        }
        else
            curr = &entry->next;
    }
}

果然，改写之后的程序简洁了许多，而且也不需要维护一个 prev 表项指针和考虑头指针的问题。

在博文Linus：利用二级指针删除单向链表中，作者对利用二级指针的程序还附上了一个比较详细的解说：

对于——

删除节点是表头的情况，输入参数中传入 head 的二级指针，在 for 循环里将其初始化 curr，然后 entry 就是 *head(*curr)，我们马上删除它，那么第 8 行就等效于 *head = (*head)->next，就是删除表头的实现。

删除节点不是表头的情况，对于上面的代码，我们可以看到——

（第12行）如果不删除当前结点 —— curr 保存的是当前结点 next 指针的地址。

（第5行） entry 保存了 *curr —— 这意味着在下一次循环：entry 就是 prev->next 指针所指向的内存。

（第8行）删除结点：*curr = entry->next; —— 于是：prev->next 指向了 entry -> next;