c语言实现一个简单的通用动态数组

背景

最近在看《系统程序员成长计划》，里面有个任务是实现一个动态数组，所以我用以前学过的知识实现了一个通用的动态数组，不过暂时只能存放int，char，double，字符串的还没实现。

设计与实现

一.动态数组结构：

struct _Darray
{
    void *a;
    int length;
    int size;
    diy_fun expand;
    diy_fun append;
    diy_fun at;
};

typedef struct _Darray * Darray;

里面有 6 个成员：

1.指针 a 指向动态分配的内存区域，类型为void *，以便存放不同的类型

2.length 存放 a 指向的内存区域的长度

3.size 存放元素的个数

4,5,6都是函数指针，分别用于存放该类型的扩展内存， 添加元素，访问某元素的函数

函数指针diy_fun类型的原型：

typedef void* (*diy_fun) (Darray da, void *x);

二.函数

要使用此动态数组，要有初始化，添加元素，释放数组这3个基本的过程。

为了实现通用类型，初始化我使用了带参数的宏：

#define DARRAY_INIT(TYPE, DA) 
{
    DA = malloc (sizeof (*DA));
    DA->size = 0;
    DA->length = 0;
    DA->expand = D_EXPAND(TYPE);
    DA->append = D_APPEND(TYPE);
    DA->at = D_AT(TYPE);
    DA->a = NULL;
    DA->expand (DA, NULL);
}

参数 TYPE 就是要存放的类型，DA是 Darray 类型的变量。D_EXPAND(TYPE)，D_AAPEND(TYPE)，D_AT(TYPE)，又是 3 个宏，展开了就是对应类型的扩展内存， 添加元素，访问某元素的函数名。他们的实现是

#define D_EXPAND(TYPE) TYPE##_expand
#define D_APPEND(TYPE) TYPE##_append
#define D_AT(TYPE)     TYPE##_at

其中一个为例，D_EXPAND(int) 展开就是int_expend，然后 void *int_expand (Darray da, void *x) 已经在别处定义好了。

回到DARRAY_INIT，这样子只要输入类型和 DA，就可以得到某特定类型的动态数组，其扩展内存， 添加元素，访问某元素的函数也匹配好了

添加元素

添加元素的思路是当已有的元素个数大于数组长度时，先扩展内存，再往所需的位置添加元素。否则直接再往所需的位置添加元素。参数x是要添加的元素的指针

Darray darray_append (Darray da, void *x)
{
    if (da->size + 1 > da->length)
    {
        da->expand (da, NULL);
    }
    da->append (da, x);
    da->size++;
    return da;
}

释放数组

void darray_free (Darray da)
{
    free (da->a);
    free (da);
}

这个很简单

扩展内存， 添加元素，访问某元素

重点是这 3 个函数怎么根据类型来实现。在这里我又使用了带参数的宏

#define _D_EXPAND(TYPE) 
void* TYPE##_expand (Darray da, void *x)
{
    TYPE *array;
   array = realloc ((TYPE *)da->a, sizeof (TYPE) * (da->length + BUFFSIZE));
    da->a = (TYPE *)array;  <span style="font-family: Arial, Helvetica, sans-serif;">//貌似不必加上(TYPE *)</span>
    da->length += BUFFSIZE;
}

#define _D_APPEND(TYPE) 
void* TYPE##_append (Darray da, void *x)
{
    *(((TYPE *)da->a) + da->size) = *((TYPE *)x);
    return ((TYPE *)da->a) + da->size;
}

#define _D_AT(TYPE) 
void* TYPE##_at (Darray da, void *x)
{
    return (void *)(((TYPE *)da->a) + *(int *)x);
}

这几个 _D_XXX(TYPE) 是用来定义函数的，为了避免类型的冲突必须做很多强制类型转换。 

以 TYPE 为 int 做例子：

 _D_EXPAND(int) 展开就是 

void* int_expand (Darray da, void *x)
{
    int *array;
   array = realloc ((int *)da->a, sizeof (int) * (da->length + BUFFSIZE));
    da->a = (int *)array; 
    da->length += BUFFSIZE;
}

这样就清晰很多了，用realloc分配一块更大的内存，然后da->a指向这块内存，并更新length。关于realloc，要注意两点：

1.当第一个参数为 NULL 时，等同于使用malloc，所以在初始化动态数组时设置da->a为NULL

2.realloc会自动释放旧的那块内存，所以不用自己free(da->a)

_D_APPEND(int) 展开就是

void* int_append (Darray da, void *x)
{
    *(((int *)da->a) + da->size) = *((int *)x);
    return ((int *)da->a) + da->size;
}

对于*((int *)x)，因为参数x的类型是void *，想将它指向的内容取出来必须先强制转换为int *再取

对于*(((int *)da->a) + da->size)，道理也一样da->a类型是void *，所以也必须强制转换

_D_AT(TYPE) 展开就是

void* int_at (Darray da, void *x)
{
    return (void *)(((int *)da->a) + *(int *)x);
}

道理和上面的差不多，不过返回的是该元素的指针

为了避免写重复的代码，所以我又定义了两个宏

#define D_type(TYPE) _D_EXPAND(TYPE)
                     _D_APPEND(TYPE)
                     _D_AT(TYPE)

#define D_T(TYPE) 
void* D_EXPAND(TYPE) (Darray da, void *x);
void* D_APPEND(TYPE) (Darray da, void *x);
void* D_AT(TYPE) (Darray da, void *x)

这样子，只要在.c文件中使用D_type(xxx)，就可以展开所有函数的定义，在.h文件中使用D_T(xxx)，就可以展开所有函数的声明

如何使用

int main ()
{
    int i;
    int n;
    int r;
    Darray d;
    DARRAY_INIT(int, d);
    while ((r = scanf("%d", &n)) != EOF)
    {
        if (r == 0) 
        {
            printf ("worry type! type again!
");
            d->size--;
            while (r = getchar() != "
" && r != EOF);
            continue;
        }
        darray_append (d, (void *)&n);
    }
    for (i = 0; i != d->size; i++)
    {
        printf ("%d ", *(int *)d->at(d, &i));   
    }
    printf ("
");
    darray_free (d);
    return 0;
}

此动态数组使用方法大致如此，根据你使用的类型做好类型转换即可。不过对元素的输入必须说明一下

    while ((r = scanf("%d", &n)) != EOF)
    {
        if (r == 0) 
        {
            printf ("worry type! type again!
");
            d->size--;
            while (r = getchar() != "
" && r != EOF);
            continue;
        }
        darray_append (d, (void *)&n);
    }

首先，函数scanf是有返回值的，正常是返回读取的元素的个数，在linux里按下Ctrl-D就终止输入，返回EOF。但是如果输入了不匹配的类型，比如在这里输入了3.14，scanf会都到3，然后不清空缓存，下一次调用scanf就返回0，但是错误的东西还在缓存里面，所以此时输入已经没有用，只要缓存没被清空，scanf会一直返回0，程序就死循环了。

这里使用了while (r = getchar() != " " && r != EOF)来清空缓存，网上流传的fflush(stdin)在linux下貌似没用。d->size--是为了让用户覆盖掉类型不匹配的输入。

对于char类型，因为scanf会连‘ ’一起读入，导致数组中每个元素后面多了10这个换行键。所以可以：

/*.......*/
char c;
/*.......*/
while (scanf("%c%c", &n, &c) != EOF)
{
/*.......*/
}
/*.......*/

这样来吃掉换行键

小结

1.《系统程序员成长计划》中反复强调不要写重复的代码，我觉得是非常有道理的。我也尝试过复制粘贴正确代码，然后根据功能的不同小部分修改，可是最后反而产生更多错误，或者引入更多元素，提高了代码的耦合度。所以统一的接口和实现变得非常重要

2.这次我练习了宏的使用。当阅读高手的代码时总能发现高手们对宏真是爱不释手，宏用得好是神兵利器，可是同时宏也很难调试，必须非常谨慎地使用

3.这个动态数组的实现还是非常简陋，希望以后能改进代码，更优雅地实现这个设计

下面附上完整的代码，在Ubuntu上用gcc编译通过

darray.h

#ifndef DARRAY_H
#define DARRAY_H

#define BUFFSIZE 2

#define DARRAY_INIT(TYPE, DA) 
{
    DA = malloc (sizeof (*DA));
    DA->size = 0;
    DA->length = 0;
    DA->expand = D_EXPAND(TYPE);
    DA->append = D_APPEND(TYPE);
    DA->at = D_AT(TYPE);
    DA->a = NULL;
    DA->expand (DA, NULL);
}

#define _D_EXPAND(TYPE) 
void* TYPE##_expand (Darray da, void *x)
{
    TYPE *array;
   array = realloc ((TYPE *)da->a, sizeof (TYPE) * (da->length + BUFFSIZE));
    da->a = (TYPE *)array;
    da->length += BUFFSIZE;
}

#define _D_APPEND(TYPE) 
void* TYPE##_append (Darray da, void *x)
{
    *(((TYPE *)da->a) + da->size) = *((TYPE *)x);
    return ((TYPE *)da->a) + da->size;
}

#define _D_AT(TYPE) 
void* TYPE##_at (Darray da, void *x)
{
    return (void *)(((TYPE *)da->a) + *(int *)x);
}

#define D_type(TYPE) _D_EXPAND(TYPE)
                     _D_APPEND(TYPE)
                     _D_AT(TYPE)

#define D_EXPAND(TYPE) TYPE##_expand
#define D_APPEND(TYPE) TYPE##_append
#define D_AT(TYPE)     TYPE##_at

#define D_T(TYPE) 
void* D_EXPAND(TYPE) (Darray da, void *x);
void* D_APPEND(TYPE) (Darray da, void *x);
void* D_AT(TYPE) (Darray da, void *x)

struct _Darray;
typedef struct _Darray * Darray;
typedef void* (*diy_fun) (Darray da, void *x);

struct _Darray
{
    void *a;
    int length;
    int size;
    diy_fun expand;
    diy_fun append;
    diy_fun at;
};


Darray darray_append (Darray da, void *x);
void darray_free (Darray a);
D_T(char);
D_T(int);
D_T(double);

#endif

darray.c

#include <stdio.h>
#include <stdlib.h>
#include "darray.h"

Darray darray_append (Darray da, void *x)
{
    if (da->size + 1 > da->length)
    {
        da->expand (da, NULL);
    }
    da->append (da, x);
    da->size++;
    return da;
}

void darray_free (Darray da)
{
    free (da->a);
    free (da);
}

D_type(char);
D_type(int);
D_type(double);

da.c

#include "darray.h"
#include <stdio.h>
#include <stdlib.h>

int main ()
{
    int i;
    int n;
    int r;
    Darray d;
    DARRAY_INIT(int, d);
    while ((r = scanf("%d", &n)) != EOF)
    {
        if (r == 0) 
        {
            printf ("worry type! type again!
");
            d->size--;
            while (r = getchar() != "
" && r != EOF);
            continue;
        }
        darray_append (d, (void *)&n);
    }
    for (i = 0; i != d->size; i++)
    {
        printf ("%d ", *(int *)d->at(d, &i));   
    }
    printf ("
");
    darray_free (d);
    return 0;
}