第 4 讲 · 指针、结构与动态内存

链表、树和图之所以能够动态生长，靠的是指针和动态内存。这里最容易混乱的不是语法，而是三个问题：指针现在指向谁、那块对象还活着吗、谁负责释放它？

指针保存地址

int x = 10;
int *p = &x;

p 的值是 x 的地址，*p 才是该地址上的整数。&x 取地址，*p 解引用。指针类型决定解引用时如何解释内存，以及 p+1 要跨过多少字节。

指针使用前必须指向合法对象。未初始化的指针、已经离开作用域的局部变量地址、已经 free 的地址，都不能再解引用。

数组与指针相似但不相同

在大多数表达式中，数组名会转换成首元素地址，所以 a[i] 等价于 *(a+i)。但数组本身是一块固定对象，数组名不能改成指向别处；普通指针变量可以重新赋值。

int a[5];
int *p = a;       /* p 可以移动 */
int (*q)[5] = &a; /* q 指向整个含 5 个 int 的数组 */
int *r[5];        /* r 是由 5 个 int* 组成的数组 */

括号改变结合方式，因此“数组指针”和“指针数组”必须从变量名向外读。

参数传递仍然是值传递

C 函数参数都是值传递。把指针传给函数，是复制一份地址值；通过这份地址可以修改所指对象，但在函数里让指针变量改指别处，不会自动改变调用者的指针变量。

若函数要修改调用者保存的指针本身，需要传入“指向该指针的指针”，或者返回新的指针。这也是链表插入可能改变头指针时常见的两种接口。

动态内存的生命周期

int *a = malloc((size_t)n * sizeof *a);
if (a == NULL) {
    /* 分配失败 */
}
/* 使用 a */
free(a);
a = NULL;

malloc 只分配未初始化的字节；calloc 会清零；realloc 可能搬迁整块内存，因此成功后旧指针不能再用。每一块成功分配的内存最终应恰好释放一次。

常见错误包括：内存泄漏、重复释放、释放非起始地址、越界写、释放后继续访问。

结构把相关字段组成一个对象

typedef struct Student {
    int id;
    char name[32];
    double score;
} Student;

结构变量用 . 访问成员，结构指针用 ->。表达式 p->id 等价于 (*p).id。

结构可以整体赋值和作为函数参数，但按值传入会复制全部字段。较大的结构通常传指针；只读时使用 const Student *。

自引用结构形成链

typedef struct Node {
    int data;
    struct Node *next;
} Node;

结点中不能直接包含另一个完整的同类型结点，否则大小会无限递归；保存同类型指针则只占固定地址空间。

创建结点最好集中到函数中：

Node *new_node(int value) {
    Node *p = malloc(sizeof *p);
    if (p == NULL) return NULL;
    p->data = value;
    p->next = NULL;
    return p;
}

这样每次创建都能统一完成判空和初始化。

函数指针与回调

函数也有地址。标准库 qsort 不知道元素的具体类型和排序规则，因此接收一个比较函数指针。比较函数必须遵守约定：小于返回负数，等于返回零，大于返回正数。

int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

不要直接 return x-y，因为整数差可能溢出。

预处理、字符分类与命令行参数

源课件把几项常用 C 工具放在复杂程序设计部分：

  • #define 在编译前做文本级替换。带参数宏必须给参数和整个展开式加括号，并注意参数可能被求值多次；
  • <ctype.h> 中的 isalpha、isdigit、isspace、tolower 等函数适合词法扫描。传入值应为 EOF，或能表示为 unsigned char 的值；
  • main(int argc, char *argv[]) 通过 argc 给出参数个数，argv 保存各参数字符串，适合把输入文件名和运行选项放到命令行；
  • 函数指针既可以作为 qsort 的比较器，也可以组成操作表，让程序按类型选择处理函数。

这些工具不改变数据结构本身，却能让文件处理、排序和综合项目的接口更清楚。

画图追踪指针

处理动态结构时，把每个结点画成“数据域 + 指针域”，把指针变量画成单独的箭头。每执行一条赋值就移动或重连对应箭头。若旧链接还没保存就被覆盖，那部分结构会立刻丢失。

这也是源课件反复强调链表题要在草稿纸上画图的原因：图能把“地址值的变化”变成肉眼可检查的结构变化。

评论