动态数组代码实现

一、动态数组

一般在静态数组定义后，系统就会为其分配对应长度的连续的专有内存空间，可是，我们都知道，不同的运行样例，所需要的数组长度是不一样的，为了所有样例都可以执行，一般我们会将数组长度设置为一个很大的值，比如：我一般都是借助宏定义直接声明1000，这个长度是可以满足我日常所需的。虽然这种方式，满足了一般运行的要求，但是它极大的浪费了内存。

于是我们引出了动态数组的概念，顾名思义，“动态”体现在数组长度可以由用户自己定义上。那么今天来总结一下，动态数组的两种实现方式。

二、单向链表设计思路

1、思路图

2、定义struct dynamicArray结构体

2.1、属性：

• void ** pAddr 维护真实在堆区创建的数组的指针

• int m_capacity; 数组容量

• int m_size; 数组大小

struct dynamicArray {

    void **pAddr; //维护真实在堆区创建的数组的指针

    int m_capacity; //数组容量

    int m_size; //数组大小
};

3、 动态数组初始化

//初始化数组
struct dynamicArray *init_DynamicArray(int capacity) {
    if (capacity <= 0) {
        return NULL;
    }

    //跟数组分配空间
    struct dynamicArray *array = malloc(sizeof(struct dynamicArray));
    if (array == NULL) {

        return NULL;
    }
    //数组分配堆区
    //数组初始化
    array->pAddr = malloc(sizeof(void *) * capacity);
    array->m_capacity = capacity;
    array->m_size = 0;

    return array;
}

3、插入数组

//插入数组
void insert_DynamicArray(struct dynamicArray *array, int pos, void *data) {

    if (array == NULL) {
        return;
    }
    if (data == NULL) {
        return;
    }

    //无效位置 尾插
    if (pos < 0 || pos > array->m_size) {
        pos = array->m_size;
    }
    //判断数组是否满了，满了就动态扩展
    if (array->m_size == array->m_capacity) {

        //1.计算新空间大小
        int newCapacity = array->m_capacity * 2;

        //2.给每个元素申请新的堆空间
        void **newSpace = malloc(sizeof(void *) * newCapacity);

        //3.将原有的数据拷贝新空间中
        memcpy(newSpace, array->pAddr, sizeof(void *) * array->m_capacity);

        //4.释放原有的内存空间
        free(array->pAddr);

        //5.更新新空间指向
        array->pAddr = newSpace;

        //6.更新新容量
        array->m_capacity = newCapacity;

    }

    //插入新的元素
    //移动元素 进行插入新的元素
    for (int i = array->m_size - 1; i >= pos; i--) {
        //所有数据向后移动
        array->pAddr[i + 1] = array->pAddr[i];
    }

    //将新元素 插入到指定位置
    array->pAddr[pos] = data;
    //更新大小
    array->m_size++;
}

4、遍历数组

//遍历数组
void forEach_DynamicArray(struct dynamicArray *array, void(*myPrint)(void *)) {
    if (array == NULL) {

        return;
    }
    if (myPrint == NULL) {

        return;
    }
    for (int i = 0; i < array->m_size; i++) {
        myPrint(array->pAddr[i]);
    }
}

这里myPrint为用户余姚自定义的回调函数

5、删除数组

• 按位置删除

//删除数组 按位置删除
void removeByPos_DynamicArray(struct dynamicArray *array, int pos) {

    if (array == NULL) {
        return;
    }

    //无效位置删除
    if (pos < 0 || pos > array->m_size - 1) {
        return;
    }
    //数据向前移动一位
    for (int i = 0; i < array->m_size; i++) {
        array->pAddr[i] = array->pAddr[i + 1];
    }

    //更新数组大小
    array->m_size--;
}

• 按值删除

//删除数组 按值删除
void removeByValue_DynamicArray(struct dynamicArray *array, void *data, int (*myCompare)(void *, void *)) {

    if (array == NULL) {
        return;
    }

    if (data == NULL) {
        return;
    }
    //
    for (int i = 0; i < array->m_size; i++) {

        if (myCompare(array->pAddr[i], data)) {

            //如果找到要删除的数据,i就是要删除的位置
            removeByPos_DynamicArray(array, i);
            break;
        }
    }

myCompare为回调函数，用户自定义比较规则

6、销毁数组

//销毁数组
void destroy_DynamicArray(struct dynamicArray* array)
{
	if (array == NULL)
	{
		return;	
    }
	if (array->pAddr != NULL)
	{
		free(array->pAddr);
		array->pAddr = NULL;
	}
	free(array);
	array = NULL;
}

三、调试

1、回调函数 myPrintPerson

//回调函数
void myPrintPerson(void *data) {
    struct person *p = data;
    printf("姓名：%s,年龄：%d\n", p->name, p->age);
}

2、回调函数 myCompare

//回调函数
int myCompare(void *data1, void *data2) {

    struct person *p1 = data1;
    struct person *p2 = data2;
    p1->name;
    p2->name;

    return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}

3.测试

• 定义结构体Person

struct person {
    char name[64];
    char age;
};

• main

int main() {

    //初始化数组
    struct dynamicArray *array = init_DynamicArray(5);

    //准备数据
    struct person p1 = {"亚瑟", 18};
    struct person p2 = {"安琪拉", 12};
    struct person p3 = {"凯", 11};
    struct person p4 = {"孙悟空", 12};
    struct person p5 = {"达摩", 111};
    struct person p6 = {"牛魔", 123};

    printf("插入数据后：容量：%d 大小：%d\n", array->m_capacity, array->m_size);
    //插入数据
    insert_DynamicArray(array, 0, &p1);
    insert_DynamicArray(array, 0, &p2);
    insert_DynamicArray(array, 1, &p3);
    insert_DynamicArray(array, 0, &p4);
    insert_DynamicArray(array, -1, &p5);
    insert_DynamicArray(array, 2, &p6);

    //遍历数据
    forEach_DynamicArray(array, myPrintPerson);
    printf("插入数据后：容量：%d 大小：%d\n", array->m_capacity, array->m_size);

    //测试删除
    removeByPos_DynamicArray(array, 0);
    forEach_DynamicArray(array, myPrintPerson);
    printf("删除数据后：容量：%d 大小：%d\n", array->m_capacity, array->m_size);


    struct person p = {"达摩", 111};
    removeByValue_DynamicArray(array, &p, myCompare);
    forEach_DynamicArray(array, myPrintPerson);
    printf("删除数据后：容量：%d 大小：%d\n", array->m_capacity, array->m_size);

    return 0;
}