简述C语言动态数组的构成

数组的优点在于随机存取，然而其的缺点也是十分明显的 ，就是一旦建立其大小就不能够改变。若用数组存储数据，则需创建一个可能存放最大空间的数组，这无疑是浪费空间。动态数组就很好的解决了这个问题。动态数组的思维思路是：先建立一定大小的数组，向这个数组存放数据，如果数组已满，则重新申请一个更大的空间来存放。每次重新申请时可以指定增量的大小(一般为原来数据的1.5倍)，也可以固定大小。这样做的好处是空间浪费不多，其不足是重新申请空间浪费时间，每次重新申请空间时须将原来的数据拷贝到新申请的空间，当数组很大时，这种浪费还是相当可观的。

接下来是对动态数组实现的说明：
先建立动态数组的存储结构：

typedef struct _DArray
{
    int size;
    int count;
    void **data;
}DArray;

接下来定义一个enum来存放程序中函数的返回值，可以不定义：

typedef enum _Ret
{
    RET_OK = 1,
    RET_FAIL,
    RET_OOM    
}Ret;

为了使程序更具通用性可以定义一个回调函数原型，用于回调

typedef void (*VisitFunc)(void *ctx, void *data);

定义一个用于测试的宏

#define return_val_if_fail(p, val)/
if(!(p)){printf("%s:%d"#p" failed./n",__func__,__LINE__); return val;}

下面定义数组的基本操作，包括：

DArray *darray_create();
static Ret darray_expand(DArray *darray, int needone);
Ret darray_preapppend(DArray *darray, void * data);
Ret darray_append(DArray *darray, void * data);
Ret darray_insert(DArray *darray, int index, void * data);
Ret darray_delete(DArray *darray, int index);
Ret darray_shrink(DArray *darray);
int darray_len(DArray * darray);
Ret darray_set_by_index(DArray *darray, int index, void *data);
Ret darray_foreach(DArray *darray, VisitFunc visitfunc, void *ctx);
Ret darray_destroy(DArray *darray);

头文件基本定义结束，保存为darray.h
为了优化一般会在头文件中定义选择编译的宏

#ifndef DARRAY_H
#define DARRAY_H
。。。
。。。
#endif /*DARRAY_H*/

避免重复编译

完整头文件如下(darray.h)：

#ifndef DARRAY_H
#define DARRAY_H
#define DEFAULT_A_SIZE 10

/*

• File: darray.h：动态数组函数实现
• /

typedef struct _DArray
{
    int size;
    int count;
    void **data;

}DArray;

typedef enum _Ret
{
    RET_OK = 1,
    RET_FAIL,
    RET_OOM    
}Ret;

typedef void (*VisitFunc)(void *ctx, void *data);

#define return_val_if_fail(p, val)/
    if(!(p)){printf("%s:%d"#p" failed./n",__func__,__LINE__); return val;}

DArray *darray_create();
static Ret darray_expand(DArray *darray, int needone);
Ret darray_preapppend(DArray *darray, void * data);
Ret darray_append(DArray *darray, void * data);
Ret darray_insert(DArray *darray, int index, void * data);
Ret darray_delete(DArray *darray, int index);
Ret darray_shrink(DArray *darray);    
int darray_len(DArray * darray);
Ret darray_set_by_index(DArray *darray, int index, void *data);
Ret darray_foreach(DArray *darray, VisitFunc visitfunc, void *ctx);
Ret darray_destroy(DArray *darray);

#endif /*DARRAY_H*/

以下是函数实现部分（darray.c）：

#include "darray.h"
#include <malloc.h>

/*

• File: darray.c：动态数组函数实现

• /

  /*
  *功能：实现一个DArray结构体的初始化
  *参数：void
  *返回：DArray结构体
  */

DArray *darray_create()
{        
    int i = 0;
    DArray *darray = (DArray *)malloc(sizeof(DArray));
    if(darray != NULL)
    {
        darray->count = 0;
        darray->size = 0;
        darray->data = (void **)malloc(sizeof(void *) * DEFAULT_A_SIZE);

        if(darray->data !=NULL)
        {
            darray->size = DEFAULT_A_SIZE;
            for(i = 0; i <darray->size;i++ )
            {
                darray->data[i] = NULL;
            }
        }        
        return darray;
    }

    return NULL;
}
/*
*功能：添加（尾）元素
*参数：darray:指定数组  data：插入的数据的指针
*返回：Ret 
*/


Ret darray_append(DArray *darray,void * data)
{
    return_val_if_fail(darray != NULL && data != NULL, RET_FAIL);

    if(darray ==NULL || data == NULL)    
    {
        return RET_FAIL;
    }

    if((darray->count + 1 ) >= darray->size)
    {    
        darray_expand(darray, 2);

    }

    darray->data[darray->count] = data;

    darray->count++;

    return RET_OK;

}

/*
*功能：替换数组指定位置的值
*参数：参数：darray:指定数组 index：插入位置 data：插入的数据的指针
*/

Ret darray_set_by_index(DArray *darray, int index, void *data)
{
    return_val_if_fail(darray != NULL && data != NULL, RET_FAIL);

    if(darray ==NULL || data == NULL)
    {
        return RET_FAIL;
    }
    if(index <0 || index >= darray->count)
    {    
        return RET_FAIL;
    }

    darray->data[index] = data;
    return RET_OK;

}

/*
*功能：增加指定数组的容量
*声明：有可能引起新内存申请，内存拷贝，从而改变指针具体指向
*参数：darray:要操作的数组指针地址 needone:要增加的数量(这里用于选择)
*/

static Ret darray_expand(DArray *darray, int needone)
{
    int newallocsize = 0;

    if(needone == 2)
    {
         newallocsize = darray->count + (darray->count>>1)+DEFAULT_A_SIZE;
    }
    else
    {
        newallocsize = darray->count + 1;
    }
    void **data = (void **)realloc(darray->data, sizeof(void *) *     newallocsize);
    if(data != NULL)
    {
        darray->data = data;
        darray->size = newallocsize;

    }
    return RET_OK;

}

/*
*功能：缩减指定数组的容量
*声明：有可能引起新内存申请，内存拷贝，从而改变指针具体指向
*参数：darray:要操作的数组指针地址 （视情况缩减为原来的1.5倍，这样不会不用每次都执行内存分配）
*/

Ret darray_shrink(DArray *darray)
{
    if((darray->count >> 1) < darray->size && (darray->size > DEFAULT_A_SIZE))
    {
        int newallocsize = darray->count +darray->count>>1;
        void **data = (void **)realloc(darray->data, sizeof(void *) * newallocsize);
        if(data != NULL)
        {
            darray->data = data;
            darray->size = newallocsize;

        }

    return RET_OK;    
    }
}

/*
*功能：删除元素
*参数：darray:指定数组 index：数据的位置
*返回：Ret
*/

Ret darray_delete(DArray *darray, int index)
{
    int i = 0;

    for(i = index; (i+1) < darray->count; i++)
    {
        darray->data[i] = darray->data[i + 1];        
    }

    darray->count--;

    darray_shrink(darray);

    return RET_OK;
}

/*
*功能：添加（头）元素
*参数：darray:指定数组 data：插入的数据的指针
*返回：Ret
*/

Ret darray_preappend(DArray *darray, void * data)
{
    return_val_if_fail(darray != NULL && data != NULL, RET_FAIL);

    if(darray ==NULL || data == NULL)
    {
        return RET_FAIL;
    }

    if(darray->count + 1 > darray->size)
    {
        darray_expand(darray, 2);
    }
    int i = 0;
    for(i = darray->count; i >  0; )
    {
        darray->data[i] = darray->data[i - 1];
        i--;
    }
    darray->data[0] = data;
    darray->count++;

    return RET_OK;
}

/*
*功能：插入元素
*参数：darray:指定数组 index：插入位置 data：插入的数据的指针
*返回：Ret
*/

Ret darray_insert(DArray *darray, int index, void * data)
{
    return_val_if_fail(darray != NULL && data != NULL, RET_FAIL);

    if(darray ==NULL || data == NULL)
    {
        return RET_FAIL;
    }

    if(darray->count + 1 > darray->size)
    {
        darray_expand(darray, 1);
    }
    int i = 0;
    for(i = darray->count; i >  index; )
    {
        darray->data[i] = darray->data[i - 1];
        i--;
    }
    darray->data[index] = data;
    darray->count++;

    return RET_OK;
}

/*
*功能：遍历数组
*参数：darray:指定数组 visitfunc：回调函数 ctx：上下文
*返回：Ret
*/

Ret darray_foreach(DArray *darray, VisitFunc visitfunc, void *ctx)
{
    int index = 0;

    while(index < darray->count)
    {
        visitfunc(ctx, darray->data[index]);
        index ++;    
    }

    return RET_OK;
}

/*
*功能：数组长度
*参数：darray:指定数组
*返回：数组大小
*/

int darray_len(DArray * darray)
{
    return darray->count;
}

/*
*功能：释放指定数组内存
*参数：darray:指定数组
*返回：Ret
*/

Ret darray_destroy(DArray *darray)
{
    if(darray == NULL)
    {
        return RET_OK;
    }

    free(darray->data);    
    darray->data = NULL;

    free(darray);
    darray = NULL;
    return RET_OK;
}
（darraytest.c）

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

/*

• File: darraytest.c：动态数组函数实现
• /
  /*
• 功能：测试的打印函数，用于回调
• /

void print_int(void *ctx, void *data)
{
    printf(".........%d/n",*(int *)data);
}

int main(int argc, char *argv[])
{

    int i = 0;
    int a = 8;
    int b = 9999;
    int c = 555;
    int u = 7777;

/* int i = 0;
char *a =”aaaaa”;
char *b = “bbbbbbbbb”;
char *c = “ccccccc”;
char *u = “uuuuuuuuuuuu”;
*/

    DArray *darray = darray_create();

    for(i  = 0;i <23; )
    {
        darray_append(darray, &a);
        i++;
    }

    darray_insert(darray, 3, &b);    
    darray_set_by_index(darray, 20, &u);

    for(i = 0; i < 16; i++)
    {
        darray_delete(darray, 0);
    }

    darray_preappend(darray, &b);
    int j = 0;
    for(j = 0;j < darray->count; )
    {    
        printf("%d/n",*(int*)darray->data[j]);
        j++;
    }


    darray_append(darray,&b);
    darray_append(darray,&b);
    darray_append(darray,&b);
    printf("%d/n",darray->size);
    darray_foreach(darray, print_int, NULL);
    darray_destroy(darray);
}

---

转载请注明出处@Berome