线性表之动态数组

动态数组的初始化

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//动态数组的初始化
struct  dynamicArray 
{
	void** pAddr; //维护真实在堆区开辟的数组的指针
	int capicity; //数组的容量
	int size; //数组大小
};

//初始化数组
dynamicArray* init_Array(int capicity)
{
	if (capicity <= 0)
	{
		return NULL;
	}
	//现在堆区开辟一块空间用来存放动态数组结构体                                      
	dynamicArray* array = (dynamicArray*)malloc(sizeof(dynamicArray));
	if (array == NULL)
	{
		return NULL;
	}
	// 动态数组的开辟空间大小=数据中每个元素的大小*元素的个数
	array->pAddr = (void**)malloc(sizeof(void*)*capicity);
	array->capicity = capicity;
	array->size = 0;
	return array;
}
int main()
{
	dynamicArray* p=init_Array(5);
	printf("动态数组的容量：%d  动态数组的大小:%d", p->capicity, p->size);
	return 0;
}

动态数组插入和遍历功能实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct person {
	char name[32];
	int age;
};
void print(void* data)
{
	person *p = (person*)data;
	printf("姓名:%s\t年龄：%d\n", p->name, p->age);
}
//动态数组的初始化
struct  dynamicArray 
{
	void** pAddr; //维护真实在堆区开辟的数组的指针
	int capicity; //数组的容量
	int size; //数组大小
};

//初始化数组
dynamicArray* init_Array(int capicity)
{
	if (capicity <= 0)
	{
		return NULL;
	}
	//现在堆区开辟一块空间用来存放动态数组结构体                                      
	dynamicArray* array = (dynamicArray*)malloc(sizeof(dynamicArray));
	if (array == NULL)
	{
		return NULL;
	}
	// 动态数组的开辟空间大小=数据中每个元素的大小*元素的个数
	array->pAddr = (void**)malloc(sizeof(void*)*capicity);
	array->capicity = capicity;
	array->size = 0;
	return array;
}

//动态数组插入和遍历功能实现
//参数1：动态数组名 参数2：插入的位置 参数3：插入的数据
void insert_array(dynamicArray* array,int pos,void* data)
{
	if (array == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	//无效位置  尾插
	if(pos<0||pos>array->size)
		{
		pos = array->size;
		}
	//判断动态数组是否处于填满的状态
	//当size大于容量的时候就会报错
	if (array->size == array->capicity)
	{
		//扩大动态数组的容量（每次扩大两倍）
		//需要在堆区开辟一个新的更大的空间来存放之前动态数组的数据
		int newCapicity = array->capicity * 2;
		//开辟一个更大的空间
		void** newSpace = (void**)malloc(sizeof(void*) * newCapicity);
		if (newSpace == NULL)
		{
			return;
		}
		//将原先动态数组里面的数组移至新的动态数组里面
		memcpy(newSpace, array->pAddr, sizeof(void*) * array->capicity);
		//释放原先的动态数组
		free(array->pAddr);
		//将原先的动态数组指向这个新开辟的更大的空间
		array->pAddr = newSpace;
		//更新新的容量
		array->capicity = newCapicity;
	}

	//插入数据
	//移动元素进行插入
	//要从最后一个元素往后移动，防止发生元素覆盖
	for (int i = array->size-1; i >= 0; i--)
	{
		//数据向后移动
		array->pAddr[i+1] = array->pAddr[i];
		//每插入一个数据，更新大小
	}
	//移动元素是为了把要插入的地方空出来
	//移动完后，插入新数据
	array->pAddr[pos] = data;
	//每插入一个数据，数组当前大小加一
	array->size++;
}
//打印动态数组
void print_array(dynamicArray* array,void(*print)(void *))
{
	//对每一个传入的参数都要进行检测
	if (array == NULL)
	{
		return;
	}
	if (print == NULL)
	{
		return;
	}

	for (int i = 0; i < array->size; i++)
	{
		//因为不知道用户传入的数据类型，无法确定该如何打印
		//所以需要用户自己决定打印输出内容
		print(array->pAddr[i]);
	}
}

int main()
{
	dynamicArray* p=init_Array(3);
	printf("未插入元素前动态数组的容量：%d  动态数组的大小:%d\n", p->capicity, p->size);
	person p1 = { "大忽悠",18 };
	person p2 = { "小朋友",19 };
	person p3 = { "大忽悠",20 };
	person p4 = { "大朋友",21 };
	//插入
	insert_array(p, 0, &p1);
	insert_array(p, 0, &p2);
	insert_array(p, 0, &p3);
	insert_array(p, 0, &p4);
	//打印
	print_array(p, print);
	printf("未插入元素前动态数组的容量：%d  动态数组的大小:%d\n", p->capicity, p->size);
	return 0;
}