C 語言結構體指標強制轉換詳解：qsort 比較函式實作原理

程式碼片段

typedef struct {
    string dna;
    int count;
} DNA;

DNA dna[101];

int cmp(const void *a, const void *b) {
    DNA *aa = (DNA *)a;
    DNA *bb = (DNA *)b;
    return aa->count - bb->count;
}

qsort(dna, m, sizeof(dna[0]), cmp);

核心問題：為何要 (DNA *) 強制轉換？

1. void* 是「通用位址」，無型別資訊

• qsort 為通用排序函式，接受 void* 指向元素陣列。
• 比較函式參數 const void *a, *b 僅傳遞元素的記憶體位址，編譯器不知道指向什麼型別。

2. 指標型別決定「如何解讀記憶體」

• DNA *aa 告訴編譯器：「這個位址存放的是 DNA 結構體」。
• 轉換後，aa->count 會依據 DNA 結構體佈局（count 的位移量）正確存取該欄位。
• 若不轉換直接寫 a->count，編譯錯誤：void* 無法解引用。

3. 記憶體佈局圖解

dna 陣列記憶體：
+--------+--------+--------+--------+ ... (每個 DNA 結構體)
| dna[0] | dna[1] | dna[2] | dna[3] |
+--------+--------+--------+--------+
  ^      ^
  a      b   (qsort 傳給 cmp 的 void* 指標)

cmp 內部：
DNA *aa = (DNA*)a;  // aa 指向 dna[0] 開頭
aa->count  ==  *(int*)((char*)aa + offsetof(DNA, count))

為何使用 const void*？

• 通用性：同一個 qsort 可排序 int[]、double[]、struct[] 等任意型別。
• 類型安全：const 承諾比較函式不修改元素內容。
• C 語言無模板/泛型，void* 是實現多態的唯一手段。

常見錯誤與避坑

1. 減法溢位：return aa->count - bb->count; 若 count 可能為 INT_MIN，減法會溢位導致錯誤排序。
   正確寫法：return (aa->count > bb->count) - (aa->count < bb->count); 或 return aa->count < bb->count ? -1 : (aa->count > bb->count);
2. 結構體填充對齊：sizeof(dna[0]) 包含編譯器插入的填充位元組，qsort 以此為元素大小正確跳躍。
3. 轉換語法：C 語言 (DNA*)a，C++ 建議 static_cast(a)。

C++ 現代替代方案

#include 
#include 

std::vector vec(dna, dna + m);
std::sort(vec.begin(), vec.end(), 
    [](const DNA& a, const DNA& b) { return a.count < b.count; });

• 型別安全、無需 void*、支援 Lambda、效能不遜於 qsort。

總結

void* 傳遞「位址」，(DNA*) 賦予「型別意義」，使編譯器能依結構體定義正確存取成員。這是 C 語言實現泛型演算法的核心機制，理解記憶體佈局與指標轉換語意，是寫出正確、高效系統級程式碼的基礎。