C语言数据结构一：动态数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言数据结构一：动态数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、概念认知

先说一个概念：数组是一段连续的内存空间。存储相同的数据类型。

数组的两个关键点：

连续内存；

相同类型。

第一个特征：起点。

首先连续内存：所以为了找到动态数组我们必须找到一个首元素地址。（内存首地址。）

如果不知道首地址，那无法找到并操作内存空间。

第二个特征：容量。

知道首地址了，我们需要知道元素的个数。动态数组：动态，可以动态插入、删除、扩展容量。所以我们必须有个初始容量。开辟多大空间，放多少个元素。除了容量，最好还有一个状态量：表示当前的数据量：也就是说长度。

容量说的是：可以放多少数据。

长度说的是：当前有多少数据。

我的钱包（=银行）（容量）无限大，而我当前拥有的钱有限（长度）。

第三个特征：类型。

我们虽然有了首地址，也有了元素个数，但是我们还是不知道开辟多大空间。因为我们还需要元素的大小。元素所占内存的大小，其实就是元素的类型。可是：

C语言无法动态获取数据的类型。

好在我们还有void*类型可以指向任意类型的指针。

所以我们虽然不知道具体元素的类型，但是我们可以定义一个通用的指针类型，指向我们的元素的地址即可。所以我们的元素就是地址。

所以我们的元素类型就是void*。所以我们的数组指针就是void**类型。

二、实现

动态数组其实就是一种结构体。一种自定义类型。

2.1定义数据结构。

先写数据信息结构。

首地址，就像存储字符串数组一样。

char * arr[] = {"aaa", "bbb", "ccc"};

arr数组中每个元素都是char*类型，那么arr如果写入结构体中，可以定义为：

struct DemoStruct
{
    char ** arr;
    int b;
}

同样道理：元素类型为void*。那么定义数组则为void** arr；

//1. 先把所需要的数据信息结构定义下来
struct DynamicArray
{
	//数组存储元素的空间的首地址
	void **addr;
	//存储数据的内存中最大能够容纳多少元素
	int capacity; //容量
	//当前存储数据的内存中有多少个元素
	int size; //大小
};

2.2 头文件

#pragma once

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

#ifdef __cplusplus
extern "C"{
#endif

	//1. 先把所需要的数据信息结构定义下来
	struct DynamicArray
	{
		//数组存储元素的空间的首地址
		void **addr;
		//存储数据的内存中最大能够容纳多少元素
		int capacity; //容量
		//当前存储数据的内存中有多少个元素
		int size; //大小
	};

	//初始化数组
	struct DynamicArray *Init_DynamicArray(int capacity);
	//插入元素
	void Insert_DynamicArray(struct DynamicArray *arr, int pos, void *data);
	//遍历
	void Foreach_DynamicArray(struct DynamicArray *arr, void(*_callback)(void *));
	//位置删除
	void RemoveByPos_DynamicArray(struct DynamicArray *arr, int pos);
	//按值删除
	void RemoveByValue_DynamicArray(struct DynamicArray *arr, void *data, int(*compare)(void*, void *));
	//销毁数组
	void Destroy_DynamicArray(struct DynamicArray *arr);

#ifdef __cplusplus
}
#endif

头文件中，我们要写入关于这个数组结构体的一些方法声明，然后去.c源文件中去实现。

2.3初始化

首先是初始化数组。给数组分配内存，也就是给这个结构体分配内存。

我们的动态数组初始化也是：struct DynamicArray * arr = malloc(sizeof(struct DynamicArray));

arr这个指针指向这个数组的结构体：即动态数组。

动态数组其实就是一种结构体。

然后这个结构体的一个属性：首地址：首地址指向整个数组地址。为整个数组开辟空间。就像是char * arr = malloc(sizeof(char*)*Num)一样操作。

arr->addr = malloc（sizeof(元素类型)* Num）;这里Num为Capacity。元素类型为void*由使用方指定。

arr->addr = malloc(sizeof(void*)*arr->capacity);

此时没有插入值，所以size为零。

//初始化数组
struct DynamicArray *Init_DynamicArray(int capacity)
{
	if (capacity <= 0)
	{
		return NULL;
	}

	struct DynamicArray *arr = malloc(sizeof(struct DynamicArray));
	if (NULL == arr)
	{
		return NULL;
	}
	arr->capacity = capacity;
	arr->addr = malloc(sizeof(void *)*arr->capacity);
	arr->size = 0;

	return arr;
}

2.4插入元素

此时注意我们输入函数的是结构体指针。

//插入元素
void Insert_DynamicArray(struct DynamicArray *arr, int pos, void *data)
{

	if (NULL == arr)
	{
		return;
	}

	if (NULL == data)
	{
		return;
	}

	if (pos < 0 || pos > arr->size)
	{
        // 如果插入时，pos大于当前的长度，则直接把数据放在数组最后面。
		pos = arr->size;
	}

	//判断空间是否足够
	if (arr->size >= arr->capacity)
	{

		//1. 申请一块更大的内存空间
		int newcapacity = arr->capacity * 2;   // C#中动态数组也是如此操作的。
		void **newspace = malloc(sizeof(void *)* newcapacity);

		//2. 将原来空间的数据拷贝到新空间
		memcpy(newspace, arr->addr, sizeof(void *)* arr->capacity);

		//3. 释放原来空间的内存
		free(arr->addr);

		//4. 更新addr指向
		arr->addr = newspace;
		arr->capacity = newcapacity;

	}


	//移动元素，给pos位置空出位置来
	for (int i = arr->size - 1; i >= pos; --i)
	{
		arr->addr[i + 1] = arr->addr[i];
	}

	//将新元素插入到pos位置
	arr->addr[pos] = data;
	arr->size++;
}

2.5遍历查看

遍历时，我们不知道元素的内部结构（数据结构），所以这个打印查看函数，需要使用方提供，

使用方调用我们这个方法，我们这个方法反向回调使用方的提供的函数。因为我们不知道使用方使用什么类型，使用方自己知道如何打印自己的数据结构（数据信息）。

回调函数定义方法：

返回值类型（*回调函数名称）（参数列表）

//遍历
void Foreach_DynamicArray(struct DynamicArray *arr, void(*_callback)(void *))
{
	if (NULL == arr)
	{
		return;
	}

	if (NULL == _callback)
	{
		return;
	}

	for (int i = 0; i < arr->size; ++i)
	{
		_callback(arr->addr[i]);
	}


}

2.6删除

//位置删除
void RemoveByPos_DynamicArray(struct DynamicArray *arr, int pos)
{

	if (NULL == arr)
	{
		return;
	}

	if (pos < 0 || pos > arr->size - 1)
	{
		return;
	}


	for (int i = pos; i < arr->size - 1; ++i)
	{
		arr->addr[i] = arr->addr[i + 1];
	}


	arr->size--;
}

//按值删除
void RemoveByValue_DynamicArray(struct DynamicArray *arr, void *data, int(*compare)(void*, void *))
{
	if (NULL == arr)
	{
		return;
	}

	if (NULL == data)
	{
		return;
	}

	if (NULL == compare)
	{
		return;
	}


	for (int i = 0; i < arr->size; ++i)
	{
		if (compare(arr->addr[i], data))
		{
			RemoveByPos_DynamicArray(arr, i);
			break;
		}
	}

}

2.7销毁

//销毁数组
void Destroy_DynamicArray(struct DynamicArray *arr)
{
	if (NULL == arr)
	{
		return;
	}

	if (arr->addr != NULL)
	{
		free(arr->addr);
		arr->addr = NULL;
	}

	free(arr);
	arr = NULL;
}

原则上，谁molloc的，谁free，但是具体元素数据指向哪里，我们并不知道，且使用方知道，使用方也必须开辟，使用方开辟，那就由使用方释放。我们只free我们自己开辟的，开辟从外到内，释放是从内到外：先释放内部属性的指针：arr->addr的内存，然后再释放整个结构体指针。

使用方测试：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"DynamicArray.h"


struct Person
{
	char name[64];
	int age;
};

void myPrint(void *data)
{
	struct Person *person = (struct Person *)data;
	printf("Name:%s Age:%d\n", person->name,person->age);
}

int myCompare(void *d1,void *d2)
{
	struct Person *p1 = (struct Person *)d1;
	struct Person *p2 = (struct Person *)d2;

	return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}


void test()
{
	//创建动态数组
	struct DynamicArray *da = Init_DynamicArray(5);
	//动态数组添加元素
	struct Person p1 = { "aaa", 10 };
	struct Person p2 = { "bbb", 20 };
	struct Person p3 = { "ccc", 30 };
	struct Person p4 = { "ddd", 40 };
	struct Person p5 = { "eee", 50 };
	struct Person p6 = { "fff", 60 };
	
	Insert_DynamicArray(da, 0, &p1);
	Insert_DynamicArray(da, 0, &p2);
	Insert_DynamicArray(da, 0, &p3);
	Insert_DynamicArray(da, 1, &p4);
	Insert_DynamicArray(da, 1, &p5);

	printf("capacity:%d\n",da->capacity);
	Insert_DynamicArray(da, 100, &p6);  //3 5 4 2 1 6
	printf("capacity:%d\n", da->capacity);

	Foreach_DynamicArray(da, myPrint);

	printf("---------------\n");
	RemoveByPos_DynamicArray(da,2);//3 5 2 1 6
	Foreach_DynamicArray(da, myPrint);

	printf("---------------\n");
	struct Person pDel = { "aaa", 10 };
	RemoveByValue_DynamicArray(da, &pDel, myCompare);

	//da->addr = NULL;

	Foreach_DynamicArray(da, myPrint);

	//销毁
	Destroy_DynamicArray(da);
}

int main(){

	test();

	system("pause");
	return EXIT_SUCCESS;
}