C语言 -- 动态数组&链表

目录

动态数组

 动态数组的实现：

用户test

链表

目的：

链表的结构体：

链表的实现：

初始化链表

插入节点

遍历链表

删除节点

清空链表、销毁链表

用户回调函数

给用户提供接口获取链表长度

用户test

---

动态数组

将数组开辟到堆区，实现动态扩展。

问题：

① 用户的数据类型无法确定；

② 用户的数据无法确定创建在堆区还是栈区；

③ 不管数据在堆区还是栈上，都是在内存中，就会有地址，只需维护数据的地址就行。eg：如果数据类型是 int，则使用 int* 来指向该数据地址。

所以，这里使用万能指针 void* 来指向用户的数据地址。

第二点，我们是在堆区创建的一个数组，每一个元素都是 void* 类型的。如果要操纵这个数组，则可以使用二级指针 void** 来指向该数组的地址。

 动态数组的实现：

typedef struct DynamicArray
{
	void** pAddr;	//维护真实在堆区开辟的数组的二级指针
	int m_Capacity; //数组容量
	int m_Size;     //数组大小
}dynamicArray;
//初始化数组,参数：初始数组的容量。返回值：数组指针
dynamicArray* init_dynamicArray(int capacity)
{
	if (capacity <= 0)
	{
		return NULL;
	}
	//给数组分配内存
	dynamicArray* arr = malloc(sizeof(dynamicArray));
	if (arr == NULL)
		return NULL;
	//数组属性初始化
	arr->pAddr = malloc(sizeof(void*) * capacity); //我们维护的数据类型是void*，
 //这里是capacity个void*类型的数据大小，又malloc返回的是void**类型，pAddr同样是void**类型
	arr->m_Capacity = capacity;
	arr->m_Size = 0;
}
//数组元素插入
void insert_dynamicArray(dynamicArray* arr, void* data, int pos)
{
	if (arr == NULL)
		return;
	if (data == NULL)
		return;
	if (pos<0 || pos>arr->m_Size)
		pos = arr->m_Size;
	//判断数组是否满了
	if (arr->m_Size == arr->m_Capacity)
	{
		//计算新的空间大小
		int newCapacity = arr->m_Capacity * 2;
		//开辟新空间
		void** newSpace = malloc(sizeof(void*) * newCapacity);
		//将原空间下数据拷贝到新空间下
		memcpy(newSpace, arr->pAddr, sizeof(void*) * arr->m_Capacity);
		//释放原空间
		free(arr->pAddr);
		//更改指向
		arr->pAddr = newSpace;
		//更新容量
		arr->m_Capacity = newCapacity;
	}	
	//将新元素插入到指定位置
	for (int i = arr->m_Size - 1; i >= pos; i--)  //从最后边的数据开始移
	{
		arr->pAddr[i + 1] = arr->pAddr[i];
	}
	arr->pAddr[pos] = data;
	//更新数组大小
	arr->m_Size++;
}
//遍历
void foreach_dynamicArray(dynamicArray* arr,void(*myPrint)(void*))
{
	if (arr == NULL)
		return;
	for (int i = 0; i < arr->m_Size; i++)
	{
		myPrint(arr->pAddr[i]);
	}
}
//删除数组中元素
//按照位置删除
void removeByPos_dynamicArray(dynamicArray* arr, int pos)
{
	if (arr == NULL)
		return;
	if (pos<0 || pos>arr->m_Size - 1)
		return;
	for (int i = pos; i < arr->m_Size; i++)
	{
		arr->pAddr[i] = arr->pAddr[i + 1];
	}
	arr->m_Size--;
}
//按照数值删除
void removeByVal_dynamicArray(dynamicArray* arr, void* data, int(*myCompare)(void*,void*))
{
	if (arr == NULL)
		return;
	if (data == NULL)
		return;
	for (int i = 0; i < arr->m_Size; i++)
	{
		if (myCompare(arr->pAddr[i], data))//利用回调函数让用户告诉我们如何对比数据
		{
			removeByPos_dynamicArray(arr,i);
			break;
		}
	}
}

void destory_dynamicArray(dynamicArray* arr)
{
	if (arr == NULL)
		return;
	//内部维护在堆区数组指针先释放
	if (arr->pAddr != NULL)
	{
		free(arr->pAddr);
		arr->pAddr = NULL;
	}
	free(arr);
	arr = NULL;
}

用户test

typedef struct Person  //用户的数据类型
{
	char name[32];
	int age;
}person;
//回调函数，打印用户数据
void printPerson(void* data)
{
	person* person = data;
	printf("Name:%s Age:%d\n", person->name, person->age);
}
int comparePerson(void* data1, void* data2)
{
	person* p1 = data1;
	person* p2 = data2;
	return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}


void test01()
{
	dynamicArray* arr = init_dynamicArray(5);
	person p1 = { "sun",18 };
	person p2 = { "yu",19 };
	person p3 = { "hang",17 };
	person p4 = { "li",20 };
	person p5 = { "hai",21 };

	printf("插入数据前：容量 = %d,大小 = %d\n", arr->m_Capacity, arr->m_Size);
	insert_dynamicArray(arr, &p1, 0);
	insert_dynamicArray(arr, &p2, 1);
	insert_dynamicArray(arr, &p3, -1);
	insert_dynamicArray(arr, &p4, 0);
	insert_dynamicArray(arr, &p5, 2);

	foreach_dynamicArray(arr, printPerson);
	printf("插入数据后：容量 = %d,大小 = %d\n", arr->m_Capacity, arr->m_Size);
	printf("-------------------------------\n");
	//按位置删除
	removeByPos_dynamicArray(arr,0);
	foreach_dynamicArray(arr, printPerson);
	printf("-------------------------------\n");
	//按值删除
	removeByVal_dynamicArray(arr, &p5, comparePerson);
	foreach_dynamicArray(arr, printPerson);
    printf("删除数据后：容量 = %d,大小 = %d\n", arr->m_Capacity, arr->m_Size);

	destory_dynamicArray(arr);
	arr = NULL;
}

插入数据前：容量 = 5,大小 = 0
Name:li Age:20
Name:sun Age:18
Name:hai Age:21
Name:yu Age:19
Name:hang Age:17
插入数据后：容量 = 5,大小 = 5
-------------------------------
Name:sun Age:18
Name:hai Age:21
Name:yu Age:19
Name:hang Age:17
-------------------------------
Name:sun Age:18
Name:yu Age:19
Name:hang Age:17
删除数据后：容量 = 5,大小 = 3

链表

目的：

设计一个可以存不同类型数据的链表。

首先来看一个存储void*类型数据的普通链表。

 其中的一个节点只是一个独立的个体，无法代表整个链表。

链表的结构体：

整个链表用一个新的结构体来维护，如下：

struct LList
{
    struct LinkNode pHeader;  //链表的头结点，拿到链表的头结点即可还原整个链表
    int m_Size;               //记录链表的节点个数
}

在动态数组的实现中，我们可以随时访问动态数组的容量arr->m_Capacity，但由于整个数组的结构体暴露给了用户，导致用户也可以随意修改。

链表的实现中，我们就不直接让用户拿到链表的结构体 LList，防止其被篡改。进行如下操作：

typedef void* LinkList;  //给 void* 起别名

则用户拿到的数据永远都是 void* 类型的，我们在操作的时候，再把void*转为struct LList类型。

链表的实现：

//链表的节点结构体
typedef struct LinkNode
{
	void* data;
	struct LinkNode* next;
}LinkNode;

//链表结构体
typedef struct LList
{
	struct LinkNode pHeader;
	int m_Size;
}Llist;

//void别名
typedef void* LinkList;

初始化链表

//初始化链表
LinkList init_LinkList()
{
	//分配内存
	Llist* mylist = malloc(sizeof(Llist));
	if (mylist == NULL)
		return;
	mylist->pHeader.data = NULL;
	mylist->pHeader.next = NULL;
	mylist->m_Size = 0;

	return mylist;  //返回的是void*类型
}

插入节点

//插入节点
void insert_LinkList(LinkList list, int pos, void* data)
{
	if (list == NULL)
		return;
	if (data == NULL)
		return;
	Llist* mylist = list;
	if (pos<0 || pos>mylist->m_Size)
	{
		//如果传进来的位置是无效位置
		pos = mylist->m_Size;
	}
	//创建临时节点
	LinkNode* pCurrent = &mylist->pHeader; //pHeader直接是一个节点，所以用&取到其地址
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//此时pCurrent就是插入位置的前驱节点
	//创建新节点
	LinkNode* newNode = malloc(sizeof(LinkNode));
	newNode->data = data;
	newNode->next = NULL;
	//建立节点之间的关系
	newNode->next = pCurrent->next;
	pCurrent->next = newNode;
	//更新链表长度
	mylist->m_Size++;
}

遍历链表

//遍历链表
void foreach_LinkList(LinkList list,void(*myPrint)(void*))
{
	if (list == NULL)
		return;
	//还原链表真实结构体
	Llist* mylist = list;
	LinkNode* pCurrent = mylist->pHeader.next;
	for (int i = 0; i < mylist->m_Size; i++)
	{
		myPrint(pCurrent->data); //我们不知道data的类型，所以这里使用用户自己的回调来打印
		pCurrent = pCurrent->next;
	}
}

删除节点

//删除链表节点之按位置删除
void removeByPos_LinkList(LinkList list, int pos)
{
	if (list == NULL)
		return;
	Llist* mylist = list;
	if (pos<0 || pos>mylist->m_Size - 1)
		return; //无效位置直接返回
	//找到待删除位置的前驱节点的位置
	LinkNode* pCurrent = &mylist->pHeader;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//PCurrent就是待删除节点的前驱节点
	//利用一个指针记录待删除节点
	LinkNode* pDel = pCurrent->next;
	//更改指针的指向
	pCurrent->next = pDel->next;
	//释放待删除节点
	free(pDel);
	pDel = NULL;
	mylist->m_Size--;
}
//删除链表节点之按值删除
void removeByVal_LinkList(LinkList list, void* data, int(*myCompare)(void*))
{
	if (list == NULL)
		return;
	if (data == NULL)
		return;
	//将list还原为真实链表结构体
	Llist* mylist = list;
	//创建两个辅助指针变量
	LinkNode* pPrev = &mylist->pHeader;
	LinkNode* pCurrent = mylist->pHeader.next;
	//遍历链表，找用户要删的数据
	for (int i = 0; i < mylist->m_Size; i++)
	{
		if (myCompare(data, pCurrent->data))
		{
			//开始删除,更改指针指向
			pPrev->next = pCurrent->next;
			free(pCurrent);
			pCurrent = NULL;
			mylist->m_Size--;
			break;
		}
		//辅助指针向后移动
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
}

清空链表、销毁链表

//请空链表
void clear_LinkList(LinkList list)
{
	if (list == NULL)
		return;
	Llist* mylist = list;
	LinkNode* pCurrent = mylist->pHeader.next;
	for (int i = 0; i < mylist->m_Size; i++)
	{
		//记录下一个节点的位置
		LinkNode* pNext = pCurrent->next;

		free(pCurrent);
		pCurrent = pNext;
	}
	mylist->pHeader.next = NULL;
	mylist->m_Size = 0;
}

//销毁链表
void destory_LinkList(LinkList list)
{
	if (list == NULL)
		return;
	//先清空链表再销毁头结点
	clear_LinkList(list);

	free(list);
	list = NULL;
}

用户回调函数

另外涉及到：打印用户数据，以及比较用户数据。由于我们不知道用户的数据类型，所以需要用户自己提供回调函数。

//回调函数之打印
void printPerson(void* data)
{
	Person* person = data;
	printf("Name：%s，Age：%d\n", person->name, person->age);
}
//回调函数之比较
int ComparePerson(void* data1, void* data2)
{
	Person* p1 = data1;
	Person* p2 = data2;
	return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;
}

给用户提供接口获取链表长度

//给用户提供接口获取链表长度
int size_LinkList(LinkList list)
{
	if (list == NULL)
		return -1;
	Llist* mylist = list;
	return mylist->m_Size;
}

用户test

void test02()
{
	//初始化链表
	LinkList mylist = init_LinkList(); //mylist本质是一个void*类型的，用来隐藏结构体里的数据属性
	//mylist->m_size = -1;  //err，用户访问不到真实链表中的属性

	Person p1 = { "sun",18 };
	Person p2 = { "yu",19 };
	Person p3 = { "hang",17 };
	Person p4 = { "li",20 };
	Person p5 = { "hai",21 };

	insert_LinkList(mylist, 0, &p1);
	insert_LinkList(mylist, 1, &p2);
	insert_LinkList(mylist, -1, &p3);
	insert_LinkList(mylist, 0, &p4);
	insert_LinkList(mylist, 2, &p5);
	//遍历链表
	foreach_LinkList(mylist, printPerson);
	printf("--------------------\n");
	removeByPos_LinkList(mylist,1);
	foreach_LinkList(mylist, printPerson);
	printf("--------------------\n");
	removeByVal_LinkList(mylist,&p4,ComparePerson);
	foreach_LinkList(mylist, printPerson);
	printf("链表长度为：%d\n", size_LinkList(mylist));
	printf("--------------------\n");
	//清空链表
	clear_LinkList(mylist);
	printf("清空链表后链表长度为：%d\n", size_LinkList(mylist));
	//销毁链表
	destory_LinkList(mylist);
	mylist = NULL;
}

Name：li，Age：20
Name：sun，Age：18
Name：hai，Age：21
Name：yu，Age：19
Name：hang，Age：17
--------------------
Name：li，Age：20
Name：hai，Age：21
Name：yu，Age：19
Name：hang，Age：17
--------------------
Name：hai，Age：21
Name：yu，Age：19
Name：hang，Age：17
链表长度为：3
--------------------
清空链表后链表长度为：0