原理介绍
我们利用万能指针来实现动态数组，数组元素类型可以是任意类型，因为我们只维护用户提供的数据的地址，所以可以用万能指针来接受，这样就实现了类似C++中的模板功能了。
先说说动态数组和静态数组。静态数组一旦建立它的空间是不可变的，比如我们在栈上开辟的空间，一旦开辟，长度就不可变。如果我们用malloc在堆区开辟的数组，如果当我们检测到数组已经满了，我们可以重新开辟一块更大的空间，将原有的数据拷贝到新的空间，这样就实现动态数组的效果了。
实现算法预览
DynamicArray.h
#pragma once#ifndef __DYNAMICARRAY_H__#define __DYNAMICARRAY_H__#define _CRT_SECURE_NO_WARNINGS//动态数组typedef struct DynamicArray{void** pArr;//数组元素具体存储位置，由于不知道用户存储的数据类型和数据位置统一用void*来指向用户存储的每一个元素int m_size;//数组大小int m_capacity;//数组容量}DynamicArray;//初始化动态数组DynamicArray* Init_DynamicArray(int capacity);//动态数组插入数据//模拟数组pos范围0 ~ arr->m_size - 1int InsertByIndex_DynamicArray(DynamicArray* arr, void * data, int pos);//动态数组进行遍历void Foreach_DynamicArray(DynamicArray* arr, void(*Foreach_Function)(void*));//动态数组删除元素根据元素下标int RemoveByIndex_DynamicArray(DynamicArray* arr, int pos);//动态数组删除元素根据元素的值int RemoveByValue_DynamicArray(DynamicArray* arr, void* data, int(*compare)(void* data1, void* data2));//动态数组销毁int Destroy_DynamictArray(DynamicArray* arr);#endif // !__DYNAMICARRAY_H__
实现代码展示
DynamicArray.c
#include <stdio.h>#include <stdlib.h>#include "DynamicArray.h"//初始化动态数组DynamicArray* Init_DynamicArray(int capacity){DynamicArray* arr = (DynamicArray*)malloc(sizeof(DynamicArray));if (NULL == arr){return NULL;}arr->m_capacity = capacity;arr->pArr = malloc(sizeof(void*)*capacity);arr->m_size = 0;return arr;}//动态数组插入数据//模拟数组pos范围0 ~ arr->m_size - 1int InsertByIndex_DynamicArray(DynamicArray* arr, void * data, int pos){if (NULL == arr || NULL == data){return 0;}//位置非法 进行尾插if (pos < 0 || pos >= arr->m_size){pos = arr->m_size;}//判断数组是否满载if (arr->m_size >= arr->m_capacity){//进行扩容int newCapacity = arr->m_capacity * 2;//arr->pArr = (void**)realloc((void*)arr->pArr, newCapacity);//数据复制有问题 error//手动复制void** pArr = malloc(sizeof(void*)*newCapacity);for (int i = 0; i < arr->m_capacity; i++){pArr[i] = arr->pArr[i];}if (arr->pArr != NULL){free(arr->pArr);arr->pArr = NULL;}arr->pArr = pArr;arr->m_capacity = newCapacity;}//将插入位置以及其后的数组元素往后移动一位for (int i = arr->m_size - 1; i >= pos; i--){arr->pArr[i + 1] = arr->pArr[i];}//将新元素进行插入arr->pArr[pos] = data;arr->m_size++;return 1;}//动态数组进行遍历void Foreach_DynamicArray(DynamicArray* arr, void(*Foreach_Function)(void*)){if (NULL == arr){return;}for (int i = 0; i < arr->m_size; i++){//并不知道用户的数据类型，让用户自己提供遍历数组元素的回调函数Foreach_Function(arr->pArr[i]);}return;}//动态数组删除元素根据元素下标int RemoveByIndex_DynamicArray(DynamicArray* arr, int pos){//arr 为NULL 和传入位置非法 返回if (NULL == arr || pos<0 || pos>arr->m_size - 1){return 0;}//将删除位置后面的所有元素往前移一位进行覆盖for (int i = pos; i < arr->m_size - 1; i++){arr->pArr[i] = arr->pArr[i + 1];}arr->m_size--;return 1;}//动态数组删除元素根据元素的值int RemoveByValue_DynamicArray(DynamicArray* arr, void* data, int(*compare)(void* data1, void* data2)){//arr 为NULL 和传入位置非法 返回if (NULL == arr || NULL == arr){return 0;}for (int i = 0; i < arr->m_size; i++){if (compare(arr->pArr[i], data)){RemoveByIndex_DynamicArray(arr, i);break;}}return 1;}//动态数组销毁int Destroy_DynamictArray(DynamicArray* arr){if (NULL == arr){return 0;}if (arr->pArr != NULL){free(arr->pArr);arr->pArr = NULL;}free(arr);arr = NULL;return 1;}
Main.c
#define _CRT_SECURE_NO_WARNINGS#include <stdlib.h>#include <stdio.h>#include <string.h>#include "DynamicArray.h"//使用结构体数据类型 测试动态数组typedef struct Hero{char name[64];int age;}Hero;int Compare_Hero(void* hero1, void* hero2){Hero* h1 = (Hero*)hero1;Hero* h2 = (Hero*)hero2;return h1->age == h2->age && strcmp(h1->name, h2->name) == 0;}void Print_Hero(Hero* hero){if (NULL == hero){return;}printf("name:%s,age:%d\n",hero->name,hero->age);return;}int main(int argc, char *argv[]){Hero h1 = { "关羽",38 };Hero h2 = { "张飞",39 };Hero h3 = { "赵云",29 };Hero h4 = { "许褚",19 };Hero h5 = { "鲁肃",25 };Hero h6 = { "周瑜",27 };DynamicArray* arr = Init_DynamicArray(5);printf("插入数据前动态数组容量:%d\n", arr->m_capacity);InsertByIndex_DynamicArray(arr, &h1, 0);InsertByIndex_DynamicArray(arr, &h2, 0);InsertByIndex_DynamicArray(arr, &h3, 0);InsertByIndex_DynamicArray(arr, &h4, 2);InsertByIndex_DynamicArray(arr, &h5, 100);InsertByIndex_DynamicArray(arr, &h6, 1);Foreach_DynamicArray(arr, Print_Hero);//正确顺序：赵云 周瑜 张飞 许褚 关羽 鲁肃printf("插入数据后动态数组容量:%d\n", arr->m_capacity);printf("删除index = 3的元素\n");RemoveByIndex_DynamicArray(arr, 3);Foreach_DynamicArray(arr, Print_Hero);printf("删除赵云\n");RemoveByValue_DynamicArray(arr, &h3, Compare_Hero);Foreach_DynamicArray(arr, Print_Hero);Destroy_DynamictArray(arr);return 0;}
