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 所记录 的地址，直接写入原来的对象。

malloc 在 heap 上分配空间

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

典型写法是：

struct node *x;
x = malloc(sizeof(struct node));

现在 x 就指向一段足以容纳一个 struct node 的新空间。

但要记住两件事：

• malloc 只会给你空间，不会自动填好字段；
• 真实程序最终仍然要处理 free 与 ownership 问题。

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”。

struct 把相关字段组成一个 record

例如：

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

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

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

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

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

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

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

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

常见错误

快速检查

一个完整的 memory 流程

lecture 里的 rationalADT 例子和 tutorial 里的 student 例子，其实都在 讲同一件事：如果你在 heap 上开了空间，就要知道 object 之后怎样被使用， 以及什么时候要收回来。

可以把整个流程记成四步：

1. 先 malloc 一块空间；
2. 再用 field assignment 或 fscanf 初始化；
3. 使用期间保持 pointer 有效；
4. 用完之后 free，如果还有 file，也要 fclose。

这个流程不只是程序风格，而是资料结构程序最重要的安全习惯。当你以后看到 stack node、queue node、或者 hashtable cell，都应该马上问：这个 object 从 哪里来？又要去哪里？

一个更完整的 struct trace

student 例子值得再慢读一次，因为它同时牵涉 pointer、struct、file input 和 ownership。

先看这几行：

Sdata *p;
p = (Sdata *)malloc(sizeof(Sdata));
FILE *fp = fopen("example.txt", "r");
fscanf(fp, "%s %d %s", p->name, &p->age, p->address);

可以把 trace 拆成四个问题：

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

当你可以清楚答出这四条时，说明你已经开始把 pointer、field access 和 resource ownership 放进同一个框架里理解，而不是逐句死记。

练习