0.1 Pointer、内存与 struct

CSCI2520 虽然不要求你只能用 C 作答，但课堂确实经常用 C 去解释资料结构。原 因很直接：pointer、heap allocation 与 data layout 可以把资料结构在内存 里的行为直接展示出来。

这一节不是一般程序语言教程，而是为了让你后面读 stack、queue、hash table 实现时，不会因为看不懂 C 而失去整个概念。

动机

本地 tutorial 材料强调：考试与书面作业并不限制你一定使用某种语言。但 lecture 与 tutorial 仍然用 C 去说明：

• pointer 实际保存什么；
• 节点怎样用 malloc 建立；
• struct 怎样把字段组织成一个 record；
• typedef 怎样协助 ADT 接口隐藏底层表示。

如果这几样读错，问题不只是 syntax，而是你会看不见资料结构究竟怎样在内存 里运作。

Pointer 保存的是地址，不是值

Tutorial 1 特别区分两个符号：

• &x 表示“x 的地址”；
• *p 表示“pointer p 所指向地址中的值”。

这两个概念一定不能混淆。Pointer 不是 object 本身，而是 object 所在位置 的记录。

int firstvalue = 5, secondvalue = 15;
int *p1, *p2;

p1 = &firstvalue;
p2 = &secondvalue;
*p1 = 10;
*p2 = *p1;
p1 = p2;
*p1 = 20;

int firstvalue = ...; int secondvalue = ...; int *p1, *p2;

读 pointer trace 时，最好一直把两件事分开：

• 每个 pointer 现在指向哪里？
• 那个地址里的值现在是多少？

Dereference 是经地址去读或写

当 pointer 已经持有合法地址之后，dereference 才有意义。

int x = 7;
int *p = &x;
*p = 12;

最后 x 会变成 12。*p = 12 不是建立一个新整数，而是经 p 所记录 的地址，直接写入原来的对象。

局部对象与动态分配对象有不同的生命周期

地址只有在该地址中的对象仍然存活时才有意义。在代码块内声明的局部对象通常 具有 automatic storage duration；执行离开该代码块后，对象的生命周期便 结束。因此，返回局部变量的地址，只会留下一个仍然记得旧位置、却不再指向 存活对象的 pointer。

int *bad_address(void) {
   int local = 7;
   return &local;             /* 函数返回后立即成为 dangling pointer */
}

由 malloc 得到的空间具有 allocated storage duration。即使建立它的 函数已经返回，这块空间仍然存在，直至程序把该次 allocation 交给 free。 这种较长的生命周期，让 linked structure 可以保留先前操作建立的节点。但它 并不表示节点可以永久使用：free(x) 之后，x 及所有保存同一地址的 alias 都成为 dangling pointer。Scope 回答“这个 pointer 变量可以在哪里被命名”， lifetime 回答“它指向的对象现在是否仍存在”；两者不能混为一谈。

malloc 在 heap 上分配空间

资料结构实现经常需要动态建立节点，而不是预先知道总共要几格。这个时候 就要靠 malloc。

典型写法是：

struct node *x = malloc(sizeof *x);
if (x == NULL) {
   /* 报告 allocation failure，或把失败传给调用者 */
}

在成功路径上，x 指向一段足以容纳一个 struct node 的新空间。 sizeof *x 直接跟随 x 的声明类型，不必重复写类型名称。在 C 中， <stdlib.h> 声明 malloc，其返回的 void * 不需要强制转换。

但要记住三件事：

• dereference 之前先检查 x != NULL；
• 在其他代码读取字段之前，逐一初始化所需字段；
• 明确哪一部分程序拥有该节点，并负责最终释放它。

Ownership 让 allocation 成为完整流程

面对每一次 allocation，都应该问三个问题：谁建立它，哪些 pointer 只是暂时 借用访问权，最后由谁释放它？Owner 负责恰好一次结束该 allocation。 Borrowed pointer 可以在 owner 的规则下读写存活对象，却不能比对象活得更久， 也不能在没有转移 ownership 的情况下自行释放对象。

如果最后一个可用 pointer 被覆盖，仍然存活的 allocation 会变得不可到达， 形成 memory leak。如果 owner 已经释放对象，其他 alias 再访问它便是 use-after-free。如果两条路径都误以为自己是 owner，则可能发生 double free。 C 不会自动阻止这些错误，因此 ADT 实现必须让每个操作的 ownership contract 保持清楚。

typedef 让接口更易读

Tutorial 也复习 typedef，因为 ADT 接口经常要用简短名称去遮蔽又长又底层 的 pointer type。

typedef struct node *nodePtr;
typedef int stackElementT;

typedef 不会建立新的 runtime 对象；它只会建立新的类型名称。好处是：

• function prototype 更短；
• header file 更容易扫读；
• ADT 边界更清楚。

当课程写 stackADT 时，这个名字本身就是 abstraction 的一部分。它要求 client 把这个对象理解为“一个 stack”，而不是“某个具体 struct 的 pointer”。

不过 type alias 本身不会令表示自动变成私有。真正的 representation hiding 需要在 interface 中只声明不完整的结构类型，再把字段定义放进 implementation file。typedef 为 client 提供易读的 handle，而 incomplete type 才会阻止 client 直接访问内部字段。

struct 把相关字段组成一个 record

例如：

struct node {
   int data;
   struct node *next;
};

这就是 linked-list node 的典型形状：一个字段放 payload，一个字段记录下 一个 node 的地址。

这个定义可以 self-reference，是因为节点并没有直接包含另一个完整节点。 Compiler 读取 struct node 期间，已经可以用该 tag 声明 struct node *next，因为 object pointer 的大小是已知的。如果改成 struct node next;，每个 node 都要内含另一个完整 node，类型大小便永远无法 确定。

对 node pointer p 而言，p->next 等价于 (*p).next。更新这个字段，是在 linked structure 的 memory graph 中改动一条边，而不是搬动 node 本身；改变 的是从 p 出发，下一步可以到达哪个 node。

重点不只是语法上的分组，而是它让你能精确建模资料结构需要维持的状态。

struct cellT {
   queueElementT element;
   struct cellT *next;
};

定理 / 命题

证明思路

第一个命题来自 dereference 的含义：它要访问 pointer 所指明的对象。若没有 一个类型相容且仍存活的对象可供访问，C 的执行模型便没有合法目标，该操作是 undefined behavior。函数返回或 free 之后，即使 pointer 仍保存旧地址的 数值，也不会延长原对象的生命周期。

第二个命题可把每个 node 看成 vertex，把每个 pointer field 看成 directed edge。覆盖通往某段仍需保留的 sublist 的唯一 edge，会使该 sublist 不可到达； 在 free(old) 之后才读取 old->next，则违反第一个命题。因此 dequeue 要先 保存 successor 再释放旧 head；enqueue 要先接上 fresh node 再推进 tail。 空 queue 与单节点 queue 还要单独更新 root，因为这时 head 与 tail 指向同一 node。

这些工具怎样直接连到 ADT 设计

课堂的 C 语言 review 与 ADT lecture 不是两条分开的线。

• Pointer 让一个 object 可以指向另一个 object；
• malloc 让节点可以按操作需要动态建立；
• struct 让多个相关字段可以被当成一个整体维护；
• typedef 让 ADT 接口可以把实现细节藏起来。

所以当课程说 ADT 要暴露 “what” 而隐藏 “how” 时，上面几样工具正是 C 里实现这种分离的方法。

常见错误

快速检查

一个更完整的 struct trace

student 例子值得再慢读一次，因为它同时牵涉 pointer、struct、file input 和 ownership。把成功与清理边界都写出来后，流程会更完整：

先看这几行：

Sdata *p = malloc(sizeof *p);
if (p == NULL) return EXIT_FAILURE;

FILE *fp = fopen("example.txt", "r");
if (fp == NULL) {
   free(p);
   return EXIT_FAILURE;
}

int fields = fscanf(fp, "%49s %d %49s",
                    p->name, &p->age, p->address);
fclose(fp);
if (fields != 3) {
   free(p);
   return EXIT_FAILURE;
}

/* 使用已经初始化的 record */
free(p);
p = NULL;

可以把 trace 拆成四个问题：

1. p 指向哪里？
2. p->name 和 p->address 是写入哪个 buffer？
3. &p->age 为什么要加 address？
4. 读完之后谁负责清理？

Allocation 成功后，p 指向一个存活的 Sdata object。两个 array field 传给 fscanf 时会提供首元素 pointer；整数转换则需要 &p->age。Width limit 保护各有 50 个元素的 array，不让过长 token 越界；返回值确认三个 conversion 都成功。这个 format 读取三个以 whitespace 分隔的 token，并不 适合含空格的完整地址。fclose 释放 file resource，free 结束动态对象的 lifetime。这样阅读，才是把语法放进同一个 ownership-and-state trace，而 不是逐句死记。

总结

• Pointer 保存地址；dereference 会在类型与访问规则允许时，读写该地址中的 存活对象。
• Automatic local object 在离开代码块后消失；dynamic object 存活到 free。变量仍在 scope 内或地址数值仍被保存，都不会延长 object lifetime。
• 每次 allocation 都需要检查失败、初始化字段、指定 owner，并且最终恰好 释放一次。
• Self-referential node 用 pointer 保存 link；linked structure 的操作是 memory graph 更新，次序必须维持从 ADT root 出发的可到达性。
• typedef 改善 interface 用词；真正隐藏表示的是 incomplete type 与分开的 implementation。

练习