摘要：C是一個比較底層的語言，沒有提供高級語言的很多特性，如接口，泛型等，但我們要用C寫一些通用的庫卻很需要這些機制。《代碼大全》里說過：“我們不要在一門語言上編程，而要深入一門語言去編程”，就是說我們不要受語言的限制，可以加一些人為的約定來提高語言的表達能力，達到我們的目的。

　　一個特定的排序程序

　　排序是一個很普通的任務，我們先隨便用一個排序算法實現對一個int數組的排序，先定義一個compar_int函數用來比較兩個int指針指向的類型，如果a比b大，則返回一個大于0的int值，如果a比b小，則返回一個小于0的int值，如果a和b相等，則返回0。

　　sort_int函數完整對int數組的排序，它需要3個參數，第一個參數是一個函數指針，該函數指針的簽名（就是函數聲明的參數及返回值的定義）和compar_int是一致的，第二個參數是一個int型指針，指向要排序的數組，第3個參數是要排序的數組元素個數。該函數的實現比較簡單，對數組遍歷n次，每次找到一個最小的數組元素放在數組的最左邊，遍歷完成后數組從左到右依次是從小達到排序了。

　　test_sort_int是一個單元測試函數，因為C語言的單元測試類庫都比較復雜，咱們測試一個小程序就自己寫測試代碼驗證就行了。聲明一個int數組arr并初始化，調用sort_int進行排序后，然后用一個for循環打印出排序后的數組

代碼

int compar_int(int *a, int *b){
return *a - *b;
}
void sort_int(int (*f)(int*, int*),int *arr,int n){
printf("sort_int\n");

int temp = *arr;
int *p_i = arr;
int i = 0, j = 0;
for(i = 0; i < n; i++){
int *p_j = p_i;
for(j = i + 1; j < n; j++){
p_j++;
if(f(p_i, p_j) > 0){
temp = *p_i;
*p_i = *p_j;
*p_j = temp;
}
}
p_i++;
}
}
void test_sort_int(){
int arr[] = {3, 2, 1, 5, 4};
sort_int(compar_int, arr, 5);
int i = 0;
for (i = 0; i < 5; i++){
printf("arr%d=%d\n", i, arr[i]);
}
}

　　單元測試結果如下

　　一個通用的排序程序

　　在.NET里實現排序，只要這個類型System.IComparable<T>，然后用System.Array.Sort<T>(T[] Array)方法就可以對其數組進行排序，這就是高級語言的優點，有接口，有泛型，類庫的通用性很好，算法重用性很強，我們也想用C寫一個通用的排序庫（我們假設stdlib.h里沒有定義qsort函數）。

　　我們知道在面向對象的語言里，委托和接口有時候是可以互相替換的，一個對象是否實現了一個接口，就是說一個對象是否支持這個接口定義的行為，委托也定義了一個行為，該行為可以由任何對象去實現，只要符合委托定義的參數和返回值就行。在C語言里沒有強類型的委托，但有與之相對應的函數指針可以用，這個問題就解決了。

　　另外就是高級語言里的泛型可以更好的支持算法的重用，尤其一些容器類的實現，C語言里也沒有，但C語言里的void指針可以指向任何類型，并可以在必要的時候做強制轉換。很多人都說不要隨便用void指針，我的觀點是不要因噎廢食，你要清楚你自己的目標是什么，你的目標是明確的，void指針只是你實現目標的工具而已，你把void指針的實現封裝你對外暴露的接口之內，別人又看不到你使用了void指針，或者你注釋里寫清楚你提供的函數怎么用，我想使用者不會被迷惑的。既然c語言提供了這個機制，肯定有它的最佳使用場景，在.NET沒有支持泛型之前，那些ArrayList,HashTable不也只支持一個通用的object參數嗎，你取出對象的時候不也得照樣強制轉換嗎，而且取出的是值類型的話，還得拆箱，C語言里把void*轉換成具體類型指針連這個消耗都沒有，為啥不用呀，難道為每一個類型寫一個排序程序就比用void*實現一個通用的排序程序優雅了嗎？我們要花大量的時間來提高代碼的通用性，封裝性，提供成熟的，穩定的，接口良好，說明準確的模塊，而不是花時間去研究怎么刻意的不去用void指針，或者為每一種類型寫一套類庫。　　

　　好了，看下我們從sort_int演變而來的通用的sort函數：

代碼

void copy(char *target, char *source, int len)
{
while(len-- > 0)
*target++ = *source++;
}
void sort(int (*f)(void*, void*), void *arr, int n, int size)
{
char temp[size];
char *p_i = arr;
int i = 0, j = 0;
for(i = 0; i < n; i++){
char *p_j = p_i;
for(j = i + 1; j < n; j++){
p_j+=size;
if((*f)(p_i, p_j) > 0){
copy(temp, p_i, size);
copy(p_i, p_j, size);
copy(p_j, temp, size);
}
}
p_i+=size;
}
}

　　可以看到，從代碼的結構上來看，sort和sort_int差不多，邏輯都是一樣的，只不過是把int *換成了void *，增加一個int類型的size參數的原因是我們不知道void指針到底是個指向什么類型的指針，不知道類型，就不知道它占用的字節數，而指針的算術運算需要根據指向類型占用的字節數來計算偏移量，因此我們不能對它進行算術運算。但我們把void *轉換成char *后就可以進行算術運算了，char類型占用一個字節（一般情況下），并且我們通過size參數知道了void *指向的類型的寬度，那么我們讓char *加上一個size長度的偏移量，就相當于void *指針指向的數組向后移動了一個元素，這樣我們就可以遍歷void *指向的原始數組了。

　　另外這里還引入了一個copy子函數，因為不知道void *指向的類型，所以我們聲明了一個char temp[size]的變量，正好能放下一個這種類型的對象，我們不管它是什么類型，我們只關心它有多大，然后copy函數是用來從一個char*的地址（由void*強制轉換得來，代表要排序數組的一個元素）往另一個char*的地址（我們剛剛聲明的temp）復制N個char寬度（1字節）的內存，這樣其實就實現了一個類似賦值的過程。

　　測試我們通用排序程序

　　我們先測試一個double類型數組，首先我們要定義 一個compar_double的函數來比較兩個double類型誰大誰小，是否相等，這相當于.NET里的IComparable的成員方法。

代碼

int compar_double(void *a, void *b){
double diff = *(double*)a - *(double*)b;
if(fabs(diff) < 0.00005)
return 0;
else if(diff > 0.0)
return 1;
else
return -1;
}

　　我們都知道double類型是不能直接比較的，由于精度的問題，要想比較兩個double對象是否相等，要把它們的差取絕對值后看是否小于某個特別小的浮點數，如果小于的話，我們就假設它們在這個要求的精度上是相等的。注意fabs要include <math.h>。測試代碼也很好寫，聲明一個double數組arr并初始化，調用sort函數，第一個參數傳遞剛剛定義的compar_double函數，最后一個參數傳遞sizeof(double)。

代碼

void test_sort_double(){
printf("sort_double\n");
double arr[] = {3.2,2.4,1.3,5.1,4.7};
sort(compar_double, arr, 5, sizeof(double));
int i = 0;
for (i = 0; i < 5; i++){
printf("arr%d=%.2f\n",i, arr[i]);
}
}

　　執行結果符合預期，如下

　　對指針數組的排序

　　剛才對一個double的數組進行了排序，在排序的過程中要對數組的元素進行實際的位置交換，交換的話就要涉及內存的拷貝，拷貝一個double對象就要拷貝sizeof(double)個字節，咱這個算法又是一個復雜度很高的函數，O(n*n)吧應該是，所以這樣算起來效率更低了，如果對一個很大的結構對象進行拷貝，那影響更大了，所以我們如果對一個大對象數組進行排序的話，可以把一個一個的大對象的指針搞成一個指針數組，對指針數組進行排序，那拷貝就只是一個指針的大小，指針應該很小，32位機器就是始終4個字節。

　　比如我們要對一個字符串數組進行排序吧，注意是字符串數組，不是字符數組，每個字符串是一個字符數組，多個字符串構成一個字符串數組，但我們最終的數組的元素只是一個個指向字符串（字符數組）的指針。我們在設計compar_string的時候，就應該知道void *a是一個指向指針的指針，我們先把a轉換成一個指向指針的指針(char**)a，然后再對其進行*取值，這樣就得到了具體的字符串的指針，也就是一個char*了，然后對char*比較，庫函數里有現成的，就是strcmp,我們直接調用它來完成對字符串比較。strcmp需要include <string.h>。

　　相應的測試程序和上面的差不多，只不過要arr的類型是一個指針數組，聲明字符串數組很簡單，因為字符串本身就是字符數組，字符數組名字本身就是一個指針常量，所以初始化arr就寫的比較直觀了，不用大括號套著大括號了，如下。

代碼

void test_sort_string(){
printf("sort_string\n");
char *arr[] = {
"lilei",
"hanmeimei",
"jim",
"poly",
"miss gao"
};
sort(compar_string, arr, 5, sizeof(char *));
char **arr_p = arr;
int i = 0;
for (i = 0; i < 5; i++){
printf("arr%d=%s\n",i, *arr_p++);
}
}

　　值得注意的一點是arr雖然是指針數組，是一個數組名，數組名又代表一個指針，但卻是一個指針常量，不能對其進行自增操作，所以我們得聲明 一個指向指針的指針char **arr_p來指向arr，然后才能遍歷指針數組并打印它的值。測試結果如下

　　小節

　　用C語言實現泛型（模板）除了用指針外還可以使用宏，但宏理解起來更麻煩，調試也麻煩，還不如耗點兒性能用指針強制轉換呢。我是一個C的新手，可能在帖子里有一些幼稚的錯誤，歡迎大家多多指點，我是寫了半天程序了，才知道類庫里有一個qsort函數和我想要實現的函數幾乎一樣，參數的類型個數都一樣，真巧了，熱。