数据结构---动态数组

 一、数据结构基本理论

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。强调数据元素之间的关系

算法五个特性：
        输入、输出、有穷、确定、可行

数据结构分类：
        逻辑结构：集合、线性结构、树形结构、图形结构

        物理结构：顺序存储、链式存储、索引存储、散列存储(哈希存储)

二、动态数组实现

1.设计

        struct dynamicArray

        属性:
        void ** pAddr  维护真实在堆区创建的数组的指针

        int capacity；  数组容量·
        int m_size；  数组大小

2.动态数组初始化

struct dynamicArray* init_DynamicArray(int capacity);

3.插入数组

void insert_DynamicArray(struct dynamicArray* array, int pos, void* data);

4.遍历数组

void foreach_DynamicArray(struct dynamicArray* array, void(*myPrint)(void*));

5.删除数组

按位置删除

void removeByPos_DynamicArray(struct dynamicArray* array, int pos);

按值删除数据

void removeByValue_DynamicArray(struct dynamicArray* array, void* data, int(*myCompare)(void*, void*));

6.销毁数组

void destroy_DynamicArray(struct dynamicArray* array);

代码如下： 

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

//动态数组结构体
struct dynamicArray
{
	void** pAddr;//维护真实在堆区创建的数组的指针
	
	int m_capacity;//数组容量

	int m_size;//数组大小
};

//初始化数组
struct dynamicArray* init_DynamicArray(int capacity)
{
	if (capacity <= 0)
	{
		return NULL;
	}
	//给数组分配空间
	struct dynamicArray* array = malloc(sizeof(struct dynamicArray));
	if (array == NULL)
	{
		return NULL;
	}

	array->pAddr = malloc(sizeof(void*) * capacity);
	array->m_capacity = capacity;
	array->m_size = 0;

	return array;
};

//插入数据
void insert_DynamicArray(struct dynamicArray *array,int pos,void *data)
{
	if (array == NULL) 
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	//无效位置	尾插
	if (pos < 0 || pos > array->m_size)
	{
		pos = array->m_size;
	}

	//判断是否满了，如果满了动态扩展
	if (array->m_size == array->m_capacity)
	{
		//1.申请更大的内存空间
		int newCapacity = array->m_capacity * 2;

		//2.创建空间
		void** newSpace = malloc(sizeof(void*) * newCapacity);

		//3.将原有的数据拷贝到新空间下
		memcpy(newSpace, array->pAddr, sizeof(void*) * array->m_capacity);

		//4.释放原有内存空间
		free(array->pAddr);

		//5.更新新空间指向
		array->pAddr = newSpace;

		//6.更新新容量
		array->m_capacity = newCapacity;
	}

	//插入新元素
	//移动元素	进行插入新元素 
	for (int i = array->m_size - 1; i >= pos; i--)
	{
		//数据向后移动
		array->pAddr[i + 1] = array->pAddr[i];
	}
	//将新元素插入到指定位置上
	array->pAddr[pos] = data;

	//更新大小
	array->m_size++;
};

//遍历数组
void foreach_DynamicArray(struct dynamicArray* array,void(*myPrint)(void *))
{
	if (array == NULL)
	{
		return;
	}
	if (myPrint == NULL)
	{
		return;
	}
	for (int i = 0; i < array->m_size; i++)
	{
		myPrint(array->pAddr[i]);
	}
}

//删除数组	按位置删除
void removeByPos_DynamicArray(struct dynamicArray * array, int pos)
{
	if (NULL == array)
	{
		return;
	}
	if (pos < 0 || pos > array->m_size - 1)
	{
		return;
	}

	//数据前移
	for (int i = pos; i < array->m_size - 1; i++)
	{
		array->pAddr[i] = array->pAddr[i + 1];
	}

	//更新数组大小
	array->m_size--;

}	

//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray *array,void *data,int(* myCompare)(void *,void *))
{
	if (array == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	for (int i = 0; i < array->m_size; i++)
	{
		if (myCompare(array->pAddr[i], data))
		{
			//如果找到要删除的数据,i就是要删除的具体位置
			removeByPos_DynamicArray(array, i);
			break;
		}
	}
}

//销毁数组
void destroy_DynamicArray(struct dynamicArray* array)
{
	if (array == NULL)
	{
		return;
	}
	if (array->pAddr != NULL)
	{
		free(array->pAddr);
		array->pAddr = NULL; 
	}

	free(array);
	array = NULL;
}




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

void myPrintPerson(void* data)
{
	struct Person* p = data;
	printf("姓名：%s 年龄：%d\n", p->name, p->age);
}

int myComparePerson(void *data1, void *data2)
{
	struct Person* p1 = data1;
	struct Person* p2 = data2;

	return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}
int main()
{
	//初始化动态数组
	struct dynamicArray* array = init_DynamicArray(5);

	//准备数据
	struct Person p1 = { "亚瑟",18 };
	struct Person p2 = { "妲己",20 };
	struct Person p3 = { "安其拉",19 };
	struct Person p4 = { "凯",21 };
	struct Person p5 = { "孙悟空",999 };
	struct Person p6 = { "李白",999 };

	printf("插入数据前容量：%d 大小：%d\n", array->m_capacity, array->m_size);

	//插入数据
	insert_DynamicArray(array, 0, &p1);
	insert_DynamicArray(array, 0, &p2);
	insert_DynamicArray(array, 1, &p3);
	insert_DynamicArray(array, 0, &p4);
	insert_DynamicArray(array, -1, &p5);
	insert_DynamicArray(array, 2, &p6);

	//凯  妲己  李白  安其拉  亚瑟  孙悟空

	//遍历数组
	foreach_DynamicArray(array, myPrintPerson);

	printf("插入数据后容量：%d 大小：%d\n", array->m_capacity, array->m_size);
	

	//测试删除	按位置删除
	removeByPos_DynamicArray(array, 2);
	printf("-------------------\n");
	foreach_DynamicArray(array, myPrintPerson);
	printf("删除数据后容量：%d 大小：%d\n", array->m_capacity, array->m_size);


	struct Person p = { "亚瑟",18 };
	removeByValue_DynamicArray(array, &p,myComparePerson);
	printf("-------------------\n");
	foreach_DynamicArray(array, myPrintPerson);
	printf("删除数据后容量：%d 大小：%d\n", array->m_capacity, array->m_size);

	//销毁数组
	destroy_DynamicArray(array);
	array = NULL;

	return 0;
}

三、实现分文件编写 

dynamicArray.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS  
#include<stdio.h>
#include<string.h>
#include<stdlib.h>


//动态数组结构体
struct dynamicArray
{
	void** pAddr;//维护真实在堆区创建的数组的指针

	int m_capacity;//数组容量

	int m_size;//数组大小
};

//初始化数组
struct dynamicArray* init_DynamicArray(int capacity);


//插入数据
void insert_DynamicArray(struct dynamicArray* array, int pos, void* data);



//遍历数组
void foreach_DynamicArray(struct dynamicArray* array, void(*myPrint)(void*));


//删除数组	按位置删除
void removeByPos_DynamicArray(struct dynamicArray* array, int pos);


//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray* array, void* data, int(*myCompare)(void*, void*));


//销毁数组
void destroy_DynamicArray(struct dynamicArray* array);

dynamicArray.c

#include"dynamicArray.h"


//初始化数组
struct dynamicArray* init_DynamicArray(int capacity)
{
	if (capacity <= 0)
	{
		return NULL;
	}
	//给数组分配空间
	struct dynamicArray* array = malloc(sizeof(struct dynamicArray));
	if (array == NULL)
	{
		return NULL;
	}

	array->pAddr = malloc(sizeof(void*) * capacity);
	array->m_capacity = capacity;
	array->m_size = 0;

	return array;
};

//插入数据
void insert_DynamicArray(struct dynamicArray *array,int pos,void *data)
{
	if (array == NULL) 
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	//无效位置	尾插
	if (pos < 0 || pos > array->m_size)
	{
		pos = array->m_size;
	}

	//判断是否满了，如果满了动态扩展
	if (array->m_size == array->m_capacity)
	{
		//1.申请更大的内存空间
		int newCapacity = array->m_capacity * 2;

		//2.创建空间
		void** newSpace = malloc(sizeof(void*) * newCapacity);

		//3.将原有的数据拷贝到新空间下
		memcpy(newSpace, array->pAddr, sizeof(void*) * array->m_capacity);

		//4.释放原有内存空间
		free(array->pAddr);

		//5.更新新空间指向
		array->pAddr = newSpace;

		//6.更新新容量
		array->m_capacity = newCapacity;
	}

	//插入新元素

	//移动元素	进行插入新元素 
	for (int i = array->m_size - 1; i >= pos; i--)
	{
		//数据向后移动
		array->pAddr[i + 1] = array->pAddr[i];
	}
	//将新元素插入到指定位置上
	array->pAddr[pos] = data;

	//更新大小
	array->m_size++;
};

//遍历数组
void foreach_DynamicArray(struct dynamicArray* array,void(*myPrint)(void *))
{
	if (array == NULL)
	{
		return;
	}
	if (myPrint == NULL)
	{
		return;
	}
	for (int i = 0; i < array->m_size; i++)
	{
		myPrint(array->pAddr[i]);
	}
}

//删除数组	按位置删除
void removeByPos_DynamicArray(struct dynamicArray * array, int pos)
{
	if (NULL == array)
	{
		return;
	}
	if (pos < 0 || pos > array->m_size - 1)
	{
		return;
	}

	//数据前移
	for (int i = pos; i < array->m_size - 1; i++)
	{
		array->pAddr[i] = array->pAddr[i + 1];
	}

	//更新数组大小
	array->m_size--;

}	

//按值删除数据
void removeByValue_DynamicArray(struct dynamicArray *array,void *data,int(* myCompare)(void *,void *))
{
	if (array == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	for (int i = 0; i < array->m_size; i++)
	{
		if (myCompare(array->pAddr[i], data))
		{
			//如果找到要删除的数据,i就是要删除的具体位置
			removeByPos_DynamicArray(array, i);
			break;
		}
	}
}

//销毁数组
void destroy_DynamicArray(struct dynamicArray* array)
{
	if (array == NULL)
	{
		return;
	}
	if (array->pAddr != NULL)
	{
		free(array->pAddr);
		array->pAddr = NULL; 
	}

	free(array);
	array = NULL;
}

测试：

#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 myPrintPerson(void* data)
{
	struct Person* p = data;
	printf("姓名：%s 年龄：%d\n", p->name, p->age);
}

int myComparePerson(void *data1, void *data2)
{
	struct Person* p1 = data1;
	struct Person* p2 = data2;

	return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}
int main()
{
	//初始化动态数组
	struct dynamicArray* array = init_DynamicArray(5);

	//准备数据
	struct Person p1 = { "亚瑟",18 };
	struct Person p2 = { "妲己",20 };
	struct Person p3 = { "安其拉",19 };
	struct Person p4 = { "凯",21 };
	struct Person p5 = { "孙悟空",999 };
	struct Person p6 = { "李白",999 };

	printf("插入数据前容量：%d 大小：%d\n", array->m_capacity, array->m_size);

	//插入数据
	insert_DynamicArray(array, 0, &p1);
	insert_DynamicArray(array, 0, &p2);
	insert_DynamicArray(array, 1, &p3);
	insert_DynamicArray(array, 0, &p4);
	insert_DynamicArray(array, -1, &p5);
	insert_DynamicArray(array, 2, &p6);

	//凯  妲己  李白  安其拉  亚瑟  孙悟空

	//遍历数组
	foreach_DynamicArray(array, myPrintPerson);

	printf("插入数据后容量：%d 大小：%d\n", array->m_capacity, array->m_size);
	

	//测试删除	按位置删除
	removeByPos_DynamicArray(array, 2);
	printf("-------------------\n");
	foreach_DynamicArray(array, myPrintPerson);
	printf("删除数据后容量：%d 大小：%d\n", array->m_capacity, array->m_size);


	struct Person p = { "亚瑟",18 };
	removeByValue_DynamicArray(array, &p,myComparePerson);
	printf("-------------------\n");
	foreach_DynamicArray(array, myPrintPerson);
	printf("删除数据后容量：%d 大小：%d\n", array->m_capacity, array->m_size);

	//销毁数组
	destroy_DynamicArray(array);
	array = NULL;

	return 0;
}