到目前為止，所有變數的大小都在編譯期決定。但真實程式常常要到執行期才知道需要多少空間 ——使用者會輸入幾筆資料？檔案有多大？這就需要動態記憶體：向系統的堆積（heap）要空間， 用完再親手還回去。「親手」二字正是 C 的力量與危險所在。
學習目標
- 分辨堆疊（stack）與堆積（heap）的差異與各自的適用場景
- 熟練
malloc/calloc/realloc/free的完整用法 - 養成「檢查回傳 NULL、free 後設 NULL」的防禦習慣
- 會實作成長式動態陣列（容量倍增策略）
- 會動態配置二維陣列（兩種方法）
- 能辨識並避免四大經典錯誤：洩漏、懸空指標、重複釋放、越界
對照 K&R 章節
| 本單元主題 | K&R 2nd Edition |
|---|---|
| 儲存管理（malloc/free） | §7.8.5 Storage Management |
| alloc/afree 的手工實作 | §5.4（簡化版）、§8.7（完整版） |
| 函式庫規格 | Appendix B5: Utility Functions (stdlib.h) |
觀念講解
1. 堆疊 vs 堆積
高位址 +--------------------+
| 堆疊 (stack) | 區域變數、函式呼叫框架
| | | 自動配置、自動釋放、速度快
| v | 大小有限（macOS 預設 8MB）
| |
| ^ |
| | |
| 堆積 (heap) | malloc 配置的空間
| | 手動配置、手動釋放
+--------------------+ 大小受實體記憶體限制
| 全域/靜態資料 |
+--------------------+
低位址 | 程式碼 |
+--------------------+| 堆疊 | 堆積 | |
|---|---|---|
| 配置方式 | 自動（宣告即配置） | 手動（malloc） |
| 釋放方式 | 自動（離開作用域） | 手動（free） |
| 生命週期 | 跟著作用域 | 由你決定 |
| 大小 | 編譯期固定、總量小 | 執行期決定、總量大 |
| 速度 | 極快（移動指標） | 較慢（搜尋可用區塊） |
2. malloc 家族總表
| 函式 | 原型 | 功能 |
|---|---|---|
malloc |
void *malloc(size_t size) |
配置 size bytes，內容未初始化 |
calloc |
void *calloc(size_t n, size_t size) |
配置 n×size bytes，全部清零 |
realloc |
void *realloc(void *p, size_t size) |
調整既有區塊大小，內容保留 |
free |
void free(void *p) |
釋放；free(NULL) 是安全的 no-op |
標準用法（每一行都有理由）：
int *arr = malloc(n * sizeof *arr); /* sizeof *arr：型別改了也不用改這行 */
if (arr == NULL) { /* malloc 可能失敗！ */
perror("malloc");
exit(EXIT_FAILURE);
}
/* ... 使用 arr[0..n-1] ... */
free(arr); /* 有借有還 */
arr = NULL; /* 防懸空指標的慣例 */void * 會自動轉換成任何物件指標型別，所以 C 裡不需要（也不建議）轉型 malloc 的回傳值。
3. realloc 的正確姿勢
int *tmp = realloc(arr, new_size * sizeof *arr);
if (tmp == NULL) {
/* 失敗時原區塊仍有效！直接 arr = realloc(...) 會弄丟它（洩漏） */
free(arr);
exit(EXIT_FAILURE);
}
arr = tmp;要點：用暫存指標接住 realloc 的結果；realloc 可能搬家（回傳新位址）， 所以舊指標在成功後一律視為失效。
4. 動態陣列的成長策略
每次滿了就 realloc(+1) 是 O(n²) 的災難；標準做法是容量倍增：
if (len == cap) {
cap = (cap == 0) ? 8 : cap * 2; /* 8, 16, 32, 64, ... */
T *tmp = realloc(data, cap * sizeof *data);
/* ...檢查、指回... */
}
data[len++] = new_element;攤銷分析：n 次 append 總共只搬 O(n) 個元素，平均每次 O(1)。
5. 動態二維陣列的兩種做法
方法 A：指標陣列（各列獨立 malloc）——彈性大、可各列不同長，但記憶體不連續：
int **m = malloc(rows * sizeof *m);
for (int i = 0; i < rows; i++)
m[i] = malloc(cols * sizeof **m);
/* 釋放要反著來：先每列、再指標陣列 */方法 B：一大塊 + 索引計算——連續記憶體、一次 malloc/free、快取友善：
int *m = malloc(rows * cols * sizeof *m);
/* 存取：m[i * cols + j] */6. 四大經典錯誤
| 錯誤 | 症狀 | 預防 |
|---|---|---|
| 記憶體洩漏 | 長時間執行後記憶體耗盡 | 每條路徑都要 free；工具：leaks、Valgrind、-fsanitize=address |
| 懸空指標 | free 後繼續使用，行為隨機 | free 後立刻設 NULL |
| 重複釋放 | crash 或堆積損壞 | free 後設 NULL（free(NULL) 無害） |
| 越界存取 | 蓋壞相鄰資料或 crash | 記牢配置大小；用 -fsanitize=address 抓 |
範例程式
| 檔案 | 內容 |
|---|---|
01_malloc_basics.c |
malloc/calloc/free 基礎、NULL 檢查、sizeof *p 慣用法、free 後設 NULL、字串複製 my_strdup |
02_dynamic_array.c |
realloc 正確用法、成長式動態陣列（push/容量倍增）完整實作 |
03_dynamic_2d.c |
動態二維陣列兩種做法（指標陣列 vs 一大塊）、正確釋放順序、效能與佈局比較 |
編譯與執行（以第一個為例）：
cc -std=c11 -Wall -Wextra -o /tmp/demo 01_malloc_basics.c
/tmp/demo建議再用 AddressSanitizer 跑一次，體驗它抓錯的威力：
cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/demo 01_malloc_basics.c && /tmp/demo常見錯誤與陷阱
1. 忘記檢查 malloc 回傳值
int *p = malloc(n * sizeof *p);
p[0] = 1; /* 若 malloc 失敗，這裡解參考 NULL */修正：配置後立刻檢查 if (p == NULL)。
2. use-after-free（懸空指標）
free(p);
printf("%d\n", *p); /* p 指向已歸還的記憶體：未定義行為 */修正：free(p); p = NULL; ——之後誤用會立刻 crash 在 NULL，容易定位。
3. double free
free(p);
free(p); /* 堆積結構被破壞，macOS 會 abort */修正：同上，free 後設 NULL；free(NULL) 保證無害。
4. realloc 直接指回原指標
p = realloc(p, bigger); /* realloc 失敗回傳 NULL，原區塊位址被蓋掉 -> 洩漏 */修正：先用暫存指標接住，成功才指回。
5. 配置大小算錯
int *p = malloc(n); /* 少乘 sizeof(int)：只有 n bytes！ */
char *q = malloc(strlen(s)); /* 忘了 '\0'：少 1 byte */修正：malloc(n * sizeof *p)；字串用 malloc(strlen(s) + 1)。
練習題
- 寫
int *make_range(int n)：回傳動態配置、內容為0..n-1的陣列；呼叫端負責 free。 - 寫
char *my_strdup(const char *s)：動態複製字串（不可用系統的 strdup）。 - 寫
int *concat(const int *a, int na, const int *b, int nb)： 配置新陣列並串接兩個來源陣列。 - 為
02_dynamic_array.c的動態陣列補上pop（移除末尾）與shrink_to_fit（realloc 縮小到剛好）操作。 - 用「方法 B（一大塊）」寫動態配置的 n×n 乘法表，印出後正確釋放。
- （進階）實作一個簡單的單向鏈結串列：
push_front、print、free_list， 確保用leaks或 ASan 驗證零洩漏。
延伸閱讀
- K&R §8.7：自己寫一個 malloc（storage allocator 的完整實作）
man malloc（macOS）；leaks與MallocStackLogging的用法- Valgrind／AddressSanitizer 文件：動態記憶體除錯的兩大神器
- 下一單元
08-recursion：遞迴思考與經典演算法