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 所記錄 的地址，直接寫入原本的物件。

區域物件與動態分配物件有不同的生命週期

地址只有在該地址中的物件仍然存活時才有意義。在 code block 內宣告的區域 物件通常具有 automatic storage duration；執行離開該 block 後，物件的 生命週期便結束。因此，回傳區域變量的地址，只會留下一個仍然記得舊位置、卻 不再指向存活物件的 pointer。

int *bad_address(void) {
   int local = 7;
   return &local;             /* function 回傳後立即成為 dangling pointer */
}

由 malloc 取得的空間具有 allocated storage duration。即使建立它的 function 已經回傳，該空間仍然存在，直至程式把該次 allocation 交給 free。 這種較長的生命週期，令 linked structure 可以保留先前操作建立的 node。但它 並不代表 node 可以永久使用：free(x) 之後，x 及所有保存同一地址的 alias 都成為 dangling pointer。Scope 回答「這個 pointer 變量可以在哪裡被命名」， lifetime 回答「它指向的物件現在是否仍然存在」；兩者不能混為一談。

malloc 在 heap 上分配空間

資料結構實作經常需要動態建立節點，而不是預先知道總共要幾多格。呢個時候 就要靠 malloc。

典型寫法係：

struct node *x = malloc(sizeof *x);
if (x == NULL) {
   /* 報告 allocation failure，或把失敗傳給 caller */
}

在成功路徑上，x 指向一段足以容納一個 struct node 的新空間。 sizeof *x 直接跟隨 x 的宣告型別，不必重複寫型別名稱。在 C 中， <stdlib.h> 宣告 malloc，其回傳的 void * 不需要強制轉換。

但要記住三件事：

• dereference 之前先檢查 x != NULL；
• 在其他程式碼讀取欄位之前，逐一初始化所需欄位；
• 明確哪一部分程式擁有該 node，並負責最終釋放它。

Ownership 令 allocation 成為完整流程

面對每一次 allocation，都應該問三個問題：誰建立它，哪些 pointer 只是暫時 借用存取權，最後由誰釋放它？Owner 負責恰好一次結束該 allocation。 Borrowed pointer 可以在 owner 的規則下讀寫存活物件，卻不能比物件活得更久， 亦不能在沒有轉移 ownership 的情況下自行釋放物件。

如果最後一個可用 pointer 被覆寫，仍然存活的 allocation 會變得不可到達， 形成 memory leak。如果 owner 已經釋放物件，其他 alias 再存取它便是 use-after-free。如果兩條路徑都誤以為自己是 owner，則可能發生 double free。 C 不會自動阻止這些錯誤，因此 ADT implementation 必須令每個 operation 的 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 中只宣告不完整的 structure type，再把欄位定義放進 implementation file。typedef 為 client 提供易讀的 handle，而 incomplete type 才會阻止 client 直接存取內部欄位。

struct 把相關欄位組成一個 record

例如：

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

這就是 linked-list node 的典型形狀：一個欄位放 payload，一個欄位記錄下一 個 node 的地址。

這個定義可以 self-reference，是因為 node 並沒有直接包含另一個完整 node。 Compiler 讀取 struct node 期間，已經可以用該 tag 宣告 struct node *next，因為 object pointer 的大小是已知的。如果改成 struct node next;，每個 node 都要內含另一個完整 node，type 的大小便永遠 無法確定。

對 node pointer p 而言，p->next 等價於 (*p).next。更新這個欄位，是在 linked structure 的 memory graph 中改動一條 edge，而不是搬動 node 本身； 改變的是由 p 出發，下一步可以到達哪個 node。

重點不只是語法上的分組，而是它令你能夠精確建模資料結構需要維持的狀態。

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

定理 / 命題

證明思路

第一個命題來自 dereference 的含義：它要存取 pointer 所指明的物件。若沒有 一個型別相容而且仍存活的物件可供存取，C 的 execution model 便沒有合法 target，該操作是 undefined behavior。Function 回傳或 free 之後，即使 pointer 仍保存舊地址的數值，亦不會延長原物件的生命週期。

第二個命題可把每個 node 看成 vertex，把每個 pointer field 看成 directed edge。覆寫通往某段仍需保留的 sublist 的唯一 edge，會令該 sublist 不可到達； 在 free(old) 之後才讀取 old->next，則違反第一個命題。因此 dequeue 要先 保存 successor 再釋放舊 head；enqueue 要先接上 fresh node 再推進 tail。 空 queue 與單 node 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；integer conversion 則需要 &p->age。Width limit 保護各有 50 個元素的 array，避免過長 token 越界； return value 確認三個 conversion 都成功。這個 format 讀取三個以 whitespace 分隔的 token，並不適合含空格的完整地址。fclose 釋放 file resource， free 結束 dynamic object 的 lifetime。這樣閱讀，才是把 syntax 放進同一個 ownership-and-state trace，而不是逐句死記。

總結

• Pointer 保存地址；dereference 會在型別與存取規則容許時，讀寫該地址中的 存活物件。
• Automatic local object 在離開 code block 後消失；dynamic object 存活至 free。變量仍在 scope 內或地址數值仍被保存，都不會延長 object lifetime。
• 每次 allocation 都需要檢查失敗、初始化欄位、指定 owner，並且最終恰好 釋放一次。
• Self-referential node 用 pointer 保存 link；linked structure 的 operation 是 memory graph 更新，次序必須維持由 ADT root 出發的可到達性。
• typedef 改善 interface 用詞；真正隱藏 representation 的是 incomplete type 與分開的 implementation。

練習