7.1 C/C++ 实现动态数组

#include <stdlib.h>
#include <string.h>

struct DynamicArray
{
    void **addr;   // 存放元素或结构体的首地址
    int curr_size; // 存放当前元素数量
    int max_size;  // 存放当前最大元素数
};

// 初始化动态数组,初始化后直接返回数组的首地址
struct DynamicArray *InitDynamicArray(int size)
{
    // 如果小于0则说明没有元素,返回NULL
    if (size <= 0)
    {
        return NULL;
    }

    // 分配结构指针,此处分配的是结构体指针,并没有分配空间
    struct DynamicArray *ptr = malloc(sizeof(struct DynamicArray));
    if (ptr != NULL)
    {
        // 将当前元素索引设置为0
        ptr->curr_size = 0;
        // 默认最大数组元素数为size
        ptr->max_size = size;
        // 实际分配存储空间大小是max_size最大元素
        ptr->addr = malloc(sizeof(void *) * ptr->max_size);
        return ptr;
    }
    return NULL;
}

// 将元素插入到指定位置
void InsertDynamicArray(struct DynamicArray *ptr, int index, void *data)
{
    // 判断如果数组不为空,或者是data不为空,则继续执行
    if (ptr != NULL || data != NULL)
    {
        // 如果插入位置小于当前0,或者大于当前元素总个数
        if (index < 0 || index > ptr->curr_size)
        {
            // 就自动把它插入到元素的末尾位置
            index = ptr->curr_size;
        }

        // 紧接着判断当前元素数是否大于最大值,大于则分配空间
        if (ptr->curr_size >= ptr->max_size)
        {
            // 分配一块更大的空间,这里分配原始空间的2倍
            int new_max_size = ptr->max_size * 2;
            void **new_space = malloc(sizeof(void *) * new_max_size);

            // 接着将原来空间中的数据拷贝到新分配的空间
            memcpy(new_space, ptr->addr, sizeof(void *) * ptr->max_size);

            // 释放原来的内存空间,并更新指针的指向为新空间的地址
            free(ptr->addr);
            ptr->addr = new_space;
            ptr->max_size = new_max_size;
        }

        // 开始移动元素,给ins元素腾出空来
        for (int x = ptr->curr_size - 1; x >= index; --x)
        {
            // 从后向前,将前一个元素移动到后一个元素上
            ptr->addr[x + 1] = ptr->addr[x];
        }
        // 设置好指针以后,开始赋值
        ptr->addr[index] = data;
        ptr->curr_size++;
        return 1;
    }
    return 0;
}

// 遍历数组中的元素,这里的回调函数是用于强制类型转换,自定义输出时使用
void ForeachDynamicArray(struct DynamicArray *ptr, void(*_callback)(void *))
{
    if (ptr != NULL || _callback != NULL)
    {
        for (int x = 0; x < ptr->curr_size; x++)
        {
            // 调用回调函数并将数组指针传递过去
            _callback(ptr->addr[x]);
        }
    }
}

// 根据位置删除指定元素,index = 元素的下标位置
void RemoveByPosDynamicArray(struct DynamicArray *ptr, int index)
{
    if (ptr == 0)
        return 0;

    // 判断当前插入位置index必须大于0且小于curr_size
    if (index > 0 || index < ptr->curr_size - 1)
    {
        for (int i = index; i < ptr->curr_size - 1; ++i)
        {
            // 每次循环都将后一个元素覆盖到前一个元素上
            ptr->addr[i] = ptr->addr[i + 1];
        }

        // 最后当前元素数量应该减去1
        ptr->curr_size--;
    }
}

// 按照元素的指定值进行元素删除,这里需要回调函数指定要删除元素的值是多少
void RemoveByValueDynamicArray(struct DynamicArray *ptr, void *data, int(*compare)(void*, void *))
{
    if (ptr != NULL && data != NULL && compare != NULL)
    {
        for (int i = 0; i < ptr->curr_size; ++i)
        {
            if (compare(ptr->addr[i], data))
            {
                RemoveByPos_DynamicArray(ptr, i);
                break;
            }
        }
    }
}

// 销毁数组
void DestroyDynamicArray(struct DynamicArray *ptr)
{
    if (ptr != NULL)
    {
        if (ptr->addr != NULL)
        {
            free(ptr->addr);
            ptr->addr = NULL;
        }
        free(ptr);
        ptr = NULL;
    }
}

#include "dynamic.h"

// 自定义结构体
struct Student
{
    int uid;
    char name[64];
    int age;
};

// 回调函数用于输出元素
void MyPrint(void *data)
{
    // 强制类型转换,转成我们想要的类型
    struct Student *ptr = (struct Student *)data;
    printf("Uid: %d --> Name: %s \n", ptr->uid, ptr->name);
}

// 回调函数用于对比元素
int myCompare(void *x, void *y)
{
    struct Student *p1 = (struct Student *)x;
    struct Student *p2 = (struct Student *)y;

    if (strcmp(p1->name, p2->name) == 0)
    {
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[])
{
    //创建动态数组
    struct DynamicArray *ptr = InitDynamicArray(5);

    // 创建元素
    struct Student stu1 = { 1001, "admin1", 22 };
    struct Student stu2 = { 1002, "admin2", 33 };
    struct Student stu3 = { 1003, "admin3", 44 };
    struct Student stu4 = { 1004, "admin4", 55 };

    // 将元素插入到数组
    InsertDynamicArray(ptr, 0, &stu1);
    InsertDynamicArray(ptr, 1, &stu2);
    InsertDynamicArray(ptr, 3, &stu3);
    InsertDynamicArray(ptr, 4, &stu4);

    // 根据下标移除元素
    RemoveByPosDynamicArray(ptr, 0);

    // 删除元素是p_delete的数据
    struct Student p_delete = { 1002, "admin2", 33 };
    RemoveByValueDynamicArray(ptr, &p_delete, myCompare);

    // 遍历元素
    ForeachDynamicArray(ptr, MyPrint);

    // 销毁顺序表
    DestroyDynamicArray(ptr);

    system("pause");
    return 0;
}