论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2010-09-26 06:57 |只看该作者 |倒序浏览

本帖最后由 onlytiancai 于 2010-09-26 07:04 编辑

摘要：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]);
}
}

复制代码

单元测试结果如下

sort_int
arr0=1
arr1=2
arr2=3
arr3=4
arr4=5

复制代码

一个通用的排序程序
　　在.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]);
}
}

复制代码

执行结果符合预期，如下

sort_double
arr0=1.30
arr1=2.40
arr2=3.20
arr3=4.70
arr4=5.10

复制代码

对指针数组的排序
　　刚才对一个double的数组进行了排序，在排序的过程中要对数组的元素进行实际的位置交换，交换的话就要涉及内存的拷贝，拷贝一个double对象就要拷贝sizeof(double)个字节，咱这个算法又是一个复杂度很高的函数，O(n*n)吧应该是，所以这样算起来效率更低了，如果对一个很大的结构对象进行拷贝，那影响更大了，所以我们如果对一个大对象数组进行排序的话，可以把一个一个的大对象的指针搞成一个指针数组，对指针数组进行排序，那拷贝就只是一个指针的大小，指针应该很小，32位机器就是始终4个字节。
　　比如我们要对一个字符串数组进行排序吧，注意是字符串数组，不是字符数组，每个字符串是一个字符数组，多个字符串构成一个字符串数组，但我们最终的数组的元素只是一个个指向字符串（字符数组）的指针。我们在设计compar_string的时候，就应该知道void *a是一个指向指针的指针，我们先把a转换成一个指向指针的指针(char**)a，然后再对其进行*取值，这样就得到了具体的字符串的指针，也就是一个char*了，然后对char*比较，库函数里有现成的，就是strcmp,我们直接调用它来完成对字符串比较。strcmp需要include <string.h>。

int compar_string(void *a, void *b){
return strcmp(*(char**)a, *(char**)b);
}

复制代码

　　相应的测试程序和上面的差不多，只不过要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，然后才能遍历指针数组并打印它的值。测试结果如下

sort_string
arr0=hanmeimei
arr1=jim
arr2=lilei
arr3=miss gao
arr4=poly

复制代码

小节
　　用C语言实现泛型（模板）除了用指针外还可以使用宏，但宏理解起来更麻烦，调试也麻烦，还不如耗点儿性能用指针强制转换呢。我是一个C的新手，可能在帖子里有一些幼稚的错误，欢迎大家多多指点，我是写了半天程序了，才知道类库里有一个qsort函数和我想要实现的函数几乎一样，参数的类型个数都一样，真巧了，热。

这里的格式编排很差，我发到博客园了，可以直接看，链接如下
http://www.cnblogs.com/onlytiancai/archive/2010/09/25/1834926.html