经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
C语言学习:算法实现层面套数
来源:cnblogs  作者:大天使维迦  时间:2021/4/6 10:15:57  对本文有异议

 


 

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

//// 插入排序默认从大到小//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 b\n", &b);

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

    printf("%p : int * d\n", 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)

使用还是一样  sort_insert_int(a, LEN(a), _compare_2); 跑起来. 第一种函数模板, 在嵌入式用的多

第二种在实战中用的多, 对于处理各种算法相关的代码很普遍. 到这里应该可以理解上面那些

C 封装中一个小函数存在的套路


 

另外如果你想更好的提升你的编程能力,学好C语言C++编程!弯道超车,快人一步!笔者这里或许可以帮到你~

分享(源码、项目实战视频、项目笔记,基础入门教程)

欢迎转行和学习编程的伙伴,利用更多的资料学习成长比自己琢磨更快哦!

编程学习:


 

编程学习:


 

原文链接:http://www.cnblogs.com/zuishuaideou/p/14592296.html

 友情链接: NPS