8. 指针

1. 定义

不同概念

本篇讲义所说的指针，和 体系结构 中的指针不是同一个概念：前者指语言特性，是 C 语言中一类类型的统称；后者指特定的整数字节地址（偏移量）。

1. 指针是一种对象类型，它引用函数或另一种类型的对象
2. 指针可以不引用任何内容，此时他是一个空指针

2. 声明

1. 指针声明符的格式：* 声明符（一个星加上另一个声明符）

   函数声明符：声明符 ( 形参列表 )
   数组声明符：声明符 [ 表达式 ]
   当上述两行的声明符是指针声明符时，得加括号

2. 其中 声明符 可以是标识符，也可以是其他的声明符（包括指针声明符）

3. 如果指针声明符是其他声明符的 声明符 部分，那么声明一个“指向”其他声明符声明的类型“的指针”

   int **p;
    // '**p' 是 指针声明符
    // 他的“声明符”部分为 '*p'，是个指针声明符
    // 声明一个指向“指向 int 的指针”的指针

3. 取地址与解引用

指针最基础的两个操作是取地址 & 和解引用 *。前者从对象得到地址，后者通过地址访问对象。

int n = 10;
int *p = &n;

*p = 20;

这里 p 保存 n 的地址，对 *p 赋值会直接修改 n。空指针或无效地址解引用会导致未定义行为，因此解引用前应保证地址有效。

4. 空指针

空指针表示“不指向任何对象”，通常写作 NULL。空指针可以比较、赋值、传参，但不能解引用。

#include <stddef.h>

int *p = NULL;
if (p == NULL) {
    /* 尚未绑定对象 */
}

5. 指针与数组

数组表达式在大多数上下文会退化为首元素指针，因此数组与指针在访问语法上经常看起来相似，但两者并不是同一种类型。

int arr[4] = {1, 2, 3, 4};
int *p = arr;      /* 等价于 &arr[0] */

int a = arr[2];
int b = p[2];

arr 的类型是“4 个 int 的数组”，p 的类型是“指向 int 的指针”；sizeof arr 与 sizeof p 一般不同。

6. 指针算术

指针加减是按“所指对象类型大小”移动，而不是按字节裸移动。p + 1 表示跳到下一个同类型对象地址。

int arr[3] = {10, 20, 30};
int *p = arr;

int x = *(p + 1); /* 20 */

越过同一数组对象边界（除“尾后位置”外）进行访问是未定义行为。

7. const 与指针

const 位置不同，含义不同：

int a = 1;
int b = 2;

const int *p1 = &a; /* 不能通过 p1 修改对象值 */
int *const p2 = &a; /* p2 的地址绑定不可变 */

这两种形式分别约束“所指对象可改性”和“指针自身可改性”，阅读声明时要分开判断。

8. 函数指针

函数也有地址，可通过函数指针实现回调与策略分发。

int add(int x, int y) {
    return x + y;
}

int main(void) {
    int (*fp)(int, int) = add;
    return fp(3, 4) == 7 ? 0 : 1;
}

函数指针是 C 接口抽象的关键能力，标准库中的 qsort、bsearch 都依赖它。

9. 习题

#10801

⚡2⏳2

实现整数数组的原地反转：

#include <stddef.h>

void reverse_i32(int *items, size_t count);

要求：

1. 反转后，第 i 个元素应当等于反转前的第 count - 1 - i 个元素。
2. count 为 0 时不得访问 items，此时 items 可以为 NULL。
3. count 大于 0 时，items 必须指向至少包含 count 个 int 的数组。
4. 函数体只能使用指针运算和解引用访问元素，不得使用下标运算符。
5. 时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

#10802

⚡3⏳2

实现带回调的条件计数：

#include <stdbool.h>
#include <stddef.h>

typedef bool (*IntPredicate)(int value);

bool count_if_i32(
    const int *items,
    size_t count,
    IntPredicate predicate,
    size_t *out_count
);

要求：

1. 成功时按下标递增顺序把每个元素恰好传给 predicate 一次，并通过 out_count 返回结果。
2. count 为 0 时 items 可以为 NULL，函数应成功并返回计数 0。
3. predicate 或 out_count 为 NULL，以及 count > 0 但 items 为 NULL 时，返回 false。
4. 失败时不得修改 *out_count。
5. 时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

#10803

⚡4⏳3

实现使用函数指针比较元素的通用稳定排序：

#include <stdbool.h>
#include <stddef.h>

typedef int (*CompareFn)(const void *left, const void *right);

bool generic_stable_sort(
    void *base,
    size_t count,
    size_t element_size,
    CompareFn compare
);

要求：

1. compare 的返回值小于、等于或大于 0 时，分别表示左侧元素应排在右侧元素之前、两者等价或左侧元素应排在右侧元素之后。
2. 等价元素排序后的相对次序不得改变。
3. count 为 0 时 base 可以为 NULL；element_size 必须大于 0，compare 必须有效。
4. 拒绝会使 count * element_size 溢出的调用，失败时不得修改数组。
5. 只能按字节交换对象表示，不得假设元素具有某个具体类型。
6. 使用稳定插入排序，额外空间复杂度为 $O(1)$。

形参数组声明的调整规则

关于指针

本节涉及指针语法（int *a 是声明指针类型的形参，* 表示间接访问）。指针是第8章的核心内容，此处只需理解「函数通过指针形参可以访问调用方传入的对象」即可。

函数形参中写成数组形式时，会调整为指针类型参与函数类型匹配。例如 void f(int a[10]); 与 void f(int *a); 在函数声明层面等价。这个规则经常导致“在声明里写了长度就以为接口会自动检查长度”的误解；长度约束若要生效，仍需由调用方协议或额外参数保证。

void fill(int a[10], int n);   /* 声明层面 a 仍是 int * */
void fill(int *a, int n);      /* 与上式兼容 */

void 指针的转换边界

对象指针在 void* 之间的往返转换是 C 里常见能力，但前提是“转回原始对象类型”再使用。若转成不兼容类型后直接解引用，行为就不再有保障。

int x = 42;
void *vp = &x;
int *ip = (int *)vp;   /* 转回原类型 */

这个模式常用于通用容器和回调接口，但转换点应尽量集中、可审计。