数据结构与算法_C语言动态数组案例

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

typedef struct __DYNAMICARR
{
	void**m_data;
	int m_capacity;
	int m_size;
}DynamicArr;

//初始化动态数组
DynamicArr*init_DyArr(int capacity)
{
	DynamicArr*p = malloc(sizeof(DynamicArr));
	if (p==NULL)
	{
		return NULL;
	}
	p->m_data = malloc(sizeof(void*)*capacity);
	p->m_capacity = capacity;
	p->m_size = 0;
}

//插入数据
void insert_DyArr(DynamicArr*p, void*data, int pos )
{
	if (p==NULL||data==NULL)
	{
		return;
	}
	//如果插入位置输入无效,或者不合法,则在尾部插入数据
	if (pos<0||pos>=p->m_size)
	{
		pos = p->m_size;
	}
	//如果数组大小与容量相等,开辟更大空间,扩大容量,并将原始数据全部拷贝过来
	if (p->m_size==p->m_capacity)
	{
		int newCapacity = p->m_capacity * 1.5;
		void**newSpace = malloc(sizeof(void*)*newCapacity);
		memcpy(newSpace, p->m_data, sizeof(void*)*p->m_capacity);
		free(p->m_data);
		p->m_data = newSpace;
		p->m_capacity = newCapacity;
	}
	//插入数据
	if (p->m_size > 0)
	{
		for (int i = p->m_size - 1; i >= pos; i--)
		{
			p->m_data[i + 1] = p->m_data[i];
		}
	}
	p->m_data[pos] = data;
	p->m_size++;
}

//遍历数据
void print_DyArr(DynamicArr*p,void(*callback)(void*))
{
	if (p==NULL)
	{
		return;
	}
	for (int i = 0; i < p->m_size;i++)
	{
		callback(p->m_data[i]);
	}
}

void print_DyArr_Msg(DynamicArr*p)
{
	if (p==NULL)
	{
		return;
	}
	printf("当前数组大小:%d\t当前数组容量:%d\n", p->m_size, p->m_capacity);
}

//动态数组删除功能
//第一种,byPos
void rmovByPos_DyArr(DynamicArr*p,int pos)
{
	if (p==NULL)
	{
		return;
	}
	if (pos<0||pos>=p->m_size)		//无法找到该位置时,直接返回
	{
		return;
	}
	for (int i = pos+1;i<p->m_size;i++ )
	{
		//启始位置为pos+1
		p->m_data[i - 1] = p->m_data[i];
	}
	p->m_size--;
}
//第二种,byValue
void rmovByValue_DyArr(DynamicArr*p, void*data,int (*cmp)(void*,void*))
{
	if (p == NULL)
	{
		return;
	}
	for (int i = 0 ; i < p->m_size ; i++)
	{
		if (cmp(p->m_data[i],data))
		{
			rmovByPos_DyArr(p, i);
			return;
		}
	}
}

//销毁数组
void destroy_DyArr(DynamicArr**p)
{
	if ((*p)->m_data!=NULL)
	{
		free((*p)->m_data);
		(*p)->m_data = NULL;
	}
	free(*p);
	*p = NULL;
}

/*--------------------------------用户区-----------------------------*/
//设计一个结构体
typedef struct __HERO
{
	char name[64];
	int attack;
}Hero;

//打印函数
void print_Hero(void*data)
{
	Hero*p = (Hero*)data;
	printf("%s\t%d\n", p->name, p->attack);
}

//比较数据
int cmp_Hero(void*data1,void*data2)
{
	Hero*h1 = (Hero*)data1;
	Hero*h2 = (Hero*)data2;
	return (strcmp(h1->name, h2->name) == 0);
}

//测试函数
void test()
{
	Hero h1 = { "张飞",85 };
	Hero h2 = { "赵云",95 };
	Hero h3 = { "刘备",78 };
	Hero h4 = { "关羽",93 };
	Hero h5 = { "曹操",81 };
	Hero h6 = { "孙权",72 };
	Hero h[3] = 
	{
		{ "孙尚香",77 },
		{ "大乔",65 },
		{ "黄盖",85 }
	};
	DynamicArr * p = init_DyArr(5);
	print_DyArr_Msg(p);

	insert_DyArr(p, &h1, 10);
	insert_DyArr(p, &h2, 0);
	insert_DyArr(p, &h3, 0);
	insert_DyArr(p, &h4, 0);
	insert_DyArr(p, &h5, 1);
	insert_DyArr(p, &h6, 3);
	for (int i = 0 ; i < 3; i++)
	{
		insert_DyArr(p, (h + i), -1);
	}
	
	printf("-------------------------------\n");
	print_DyArr(p, print_Hero);
	print_DyArr_Msg(p);
	printf("-------------------------------\n");
	rmovByPos_DyArr(p, 2);
	print_DyArr(p, print_Hero);
	print_DyArr_Msg(p);
	printf("-------------------------------\n");
	rmovByValue_DyArr(p, &h[0], cmp_Hero);
	print_DyArr(p, print_Hero);
	print_DyArr_Msg(p);
	printf("-------------------------------\n");
	destroy_DyArr(&p);
	print_DyArr(p, print_Hero);
	print_DyArr_Msg(p);
}

int main()
{
	test();
	system("pause");
	return 0;
}