C语言学习：算法实现层面套数

915 0 0

作者:大天使维迦

前言：一个普通的插入排序.

//// 插入排序默认从大到小//externvoidsort_insert_int(inta[],int len) {

int i, j;

for(i =1; i < len; ++i) {

intkey = a[j = i];

// 从小到大while(j >0&& a[j -1] < key) {

a[j] = a[j -1];

--j;

}

a[j] = key;

}

}

这时候有人就想了, 那数组是 double 的, 那怎么弄了. 也有一种解决方案

#definesort_insert(a, len) _Generic(a

, int* : sort_insert_int

, double* : sort_insert_double

, default: sort_insert_default) (a, len)

是不是有所启发. 当然了. 对于上面是使用从大到小封装. 那如果需要从小到大呢. 可以这么做

staticinlineint_compare_2(constintleft,constint key) {

returnleft - key;

} externvoidsort_insert_2(inta[],int len,

intcompare(constintleft,constint key)) {

int i, j;

for(i =1; i < len; ++i) {

intkey = a[j = i];

while(j >0&& compare(a[j -1], key) <0) {

a[j] = a[j -1];

--j;

}

a[j] = key;

}

}

单独把比较的行为抽象出来, 注册进去. 是不是很开心.

细致一点封装

　　也许到这里会更开心. 既然能通过高科技泛型模拟出来. 那我们不也可以使用旧科技弄弄.

typedefint(* compare_f)(constvoid* left,constvoid* key);staticinlineint_compare_3(constvoid* left,constvoid* key) {

return*(int*)left - *(int*)key;

}externvoidsort_insert_3_(void* data, size_t ez,int len, compare_f compare) {

char* a = data;

void* key;

int i, j;

if((key =malloc(ez)) == NULL)

return;

for(i =1; i < len; ++i) {

memcpy(key, &a[i * ez], ez);

for(j = i; j >0&& compare(&a[(j -1) * ez], key) <0; --j)

memcpy(&a[j * ez], &a[(j -1) * ez], ez);

if(j != i)

memcpy(&a[j * ez], key, ez);

}

free(key);

}#definesort_insert_3(a, len, compare) sort_insert_3_(a, sizeof(*(a)), len, (compare_f)compare)

是不是很巧妙, 一切都编程 void * 了. 当然了如果使用 C99 版本以上, 或者说用高版本的 GCC.

可以写的更好.

externvoidsort_insert_4_(void* data, size_t ez,int len, compare_f compare) {

char* a = data;

char key[ez];

int i, j;

for(i =1; i < len; ++i) {

memcpy(key, &a[i * ez], ez);

for(j = i; j >0&& compare(&a[(j -1) * ez], key) <0; --j)

memcpy(&a[j * ez], &a[(j -1) * ez], ez);

if(j != i)

memcpy(&a[j * ez], key, ez);

}

}

这里用了 C99 的 VLA 特性. 不知道细心的同学是否和思考. GCC 是怎么实现 VLA 可变长数组呢.

拨开云雾见青天, 我们不妨来个实验验证一哈. 看下面测试代码

#include #include /* * file : vla.c

* make : gcc -g -Wall -O2 -o vla.exe vla.c

*

*/intmain(intargc,char* argv[]) {

chara[10];

intb =7;

char c[b];

int* d =malloc(sizeof(int));

if(d == NULL)

exit(EXIT_FAILURE);

*d =1000;

chare[*d];

printf("%p : char a[10]n", a);

printf("%p : int bn", &b);

printf("%p : char c[b]n", c);

printf("%p : int * dn", d);

printf("%p : char e[*d]n", e);

free(d);

return EXIT_SUCCESS;

}

最终输出结果是

通过地址匹配对于 vla 可变数组, GCC是放在栈上的. 所有可以预测, 当可变数组大小太大. 函数栈会直接崩溃.

如果你有想法, 那么就去实现它, 多数简单我们还是能独立捉出来滴~~

通用套路

　　还有一种套路, 采用宏模板去实现, 简单提一下这个思路. 看下面代码

#ifdefined(__T)#define__f(type) sort_insert_##type#define__F(type) __f(type)staticvoid__F(__T) (__T a[],intlen,intcompare(const__T left,const __T key)) {

int i, j;

for(i =1; i < (int)len; ++i) {

__T key = a[j = i];

while(j >0&& compare(a[j -1], key) <0) {

a[j] = a[j -1];

--j;

}

a[j] = key;

}

}#endif

一般而言上面模板函数都会封装在一个局部文件中使用的时候也很方便, 例如下面这样

// 定义部分, 声明和定义分离可以自己搞#undef__T#define__T int#include "sort_insert.c"// 使用部分和普通函数无异sort_insert_int(a, LEN(a), _compare_2);

当然除了上面一种基于文件的函数模板. 还用一种纯基于函数宏的函数模板实现.

#definesort_insert_definition(T) staticvoidsort_insert_##T (T a[],intlen,intcompare(constT left,const T key)) {

int i, j;

for(i =1; i < len; ++i) {

T key = a[j = i];

while(j >0&& compare(a[j -1], key) <0) {

a[j] = a[j -1];

--j;

}

a[j] = key;

}

}

sort_insert_definition(int)