[数据结构与算法]c语言实现动态数组

动态数组是一种比较常用的集合类，其相对于普通数组的优势是可以自动增容，相对于链表的优势是可以下标访问。

首先设计接口：

1、数据结构如下：

#include<stdint.h>
/// <summary>
/// 数组对象
/// </summary>
typedef struct	 {
	//元素个数
	size_t count;
	//容量
	size_t capacity;
	//元素大小
	size_t elementSize;
	//数据
	uint8_t* _array;
}acf_array;

2、函数：

/// <summary>
/// 初始化
///elementSize默认为指针长度
/// </summary>
/// <param name="array">需要初始化的数组对象</param>
/// <returns></returns>
 void acf_array_init(acf_array* array);
/// <summary>
/// 初始化
/// </summary>
/// <param name="array">需要初始化的数组对象</param>
/// <param name="elementSize">元素的大小</param>
/// <returns></returns>
 void acf_array_init2(acf_array* array, size_t elementSize);
/// <summary>
/// 初始化
/// </summary>
/// <param name="array">需要初始化的数组对象</param>
/// <param name="elementSize">拷贝的数组对象</param>
/// <returns></returns>
 void acf_array_init_from_copy(acf_array* ,const acf_array*);
/// <summary>
/// 返初始化
/// </summary>
/// <param name=""></param>
/// <returns></returns>
 void acf_array_deinit(acf_array* );
/// <summary>
/// 添加元素,通过指针的方式
/// </summary>
/// <param name="array">数组对象</param>
/// <param name="pItem">元素地址指针，需确保元素值长度大于等于elementSize</param>
/// <returns></returns>
 void acf_array_add_ptr(acf_array* array, void* pItem);
/// <summary>
/// 插入元素,通过指针的方式
/// </summary>
/// <param name="array">数组对象</param>
/// <param name="index">插入的下标</param>
/// <param name="pItem">元素地址指针，需确保元素值长度大于等于elementSize</param>
/// <returns></returns>
 void acf_array_insert_ptr(acf_array* array, size_t index, void* pItem);
/// <summary>
/// 移除元素
/// </summary>
/// <param name="array">数组对象</param>
/// <param name="index">需要移除的元素下标</param>
/// <returns></returns>
 void acf_array_remove_at(acf_array* array, size_t index);
/// <summary>
/// 获取元素
/// </summary>
/// <param name="array"><数组对象/param>
/// <param name="index">元素下标</param>
/// <returns>元素的指针</returns>
 void* acf_array_get_ptr_at(acf_array* array, size_t index);
/// <summary>
/// 翻转元素
/// </summary>
/// <param name="array">数组对象</param>
/// <returns></returns>
 void acf_array_reverse(acf_array* array);
/// <summary>
/// 清除元素
/// </summary>
/// <param name=""><array/param>
/// <returns></returns>
 void acf_array_clear(acf_array* array);

关键实现：

1、动态增容

数组的长度是可以根据实际变化的，当加入的新数据大于当前数组长度时，就需要申请一块新的内存，把原来的数据拷贝过去然后再加入新的数据，数组长度是以倍增的方式增长的。具体实现如下：

static void ensure_capacity(acf_array* _this) {
	if (_this->count == _this->capacity)
	{
		_this->capacity = _this->count == 0 ? 4 : _this->count * 2;
		if (!_this->_array)
		{
			_this->_array = malloc(_this->elementSize * _this->capacity);
		}
		else
		{
			_this->_array = realloc(_this->_array, _this->elementSize * _this->capacity);
		}
	}
}

2、插入

插入元素的时候需要，将插入位置后面的所有元素向后移动，然后再将元素插入相应位置：

 void acf_array_insert_ptr(acf_array* _this, size_t index, void* ptr)
{
	ensure_capacity(_this);
	if (index < _this->count)
	{
		memmove(_this->_array + (index + 1) * _this->elementSize, _this->_array + index * _this->elementSize, (_this->count - index) * _this->elementSize);
	}
	memcpy(_this->_array + index* _this->elementSize, ptr, _this->elementSize);
	_this->count++;
}

3、移除

移除元素的时候需要，将移除位置后面的所有元素向前移动

 void acf_array_remove_at(acf_array* _this, size_t index)
{
	_this->count--;
	if (index < _this->count) {
		memmove(_this->_array + index * _this->elementSize, _this->_array + (index + 1) * _this->elementSize, (_this->count - index) * _this->elementSize);
	}
}

使用例子：

1、整型：

extern"C" {
#include"acf_array.h"
}



int main()
{
	//初始化
	acf_array  arr1;
	acf_array_init2(&arr1, sizeof(int));

	//添加元素
	for (int i = 0; i < 500; i++)
		acf_array_add_ptr(&arr1, &i);

	//插入元素
	int d = 10;
	acf_array_insert_ptr(&arr1, 2, &d);

	//移除元素
	acf_array_remove_at(&arr1, 1);

	//遍历1
	for (int i = 0; i < arr1.count; i++)
	{
		int* p = (int*)acf_array_get_ptr_at(&arr1, i);
		printf("%d ", *p);
	}
	//遍历2
	int* array = (int*)arr1._array;
	for (int i = 0; i < arr1.count; i++)
	{
		printf("%d ", array[i]);
	}
	//反初始化
	acf_array_deinit(&arr1);
    return 0;
}

2、指针：

extern"C" {
#include"acf_array.h"
}

typedef struct
{
	int num;
}A;
int main()
{
//初始化
	acf_array  arr2;
	acf_array_init2(&arr2, sizeof(A*));
	//添加元素
	for (int i = 0; i < 500; i++)
	{
		A* a = (A*)malloc(sizeof(A));
		a->num = i;		
		acf_array_add_ptr(&arr2, &a);


	}
	//插入元素
	A* a2 = (A*)malloc(sizeof(A));
	a2->num = 1024;
	acf_array_insert_ptr(&arr2, 2, &a2);
	
	//移除元素
	//移除前释放内存
	A** pA = (A**)acf_array_get_ptr_at(&arr2, 1);
	free(*pA);
	acf_array_remove_at(&arr2, 1);

	//遍历1
	for (int i = 0; i < arr2.count; i++)
	{
		A** p = (A**)acf_array_get_ptr_at(&arr2, i);
		printf("%d ", (*p)->num);
	}
	//遍历2
	A** array2 = (A**)arr2._array;
	for (int i = 0; i < arr2.count; i++)
	{
		printf("%d ", array2[i]->num);
	}

	//反初始化前将元素指向的内容释放以免造成内存泄露
	for (int i = 0; i < arr2.count; i++)
	{
		free(array2[i]);
	}
	//反初始化
	acf_array_deinit(&arr2);
    return 0;
}

3、结构体：

extern"C" {
#include"acf_array.h"
}

typedef struct
{
	int num;
}A;

int main()
{	
    //初始化
	acf_array  arr3;
	acf_array_init2(&arr3, sizeof(A));
	//添加元素
	for (int i = 0; i < 500; i++)
	{
		A a ;
		a.num = i;
		acf_array_add_ptr(&arr3, &a);
	}
	//插入元素
	A a3;
	a3.num = 1024;
	acf_array_insert_ptr(&arr3, 2, &a2);

	//移除元素
	acf_array_remove_at(&arr3, 1);

	//遍历1
	for (int i = 0; i < arr3.count; i++)
	{
		A* p = (A*)acf_array_get_ptr_at(&arr3, i);
		printf("%d ", p->num);
	}
	//遍历2
	A* array3 = (A*)arr3._array;
	for (int i = 0; i < arr3.count; i++)
	{
		printf("%d ", array3[i].num);
	}

	//反初始化
	acf_array_deinit(&arr3);

	return 0;
}

详细代码：

https://download.csdn.net/download/u013113678/21833678