非常好!受益匪浅
插入排序函数的实现: void insert_sort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)) { unsigned char tmp_ch; unsigned char * base_ch; int i, j, k; for(i=1; i<nmemb; i++){ for(j=i-1; j>=0; j--){ if(compar(base+(j*size), base+(j+1)*size) > 0){ //exchange the two elements of sort_t; base_ch = base+(j*size); for(k=0; k<size; k=k+1){ //here 1 == sizeof(unsigned char); tmp_ch = base_ch[k]; base_ch[k] = base_ch[k+size]; base_ch[k+size] = tmp_ch; } } } } return; } int cmp(const void * ptra, const void * ptrb) { return (*(sort_t *)ptra).key - (*(sort_t *)ptrb).key; }
exchange的实现也可以这样写: //exchange the two elements of sort_t; base_ch = base+(j*size); for(k=0; k<size; k=k+1){ //here 1 == sizeof(unsigned char); base_ch[k] = base_ch[k] ^ base_ch[k+size]; base_ch[k+size] = base_ch[k] ^ base_ch[k+size]; base_ch[k] = base_ch[k] ^ base_ch[k+size]; }
泛型二分查找的实现: void *binary_search(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { int low = 0, high = nmemb-1, middle = (low+high)/2, compar_st = 0; while(low <= high){ compar_st = compar(base+middle*size, key); if(compar_st > 0){ high = middle-1; }else if(compar_st < 0){ low = middle+1; }else{ return (void *)(base+middle*size); } middle = (low+high)/2; } return NULL; } int cmp(const void * ptra, const void * ptrb) { return (*(sort_t *)ptra).key - (*(sort_t *)ptrb).key; }
非常好,通俗易懂
受益非浅!
非常好,本来这个“回调函数”也没什么神秘的,看别人的越看越胡图。
”如果参数是一个函数指针,调用者可以传递一个函数的地址给实现者,让实现者去调用它,这称为回调函数(Callback Function)。“ 你的这段描述有误,应该是--如果参数是一个函数指针,实现者可以传递一个函数的地址给调用者,让调用者去调用它,这称为回调函数(Callback Function)
// ty109_vc.cpp : Defines the entry point for the console application. // #include "stdafx.h" #define MAX_SIZE 13 int cmp_array(void *a, void *b) { if(*(int *)a > *(int *)b) return -1; if(*(int *)a == *(int *)b) return 0; else return 1; } typedef int (*callback_t)(void *, void *); void *insertion_sort(void *data[], int num, callback_t callback) { int i,j; void *tmp; for(i=1; i<num; i++){ tmp = data[i]; j = i - 1; while(j>=0 && callback(data[j], tmp)<0){ data[j+1] = data[j]; j--; } data[j+1] = tmp; } return data[num-1]; } int _tmain(int argc, _TCHAR* argv[]) { int number[MAX_SIZE] = {64,61,13,14,86,41,16,31,58,64,21,54,65}; int *pnumber[MAX_SIZE]; int i; for(i=0; i<MAX_SIZE; i++){ pnumber[i] = &number[i]; } int *psort = (int *)insertion_sort((void **)pnumber, MAX_SIZE, cmp_array); printf("max = %d\n",*psort); for(i=0; i<MAX_SIZE; i++){ printf("max = %d\n",*pnumber[i]); } return 0; }
书上写的是 “请仿照本节的例23.8自己实现C标准库的qsort(3)和bsearch(3)函数”。 标准库中的qsort可以对任何数据类型进行排序,这个难度真不是一般的高,我苦思一晚,得出的结论是只能利用指针对任何数据类型排序,和tangfei网友一样。 至于网络版的习题,则容易多了,K&R中是对char排序,很easy。不过楼上的实现似乎都忘了这是quicksort,快排啊! 建议新版中将习题改成网络版的样子,不然难度实在太大了。
我找到一种绝妙的方法来实现书上习题的要求,一会儿写下来!
#include <string.h> #include "qsort.h" void swap(void *vp1, void *vp2, size_t size) { char buffer[size]; memcpy(buffer, vp1, size); memcpy(vp1, vp2, size); memcpy(vp2, buffer, size); } void qsort(void *base, size_t nmemb, size_t size, compar_t compar) { char *_base = base; size_t i, j; for (i = 0; i < (nmemb - 1); i++) for (j = i + 1; j < nmemb; j++) if (compar(_base + size * i, _base + size * j) > 0) swap(_base + size * i, _base + size * j, size); } 快排先不管了,至少实现了标准库中函数接口的要求。
/* mqsort.c */ #include <string.h> #include "mqsort.h" void swap(void *vp1, void *vp2, size_t size) { char buffer[size]; memcpy(buffer, vp1, size); memcpy(vp1, vp2, size); memcpy(vp2, buffer, size); } size_t Partition(void *base, size_t start, size_t end, size_t size, compar_t compar) { void *_base = base; while (start < end) { while (start < end && compar(_base + (start-1) * size, _base + (end-1) * size) <= 0) end--; if (start != end) swap(_base + (start-1) * size, _base + (end-1) * size, size); while (start < end && compar(_base + (start-1) * size, _base + (end-1) * size) <= 0) start++; if (start != end) swap(_base + (start-1) * size, _base + (end-1) * size, size); } return start; } void quicksort(void *base, size_t start, size_t end, size_t size, compar_t compar) { size_t mid; if (start < end) { mid = Partition(base, start, end, size, compar); quicksort(base, start, mid - 1, size, compar); quicksort(base, mid + 1, end, size, compar); } }
/* mqsort.c */ #include <string.h> #include "mqsort.h" void swap(void *vp1, void *vp2, size_t size) { char buffer[size]; memcpy(buffer, vp1, size); memcpy(vp1, vp2, size); memcpy(vp2, buffer, size); } size_t Partition(void *base, size_t start, size_t end, size_t size, compar_t compar) { void *_base = base; while (start < end) { while (start < end && compar(_base + (start-1) * size, _base + (end-1) * size) <= 0) end--; if (start != end) swap(_base + (start-1) * size, _base + (end-1) * size, size); while (start < end && compar(_base + (start-1) * size, _base + (end-1) * size) <= 0) start++; if (start != end) swap(_base + (start-1) * size, _base + (end-1) * size, size); } return start; } void quicksort(void *base, size_t start, size_t end, size_t size, compar_t compar) { size_t mid; if (start < end) { mid = Partition(base, start, end, size, compar); quicksort(base, start, mid - 1, size, compar); quicksort(base, mid + 1, end, size, compar); } } void mqsort(void *base, size_t nmemb, size_t size, compar_t compar) { quicksort(base, 1, nmemb, size, compar); }
/* mbsearch.c */ #include <stddef.h> #include "mbsearch.h" void * mbsearch(const void *key, const void *base, size_t nmemb, size_t size, compar_t compar) { const char *_base = base; size_t start = 0, end = nmemb - 1; while (start <= end) { size_t mid = (start + end) / 2; if (compar(key, _base + size * mid) < 0) end = mid - 1; else if (compar(key, _base + size * mid) > 0) start = mid + 1; else return (void *)(_base + size * mid); } return NULL; }
如果您有建设性意见,哪怕只是纠正一个错别字,也请不吝赐教,您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见!