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 放在同一個框架裡面理解，而唔係逐句死記。

練習