0.1 Pointer、記憶體與 struct

鏈結結構需要繼續存取先前操作建立的物件。複製 pointer 只保留地址，既不會 複製物件，也不會延長物件的生命週期。後續走訪能否到達有效節點、會否失去 部分結構、會否存取已釋放的儲存空間，都取決於這些區別。

C 把這些選擇明確地寫在程式中：pointer 連接物件，malloc 取得可在函數 返回後繼續存活的儲存空間，struct 則把操作必須共同維護的欄位組織起來。 ADT 可以向呼叫者隱藏這些欄位，但實作仍須在每次更新後維持正確狀態， 並明確界定儲存空間的擁有權。

Pointer 儲存的是地址，不是值

下面兩個運算符區分物件與地址：

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

Pointer 與它指向的 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 狀態時，要分別記錄兩項資料：

• 每個 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 令介面更易讀

ADT 介面可以用 typedef 為較長的 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 介面

這些語言機制分別承擔 ADT 實作中的不同工作。

• Pointer 令一個 object 可以指向另一個 object；
• malloc 令節點可以按操作需要而動態建立；
• struct 令多個相關欄位可以被當作一個整體維持；
• typedef 令 ADT 介面可以把實作細節藏起來。

公開介面規定操作的行為；pointer、配置規則和私有 struct 則決定如何實現 這些行為。兩者的分離會在 stack 與 queue 的不同表示中具體呈現。

常見錯誤

快速檢查

一個更完整的 struct trace

下面的 record 包含兩個固定大小的字串 buffer 及一個整數欄位。讀取流程先 檢查 allocation、檔案開啟及轉換結果，再使用 record，最後釋放取得的資源。

typedef struct Student_Data {
   char name[50];
   int age;
   char address[50];
} Sdata;

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 為何需要取地址？
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。

練習