数据结构与算法：动态数组（利用万能指针实现任意类型数组操作）

た入场券 2022-05-31 05:51 173阅读 0赞

# 原理介绍 #

**我们利用万能指针来实现动态数组，数组元素类型可以是任意类型，因为我们只维护用户提供的数据的地址，所以可以用万能指针来接受，这样就实现了类似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 - 1
    int 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 - 1
    int 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;
    }

# 运行结果检测 #

![SouthEast][]

[SouthEast]: /images/20220531/32d54fda602b4f348efcb711d856b9df.png