C语言数据结构 - 动态数组

深碍√TFBOYSˉ_ 2023-10-10 18:43 48阅读 0赞

#include <stdlib.h>
    
    typedef int bool;
    #define TRUE 1
    #define FALSE 0
    
    // 动态数组元素类型E（E是别名，定义别名的好处是：后期只要改此处E对应的实际类型即可控制全局）
    typedef int E;
    
    // 动态数组结构体
    typedef struct List {
        E *array; // 底层容器：数组
        int capacity; // 底层容器的容量：数组的长度
        int size; // 底层容器存入元素的个数
    } ArrayList;
    
    // 动态数组最低容量，设置最低容量的目的是避免容量设置过小，导致频繁动态数组扩容和缩容，可根据实际要求设置此参数大小
    #define MIN_CAPACITY 16
    
    /*!
     * 初始化动态数组
     * @return 动态数组指针
     */
    ArrayList* init() {
        ArrayList* list = (ArrayList*) malloc(sizeof(ArrayList));
    
        // 申请动态数组结构体内存失败
        if(list == NULL) {
            return NULL;
        }
    
        // 动态数组底层容器使用动态内存
        list->array = (E *) malloc(sizeof(E) * MIN_CAPACITY);
    
        // 申请内存失败，则初始化失败
        if (list->array == NULL) {
            // 同时释放掉已经申请到的动态数组结构体的内存
            free(list);
            return NULL;
        }
    
        // 初始化动态数组结构体其他成员
        list->capacity = MIN_CAPACITY;
        list->size = 0;
    
        return list;
    }
    
    /*!
     * 释放动态数组
     * @param list 动态数组
     */
    void destroy(ArrayList* list) {
        if(list != NULL) {
            // 释放底层容器占用的内存
            free(list->array);
            // 释放动态数组结构体占用的内存
            free(list);
        }
    }
    
    /*!
     * 重置动态数组的容量
     * @param list 动态数组
     * @param newCap 新容量
     * @return 重置结果
     */
    bool resize(ArrayList *list, int newCap) {
        // 如果新容量 小于 最小容量，则无需重置（避免频繁的扩容和缩容）
        if (newCap <= MIN_CAPACITY) {
            return TRUE;
        }
    
        // 根据新容量要求，来重新申请底层容器的内存
        void *p = realloc(list->array, sizeof(E) * newCap);
    
        // 申请内存失败
        if (p == NULL) {
            return FALSE;
        }
    
        // 更新动态数组结构体成员
        list->array = (E *) p;
        list->capacity = newCap;
    
        return TRUE;
    }
    
    /*!
     * 在指定位置插入元素
     * @param list 动态数组
     * @param ele 元素值
     * @param index 指定插入位置
     * @return 操作结果
     */
    bool add(ArrayList *list, int index, E ele) {
        // 尾部（list->size索引）插入不算越界
        if (index < 0 || index > list->size) {
            return FALSE;
        }
    
        // 容量不足，则需要扩容
        if (list->size == list->capacity) {
            if (!resize(list, list->capacity << 1)) { // 默认扩容为原容量的两倍
                // 重置容量失败，则无法插入
                return FALSE;
            }
        }
    
        // 如果不是尾部插入
        if (index < list->size) {
            // 则相当于将 index ~ list->size - 1 索引位置的元素 统一后移一位
            for (int i = list->size; i > index; i--) {
                list->array[i] = list->array[i - 1];
            }
        }
    
        // 将index位置更新为新元素值
        list->array[index] = ele;
        // 存入动态数组的元素个数+1
        list->size++;
    
        return TRUE;
    }
    
    /*!
     * 删除指定位置元素
     * @param list 动态数组
     * @param index 指定删除位置
     * @return 被删除的元素值（如果对应删除位置越界，则返回NULL）（注意：返回值是特地申请内存存储的，因此使用完需要记得释放，避免内存泄露）
     */
    E* delete(ArrayList *list, int index) {
        // 越界位置不能删除
        if (index < 0 || index >= list->size) {
            return NULL;
        }
    
        // 申请新内存，缓存将被删除的元素值
        E* p = (E*) malloc(sizeof(E));
        *p = list->array[index];
    
        // 删除index位置的元素，相当于index+1 ~ list->size - 1 索引范围的元素 都前移一位
        for (int i = index; i <= list->size - 1; i++) {
            list->array[i] = list->array[i + 1];
        }
    
        // 删除元素后，动态数组存储的元素个数-1
        list->size--;
    
        // 动态数组存储的元素个数 少于 容量一半时，可以进行缩容（缩容为之前容量的一半）
        int newCap = list->capacity >> 1;
        if (list->size < newCap) {
            // 这里缩容失败不影响删除操作，前面已完成了删除操作
            resize(list, newCap);
        }
    
        // 返回被删除的元素的地址（缓存地址）
        return p;
    }
    
    /*!
     * 更新指定位置的元素值
     * @param list 动态数组
     * @param ele 元素值
     * @param index 指定位置
     * @return 操作结果
     */
    bool set(ArrayList *list, int index, E ele) {
        // 越界位置无法更新
        if (index < 0 || index >= list->size) {
            return FALSE;
        }
    
        list->array[index] = ele;
    
        return TRUE;
    }
    
    /*!
     * 获取指定位置的元素
     * @param list 动态数组
     * @param index 指定位置
     * @return 动态数组元素的地址
     */
    E * get(ArrayList *list, int index) {
        // 越界位置无法获取
        if (index < 0 || index >= list->size) {
            return NULL;
        }
    
        return &list->array[index];
    }