練習題與詳解 — 07 動態記憶體管理（Dynamic Memory）

本檔收錄本單元的練習題、完整解題思路與參考解答。 強烈建議先自己動手做：看完題目就闔上這份檔案，寫出你的版本、編譯、執行、卡住了再回來看「解題思路」；真的做完了，再對照「參考解答」與「程式碼講解」。每題的完整程式碼也放在 exercises/ 資料夾，可直接編譯：

cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_make_range.c && /tmp/out

本單元的每一題都建議再用 AddressSanitizer 跑一次，驗證沒有洩漏、越界與 use-after-free：

cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out exercises/ex1_make_range.c && /tmp/out

練習 1：make_range —— 回傳動態配置的陣列（難度：基礎）

題目

寫函式 int *make_range(int n)：回傳動態配置、內容為 0..n-1 的陣列； 呼叫端負責 free。n <= 0 或配置失敗時回傳 NULL。在 main 中配置 10 個元素、印出、釋放，並測試 n = 0 與負數的邊界。

解題思路

為什麼需要動態配置？ 函式不能回傳區域陣列（函式返回就消失），而 n 是執行期才知道的——這正是 malloc 的用武之地：堆積上的空間活到 free 為止，跨函式傳遞完全安全。
標準四步驟（單元講義的「每一行都有理由」範本）： - 防衛輸入：n <= 0 直接回 NULL（配置 0 bytes 的語意曖昧，不如明確拒絕）； - 配置：malloc((size_t)n * sizeof *a)——sizeof *a 的寫法讓「元素型別」只寫在宣告那一行，之後改型別不用改這行； - 檢查：if (a == NULL) return NULL;——malloc 會失敗，永遠要檢查； - 填值並回傳。
所有權（ownership）約定：「函式配置、呼叫端釋放」。 C 沒有語言機制強制這件事，必須寫在函式的註解裡；呼叫端用完 free(r); r = NULL;——設 NULL 是防懸空指標的便宜保險。

參考解答

/*
 * ex1_make_range.c
 * ----------------
 * 練習 1：make_range —— 回傳動態配置的 0..n-1 陣列（難度：基礎）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_make_range.c
 * 驗證：cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out ex1_make_range.c
 * 執行：/tmp/out
 */
#include <stdio.h>
#include <stdlib.h>

/*
 * 配置並回傳內容為 0..n-1 的陣列；呼叫端負責 free。
 * n <= 0 或 malloc 失敗時回傳 NULL。
 * 「函式配置、呼叫端釋放」是 C 常見的所有權約定，
 * 一定要寫在函式的文件註解裡。
 */
int *make_range(int n)
{
    if (n <= 0)
        return NULL;

    int *a = malloc((size_t)n * sizeof *a);   /* sizeof *a：型別改了不用改這行 */
    if (a == NULL)
        return NULL;                          /* malloc 可能失敗 */

    for (int i = 0; i < n; i++)
        a[i] = i;

    return a;
}

int main(void)
{
    int n = 10;
    int *r = make_range(n);

    if (r == NULL) {
        fprintf(stderr, "make_range 失敗\n");
        return EXIT_FAILURE;
    }

    printf("make_range(%d)：", n);
    for (int i = 0; i < n; i++)
        printf("%d ", r[i]);
    printf("\n");

    free(r);         /* 呼叫端履行釋放義務 */
    r = NULL;        /* 防懸空指標的慣例 */

    /* 邊界：n <= 0 應回傳 NULL 而不是配置 0 bytes */
    printf("make_range(0)  = %s\n", make_range(0) ? "非 NULL" : "NULL");
    printf("make_range(-5) = %s\n", make_range(-5) ? "非 NULL" : "NULL");

    return 0;
}

程式碼講解

malloc((size_t)n * sizeof *a)：n 先轉 size_t 再相乘，避免有號/無號混算的警告； sizeof *a 在 a 還沒指向有效記憶體時使用完全合法——sizeof 只看型別、不求值。
對照「回傳區域陣列」的錯誤版本：int a[10]; ...; return a; 編譯器直接警告懸空指標——malloc 版本正是這個問題的正解。
free(r) 之後 r = NULL;：之後誤用會立刻 crash 在 NULL（好除錯），誤 free 第二次也無害（free(NULL) 是 no-op）。
易錯處：忘了 free（洩漏——短命程式看不出來，但長時間執行的服務會被吃光記憶體）；或把 sizeof *a 寫成 sizeof a（指標大小 8，配置嚴重不足）。

範例輸出

make_range(10)：0 1 2 3 4 5 6 7 8 9 
make_range(0)  = NULL
make_range(-5) = NULL

練習 2：my_strdup —— 動態複製字串（難度：基礎）

題目

寫函式 char *my_strdup(const char *s)：動態配置剛好的空間並複製整個字串（不可用系統的 strdup）。呼叫端負責 free。驗證：複本內容相同但位址不同；複本可修改而原字串不受影響；空字串也能複製。

解題思路

需要多大空間？ strlen(s) 回傳不含 '\0' 的長度—— 配置時必須 +1 留給結尾。忘了 +1 是字串配置的頭號 bug （寫入 '\0' 時越界一個 byte，ASan 一抓一個準）。
三步：算長度 → malloc(len + 1) + 檢查 → 複製。複製用 memcpy(copy, s, len + 1)：長度已知時 memcpy 最直接， len + 1 讓 '\0' 一起搬（不必再手動補）。
為什麼標準庫的 strdup 曾經「不標準」？ strdup 是 POSIX 函式，直到 C23 才進入 C 標準——所以可攜程式常常自己寫一個，這題就是在練這件事。
驗證設計： - 印兩者的位址：不同 → 證明真的複製了，不是共用； - 修改複本首字母：原字串不動 → 證明隔離；也順便展示「字面值不可改，但堆積上的複本可以」。

參考解答

/*
 * ex2_my_strdup.c
 * ---------------
 * 練習 2：my_strdup —— 動態複製字串（難度：基礎）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_my_strdup.c
 * 驗證：cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out ex2_my_strdup.c
 * 執行：/tmp/out
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 配置一塊剛好的空間，複製整個字串（含 '\0'）。
 * 呼叫端負責 free。malloc 失敗回傳 NULL。
 */
char *my_strdup(const char *s)
{
    size_t len = strlen(s);              /* 不含 '\0' 的長度 */
    char *copy = malloc(len + 1);        /* +1：'\0' 的空間，最經典的 off-by-one */

    if (copy == NULL)
        return NULL;

    memcpy(copy, s, len + 1);            /* 長度已知，memcpy 連 '\0' 一起搬 */
    return copy;
}

int main(void)
{
    const char *original = "dynamic memory";

    char *dup = my_strdup(original);
    if (dup == NULL) {
        fprintf(stderr, "my_strdup 失敗\n");
        return EXIT_FAILURE;
    }

    printf("原字串：\"%s\"（位址 %p）\n", original, (const void *)original);
    printf("複本  ：\"%s\"（位址 %p）\n", dup, (void *)dup);
    printf("內容相同？%s；位址相同？%s\n",
           strcmp(original, dup) == 0 ? "是" : "否",
           (original == dup) ? "是" : "否");

    /* 複本住在堆積，可以修改（原字串是唯讀字面值） */
    dup[0] = 'D';
    printf("修改複本後：\"%s\"（原字串不受影響：\"%s\"）\n", dup, original);

    free(dup);
    dup = NULL;

    /* 邊界：空字串也要能複製 */
    char *empty = my_strdup("");
    printf("空字串複本：\"%s\"（長度 %zu）\n", empty, strlen(empty));
    free(empty);

    return 0;
}

程式碼講解

malloc(len + 1)：字元的 sizeof 是 1，不需要乘；+1 是本題靈魂。
memcpy(copy, s, len + 1) 對比 strcpy(copy, s)：兩者都對—— memcpy 用已算好的長度（不再掃一次字串），strcpy 讀起來更「字串味」。唯一不能用的是 strncpy（沒必要且有不補結尾的地雷）。
空字串：len = 0，配置 1 byte、複製 1 byte（就是 '\0'）—— 回傳合法的空字串，不需特判。
輸出中兩個位址一個在程式的唯讀資料區（0x1001...）、一個在堆積（0x1009...）——親眼看到「字面值」與「堆積複本」住在不同區域。
易錯處：回傳前忘了檢查 malloc；或算長度後用 sizeof s（指標大小！）配置。

範例輸出

原字串："dynamic memory"（位址 0x1001506a0）
複本  ："dynamic memory"（位址 0x1009d1ec0）
內容相同？是；位址相同？否
修改複本後："Dynamic memory"（原字串不受影響："dynamic memory"）
空字串複本：""（長度 0）

（位址每次執行不同，此為某次實際執行的結果。）

練習 3：concat —— 串接兩個陣列到新配置（難度：基礎）

題目

寫函式 int *concat(const int *a, int na, const int *b, int nb)：配置 na + nb 個 int 的新陣列，前段放 a、後段放 b，回傳新陣列（呼叫端 free）。邊界：其中一邊長度為 0（指標可為 NULL）、兩邊都空。

解題思路

佈局規劃：新陣列前 na 格放 a、後 nb 格放 b。後段的起點用指標算術表達最乾淨：out + na—— 「跳過前 na 個元素後的位置」。

   out:  [ a0 a1 a2 | b0 b1 b2 b3 ]
          ^           ^
         out         out + na

複製用 memcpy：來源與目的都是連續區塊、長度已知—— memcpy(out, a, na * sizeof *a) 與 memcpy(out + na, b, nb * sizeof *b)。
NULL + 長度 0 的細節：呼叫端傳 concat(x, 3, NULL, 0) 應該合法（「沒有第二個陣列」）。但標準規定 memcpy 收到 NULL 即使長度 0 也是未定義行為，所以複製前檢查 if (na > 0)——這是很多人不知道的角落案例。
兩邊都空：malloc(0) 的回傳值由實作決定（可能 NULL 可能非 NULL），兩種都合法；重點是之後 free 都安全。

參考解答

/*
 * ex3_concat.c
 * ------------
 * 練習 3：concat —— 配置新陣列串接兩個來源陣列（難度：基礎）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_concat.c
 * 驗證：cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out ex3_concat.c
 * 執行：/tmp/out
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 配置 na+nb 個 int 的新陣列，前段抄 a、後段抄 b。
 * 呼叫端負責 free。失敗回傳 NULL。
 */
int *concat(const int *a, int na, const int *b, int nb)
{
    if (na < 0 || nb < 0)
        return NULL;

    int *out = malloc((size_t)(na + nb) * sizeof *out);
    if (out == NULL)
        return NULL;

    /* 大小為 0 時跳過：memcpy 傳入 NULL（即使長度 0）是未定義行為 */
    if (na > 0)
        memcpy(out, a, (size_t)na * sizeof *a);        /* 前段：a 的 na 個元素 */
    if (nb > 0)
        memcpy(out + na, b, (size_t)nb * sizeof *b);   /* 後段：從 out+na 開始 */

    return out;
}

static void print_array(const char *label, const int *a, int n)
{
    printf("%s", label);
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}

int main(void)
{
    int x[] = { 1, 2, 3 };
    int y[] = { 10, 20, 30, 40 };

    int *joined = concat(x, 3, y, 4);
    if (joined == NULL) {
        fprintf(stderr, "concat 失敗\n");
        return EXIT_FAILURE;
    }

    print_array("x：       ", x, 3);
    print_array("y：       ", y, 4);
    print_array("concat：  ", joined, 7);
    free(joined);

    /* 邊界：其中一邊是空陣列 */
    int *left_only = concat(x, 3, NULL, 0);   /* nb=0：b 可為 NULL */
    print_array("x + 空：  ", left_only, 3);
    free(left_only);

    int *both_empty = concat(NULL, 0, NULL, 0);
    printf("空 + 空：  %s（0 個元素）\n",
           both_empty ? "配置成功" : "NULL");
    free(both_empty);

    return 0;
}

程式碼講解

out + na：指標算術自動乘 sizeof(int)，後段的目的地一行到位；寫成 &out[na] 也完全等價。
if (na > 0) 守門：對 memcpy(out, NULL, 0) 的防衛。很多程式碼省略它「碰巧沒事」，但 UBSan 會抓、最佳化器也有權假設指標非 NULL—— 正確程式不賭運氣。
free(both_empty)：無論 malloc(0) 回傳什麼，free 它都安全（NULL 是 no-op、非 NULL 是有效區塊）。
這個函式的模式（算總長 → 配置 → 分段複製）可以直接推廣到字串串接版 char *str_concat(const char *, const char *)——差別只在要多配 '\0'。

範例輸出

x：       1 2 3 
y：       10 20 30 40 
concat：  1 2 3 10 20 30 40 
x + 空：  1 2 3 
空 + 空：  配置成功（0 個元素）

練習 4：動態陣列 —— push / pop / shrink_to_fit（難度：進階）

題目

實作成長式動態陣列（struct dynarray { int *data; size_t len, cap; }），提供：

da_push：附加元素，容量不足時倍增（realloc 的正確姿勢）；
da_pop：移除並回傳末尾元素，空陣列要能安全拒絕；
da_shrink_to_fit：把容量縮到剛好等於長度；
da_init / da_free。

push 20 個元素觀察容量 8→16→32 的變化，pop 5 個後 shrink，全程零洩漏（ASan 驗證）。

解題思路

三個欄位的分工：data 指向堆積區塊、len 是「已使用」、cap 是「已配置」。 len <= cap 是這個結構的不變式。分開 len/cap 正是攤銷 O(1) 的關鍵—— 大多數 push 只是 data[len++] = v，不碰配置。
push 的成長策略：滿了（len == cap）才擴容，容量翻倍（首次給 8）。 realloc 三步曲（單元講義的重點）：

int *tmp = realloc(da->data, new_cap * sizeof *tmp);  /* 1. 用暫存接 */
if (tmp == NULL) return 0;                            /* 2. 失敗：原區塊仍有效 */
da->data = tmp;                                       /* 3. 成功才指回 */

直接 da->data = realloc(da->data, ...) 在失敗時會把唯一的指標蓋成 NULL—— 原區塊再也找不回來，洩漏。 3. pop 為什麼是 O(1)？ 只把 len 減一，不動容量—— 資料還在原地但邏輯上已移除。「空陣列 pop」用輸出參數 *ok 回報成敗（回傳值 0 可能是合法元素，不能當錯誤碼——練習 5 of 04 的教訓）。 4. shrink_to_fit：realloc 縮小到 len * sizeof(int)。兩個細節：len == 0 時直接 free + 歸零（realloc 到 0 的語意在 C23 前後有變，避開它）；縮小失敗（罕見）就維持原狀——不是錯誤，只是沒省到記憶體。 5. da_free：釋放後把三個欄位歸零，結構回到可重複使用的初始狀態。

參考解答

/*
 * ex4_dynarray.c
 * --------------
 * 練習 4：動態陣列 —— push / pop / shrink_to_fit（難度：進階）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_dynarray.c
 * 驗證：cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out ex4_dynarray.c
 * 執行：/tmp/out
 */
#include <stdio.h>
#include <stdlib.h>

/* 成長式動態陣列：data 指向堆積、len 是已用、cap 是已配置 */
struct dynarray {
    int *data;
    size_t len;
    size_t cap;
};

void da_init(struct dynarray *da)
{
    da->data = NULL;    /* 延遲配置：第一次 push 才要記憶體 */
    da->len = 0;
    da->cap = 0;
}

/* 附加元素；容量不足時倍增。成功回傳 1、失敗回傳 0。 */
int da_push(struct dynarray *da, int value)
{
    if (da->len == da->cap) {
        size_t new_cap = (da->cap == 0) ? 8 : da->cap * 2;   /* 8,16,32,... */
        int *tmp = realloc(da->data, new_cap * sizeof *tmp);
        if (tmp == NULL)
            return 0;              /* 失敗：原區塊仍有效，不能弄丟 */
        da->data = tmp;
        da->cap = new_cap;
    }
    da->data[da->len++] = value;
    return 1;
}

/* 移除並回傳末尾元素；空陣列回傳 0 並把 *ok 設為 0 */
int da_pop(struct dynarray *da, int *ok)
{
    if (da->len == 0) {
        *ok = 0;
        return 0;
    }
    *ok = 1;
    return da->data[--da->len];    /* 只縮 len，不動容量（O(1)） */
}

/* 把容量縮到剛好等於 len，把多配的記憶體還給系統 */
void da_shrink_to_fit(struct dynarray *da)
{
    if (da->len == 0) {            /* 全空：直接釋放 */
        free(da->data);
        da->data = NULL;
        da->cap = 0;
        return;
    }
    int *tmp = realloc(da->data, da->len * sizeof *tmp);
    if (tmp != NULL) {             /* 縮小失敗就維持原狀，不算錯誤 */
        da->data = tmp;
        da->cap = da->len;
    }
}

void da_free(struct dynarray *da)
{
    free(da->data);
    da->data = NULL;               /* 防懸空、防重複釋放 */
    da->len = da->cap = 0;
}

static void da_status(const char *label, const struct dynarray *da)
{
    printf("%-22s len=%2zu cap=%2zu 內容：", label, da->len, da->cap);
    for (size_t i = 0; i < da->len; i++)
        printf("%d ", da->data[i]);
    printf("\n");
}

int main(void)
{
    struct dynarray da;
    da_init(&da);

    /* push 20 個元素，觀察容量 8 -> 16 -> 32 的倍增 */
    for (int i = 1; i <= 20; i++)
        if (!da_push(&da, i * i)) {
            fprintf(stderr, "push 失敗\n");
            da_free(&da);
            return EXIT_FAILURE;
        }
    da_status("push 20 個之後：", &da);

    /* pop 五個 */
    int ok;
    printf("pop 出：");
    for (int i = 0; i < 5; i++)
        printf("%d ", da_pop(&da, &ok));
    printf("\n");
    da_status("pop 5 個之後：", &da);

    /* 縮到剛好 */
    da_shrink_to_fit(&da);
    da_status("shrink_to_fit 之後：", &da);

    /* 空陣列 pop 的防衛 */
    struct dynarray empty;
    da_init(&empty);
    da_pop(&empty, &ok);
    printf("空陣列 pop：ok = %d（正確拒絕）\n", ok);

    da_free(&da);
    da_free(&empty);
    return 0;
}

程式碼講解

realloc(NULL, size) 等同 malloc(size)——所以第一次 push（data == NULL）不需要特判，倍增邏輯統一處理。
輸出驗證了成長軌跡：20 個元素 → cap 停在 32（8→16→32 共搬家兩次）； pop 後 cap 不變（32）；shrink 後 cap == len == 15。
--da->len 寫在下標裡：先減再取，正好取到「原本的最後一個」。
所有會失敗的路徑（push 失敗）都先 da_free 再離開—— 每條路徑都要 free 是零洩漏的紀律；ASan 驗證通過。
這個結構就是 C++ std::vector、Go slice 的 C 骨架—— 親手寫過一次，那些容器的效能特性（攤銷 O(1)、搬家失效舊指標）就不再神祕。

範例輸出

push 20 個之後：   len=20 cap=32 內容：1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 
pop 出：400 361 324 289 256 
pop 5 個之後：     len=15 cap=32 內容：1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 
shrink_to_fit 之後： len=15 cap=15 內容：1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 
空陣列 pop：ok = 0（正確拒絕）

練習 5：動態 n×n 乘法表 —— 一大塊配置法（難度：進階）

題目

用「方法 B（一大塊 + 索引計算）」動態配置 n×n 的乘法表：一次 malloc(n * n * sizeof(int))，元素 (i,j) 存取用 m[i * n + j]。印出 9×9 乘法表後正確釋放。額外驗證一個隨機存取（如 7×8 應在 m[6*9+7]）。

解題思路

回顧兩種動態二維做法： - 方法 A（指標陣列）：rows 次 malloc，各列獨立——彈性但零碎，釋放要反著來，任何一列失敗還要回滾； - 方法 B（本題）：一整塊連續記憶體 + 自己算索引—— 一次 malloc、一次 free、快取友善、不可能「配置到一半失敗」。
索引公式就是 row-major 佈局的手動版：(i, j) → i * n + j （第 03 單元學過編譯器對 m[i][j] 做的事，現在自己做）。

   一維陣列： [ 第0列 n 個 | 第1列 n 個 | ... ]
   m[i*n + j]  ------------^ 跳過 i 列，再進 j 格

溢位意識：n * n 兩個 int 相乘可能溢位，先轉 size_t 再乘。
乘法表內容：m[i*n+j] = (i+1) * (j+1)——索引從 0 起、表從 1×1 起，+1 對齊。
釋放：整塊一個 free(table) 就完事——這正是方法 B 的優雅之處（方法 A 得先迴圈 free 每一列）。

參考解答

/*
 * ex5_mult_table.c
 * ----------------
 * 練習 5：動態 n×n 乘法表 —— 「一大塊」法（難度：進階）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_mult_table.c
 * 驗證：cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out ex5_mult_table.c
 * 執行：/tmp/out
 */
#include <stdio.h>
#include <stdlib.h>

/*
 * 方法 B（一大塊 + 索引計算）：
 * 一次 malloc n*n 個 int，元素 (i,j) 放在 m[i * n + j]。
 * 好處：記憶體連續（快取友善）、一次 malloc 一次 free、不會部分失敗。
 */
int *make_mult_table(int n)
{
    if (n <= 0)
        return NULL;

    int *m = malloc((size_t)n * (size_t)n * sizeof *m);
    if (m == NULL)
        return NULL;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            m[i * n + j] = (i + 1) * (j + 1);   /* 1×1 起跳的乘法表 */

    return m;
}

void print_table(const int *m, int n)
{
    /* 表頭 */
    printf("    |");
    for (int j = 0; j < n; j++)
        printf("%4d", j + 1);
    printf("\n----+");
    for (int j = 0; j < n; j++)
        printf("----");
    printf("\n");

    for (int i = 0; i < n; i++) {
        printf("%3d |", i + 1);
        for (int j = 0; j < n; j++)
            printf("%4d", m[i * n + j]);    /* 一維索引模擬二維 */
        printf("\n");
    }
}

int main(void)
{
    int n = 9;

    int *table = make_mult_table(n);
    if (table == NULL) {
        fprintf(stderr, "配置失敗\n");
        return EXIT_FAILURE;
    }

    printf("%d×%d 乘法表（一大塊配置法）：\n", n, n);
    print_table(table, n);

    /* 隨機存取示範：7×8 就在 [6*9+7] */
    printf("\n驗證：table[6*9+7]（= 7×8）= %d\n", table[6 * n + 7]);

    free(table);        /* 一次 free 全部歸還 */
    table = NULL;

    return 0;
}

程式碼講解

(size_t)n * (size_t)n * sizeof *m：三個因子都在 size_t 域相乘，大 n 也不會先在 int 域溢位。
m[i * n + j] 中的 n 扮演了二維陣列宣告中「欄數」的角色—— 這也解釋了第 03 單元「函式參數欄數不可省略」的原因：沒有 n 就算不出位址。
print_table 的參數是 const int *——一大塊法的另一個好處：傳遞就是普通指標 + 尺寸，沒有 int ** 與 int (*)[N] 的型別糾結。
驗證行 table[6 * n + 7] == 56：手動把 (7,8) 換算成一維索引，確認公式沒寫反（寫成 j * n + i 的話乘法表會被轉置——對稱的乘法表看不出來，所以用非對稱的存取來驗證才有效）。

範例輸出

9×9 乘法表（一大塊配置法）：
    |   1   2   3   4   5   6   7   8   9
----+------------------------------------
  1 |   1   2   3   4   5   6   7   8   9
  2 |   2   4   6   8  10  12  14  16  18
  3 |   3   6   9  12  15  18  21  24  27
  4 |   4   8  12  16  20  24  28  32  36
  5 |   5  10  15  20  25  30  35  40  45
  6 |   6  12  18  24  30  36  42  48  54
  7 |   7  14  21  28  35  42  49  56  63
  8 |   8  16  24  32  40  48  56  64  72
  9 |   9  18  27  36  45  54  63  72  81

驗證：table[6*9+7]（= 7×8）= 56

練習 6：單向鏈結串列 —— push_front / print / free_list（難度：挑戰）

題目

實作一個簡單的單向鏈結串列：

push_front：在最前面插入新節點（每個節點單獨 malloc）；
print_list：印出整條串列；
free_list：釋放所有節點。

依序插入 7、3、1 並在每步印出串列，最後釋放，用 ASan（或 macOS 的 leaks）驗證零洩漏。

解題思路

節點的定義是「自我參照結構」：

struct node {
    int value;
    struct node *next;   /* 指向同型別的下一個節點 */
};

成員不能是 struct node（無限大！），但可以是指標——大小已知（8 bytes）。 2. 空串列的表示：就是 NULL。所有操作都要能吃 NULL—— 這讓「第一個節點」不需要特判。 3. push_front 的三步（畫圖最清楚）：

   插入前： head -> [3] -> [7] -> NULL
   步驟 1： malloc 新節點 new[1]
   步驟 2： new->next = head        （新節點接住原本整條串列）
   步驟 3： 回傳 new                 （新節點成為新的頭）
   插入後： head -> [1] -> [3] -> [7] -> NULL

介面設計成「回傳新 head」：list = push_front(list, 1);—— 單純、不需要 struct node ** 的二級指標。 4. free_list 的關鍵順序：free(p) 之後 p->next 就不能讀了（use-after-free）。所以先把 next 存下來、再 free：

while (head != NULL) {
    struct node *next = head->next;   /* 先留住 */
    free(head);                       /* 再釋放 */
    head = next;
}

走訪慣用句：for (p = head; p != NULL; p = p->next)—— 鏈結串列版的「從頭走到尾」，之後樹、雜湊鏈都是它的變體。

參考解答

/*
 * ex6_linked_list.c
 * -----------------
 * 練習 6：單向鏈結串列 —— push_front / print / free_list（難度：挑戰）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex6_linked_list.c
 * 驗證：cc -std=c11 -Wall -Wextra -fsanitize=address -o /tmp/out ex6_linked_list.c
 *      （ASan 確認零洩漏；也可用 macOS 的 leaks 工具）
 * 執行：/tmp/out
 */
#include <stdio.h>
#include <stdlib.h>

/* 節點：資料 + 指向下一個節點的指標（自我參照結構） */
struct node {
    int value;
    struct node *next;
};

/*
 * 在串列最前面插入新節點。
 * 回傳新的頭指標；失敗時印錯誤並回傳原串列（不弄丟舊資料）。
 *
 *   插入前： head -> [3] -> [7] -> NULL
 *   插入 1： new[1].next = head；回傳 new
 *   插入後： head -> [1] -> [3] -> [7] -> NULL
 */
struct node *push_front(struct node *head, int value)
{
    struct node *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "push_front：malloc 失敗\n");
        return head;
    }
    n->value = value;
    n->next = head;      /* 新節點接住原本的整條串列 */
    return n;            /* 新節點成為新的頭 */
}

void print_list(const struct node *head)
{
    printf("head");
    for (const struct node *p = head; p != NULL; p = p->next)
        printf(" -> [%d]", p->value);
    printf(" -> NULL\n");
}

/* 計算長度：順便示範標準的走訪迴圈 */
int list_length(const struct node *head)
{
    int count = 0;
    for (const struct node *p = head; p != NULL; p = p->next)
        count++;
    return count;
}

/*
 * 釋放整條串列。
 * 關鍵：free(p) 之後不能再讀 p->next，
 * 所以「先記下 next、再 free 目前節點」。
 */
void free_list(struct node *head)
{
    while (head != NULL) {
        struct node *next = head->next;   /* 先留住下一個 */
        free(head);                       /* 再釋放目前的 */
        head = next;
    }
}

int main(void)
{
    struct node *list = NULL;             /* 空串列就是 NULL */

    print_list(list);

    /* push_front 疊起來：後插的在前面 */
    int data[] = { 7, 3, 1 };
    for (int i = 0; i < 3; i++) {
        list = push_front(list, data[i]);
        print_list(list);
    }

    printf("長度 = %d\n", list_length(list));

    free_list(list);
    list = NULL;                          /* 防懸空 */
    printf("釋放完成（用 ASan 編譯執行可驗證零洩漏）\n");

    return 0;
}

程式碼講解

malloc(sizeof *n)：配置一個節點。串列的美妙在於每個節點獨立配置—— 不需要預估總量，要多少拿多少（對照動態陣列要搬家）。
push_front 失敗時回傳原 head：串列完好無損，呼叫端頂多少插一筆—— 「失敗不破壞既有狀態」是好介面的特徵。
free_list 的迴圈若寫成 free(head); head = head->next; 就是教科書級的 use-after-free——ASan 會當場抓包。順序就是這題的考點。
list = NULL; 在 free_list 之後：free_list 拿到的是 head 的複本，它無法把呼叫端的 list 設成 NULL——呼叫端要自己動手（或把介面改成 void free_list(struct node **)）。
依序 push 7、3、1 得到 1 -> 3 -> 7：push_front 天生反序，這是它 O(1) 的代價；想保序要 push_back（需要 tail 指標或每次走到底）。

範例輸出

head -> NULL
head -> [7] -> NULL
head -> [3] -> [7] -> NULL
head -> [1] -> [3] -> [7] -> NULL
長度 = 3
釋放完成（用 ASan 編譯執行可驗證零洩漏）

常見錯誤解法對照

錯誤寫法	症狀	正確做法
`p = realloc(p, bigger);`	失敗時原區塊位址被 NULL 蓋掉 → 洩漏	暫存指標接住，成功才指回
`malloc(strlen(s))` 複製字串	少 1 byte，寫 `'\0'` 時越界	`malloc(strlen(s) + 1)`
`free(p)` 後繼續用 `p->next`	use-after-free，行為隨機	先存 `next` 再 free
free 了兩次	堆積損壞，macOS 直接 abort	free 後設 NULL（`free(NULL)` 無害）
忘記檢查 malloc 回傳值	失敗時解參考 NULL 而 crash	每次配置後 `if (p == NULL)`
`memcpy(dst, NULL, 0)`	未定義行為（即使長度 0）	長度為 0 時跳過複製
回傳區域陣列的位址取代 malloc	懸空指標	堆積配置 + 呼叫端 free 的所有權約定

練習 1：make_range —— 回傳動態配置的陣列（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 2：my_strdup —— 動態複製字串（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 3：concat —— 串接兩個陣列到新配置（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 4：動態陣列 —— push / pop / shrink_to_fit（難度：進階）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 5：動態 n×n 乘法表 —— 一大塊配置法（難度：進階）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 6：單向鏈結串列 —— push_front / print / free_list（難度：挑戰）

題目

解題思路

參考解答

程式碼講解

範例輸出

常見錯誤解法對照

Related articles

練習題與詳解 — 單元 01：C 語言入門（Getting Started）

單元 01：C 語言入門（Getting Started）

練習題與詳解 — 單元 02：變數與基本型別（Variables & Types）

單元 02：變數與基本型別（Variables & Types）

練習題與詳解 — 單元 03：運算子與運算式（Operators & Expressions）

單元 03：運算子與運算式（Operators & Expressions）