C基础 算法实现规模套路

引言 – 从执行狗语起

  理论及实践(有了算法到实现) 中间产生众多了程. 算法方面自身啥吧无知晓,
只能说说实现者. 例如下面

一个通常的插入排序.

//
// 插入排序默认从大到小
//
extern void sort_insert_int(int a[], int len) {
    int i, j;
    for (i = 1; i < len; ++i) {
        int key = a[j = i];
        // 从小到大
        while (j > 0 && a[j - 1] < key) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}

 

这有人便想了, 那数组是 double 的, 那怎么弄了. 也生同等栽缓解方案

#define sort_insert(a, len) \
    _Generic(a
            , int *     : sort_insert_int
            , double *  : sort_insert_double
            , default   : sort_insert_default) (a, len)

 

凡免是独具启发. 当然了. 对于地方是采用于杀及小封装.
那要是急需从小到大呢. 可以这样做

static inline int _compare_2(const int left, const int key) {
    return left - key;
} 

extern void sort_insert_2(int a[], int len,
    int compare(const int left, const int key)) {
    int i, j;
    for (i = 1; i < len; ++i) {
        int key = a[j = i];
        while (j > 0 && compare(a[j - 1], key) < 0) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}

独自把比较的行抽象出, 注册进去. 是休是那个开心.

 

前言 – 细致一点装进

  也许到这里见面还起心. 既然能由此高科技泛型模拟出来.
那我们不也得使初科技为弄.

typedef int (* compare_f)(const void * left, const void * key);

static inline int _compare_3(const void * left, const void * key) {
    return *(int *)left - *(int *)key;
}

extern void sort_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);
}

#define sort_insert_3(a, len, compare) \
    sort_insert_3_(a, sizeof(*(a)), len, (compare_f)compare)

举凡休是好巧妙, 一切都编程 void * 了.  当然了若下 C99 版本以上,
或者说用大版本的 GCC.

足描绘的又好.

extern void sort_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 <stdio.h>
#include <stdlib.h>

/*
 * file : vla.c
 * make : gcc -g -Wall -O2 -o vla.exe vla.c
 * 
 */
int main(int argc, char * argv[]) {
    char a[10];
    int b = 7;
    char c[b];
    int * d = malloc(sizeof(int));
    if (d == NULL)
        exit(EXIT_FAILURE);
    *d = 1000;
    char e[*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;
}

末段输出结果是

图片 1

由此地方匹配对于 vla 可变数组, GCC是在栈上的. 所有可以预计,
当可变数组大小太大. 函数栈会直接崩溃.

假定您有想法, 那么即使错过实现它, 多数大概我们还是能独立捉出来滴~~

 

刚好文 – 通用套路

  还有一样种套路, 采用宏模板去贯彻, 简单提一下此思路. 看下代码

#if defined(__T)

#define __f(type) sort_insert_##type
#define __F(type) __f(type)

static void __F(__T) (__T a[], int len, int compare(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);

 

自然除了上面一样种植基于文件之函数模板. 还用同样种纯基于函数宏的函数模板实现.

#define sort_insert_definition(T) \
    static void sort_insert_##T (T a[], int len, int compare(const T 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 封装中一个略函数存在的套路.

 

后记 – 路越来越小, 越来越清晰

      错误是足以改之, 欢迎指正 ~ 表示感谢哈哈

     
<<啥时成为津门首先呀>>
: http://music.163.com/\#/mv?id=197148

      图片 2

      对不起 ~ 什么都了解的好晚 ~

发表评论

电子邮件地址不会被公开。 必填项已用*标注