数据结构基础（C语言实现）—— 变长数组

仿照 Java 的 ArrayList 实现的可变长数组，可惜的是 C 语言没有像 Java 中那么灵活方便使用的泛型，需要使用无类型指针 (void *) 实现，这里只是做个笔记，就不搞的太复杂了。

容量变化规则同之前实现的顺序栈一样（PS：顺序栈的代码大部分是从这里拷贝过去的），这里再说明一下：

• 扩容规则是栈满则扩大一倍；

• 缩容规则是当前数量为容量的 1/4 时，容量缩小到当前的一半，之所以要到 1/4 的时候再缩容而不是到 1/2 就缩容，是为了防止数量刚到 1/2 时又立刻压入栈元素导致扩容；

数组结构体

//
// Created by Tianyi on 2021/10/26.
//

#ifndef UNTITLED_STRUCT_H
#define UNTITLED_STRUCT_H

#endif //UNTITLED_STRUCT_H

struct MineArrayList {
    int count;
    int capacity;
    int *arr;
};

变长数组相关操作

//
// Created by Tianyi on 2021/10/26.
//
#include <stdlib.h>

#ifndef UNTITLED_UTILS_H
#define UNTITLED_UTILS_H

#endif //UNTITLED_UTILS_H

void extendList(struct MineArrayList *list);

void reduceList(struct MineArrayList *list);

struct MineArrayList newIntArrayList(const int capacity) {
    int *arr = (int *) calloc(capacity, sizeof(int));

    struct MineArrayList al = {
            0,
            capacity,
            arr
    };

    return al;
}


void addEle(struct MineArrayList *list, int index, int element) {
    // 判断是否需要扩容
    if (list->count + 1 > list->capacity) {
        extendList(list);
    }
    // 判断传入的下标是否有效
    if (index >= list->capacity || index < 0) {
        printf("This index is invalid!!!");
        return;
    }
    // 单独拿出数组操作
    int *arr = list->arr;
    // 在指定位置插入元素
    for (int i = list->count; i > index; i--) {
        arr[i] = arr[i - 1];
    }
    arr[index] = element;
    list->count++;
}


void addLastEle(struct MineArrayList *list, int element) {
    addEle(list, list->count, element);
}


void addFirstEle(struct MineArrayList *list, int element) {
    addEle(list, 0, element);
}


void removeEle(struct MineArrayList *list, int index) {
    // 先判断 List 是否为空
    if (list->count == 0) {
        printf("This list is empty, there is no element to delete!!!");
    }
    // 判断传入的下标是否有效
    if (index >= list->capacity || index < 0) {
        printf("This index is invalid!!!");
        return;
    }
    // 单独拿出数组操作
    int *arr = list->arr;
    // 删除指定位置元素（数据往前移动，count - 1）
    for (int i = index; i < list->count - 1; ++i) {
        arr[i] = arr[i + 1];
    }
    list->count--;
    // 判断是否需要缩容
    if (list->count <= list->capacity / 4) {
        reduceList(list);
    }
}


void removeFirstEle(struct MineArrayList *list) {
    removeEle(list, 0);
}


void removeLastEle(struct MineArrayList *list) {
    removeEle(list, list->count - 1);
}

/**
 * 扩容
 * @param list 
 */
void extendList(struct MineArrayList *list) {
    int *newArr = (int *) calloc(list->capacity * 2, sizeof(int));
    int *oldArr = list->arr;
    for (int i = 0; i < list->count; ++i) {
        newArr[i] = oldArr[i];
    }
    free(oldArr);
    list->capacity = list->capacity * 2;
    list->arr = newArr;
}

/**
 * 缩容
 * @param list 
 */
void reduceList(struct MineArrayList *list) {
    int *newArr = (int *) calloc(list->capacity / 4, sizeof(int));
    int *oldArr = list->arr;
    for (int i = 0; i < list->capacity / 2; ++i) {
        newArr[i] = oldArr[i];
    }
    free(oldArr);
    list->capacity = list->capacity / 2;
    list->arr = newArr;
}


void show(const struct MineArrayList *list) {
    printf("The capacity of arraylist is %d.\n", list->capacity);
    printf("There %d elements in this list.\n", list->count);
    printf("All elements of MineArrayList:\n");
    for (int i = 0; i < list->count; ++i) {
        printf("index-%d : %d\n", i, list->arr[i]);
    }
}

测试代码

#include <stdio.h>
#include "lib/struct.h"
#include "lib/utils.h"

int main() {
    struct MineArrayList list = newIntArrayList(5);

    for (int i = 0; i < 40; i++) {
        addLastEle(&list, i);
    }
    show(&list);
    printf("======================\n");

    for (int i = 0; i < 30; ++i) {
        removeLastEle(&list);
    }
    show(&list);
    printf("======================\n");

    return 0;
}