3.数据结构之通用编程思想的引入

爱被打了一巴掌 2022-08-09 11:46 41阅读 0赞

# 数据结构之通用编程思想的引入 #

## 引言 ##

首先我们以一个简单的例子引入今天所要讨论的问题，交换两个整形变量的方法是我们常见的问题。比如如下的代码：

void swap(int *a, int *b);
    
    void swap(int *a, int *b)
    {
        //采用中间变量int temp进行交换
        int temp = *a  ;
        *a       = *b  ;
        *b       = temp;
    }
    
    int main(int argc, char **argv)
    {
         int a = 10;
         int b = 20;
    
         printf("before swap:a = %d, b = %d\n", a, b);
         swap(&a, &b);    //交换两个整形变量
         printf("before swap:a = %d, b = %d\n", a, b);
         return 0;
    }

上述的代码虽然可以实现交换两个整型变量，但是有着很大的弊端，因为交换的类型只能被限定在了整型变量，如果我们要交换float类型的变量或者或结构体类型。则需要对交换函数进行重复的书写,如下所示：

//swap函数除了类型由int类型转换为了float类型，其他的操作在原理上是没有任何区别的
    void swap(float *a, float *b);
    
    void swap(float *a, float *b)
    {
        float temp = *a;
        *a = *b;
        *b = temp;
    }

这样一个方式就会造成代码的不断重复编写，其实我们想要做的事情非常的直接，就是为了实现两个变量的交换，而不想关心其类型如何。那就需要我们做一个整体的抽象，把数据类型和算法描述分离开，这样的思想和C++的模板编程非常类似，如果采用C++的模板方式实现任意类型的两个变量的交换，具体实现如下：

templete <class T>
    void swap(T &a, T &b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

很遗憾的是，C语言并不支持模板编程（由其语法约束），但是并不妨碍我们对于泛型编程的思考。如果要使用C语言实现泛型编程的话，需要借助void *指针，从c语言的语法角度出发，void* 指针类型可以接受其他任意类型的指针。所以我们依然可以吧int *，float* 等指针作为参数进行传递，但是在swap函数的声明中使用void *类型，并且因为void* 指针并不能清楚的描述出所指向类型的大内存大小，所以我们需要传递第三个参数length去限定void \*所要交换的内存的大小（不同的数据类型传入的大小是不同的）。

具体的代码实现如下所示：

void swap(void *a, void *b, int elem_len)
    {
        void *temp = malloc(elem_len);
        if(temp == NULL){
            fprintf(stderr, "the memory is full!\n");
            exit(1);
        }
        memcpy(temp, a, elem_len);
        memcpy(a, b, elem_len);
        memcpy(b, temp, elem_len);
    
        free(temp);
        temp = NULL;
    }

这样就可以实现任意类型两个变量的交换了，再以不同类型数组元素的遍历为例，此处引入了foreach函数以及sort函数，查看他们的通用实现方法，完整代码如下图所示：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #if 1
    typedef unsigned char Boolean;
    
    typedef void (*Pfunc_print)(void *, int );
    typedef Boolean (*Comp)(void *, void *);
    
    void sort_array(int *array, int length);
    static void swap1(int *a, int *b);
    void print_array(int *array, int length);
    void swap(void *a, void *b, int elem_len);
    void foreach(void *array, int length, Print_func print);
    // print = print_int;
    
    
    void print_int(void *array, int index);
    
    void print_int(void *array, int index)
    {
        printf("%d ", *((int *)array + index));
    }
    
    void print_float(void *array, int index);
    
    void print_float(void *array, int index)
    {
        printf("%f ", *((float *)array + index));
    }
    
    void foreach(void *array, int length, Print_func print)
    {
        int i = 0; 
    
        if(array == NULL || length <= 0 || print == NULL){
            return ;
        }
    
        for(i = 0; i < length; ++i){
            print(array, i);
            //print = print_int
            //print_int(array, i);
        }
        printf("\n");
    }
    
    void swap(void *a, void *b, int elem_len)
    {
        void *temp = malloc(elem_len);
        if(temp == NULL){
            fprintf(stderr, "the memory is full!\n");
            exit(1);
        }
        memcpy(temp, a, elem_len);
        memcpy(a, b, elem_len);
        memcpy(b, temp, elem_len);
    
        free(temp);
        temp = NULL;
    }
    
    static void swap1(int *a, int *b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    void print_array(int *array, int length)
    {
        int i = 0;
    
        if(array != NULL && length > 0){
            for(i = 0; i < length; ++i){
                printf("%d ", array[i]);
            }
            printf("\n");
        }
    }
    
    void sort_array(int *array, int length)
    {
        int i = 0;
        int j = 0;
    
        if(array == NULL || length <= 0){
            return ;
        }
    
        for(i = 0; i < length - 1; ++i){
            for(j = i + 1; j < length; ++j){ 
                if(array[i] > array[j]){
                    swap(&array[i], &array[j], sizeof(array[i]));
                }
            }
        }
    }
    
    Boolean compare_int(void *a, void *b);
    
    
    //整型类型元素的比较函数
    Boolean compare_int(void *a, void *b)
    {
        return *(int *)a > *(int *)b;
    }
    
    void sort(void *array, int length, int elem_len, Comp compare);
    //对任意类型数组的排序
    void sort(void *array, int length, int elem_len, Comp compare)
    {
        int i = 0;
        int j = 0;
    
        if(array == NULL || length <= 0 || elem_len <= 0){
            return ;
        }
    
        for(i = 0; i < length - 1; ++i){
            for(j = i + 1; j < length; ++j){
               // if(array[i] > array[j]){ 
               // swap(&array[i], &array[j], elem_len);
               // }
               if(compare(((char *)array + i * elem_len),
                          ((char *)array + j * elem_len))){
                   swap((char *)array + i * elem_len,
                        (char *)array + j * elem_len,
                        elem_len);
               }
            }
        }
    }
    
    //测试代码
    int main(int argc, char **argv)
    {
        int array[] = {
       12, 2, 34, 31, 1, 67, 15 ,89, 6};
        int length = sizeof(array) / sizeof(array[0]);
        float array1[] = {
       12.3, 1.2, 0.4, 11.3, 111.44, 24.5};
        int length1 = sizeof(array1) / sizeof(array1[0]);
    
    
        foreach(array1, length1, print_float);
        foreach(array, length, print_int);
       // print_array(array, length);
       // sort_array(array, length);
        sort(array, length, sizeof(int), compare_int);
        foreach(array, length, print_int);
       // print_array(array, length);
    
        return 0;
    }
    #endif

--------------------

在介绍完泛型编程技巧的基本技术之后，在后续的数据结构的处理上我们都会实现通用数据结构，体现出C语言也能实现C++stl类似的功能。

敬请期待：

下章《数据结构之通用链表的实现》