可存舍弃意档次变量的动态数组–C语言实现

前在磨炼营的下被要求用C语言实现一个可存摒弃意档次数据的库房。现在尝试实现一个数组版本。

率先选择的结构体如下(接触了Win32编程所以长得有些像中的那个类型):

typedef struct {
    void *data;               //用于保存数据的数组
    size_t numOfElements;     //表示数组元素个数
    size_t sizeOfElements;    //表示数组元素的大小
    size_t capacity;          //表示数组实际能容纳的元素个数
} VECTOR, *LPVECTOR;

当这里存放数据用的是void *指南针,相较该余类型的指针,void *单单保留地址信息,不补助指针运算、解除引用、索引访问同自增减操作。任意档次的指针都得隐式转换成void *,而void *用强制转换成指定项目标指针才足以用其里面的数码。

由于void *免协助指针偏移操作,但是对于数组访问数,指针偏移又是必备的。大家得以以这一个更换为char *,这样我们虽然可针对该偏移任意字节以访任何岗位了。

((char *)lpVec->data) + 5;  //对data偏移5个字节

倘若假定取出数据,假定数据类型为double,这我们可如此:

((double *)lpVec->data)[3]; //访问第4个double

对于void *,除了最主旨的malloc()realloc()free()来治本内存外,大家还得如下mem体系函数:

void * memset(void *_Dst,int _Val,size_t _Size);
//将_Dst所指向的某一块内存中的前_Size个字节内容全部设定为_Val指定的ASCII值
void * memcpy(void * _Dst,const void * _Src,size_t _Size);
//将_Src所指向的某一块内存中的前_Size个字节内容拷贝到_Dst所指向内存的起始位置中
void * memmove(void *_Dst,const void *_Src,size_t _Size);
//将_Src所指向的某一块内存中的前_Size个字节内容搬移到_Dst所指向内存的起始位置中
//支持重叠内存区域的操作,而memcpy不行
int memcmp(const void *_Buf1,const void *_Buf2,size_t _Size);
//比较_Buf1和_Buf2所指向的前_Size个字节
//相等时返回0,前者较大时返回1,后者较大时返回-1
//这里面没有用到该函数

接下来是因素个数numOfElements同事实上容量capacity,在分配内存的当儿遵照其实容量来分配,而往往实际容量是比元素个数要稀的,这样在数组元素增长之上偏偏用修改数组末的骨子里地方使休待分配内存,仅当元素个数达到实际容量时才调整用相同涂鸦realloc()使得容量扩增为本的有数加倍。那样做得削减重复分配的次数,以及省多少迁移所花费的时光。

脚是意义函数的兑现(用法及C++里的Vector比较像)

/*
 * 用于创建一个VECTOR对象,可储存的元素个数为numOfElements
 * 且元素大小为sizeOfElements的数组
 */
LPVECTOR VectorCreate(size_t numOfElements, size_t sizeOfElements) {
    LPVECTOR lpVec = (LPVECTOR)malloc(sizeof(VECTOR));
    lpVec->numOfElements = numOfElements;
    lpVec->sizeOfElements = sizeOfElements;
    //若元素个数小于5,预分配5个元素大小的实际容量
    lpVec->capacity = numOfElements > 5 ? numOfElements : 5;  
    lpVec->data = malloc(lpVec->capacity * sizeOfElements);
    //所有成员初始化为0
    memset(lpVec->data, 0, lpVec->capacity * sizeOfElements);
    return lpVec;
}


/*
 * 用于重新分配内存,调整的是数组实际能容纳的元素个数。该函数只允
 * 许在对数组元素个数有修改,可能要超出或远低于实际容纳量的情况下
 * 才能调用它。不建议使用者直接调用该函数
 */
void VectorReallocate(LPVECTOR lpVec, size_t newCapacity) {
    void *vptr = realloc(lpVec->data, newCapacity * lpVec->sizeOfElements);
    if (vptr)
        lpVec->data = vptr;
    else
        return;
    lpVec->capacity = newCapacity;
    if (lpVec->numOfElements > lpVec->capacity)
        lpVec->numOfElements = lpVec->capacity;
}

//在数组现有元素的末端加入一个元素
void VectorPushBack(LPVECTOR lpVec, void *pVal) {
    //元素个数即将突破容量大小时,分配2倍大小的容量
    if (lpVec->numOfElements == lpVec->capacity)
        VectorReallocate(lpVec, 2 * lpVec->capacity);
    //将pVal所指向的数据复制到
    memcpy((char*)lpVec->data + lpVec->numOfElements++ * lpVec->sizeOfElements, pVal, lpVec->sizeOfElements);
}

//删去数组末端的元素
void VectorPopBack(LPVECTOR lpVec) {
    if (lpVec->numOfElements == 0)
        return;
    //元素个数即将达到实际容量的1/4以下时,将容量缩小为原来的1/2.
    if (lpVec->numOfElements == lpVec->capacity / 4 && lpVec->capacity > 5)
    {
        VectorReallocate(lpVec, lpVec->capacity / 2);
        lpVec->capacity /= 2;
    }
    //不需要删除数据,只需修改元素个数。
    lpVec->numOfElements--;
}

//将数组元素个数置0,但实际元素容量置为5
void VectorClear(LPVECTOR lpVec) {
    lpVec->numOfElements = 0;
    VectorReallocate(lpVec, 5);
}

//将元素val插入到数组的索引pos位置上
void VectorInsert(LPVECTOR lpVec, size_t pos, void* pVal) {
    if (pos > lpVec->numOfElements)
        return;
    else if (pos == lpVec->numOfElements)
        VectorPushBack(lpVec, pVal);  //此处可以直接使用前面的尾插函数
    else
    {
        if (lpVec->numOfElements == lpVec->capacity)
            VectorReallocate(lpVec, 2 * lpVec->capacity);
        //将插入点后面的数据全部向右偏移sizeofElements字节
        memmove((char*)lpVec->data + (pos + 1) * lpVec->sizeOfElements, (char*)lpVec->data + pos * lpVec->sizeOfElements, (lpVec->numOfElements++ - pos) * lpVec->sizeOfElements);
        //将插入元素复制到插入点上
        memcpy((char*)lpVec->data + pos * lpVec->sizeOfElements, pVal, lpVec->sizeOfElements);
    }
}

//将数组索引区间[beg,end)的元素删除
void VectorErase(LPVECTOR lpVec, size_t beg, size_t end) {
    if (beg > lpVec->numOfElements || end > lpVec->numOfElements || beg > end)
        return;
    //将删除区域末端后面的数据搬移至删除区域的起始位置
    memmove((char*)lpVec->data + beg * lpVec->sizeOfElements, (char*)lpVec->data + end * lpVec->sizeOfElements, (lpVec->numOfElements - end) * lpVec->sizeOfElements);
    //直接修改元素个数即可,被删除的元素是被直接覆盖掉
    lpVec->numOfElements -= end - beg;
}

//遍历所有元素
void VectorTraversal(LPVECTOR lpVec, void(*func)(void*)) {
    size_t i;
    for (i = 0; i < lpVec->numOfElements; ++i)
        func((char*)lpVec->data + i * lpVec->sizeOfElements);
}


//释放VECTOR内存,将指向的指针置为NULL
void VectorFree(LPVECTOR *ppVec) {
    free((*ppVec)->data);
    free(*ppVec);
    *ppVec = NULL;
}

万一我们需要输出里面的多少,可以写一个回调函数:

void PrintInt(void* pVal)
{
    printf("%d ", *(int *)pVal);
}

//...这样调用
VectorTraversal(lpVec, PrintInt);

末段是测试用之代码:

void PrintInt(void * lpVal)
{
    printf("%d ", *(int *)lpVal);
}

void PrintDouble(void * lpVal)
{
    printf("%.2f ",*(double *)lpVal);
}

int main()
{
    LPVECTOR lpVec;
    int i;
    double v;

    //测试开始 
    //使用int
    lpVec = VectorCreate(0, sizeof(int));
    for (i = 1;i <= 10;++i)
        VectorPushBack(lpVec, &i);
    VectorTraversal(lpVec, PrintInt);
    puts("");

    for (i = 0;i < 5;++i)
        VectorPopBack(lpVec);
    VectorTraversal(lpVec, PrintInt);
    puts("");

    VectorClear(lpVec);
    VectorTraversal(lpVec, PrintInt);
    puts("");

    VectorFree(&lpVec);
    if (lpVec)
        puts("-1");

    //使用double
    lpVec = VectorCreate(0, sizeof(double));
    v = 0.25;
    for (i = 0;i < 5;++i, v += 0.25)
        VectorPushBack(lpVec, &v);
    VectorTraversal(lpVec, PrintDouble);
    puts("");

    for (i = 0;i < 5;++i, v -= 0.25)
        VectorInsert(lpVec, 0, &v);
    VectorTraversal(lpVec, PrintDouble);
    puts("");

    VectorErase(lpVec, 7, 17);
    VectorTraversal(lpVec, PrintDouble);
    puts("");

    VectorFree(&lpVec);
    if (lpVec)
        puts("-1");

    return 0;
}