泛型动态数组.jpg
泛型实现思路：万能指针void *
动态数组实现思路：动态进行数组内存的扩容 realloc
泛型动态数组
数组可以存放C语言中任意数据类型的数据，包括自定义的结构体数据，数组容量会自动动态分配。
注:本文使用的IDE为Xcode,若别的IDE运行有问题，请自行稍加修改。
附上源码: 泛型动态数组源码
https://github.com/chenfanfang/data_structure
array.h 头文件
//
// array.h
// data_structure
//
// Created by chenfanfang on 2019/8/27.
// Copyright © 2019 chenfanfang. All rights reserved.
//
#ifndef array_h
#define array_h
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct array array;
//创建数组、bytes_per_element_point：数组中需要存放元素指针的大小 单位为 Byte
array *array_create(void);
//判断数组是否为空数组
bool array_is_empty(array *arr);
//获取数组的长度
int array_length(array *arr);
//获取数组中指定下标的元素
void *array_get_value_of_index(array *arr, int index);
//获取数组中第一个元素
void *array_get_first_value(array *arr);
//获取数组中最后一个元素
void *array_get_last_value(array *arr);
//往数组中添加元素【添加至尾部】
void array_add_value(array *arr, void *const data);
//往数组中指定位置插入元素
void array_insert_value_at_index(array *arr, int index, void *const data);
//移除数组中指定位置的元素
void array_remove_at_index(array *arr, int index);
//销毁数组、释放内存
void array_destroy(array *arr);
#endif /* array_h */
array.c 函数实现
//
// array.c
// data_structure
//
// Created by chenfanfang on 2019/8/27.
// Copyright © 2019 chenfanfang. All rights reserved.
//
#include "array.h"
#include <assert.h>
#include <stdbool.h>
#include <string.h>
struct array{
unsigned int capacity; //数组的容量，不够可以自动进行扩容
unsigned int length; //当前数组中拥有数据的个数
void **elements;
};
//判断数组是否需要扩容
void array_judge_capacity_is_enough(array *arr) {
if (arr->length == arr->capacity) {
arr->capacity = arr->capacity * 1.5;
arr->elements = realloc(arr->elements, arr->capacity * sizeof(void *));
}
}
//判断下标的合法性
void array_check_index(array *arr, int index) {
if (index < 0 || index > arr->length - 1) {
if (arr->length == 0) {
printf("\n\n空数组越界:index:%d\n\n",index);
}
else {
printf("\n\n数组越界 index:%d range:[0 %d]\n\n",index, arr->length - 1);
}
assert(false);
}
}
array *array_create(void) {
array *array = calloc(1, sizeof(array));
array->capacity = 10;
array->length = 0;
array->elements = calloc(array->capacity, sizeof(void *));
return array;
}
bool array_is_empty(array *arr) {
return arr->length == 0;
}
int array_length(array *arr) {
return arr->length;
}
void *array_get_value_of_index(array *arr, int index) {
array_check_index(arr, index);
return arr->elements[index];
}
void *array_get_first_value(array *arr) {
return array_get_value_of_index(arr, 0);
}
void *array_get_last_value(array *arr) {
return array_get_value_of_index(arr, arr->length - 1);
}
void array_add_value(array *arr, void *const data) {
array_insert_value_at_index(arr, arr->length, data);
}
void array_insert_value_at_index(array *arr, int index, void *const data) {
array_judge_capacity_is_enough(arr);
if (index != arr->length) {
array_check_index(arr, index);
}
arr->length = arr->length + 1;
for (int i = arr->length - 1; i > index; i--) {
arr->elements[i] = arr->elements[i - 1];
}
arr->elements[index] = data;
}
void array_remove_at_index(array *arr, int index) {
array_check_index(arr, index);
void *element = arr->elements[index];
free(element);
for (int i = index; i < arr->length - 1; i++) {
arr->elements[i] = arr->elements[i + 1];
}
arr->length = arr->length - 1;
}
void array_destroy(array *arr) {
for (int i = 0; i < arr->length; i++) {
free(arr->elements[i]);
}
free(arr->elements);
free(arr);
}
测试用例1
//测试：数组存放自定义结构体
void test_array_struct(void) {
struct custom_data {
int value;
};
size_t custom_data_size = sizeof(struct custom_data);
array *arr = array_create();
//=======================
// 添加元素
//=======================
for (int i = 0; i < 21; i++) {
struct custom_data *data = malloc(custom_data_size);
data->value = i;
array_add_value(arr, data);
}
//0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、
//=======================
// 插入元素
//=======================
struct custom_data *insert_data = malloc(custom_data_size);
insert_data->value = 999;
array_insert_value_at_index(arr, 1, insert_data);
// 0、999、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20
//=======================
// 移除元素
//=======================
array_remove_at_index(arr, 0);
//999、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20
//=======================
// 获取元素
//=======================
printf("test_array_struct\n\n");
for (int i = 0; i < array_length(arr); i++) {
struct custom_data *data = array_get_value_of_index(arr, i);
printf("%d、",data->value);
}
printf("\n\n");
array_destroy(arr);
}
测试用例2
//测试：数组存放基本数据类型 int
void test_array_int(void) {
size_t int_size = sizeof(int);
array *arr = array_create();
//=======================
// 添加元素
//=======================
for (int i = 0; i < 21; i++) {
int *data = malloc(int_size);
*data = i;
array_add_value(arr, data);
}
//0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、
//=======================
// 插入元素
//=======================
int *insert_data = malloc(int_size);
*insert_data = 999;
array_insert_value_at_index(arr, 1, insert_data);
// 0、999、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20
//=======================
// 移除元素
//=======================
array_remove_at_index(arr, 0);
//999、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20
//=======================
// 获取元素
//=======================
printf("test_array_int\n\n");
for (int i = 0; i < array_length(arr); i++) {
int *data = array_get_value_of_index(arr, i);
printf("%d、",*data);
}
printf("\n\n");
array_destroy(arr);
}
网友评论