本檔收錄 6 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住超過
30 分鐘再看「解題思路」，寫完再對照「參考解答」與「程式碼講解」。
每題的完整程式碼也放在 exercises/ 資料夾，可直接編譯執行：
cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_apply.c && /tmp/out練習 1：高階函式 apply（難度：基礎）
題目
寫一個函式 int apply(int x, int (*f)(int))，把整數 x 交給函式指標
f 處理並回傳結果。用它套用三種函式：my_abs（絕對值）、square
（平方）、inc（加一），對測試資料 -7, 0, 3, 12 各跑一輪。
輸入／輸出範例（節錄）：
f = square:
apply( -7, square) = 49
apply( 0, square) = 0解題思路
- 分析問題：
apply不關心f做什麼，它只負責「轉呼叫」。這是 高階函式（higher-order function）最原始的形式——把「行為」當資料傳遞。 - 宣告怎麼寫：參數
int (*f)(int)的括號不可省略。int *f(int)是「回傳int*的函式」宣告，完全是另一回事。 右左法則：從f出發，先碰括號內的*（是指標），再往右碰(int)（指向函式），最後往左（回傳int）。 - 呼叫怎麼寫：
f(x)與(*f)(x)等價，現代慣用前者。 - 批次測試：三個函式 × 四筆資料，自然想到「函式指標陣列」
int (*fns[])(int) = { my_abs, square, inc };搭配平行的名稱表， 雙層迴圈掃過即可——這正是資料驅動（table-driven)風格的起點。 - 邊界情況：
my_abs(0)應回 0；本題不處理INT_MIN（其絕對值 超出int範圍，是未定義行為），教學實作以一般值為主。
參考解答
/*
* ex1_apply.c — 練習 1：高階函式 apply
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_apply.c
* 執行：/tmp/out
*
* 寫一個 int apply(int x, int (*f)(int))，
* 並用它套用 my_abs、square、inc 三種函式。
*/
#include <stdio.h>
/* ---- 三個「int -> int」的目標函式 ---- */
static int my_abs(int x) { return x < 0 ? -x : x; }
static int square(int x) { return x * x; }
static int inc(int x) { return x + 1; }
/*
* apply：把「策略」當參數傳進來的高階函式。
* f 的型別是「指向 (int)->int 函式的指標」，括號不可省略。
*/
static int apply(int x, int (*f)(int))
{
return f(x); /* 透過指標呼叫，寫法與一般函式呼叫相同 */
}
int main(void)
{
/* 測試資料寫死，涵蓋負數、零、正數 */
int inputs[] = { -7, 0, 3, 12 };
int n = (int)(sizeof inputs / sizeof inputs[0]);
/* 函式指標陣列 + 名稱表：批次驅動同一組測資 */
int (*fns[])(int) = { my_abs, square, inc };
const char *names[] = { "my_abs", "square", "inc" };
int nfns = (int)(sizeof fns / sizeof fns[0]);
for (int i = 0; i < nfns; i++) {
printf("f = %s:\n", names[i]);
for (int j = 0; j < n; j++)
printf(" apply(%3d, %s) = %d\n",
inputs[j], names[i], apply(inputs[j], fns[i]));
}
/* 也可以直接以函式名稱呼叫（名稱自動退化為指標） */
printf("direct: apply(-5, my_abs) = %d\n", apply(-5, my_abs));
return 0;
}程式碼講解
apply本體只有一行return f(x);——高階函式的價值不在函式本身， 而在呼叫端獲得的組合彈性。int (*fns[])(int)讀法：fns是陣列，元素是「指向 (int)->int 函式的指標」。名稱表names[]與它平行對應，這是 C 沒有反射機制時 印出函式名的標準做法。- 易錯處：把參數寫成
int *f(int)（少了括號）會得到一個 函式宣告而非函式指標參數，編譯錯誤訊息往往令人困惑。 main最後一行示範函式名稱在運算式中自動退化為指標，apply(-5, my_abs)與apply(-5, &my_abs)完全等價。
範例輸出
f = my_abs:
apply( -7, my_abs) = 7
apply( 0, my_abs) = 0
apply( 3, my_abs) = 3
apply( 12, my_abs) = 12
f = square:
apply( -7, square) = 49
apply( 0, square) = 0
apply( 3, square) = 9
apply( 12, square) = 144
f = inc:
apply( -7, inc) = -6
apply( 0, inc) = 1
apply( 3, inc) = 4
apply( 12, inc) = 13
direct: apply(-5, my_abs) = 5練習 2：qsort 由大到小排序 double（難度：基礎）
題目
用標準函式庫的 qsort 將 double 陣列由大到小排序。
測試資料：3.14, -1.5, 2.71, 0.0, 42.0, 2.70, -1.49。
特別要求：說明為什麼浮點數的比較函式不能用相減，並用程式證明。
預期輸出：
after : 42.00 3.14 2.71 2.70 0.00 -1.49 -1.50解題思路
- qsort 的契約：比較函式簽名固定是
int cmp(const void *, const void *)，回傳負／零／正表示 「第一個引數應排在前／相等／排在後」。 - 遞減怎麼做：把回傳值反過來即可——
a > b時回-1（a 排前面）。 - 為什麼不能相減：整數常見的
return a - b;搬到浮點數上有兩個致命傷： - 回傳型別是int，(int)(2.71 - 2.70)=(int)0.01=0， 兩個明明不同的數被判成相等，排序結果不穩定甚至錯誤。 - 極端值相減可能溢位（DBL_MAX - (-DBL_MAX)是無限大）。 正確做法：用<、>明確回傳 -1/0/1。 - 驗證設計：故意放入
2.71與2.70、-1.49與-1.5這種「差距小於 1」的資料，錯誤的相減法會現形。
參考解答
/*
* ex2_qsort_desc.c — 練習 2：qsort 將 double 陣列由大到小排序
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_qsort_desc.c
* 執行：/tmp/out
*
* 重點：浮點數比較函式「不能用相減」——
* 相減轉 int 會截斷小數（0.5 - 0.1 = 0.4 -> 0，誤判相等），
* 且極端值相減可能溢位或產生 NaN。必須用比較運算子。
*/
#include <stdio.h>
#include <stdlib.h>
/*
* 遞減比較函式：回傳負值表示 a 應排在 b 前面。
* qsort 的介面規定參數是 const void *，先轉回真正的型別再比較。
*/
static int cmp_double_desc(const void *pa, const void *pb)
{
double a = *(const double *)pa;
double b = *(const double *)pb;
/* 想要遞減：a 比較大時回負值（a 排前面） */
if (a > b) return -1;
if (a < b) return 1;
return 0;
}
/* 錯誤示範用的「相減法」比較（本程式只展示它為何錯，不用它排序） */
static int cmp_wrong(const void *pa, const void *pb)
{
/* 0.4 截斷成 0 -> 誤判為相等！ */
return (int)(*(const double *)pa - *(const double *)pb);
}
static void print_array(const char *tag, const double *a, size_t n)
{
printf("%s", tag);
for (size_t i = 0; i < n; i++)
printf(" %.2f", a[i]);
printf("\n");
}
int main(void)
{
double data[] = { 3.14, -1.5, 2.71, 0.0, 42.0, 2.70, -1.49 };
size_t n = sizeof data / sizeof data[0];
print_array("before:", data, n);
qsort(data, n, sizeof data[0], cmp_double_desc);
print_array("after :", data, n);
/* 展示「相減法」為何錯：差距小於 1 的兩數被判成相等 */
double x = 2.71, y = 2.70;
printf("\nwhy subtraction is wrong:\n");
printf(" cmp_wrong(2.71, 2.70) = %d (truncated to 0: judged equal!)\n",
cmp_wrong(&x, &y));
printf(" cmp_double_desc(2.71, 2.70) = %d (correct)\n",
cmp_double_desc(&x, &y));
return 0;
}程式碼講解
cmp_double_desc先把const void *轉回const double *再解參考， 這個「兩段式還原」是所有 qsort 比較函式的固定開場。- 遞減的關鍵只在一行：
a > b時回-1。若想改回遞增，交換-1/1即可；更通用的技巧是寫一個遞增版然後回傳它的相反數。 cmp_wrong保留在程式裡當「反面教材」，main用 2.71 vs 2.70 實測給你看：回傳 0，qsort 會認為它們相等，順序聽天由命。- 易錯處：比較函式若回傳不一致（違反全序關係），
qsort的行為是 未定義的——某些平台會當機，不只是排錯而已。
範例輸出
before: 3.14 -1.50 2.71 0.00 42.00 2.70 -1.49
after : 42.00 3.14 2.71 2.70 0.00 -1.49 -1.50
why subtraction is wrong:
cmp_wrong(2.71, 2.70) = 0 (truncated to 0: judged equal!)
cmp_double_desc(2.71, 2.70) = -1 (correct)練習 3：泛型 for_each（難度：進階）
題目
模仿 qsort 的泛型介面，實作：
void for_each(void *base, size_t n, size_t size, void (*visit)(void *));對「任意型別」陣列的每個元素呼叫 visit。用三種型別驗證：
int 陣列（先印出、再就地每個乘 2）、double 陣列、字串（char*）陣列。
預期輸出：
int array : 1 2 3 4 5
after *2 : 2 4 6 8 10解題思路
- 泛型的本質：C 沒有模板，泛型函式「看不到」元素型別，
呼叫端必須把型別資訊拆成兩個數字傳進來——元素個數
n與 元素大小size（用sizeof取得）。 - 位址計算：第
i個元素的位址是(char *)base + i * size。為什麼要轉char *？因為指標算術以 「指向型別的大小」為單位，char恰好是 1 位元組，乘上size才會正確。void *在標準 C 中不允許算術。 - 回呼端還原型別：
visit收到的是「元素的位址」。對int陣列就是int *；注意字串陣列的元素本身是char *， 所以元素位址是char **——這是最容易錯的一層。 - 就地修改：因為傳的是位址而非複本，回呼可以直接改元素
（
double_int示範），這也是介面用void *而非const void *的原因。 - 複雜度：走訪一次 O(n)，無額外空間。
參考解答
/*
* ex3_for_each.c — 練習 3：泛型 for_each
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_for_each.c
* 執行：/tmp/out
*
* 模仿 qsort 的泛型介面：
* void for_each(void *base, size_t n, size_t size, void (*visit)(void *))
* 對「任意型別」陣列的每個元素呼叫 visit。
* 關鍵：泛型程式碼看不到元素型別，只能用 char* 做位元組位移。
*/
#include <stdio.h>
/*
* 泛型走訪：base 是陣列起點，n 是元素個數，size 是單一元素的位元組數。
* 第 i 個元素的位址 = (char *)base + i * size。
* 一定要先轉成 char*（位移單位 = 1 位元組）；void* 不能做算術。
*/
static void for_each(void *base, size_t n, size_t size,
void (*visit)(void *))
{
char *p = base;
for (size_t i = 0; i < n; i++)
visit(p + i * size);
}
/* ---- 各型別的 visit 回呼：把 void* 轉回真正的型別 ---- */
static void print_int(void *elem)
{
printf(" %d", *(int *)elem);
}
static void double_int(void *elem) /* 就地修改：每個元素乘 2 */
{
*(int *)elem *= 2;
}
static void print_double(void *elem)
{
printf(" %.2f", *(double *)elem);
}
static void print_str(void *elem)
{
/* 元素是 char*，elem 是「指向元素的指標」= char** */
printf(" \"%s\"", *(char **)elem);
}
int main(void)
{
int ints[] = { 1, 2, 3, 4, 5 };
double doubles[] = { 1.5, 2.25, 3.125 };
char *strs[] = { "alpha", "beta", "gamma" };
printf("int array :");
for_each(ints, 5, sizeof ints[0], print_int);
printf("\n");
/* visit 拿到的是元素位址，因此也能「就地修改」 */
for_each(ints, 5, sizeof ints[0], double_int);
printf("after *2 :");
for_each(ints, 5, sizeof ints[0], print_int);
printf("\n");
printf("double array:");
for_each(doubles, 3, sizeof doubles[0], print_double);
printf("\n");
printf("string array:");
for_each(strs, 3, sizeof strs[0], print_str);
printf("\n");
return 0;
}程式碼講解
for_each只有四行，核心是visit(p + i * size)：p已是char *，+ i * size前進到第 i 個元素的第一個位元組。print_str是本題的「陷阱檢查點」：strs的元素型別是char *，所以visit收到char **，要先解一層才得到字串。 寫成printf("%s", (char *)elem)會印出垃圾（把指標變數本身的 位元組當字串讀）。- 就地修改能成立，是因為
for_each傳的是元素位址而非值； 對照qsort的比較函式收const void *——人家只想讀不想改。 - 易錯處：
char *p = base;這行在 C 是合法的隱式轉換 （void *可自由轉任何物件指標），寫 C++ 時才需要顯式 cast。
範例輸出
int array : 1 2 3 4 5
after *2 : 2 4 6 8 10
double array: 1.50 2.25 3.12
string array: "alpha" "beta" "gamma"練習 4：多鍵排序（難度：進階）
題目
為結構 struct student { char name[16]; int score; } 用單一 qsort
呼叫完成多鍵排序：先依分數遞減，同分依姓名字典序遞增。
測試資料（刻意安排三人同分 88、兩人同分 92）：
Ivy 88, Frank 92, Alice 88, Dave 75, Carol 92, Bob 88預期排序結果：Carol 92, Frank 92, Alice 88, Bob 88, Ivy 88, Dave 75。
解題思路
- 多鍵比較的固定套路：比較函式內「先比主鍵，不相等就直接回傳； 相等才比次鍵」。串接幾層都行，qsort 只看最後的正負號。
- 主鍵遞減：
a->score < b->score時回1（a 排後面）。 分數範圍 0~100 時b->score - a->score也安全，但養成 用比較運算子的習慣可避免大數溢位。 - 次鍵遞增：
strcmp(a->name, b->name)的回傳值正好符合 qsort 契約，直接回傳即可。 - 為什麼不用「排兩次」：先按姓名排、再按分數「穩定排序」一次
也能達成——但 C 標準的
qsort不保證穩定，這條路在 C 走不通， 多鍵比較函式才是正解。 - 驗收設計：同分組內姓名故意亂序（Ivy、Alice、Bob）， 排完必須變成 Alice、Bob、Ivy 才算對。
參考解答
/*
* ex4_multikey_sort.c — 練習 4：多鍵排序（分數遞減、同分姓名遞增）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_multikey_sort.c
* 執行：/tmp/out
*
* 多鍵比較的固定套路：
* 先比主鍵，不相等就直接回傳；相等才落到次鍵。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct student {
char name[16];
int score;
};
/*
* 主鍵：score 遞減；次鍵：name 字典序遞增。
* int 相減在這裡安全嗎？score 範圍 0~100，不會溢位，可以用；
* 但為了通用性，示範用比較運算子的寫法。
*/
static int cmp_student(const void *pa, const void *pb)
{
const struct student *a = pa;
const struct student *b = pb;
if (a->score != b->score)
return (a->score < b->score) ? 1 : -1; /* 遞減：小的排後面 */
return strcmp(a->name, b->name); /* 同分：姓名遞增 */
}
int main(void)
{
struct student class[] = {
{ "Ivy", 88 },
{ "Frank", 92 },
{ "Alice", 88 },
{ "Dave", 75 },
{ "Carol", 92 },
{ "Bob", 88 },
};
size_t n = sizeof class / sizeof class[0];
printf("before sort:\n");
for (size_t i = 0; i < n; i++)
printf(" %-8s %d\n", class[i].name, class[i].score);
qsort(class, n, sizeof class[0], cmp_student);
printf("\nafter sort (score desc, then name asc):\n");
for (size_t i = 0; i < n; i++)
printf(" %-8s %d\n", class[i].name, class[i].score);
return 0;
}程式碼講解
const struct student *a = pa;：void *到具體型別的隱式轉換， 比到處寫 cast 乾淨。- 主鍵那行
(a->score < b->score) ? 1 : -1——進到這個分支時兩者 已確定不等，所以只需分「小於／大於」兩種情況。 strcmp直接當次鍵比較器用：它回傳的正負號語意與 qsort 要求 完全一致，這不是巧合——qsort 的介面就是照著strcmp家族設計的。- 易錯處：若把兩鍵寫反（先比姓名再比分數），輸出乍看也「有序」， 但同分組不會聚在一起；驗收時務必檢查同分組內的次序。
範例輸出
before sort:
Ivy 88
Frank 92
Alice 88
Dave 75
Carol 92
Bob 88
after sort (score desc, then name asc):
Carol 92
Frank 92
Alice 88
Bob 88
Ivy 88
Dave 75練習 5：表驅動狀態機（難度：挑戰）
題目
用「函式指標轉移表」實作一個狀態機，判斷字串是否符合
[+-]?digits（可帶正負號的十進位整數）。要求：
- 狀態以
enum表示，每個狀態對應一個狀態函式； - 轉移表為
state_fn table[N_STATES]； - 主迴圈只有三行（查表、呼叫、判斷是否終止）。
測試："123"、"-42"、"+7"、"0" 應 ACCEPT；
""、"+"、"12a"、"a12"、"3.14"、"-" 應 REJECT。
解題思路
- 先畫狀態圖（一定要先畫，寫碼只是抄圖）：
'+'/'-' digit
START ────────────> SIGN ─────────┐
│ digit ▼
└──────────────────────────> DIGITS ──┐ digit（自迴圈）
│ '\0'
▼
ACCEPT
（其餘輸入一律 -> REJECT）- 為什麼需要獨立的 SIGN 狀態：
"+"後面必須至少有一個數字。 若讓'+'直接跳到 DIGITS，"+"讀到'\0'就會被 DIGITS 當成正常收尾而誤判 ACCEPT。狀態的意義是「到目前為止讀了什麼」， 「剛讀完正負號」和「已讀到至少一個數字」是不同的歷史，必須分開。 - 狀態函式的介面：
enum state (*)(char c)——吃當前字元、 回傳下一個狀態。所有轉移邏輯都封裝在各自的狀態函式裡， 主迴圈完全不含 if/switch。 - 終端狀態：ACCEPT／REJECT 不會再被呼叫，表中放
NULL； 主迴圈以「到達終端狀態」為停止條件，所以永遠不會呼叫到 NULL。 - 為什麼用表不用 switch：新增狀態時只要「加一個函式＋填一格表」， 不必動主迴圈；狀態多達數十個時（如協定解析器），表驅動的 可維護性壓倒性勝出。
- 複雜度：每個字元恰好處理一次，O(n)。
參考解答
/*
* ex5_state_machine.c — 練習 5：函式指標表驅動的狀態機
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_state_machine.c
* 執行：/tmp/out
*
* 題材：判斷字串是否符合 [+-]?digits （帶正負號的整數）。
*
* 狀態圖：
*
* '+'/'-' digit
* START ────────────> SIGN ─────────┐
* │ digit ▼
* └──────────────────────────> DIGITS ──┐ digit（自迴圈）
* │ '\0'
* ▼
* ACCEPT
* （其餘輸入一律 -> REJECT）
*
* 每個狀態是一個函式，回傳下一個狀態；主迴圈只有三行。
*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
enum state { ST_START, ST_SIGN, ST_DIGITS, ST_ACCEPT, ST_REJECT, N_STATES };
/* 狀態函式：吃目前字元，回傳下一個狀態 */
typedef enum state (*state_fn)(char c);
static enum state do_start(char c)
{
if (c == '+' || c == '-') return ST_SIGN;
if (isdigit((unsigned char)c)) return ST_DIGITS;
return ST_REJECT; /* 含空字串（c=='\0'）：直接拒絕 */
}
static enum state do_sign(char c)
{
/* 正負號後「必須」接數字：這就是獨立 SIGN 狀態存在的理由 */
if (isdigit((unsigned char)c)) return ST_DIGITS;
return ST_REJECT; /* "+"、"-a" 都死在這裡 */
}
static enum state do_digits(char c)
{
if (isdigit((unsigned char)c)) return ST_DIGITS; /* 自迴圈 */
if (c == '\0') return ST_ACCEPT; /* 正常收尾 */
return ST_REJECT;
}
/* 轉移表：狀態 -> 處理函式。終端狀態不會被呼叫，放 NULL。 */
static const state_fn table[N_STATES] = {
[ST_START] = do_start,
[ST_SIGN] = do_sign,
[ST_DIGITS] = do_digits,
[ST_ACCEPT] = NULL,
[ST_REJECT] = NULL,
};
/* 主迴圈只有三行：查表 -> 間接呼叫 -> 前進 */
static int match_number(const char *s)
{
enum state st = ST_START;
for (const char *p = s; st != ST_ACCEPT && st != ST_REJECT; p++)
st = table[st](*p);
return st == ST_ACCEPT;
}
int main(void)
{
const char *tests[] = {
"123", "-42", "+7", "0", "", "+", "12a", "a12", "3.14", "-",
};
size_t n = sizeof tests / sizeof tests[0];
printf("pattern: [+-]?digits\n\n");
for (size_t i = 0; i < n; i++) {
char quoted[16];
snprintf(quoted, sizeof quoted, "\"%s\"", tests[i]);
printf(" %-8s -> %s\n", quoted,
match_number(tests[i]) ? "ACCEPT" : "REJECT");
}
return 0;
}程式碼講解
table用 C99 指定初始化器[ST_START] = do_start填表： 就算日後 enum 順序調整，對應關係也不會錯位——這是表驅動程式 的防禦性寫法。- 主迴圈
st = table[st](*p);一行做了三件事：用目前狀態查表、 間接呼叫狀態函式、接收下一個狀態。 isdigit((unsigned char)c)：ctype.h函式的參數必須是unsigned char值或 EOF，直接丟有號char（可能為負）是 未定義行為——這是老手也常忘的細節。- 迴圈條件保證只在非終端狀態呼叫
table[st]，因此 ACCEPT/REJECT 兩格的NULL永遠不會被執行。 - 易錯處：讓
'+'直接進 DIGITS 會誤收"+"。狀態機 bug 幾乎 都源於「兩段不同的歷史被塞進同一個狀態」。
範例輸出
pattern: [+-]?digits
"123" -> ACCEPT
"-42" -> ACCEPT
"+7" -> ACCEPT
"0" -> ACCEPT
"" -> REJECT
"+" -> REJECT
"12a" -> REJECT
"a12" -> REJECT
"3.14" -> REJECT
"-" -> REJECT練習 6：自製泛型排序 my_qsort（難度：挑戰）
題目
仿 K&R §5.11，自己實作泛型排序函式（內部演算法用插入排序即可），
介面與標準 qsort 完全相同：
void my_qsort(void *base, size_t n, size_t size,
int (*cmp)(const void *, const void *));要求：元素定位用 char * 位移、元素搬移用 memcpy。
用 int 陣列與字串陣列各測一次，並與標準 qsort 的結果比對。
解題思路
- 先寫「會型別」的版本：對
int陣列的插入排序是 「抓出a[i]，往前把比它大的右移，放進空位」。 泛型化就是把這三個動作翻譯成不依賴型別的操作。 - 翻譯對照表：
| 有型別的寫法 | 泛型寫法 |
|---|---|
int tmp = a[i]; |
memcpy(tmp, b + i*size, size); |
a[j] = a[j-1]; |
memcpy(b + j*size, b + (j-1)*size, size); |
a[j-1] > tmp |
cmp(b + (j-1)*size, tmp) > 0 |
- 暫存區：不知道元素型別，就開一塊「夠大的位元組緩衝區」
char tmp[64]當暫存。生產級寫法會用 VLA 或 malloc； 教學版設個上限並檢查即可。 - 為什麼是插入排序：泛型化的重點在介面而非演算法； 插入排序短小、穩定，n 小時甚至比快排快（glibc qsort 的 小區間也是切回插入排序）。
- 複雜度：O(n²) 比較與搬移；每次搬移是
memcpy(size)， 大元素的常數成本高——這也是為什麼實務上排大結構時常改排 「指標陣列」。 - 驗收：同一組資料丟給標準
qsort，memcmp比對兩者結果。
參考解答
/*
* ex6_my_qsort.c — 練習 6：自製泛型排序（介面同標準 qsort）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex6_my_qsort.c
* 執行：/tmp/out
*
* 仿 K&R §5.11：實作與標準 qsort 介面完全相同的泛型排序
* （內部用插入排序即可）。泛型的代價是：
* - 位址計算全用 char* + i * size
* - 元素搬移全用 memcpy / memmove（不知道型別，不能用 =）
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_ELEM_SIZE 64 /* 暫存單一元素用的緩衝區上限 */
/*
* my_qsort：插入排序版。
* 把第 i 個元素抓進 tmp，往前找插入點，路上的元素整段右移一格。
*/
static void my_qsort(void *base, size_t n, size_t size,
int (*cmp)(const void *, const void *))
{
char *b = base;
char tmp[MAX_ELEM_SIZE];
if (size > sizeof tmp) {
fprintf(stderr, "my_qsort: element too large\n");
exit(1);
}
for (size_t i = 1; i < n; i++) {
memcpy(tmp, b + i * size, size); /* 抓出待插入元素 */
size_t j = i;
/* 從右往左找插入點：比 tmp 大的元素往右挪一格 */
while (j > 0 && cmp(b + (j - 1) * size, tmp) > 0) {
memcpy(b + j * size, b + (j - 1) * size, size);
j--;
}
memcpy(b + j * size, tmp, size); /* 放進插入點 */
}
}
/* ---- 用兩種型別驗證泛型介面 ---- */
static int cmp_int(const void *a, const void *b)
{
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y); /* 慣用式：避免溢位的三態比較 */
}
static int cmp_str(const void *a, const void *b)
{
/* 元素是 char*，參數是「元素的位址」= const char *const * */
return strcmp(*(const char *const *)a, *(const char *const *)b);
}
int main(void)
{
int nums[] = { 42, -7, 19, 0, 88, -7, 5 };
size_t nn = sizeof nums / sizeof nums[0];
char *words[] = { "pear", "apple", "fig", "banana", "date" };
size_t nw = sizeof words / sizeof words[0];
my_qsort(nums, nn, sizeof nums[0], cmp_int);
printf("ints :");
for (size_t i = 0; i < nn; i++) printf(" %d", nums[i]);
printf("\n");
my_qsort(words, nw, sizeof words[0], cmp_str);
printf("strings:");
for (size_t i = 0; i < nw; i++) printf(" %s", words[i]);
printf("\n");
/* 與標準 qsort 對照：同一組資料應得到同樣結果 */
int check[] = { 42, -7, 19, 0, 88, -7, 5 };
qsort(check, nn, sizeof check[0], cmp_int);
printf("match standard qsort? %s\n",
memcmp(nums, check, sizeof nums) == 0 ? "yes" : "no");
return 0;
}程式碼講解
- 內層
while是插入排序的心臟：cmp(b + (j-1)*size, tmp) > 0表示「左邊那個元素比待插入的大」，就把它右移一格。注意比較的 兩個引數都是位址——tmp本身就是位元組陣列，直接可傳。 (x > y) - (x < y)是三態比較的慣用式：結果必為 -1/0/1， 且完全沒有溢位風險，值得背下來。cmp_str的 cast*(const char *const *)a：元素是char *， 所以引數是「指向char *的指標」；加上兩層const是為了 嚴格對應const void *的唯讀承諾。- 易錯處一：交錯搬移時若把
memcpy的來源／目的順序寫反， 資料會被覆蓋掉——先存tmp再右移的順序不能亂。 - 易錯處二：
j用size_t（無號），迴圈條件必須先寫j > 0再取j - 1，否則j = 0時j - 1會繞回極大值。
範例輸出
ints : -7 -7 0 5 19 42 88
strings: apple banana date fig pear
match standard qsort? yes常見錯誤解法對照
| 錯誤寫法 | 症狀 | 正解 |
|---|---|---|
比較函式用 (int)(a - b) 比 double |
差距 < 1 被判相等，排序不穩 | 用 <／> 回傳 -1/0/1（練習 2） |
int *f(int) 當函式指標參數 |
編譯錯誤：宣告了一個函式 | int (*f)(int)（練習 1） |
字串陣列回呼中 cast 成 char * |
印出亂碼 | 元素位址是 char **，先解一層（練習 3） |
| 想用「排兩次」做多鍵排序 | C 的 qsort 不穩定，結果錯亂 | 單一比較函式串接多鍵（練習 4） |
'+' 直接跳 DIGITS 狀態 |
"+" 被誤判 ACCEPT |
獨立 SIGN 狀態（練習 5） |
泛型搬移用 = 或忘了 char * 轉型 |
編譯錯誤或位移錯亂 | char * 位移 + memcpy（練習 6） |