动态数组源码

源文件

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "dynamicArray.h"

// 在项目中只作为状态码
enum STATUS_CODE
{
    ON_SUCCESS,
    MALLOC_ERROR,
    NULL_PTR,
    INVALID_ACCESS
};

#define DEFAULT_CAPACITY 10

// 静态函数：只在本源文件中使用，其他文件用不了
// 静态函数前置声明，就是在这里声明
// 不需要在.h文件中声明
static int expandDynamicArrayCapacity(DynamicArray *pArray);
// 动态数组缩容
static int shrinkDynamicArrayCapacity(DynamicArray *pArray);
// 根据元素的值，获取多以的位置
static int dynamicArrayAppointDataGetPos(DynamicArray *pArray, int data, int *pos);

// 静态函数：只在本源文件中使用，其他文件用不了
// 静态函数前置声明，就是在这里声明
// 不需要在.h文件中声明
static int expandDynamicArrayCapacity(DynamicArray *pArray)
{
    // // 判空
    // if (pArray == NULL)
    // {
    //     printf("null pointer\n");
    //     return NULL_PTR;
    // }
    //  1.数据备份
    ELEMENTTYPE *tempData = pArray->data;

    //  2.分配一块更大的内存空间
    int needExpandCapacity = pArray->capacity + (pArray->capacity >> 1);
    pArray->data = (ELEMENTTYPE *)malloc(sizeof(ELEMENTTYPE) * needExpandCapacity);
    //  判空并清除脏数据
    if (pArray->data == NULL)
    {
        return MALLOC_ERROR;
    }
    memset(pArray->data, 0, sizeof(ELEMENTTYPE) * needExpandCapacity);

    //  3.数据迁移
    for (int idx = 0; idx < pArray->size; idx++)
    {
        pArray->data[idx] = tempData[idx];
    }

    //  4.释放内存
    if (tempData != NULL)
    {
        free(tempData);
        tempData = NULL;
    }

    //  5.更新数组大小
    pArray->capacity = needExpandCapacity;
    return 0;
}

// 动态数组缩容
static int shrinkDynamicArrayCapacity(DynamicArray *pArray)
{
    // // 判空
    // if (pArray == NULL)
    // {
    //     printf("null pointer\n");
    //     return NULL_PTR;
    // }

    // 数据备份
    ELEMENTTYPE *tempData = pArray->data;

    // 申请一块更小的内存空间
    int needShrinkCapacity = pArray->capacity - (pArray->capacity >> 2);
    pArray->data = (ELEMENTTYPE *)malloc(sizeof(ELEMENTTYPE) * needShrinkCapacity);
    // 判空并清除内存空间
    if (pArray->data == NULL)
    {
        printf("malloc error\n");
        return MALLOC_ERROR;
    }
    memset(pArray->data, 0, sizeof(ELEMENTTYPE) * needShrinkCapacity);

    // 数据复制
    for (int idx = 0; idx < pArray->size; idx++)
    {
        pArray->data[idx] = tempData[idx];
    }

    // 释放内存
    if (tempData != NULL)
    {
        free(tempData);
        tempData = NULL;
    }

    // 更新新容量
    pArray->capacity = needShrinkCapacity;

    return 0;
}

// 根据元素的值，获取位置
static int dynamicArrayAppointDataGetPos(DynamicArray *pArray, int data, int *pos)
{
    // // 判空
    // if (pArray == NULL)
    // {
    //     printf("null pointer\n");
    //     return NULL_PTR;
    // }

    for (int idx = pArray->size - 1; idx >= 0; idx--)
    {
        if (pArray->data[idx] == data)
        {
            *pos = idx;
            return ON_SUCCESS;
        }
    }
    *pos = -1;
    return -1;
}

// 动态数组初始化
int dynamicArrayInit(DynamicArray *pArray, int capacity)
{
    if (pArray == NULL)
    {
        perror("null pointer error\n");
        return NULL_PTR;
    }

    if (capacity <= 0)
    {
        capacity = DEFAULT_CAPACITY;
    }
    // 动态分配空间
    pArray->data = (ELEMENTTYPE *)malloc(sizeof(ELEMENTTYPE) * capacity);
    // 指针变量初始化之后判空
    if (pArray->data == NULL)
    {
        printf("malloc error\n");
        return MALLOC_ERROR;
    }
    // 清除脏数据
    memset(pArray->data, 0, sizeof(ELEMENTTYPE) * capacity);

    // 初始化时元素个数为0
    pArray->size = 0;
    pArray->capacity = capacity;

    return ON_SUCCESS;
}

int dynamicArrayInsertData(DynamicArray *pArray, ELEMENTTYPE data)
{
    return dynamicArrayAppointPosInsertData(pArray, pArray->size, data);
}

// 动态数组在指定位置插入数组
int dynamicArrayAppointPosInsertData(DynamicArray *pArray, int pos, ELEMENTTYPE data)
{
    int ret = 0;
    // 指针判空
    if (pArray == NULL)
    {
        printf("null pointer\n");
        return NULL_PTR;
    }

    // 判断位置是否合法
    if (pos < 0 || pos > pArray->size)
    {
        return INVALID_ACCESS;
    }

    // 空间不足的预警算法是：元素个数的1.5倍比动态数组的容量大的时候
    if ((pArray->size + (pArray->size >> 1)) > pArray->capacity)
    {
        // 空间不足告急
        expandDynamicArrayCapacity(pArray);
    }

    // 从后往前，挨个将数据往后移动一个位置
    for (int idx = pArray->size; idx > pos; idx--)
    {
        pArray->data[idx] = pArray->data[idx - 1];
    }

    // 赋值
    pArray->data[pos] = data;

    // 更新数组属性
    (pArray->size)++;
    return ret;
}

// API:application programming interface
// 获取数组的元素个数
int dynamicArrayGetSize(DynamicArray *pArray, int *pSize)
{
    if (pArray == NULL)
    {
        return NULL_PTR;
    }

    if (pSize != NULL)
    {
        *pSize = pArray->size;
    }

    return ON_SUCCESS;
}

// 获取数组容量大小
int dynamicArrayGetCapacity(DynamicArray *pArray, int *pCapacity)
{
    if (pArray == NULL)
    {
        return NULL_PTR;
    }

    if (pCapacity != NULL)
    {
        *pCapacity = pArray->capacity;
    }

    return ON_SUCCESS;
}

// 动态数组删除元素，默认删除末尾元素
int dynamicArrayDeleteData(DynamicArray *pArray)
{
    return dynamicArrayAppointPosDeleteData(pArray, pArray->size - 1);
}

// 在指定位置删除元素
int dynamicArrayAppointPosDeleteData(DynamicArray *pArray, int pos)
{
    // 判空
    if (pArray == NULL)
    {
        return NULL_PTR;
    }

    // 判断位置合法性
    if (pos < 0 || pos >= pArray->size)
    {
        return INVALID_ACCESS;
    }

    // 在删除元素时会发生缩容
    if (pArray->size < (pArray->capacity - (pArray->capacity >> 1)))
    {
        shrinkDynamicArrayCapacity(pArray);
    }

    pArray->data[pos] = 0;
    // 将数据挨个往前移动
    for (int idx = pos; idx < pArray->size - 1; idx++)
    {
        pArray->data[idx] = pArray->data[idx + 1];
    }

    // 更新动态数组大小
    (pArray->size)--;

    return 0;
}

// 动态数组删除指定的值
int dynamicArrayDeleteAppointData(DynamicArray *pArray, ELEMENTTYPE data)
{
    if (pArray == NULL)
    {
        printf("null pointer");
        return NULL_PTR;
    }

    int pos = -1;
    while (dynamicArrayAppointDataGetPos(pArray, data, &pos) != -1)
    {
        dynamicArrayAppointPosDeleteData(pArray, pos);
    }

    // // 遍历数组，删除值相同的元素
    // for (int idx = pArray->size - 1; idx >= 0; idx--)
    // {
    //     if (pArray->data[idx] = data)
    //     {
    //         dynamicArrayAppointPosDeleteData(pArray, idx);
    //     }
    // }

    return 0;
}

// 获取指定位置的值
int dynamicArrayGetAppointPosData(DynamicArray *pArray, int pos, int *data)
{
    // 判空
    if (pArray == NULL)
    {
        printf("null pointer\n");
        return NULL_PTR;
    }

    // 判断位置合法性
    if (pos < 0 || pos >= pArray->size)
    {
        return INVALID_ACCESS;
    }

    if (data != NULL)
    {
        *data = pArray->data[pos];
    }

    return ON_SUCCESS;
}

// 销毁并释放内存
int dynamicArrayDestory(DynamicArray *pArray)
{
    // 判空
    if (pArray == NULL)
    {
        printf("null pointer");
        return NULL_PTR;
    }

    // 释放空间
    if (pArray->data != NULL)
    {
        free(pArray->data);
        pArray->data = NULL;
    }

    return ON_SUCCESS;
}

头文件

#ifndef __DYNAMICARRAY_H__
#define __DYNAMICARRAY_H__

// #define ELEMENTTYPE void *
#define ELEMENTTYPE int

// 动态函数结构体
typedef struct DynamicArray
{
    // 数据
    ELEMENTTYPE *data;
    // 元素个数
    int size;
    // 容量大小
    int capacity;
} DynamicArray;

// 任何一个函数必须有返回值

// 动态数组初始化
// DynamicArray *pArray:动态数组数据初始位置
// int capacity:动态数组容量
int dynamicArrayInit(DynamicArray *pArray, int capacity);

// 动态数组插入元素
// DynamicArray *pArray:动态数组数据初始位置
// ELEMENTTYPE data:要插入的数据
int dynamicArrayInsertData(DynamicArray *pArray, ELEMENTTYPE data);

// 动态数组在指定位置插入数组
// DynamicArray *pArray:动态数组数据初始位置
// int pos:插入位置
// ELEMENTTYPE data:要插入的数据
int dynamicArrayAppointPosInsertData(DynamicArray *pArray, int pos, ELEMENTTYPE data);

// 获取数组的元素个数
int dynamicArrayGetSize(DynamicArray *pArray, int *pSize);

// 获取数组容量大小
int dynamicArrayGetCapacity(DynamicArray *pArray, int *pCapacity);

// 动态数组删除元素，默认删除末尾元素
int dynamicArrayDeleteData(DynamicArray *pArray);

// 在指定位置删除元素
int dynamicArrayAppointPosDeleteData(DynamicArray *pArray, int pos);

// 动态数组删除指定的值
int dynamicArrayDeleteAppointData(DynamicArray *pArray, ELEMENTTYPE data);

// 获取指定位置的值
int dynamicArrayGetAppointPosData(DynamicArray *pArray, int pos, int *data);

// 销毁并释放内存
int dynamicArrayDestory(DynamicArray *pArray);

#endif

测试代码

#include <stdio.h>
#include <string.h>
#include "dynamicArray.h"

int main(int argc, char const *argv[])
{
    DynamicArray array;
    memset(&array, 0, sizeof(array));

#if 1
    dynamicArrayInit(&array, 5);

    int size = 0;
    dynamicArrayGetSize(&array, &size);

    int capacity = 0;
    dynamicArrayGetCapacity(&array, &capacity);

    printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    for (int idx = 0; idx < 4; idx++)
    {
        dynamicArrayInsertData(&array, idx + 1);
    }
    for (int idx = 0; idx < 4; idx++)
    {
        dynamicArrayInsertData(&array, idx + 1);
    }

    dynamicArrayGetSize(&array, &size);
    dynamicArrayGetCapacity(&array, &capacity);
    printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    // for(int idx = array.size; idx > 1; idx--)
    // {
    //     dynamicArrayDeleteData(&array);
    // }

    // dynamicArrayGetSize(&array, &size);
    // dynamicArrayGetCapacity(&array, &capacity);
    // printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    int value = 0;
    for (int idx = 0; idx < size; idx++)
    {
        dynamicArrayGetAppointPosData(&array, idx, &value);
        printf("value:%2d\t", value);
    }
    printf("\n");

    dynamicArrayAppointPosInsertData(&array, 3, 666);
    dynamicArrayGetSize(&array, &size);
    dynamicArrayGetCapacity(&array, &capacity);
    for (int idx = 0; idx < size; idx++)
    {
        dynamicArrayGetAppointPosData(&array, idx, &value);
        printf("value:%2d\t", value);
    }
    printf("\n");
    printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    dynamicArrayAppointPosInsertData(&array, 3, 777);
    dynamicArrayGetSize(&array, &size);
    dynamicArrayGetCapacity(&array, &capacity);
    for (int idx = 0; idx < size; idx++)
    {
        dynamicArrayGetAppointPosData(&array, idx, &value);
        printf("value:%2d\t", value);
    }
    printf("\n");
    printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    dynamicArrayAppointPosDeleteData(&array, 4);
    dynamicArrayGetSize(&array, &size);
    dynamicArrayGetCapacity(&array, &capacity);
    for (int idx = 0; idx < size; idx++)
    {
        dynamicArrayGetAppointPosData(&array, idx, &value);
        printf("value:%2d\t", value);
    }
    printf("\n");
    printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    dynamicArrayDeleteAppointData(&array, 4);
    dynamicArrayGetSize(&array, &size);
    dynamicArrayGetCapacity(&array, &capacity);
    for (int idx = 0; idx < size; idx++)
    {
        dynamicArrayGetAppointPosData(&array, idx, &value);
        printf("value:%2d\t", value);
    }
    printf("\n");
    printf("array->size:%d\tarray->capacity:%d\n", size, capacity);

    dynamicArrayDestory(&array);

    dynamicArrayDestory(&array);
#endif

    return 0;
}

Makefile编译文件

OBJS=$(patsubst %.c, %.o, $(wildcard ./*.c))
# 变量自定义赋值
TARGET=main

LDFLAGS=-L./src_so -L./src_a
# LIBS=-lMyAdd -lMyDiv

SO_DIR=./src_so
A_DIR=./src_a

# 变量取值用$()
$(TARGET):$(OBJS)
	$(CC) -g $^ $(LIBS) $(LDFLAGS) -o $@

# 模式匹配 %[目标]:%[依赖]
%.o:%.c
	$(CC) -c $^ -o $@

# 切换编译路径，编译动态库和静态库
# 进入静态库执行默认第一条命令
all:
	make -C $(SO_DIR)
	make -C $(A_DIR)

# 伪目标(伪文件)，指执行命令，不生成文件 否则会生成一个clean文件
.PHONY: clean

# clean:
# 	@$(RM) *.o main
clean:
	$(RM) $(OBJS) $(TARGET)
# 进到动态库或者静态库执行clean命令
	make -C $(SO_DIR) clean
	make -C $(A_DIR) clean

# `wildcard`：匹配文件 ()
# `patsubst`：模式匹配与替换
show:
	@echo $(wildcard ./*.c)
	@echo $(patsubst %.c, %.o, $(wildcard ./*.c))