众所周知，C语言是不支持泛型的，但可以利用C语言自身的语法特点来实现此特性。而此篇博文根据斯坦福公开课 《编程范式》整理，以阐述用C语言实现此种特性的大致思路，也算是一个简单的笔记。

从 Swap 谈起

交换函数应该是最常见也是最常用的函数之一，C语言的交换函数一般这样写：

1
2
3
4
5
void Swap (int *p, int *q) {
    int tmp = *p;
    *p = *q;
    *q = tmp;
}

但是如上代码仅能对 int 类型数据进行交换，如果要交换 double 或者其他类型的数据又需要写一段极其相似的代码（仅将 int 换掉），而这样无疑是不够简练的，代码也不够优美。所以我们考虑写一个能交换所有数据类型的函数，以简练代码，提高效率。

既然有这样的想法，那么我们试着去实现它。既然要普适所以数据类型，那么我们就需要向本源出发去寻找。无论什么类型的数据，在计算机底层都是以二进制储存的，这我们就找到了所有不同类型数据的共同点，也就有了设计思路：

  1. 在内存中找到两个数据的地址
  2. 从头至尾，将两个数据的每一个字节进行交换

所以结合C语言的语法特点，便有了如下代码：

1
2
3
4
5
6
void Swap (void *p, void *q, int size) {
    char buffer[size];
    memcpy(buffer, p, size);
    memcpy(p, q, size);
    memcpy(q, buffer, size);
}

就代码而言，此一类函数写就的重中之重就是 void 指针的利用，将 void 指针用于形参，以作限定。由于 void * 变量无法直接引用，因为编译器不知道此指针所指变量到底占了几个字节，且因为要适应所有数据类型，所以多传了个参数—— size ，来对传入数据类型所占字节数进行说明。而整段代码原理如下：

  1. 传入两个数据在内存中的地址以及数据所占字节数
  2. 创建临时变量字符数组 buffer[] 作为中间值（因为一个 char 占1个字节，所以正好采用字符数组来作为中间值）
  3. 与正常交换的方式相同，不过是采用 memcpy() 来进直接对内存进行操作，逐个字节进行复制

谈谈 IsSearch()

既然知道了此种思路与写法，那么我们直接看另一个简单的函数——线性查找，以 int 为例，代码是这样的：

1
2
3
4
5
6
int IsSearch (int a[], int key, int size) {
    for (int i = 0; i < size; i++)
        if (a[i] == key)
            return i;
    return -1;
}

那么如果使用泛型，代码应该怎样写呢？答案是这样的：

1
2
3
4
5
6
7
8
void* IsSearch (void* key, void* base, int n, int elemSize){
    for (int i = 0; i < n; i++) {
        void* elemAddr = (char*)base + i*elemSize;
        if (memcpy(key, elemAddr, elemSize) == 0)
            return elemAddr;
    }
    return NULL;
}

整段代码解释如下：

  1. 传入需要搜索的值，被搜索数组，数组元素数，数组每个元素所占字节数
  2. 进入循环开始查找：
    1. 先确定每一个元素的地址（由于 void* 类型的指针不支持直接操作，所以需要先将其进行强制类型转换为 char* 类型指针）
    2. 调用库函数，将 key 和数组中的元素依次进行必较
  3. 成功则返回数组对应元素的首地址，否则返回NULL

但如果我们不利用库函数来进行比较呢？我们想使用自己写的比较函数来比较，那有应该怎么做呢？（注：这个想法显然必较牵强，因为此时的这种写法无疑是更加合理的，而为了说明知识点，就加了这个想法）

（此处 qsort() 课中并未提及）在这里就不得不提一个C语言库函数了，那就是—— qsort() ，一个在调用之时需要写一个针对问题具体情况的比较函数当作参数传入函数之中，而我们这时的情况显然和 qsort() 函数面临的一样，所以我们采用相同的处理方式：传入一个必较函数，来判断两个元素是否一致。

1
2
3
4
5
6
7
8
void* IsSearch (void* key, void* base, int n, int elemSize, int (*cmpfn) (void*, void*)){
    for (int i = 0; i < n; i++) {
        void* elemAddr = (char*)base + i*elemSize;
        if (cmpfn(key, elemAddr) == 0)
            return elemAddr;
    }
    return NULL;
}

注：因为 cmpfn() 是调用者写的函数，所以其数据类型是确定的，只需直接比较就行，故只传入两个参数。

调用 IsSearch()

有了普适版（第二版）的代码，其中提供了函数接口，那么调用者应该怎么写这个函数呢？

int 类型数据

比较 int 类型数据的函数，代码如下：

1
2
3
4
5
int IntCmp (void* n1, void* n2) {
    int* ip1 = n1;
    int* ip2 = n2;
    return (*ip1 - *ip2);
}

注：此函数所带参数l类型以及返回值类型需与形参中函数一致

char* (字符串)类型数据

字符串无疑是优雅的，但在C语言中处理字符串，就完全不存在优雅这一说了，因为C语言更加底层，对于字符串的处理不如其他的一些新语言来的形象（当然也是此些语言为字符串处理做了许多预备工作，以至于处理之时只调用已有的函数即可），所以关于字符串的处理可能要更加不易理解，代码如下：

1
2
3
4
5
int StrCmp (void* vp1, void* vp2) {
    char* s1 = * (char**)vp1;
    char* s2 = * (char**)vp2;
    return strcmp(s1, s2);
}

仅看如此代码，会有种毫无头绪的感觉，那么为了更好地理解，我们需要写一下查找字符串时的全过程，代码：

1
2
3
char* key = "Li";
char* faName[] = {"zhang", "wang", "li", "zhao", "sun"};
char** found = IsSearch(&key, faName, 5, sizeof(char*), StrCmp);

好，因为单个的 char 是字符，而字符串是 char* ，那么理所当然字符串数组就是 char** 了，所以需要查找之时，传入 IsSearch() 的参数实际上是指针的指针，所以在调用比较函数之时需要进行一次解耦，将之变成两个字符串，而这也就是比较函数前两行的意义所在。

注：

  1. 为了比较函数代码美观，所以在传参之时将目标字符串也作为指针的指针传入，如只将其作为指针传入，就无需解耦和了。
  2. 在调用之时，用于接收返回值的变量必须是指针的指针，因为返回是个字符串，也就是一个字符指针