链表的清空和返回长度

2021-03-04 10:40:00 浏览数 (1)

代码语言:javascript复制
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//节点结构体
struct LinkNode {
	void* data;//万能指针接收用户输入的不同类型数据
	LinkNode* next;//指针域
};
//链表结构体
struct LList {
	LinkNode pHeader;//头节点结构体
	int size;//链表长度
};
//取个别名
typedef  void* LinkList;
//链表的初始化
LinkList init_LinkList()
{
	LList *llist=(LList*)malloc(sizeof(LList));
	if (llist == NULL)
	{
		return NULL;
	}
	//头节点初始化
	llist->pHeader.next = NULL;
	llist->pHeader.data = NULL;
	llist->size = 0;
	return llist;//返回的是链表结构体,void*指针可以接收任何类型指针的地址
}
//插入           第一个参数相当于void* list,这样用户就无法修改堆区结构体数据

//这边如果不用两个指针一前一后移动来插入,要注意curNode指针的移动位置,不要让其移到空位
void insert_LinkList(LinkList list,int pos,void* data)
{
	if (list == NULL)
		return;
	if (data == NULL)
		return;
	//这里要把用户传进的void*数据变为原来的LList数据类型
	LList* mylist =(LList*)list;
	if (pos<0 || pos>mylist->size)
	{
		//强制尾插
		pos = mylist->size;
	}
	LinkNode* curNode = &mylist->pHeader;//这里的头节点是结构体不是指针
	for (int i = 0; i < pos; i  )
	{
		//先把当前节点指针移到该插入的节点
		curNode = curNode->next;
	}
	//curNode是要插入节点的前驱
	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	newNode->next = curNode->next;
	curNode->next = newNode;


	//更新链表长度
	mylist->size  ;
}
//遍历链表
void foreach_LinkList(LinkList list,void(*myprint)(void*))
{
	if (list == NULL)
	{
		return;
	}
	if (myprint == NULL)
	{
		return;
	}
	LList *mylist = (LList*)list;
	LinkNode* curNode =mylist->pHeader.next;
	while (curNode)
	{
		//如何打印交给用户决定
		myprint(curNode->data);
		curNode = curNode->next;
	}
}
//删除指定位置的节点
void del_LinkList(LinkList mylist, int pos)
{
	if (mylist == NULL)
	{
		return;
	}
	LList *list = (LList*)mylist;
	if (pos<0 || pos>list->size)
	{
		return;
	}
	//找到插入节点的前驱节点
	LinkNode* curNode = &list->pHeader;
	//先把当前节点移到要删除节点的前面(前驱)
	for (int i = 0; i < pos; i  )
	{
		curNode = curNode->next;
	}
	//记录要删除的节点
	LinkNode* delNode = curNode->next;
	//重新建立关系
	curNode->next = delNode->next;
	//释放删除的节点
	free(delNode);
	delNode = NULL;
	//更新链表的长度
	list->size--;
}
//按照值来删除
void del_LinkList(LinkList mylist,void* data,int(*compare)(void*,void*))
{
	if (mylist == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	LList* list = (LList*)mylist;
	LinkNode* prveNode = &list->pHeader;
	LinkNode* curNode = list->pHeader.next;
	//找到data所在的节点
	while (curNode)
	{
		//找到要删除的节点
		if (compare(curNode->data,data))
		{
			printf("找到要删除的元素n");
			break;
		}
		//辅助指针往后移动
		prveNode = curNode;
		curNode = curNode->next;
	}
	//如果不为空,表示找到了要删除的节点
	if (curNode!=NULL)
	{
		prveNode->next = curNode->next;
		free(curNode);
		curNode = NULL;
		list->size--;
	}
	printf("未找到该元素n");

}
void print(void* val)
{
	int* num = (int*)val;
	printf("%d ", *num);
}
int compare(void* v1, void* v2)
{
	int* num1 = (int*)v1;
	int* num2 = (int*)v2;
	if (v1 == v2)
	{
		return 1;
	}
	return 0;
}

//清空链表
void clear_List(LinkList list)
{
	if (list == NULL)
		return;
	LList* mylist = (LList*)list;
	LinkNode* curNode = mylist->pHeader.next;
	while (curNode)
	{
		//保存住下一节点的位置
		LinkNode* nextNode = curNode->next;
		free(curNode);
		curNode = nextNode;
	}
	//头节点的next指针置空
	mylist->pHeader.next = NULL;
	//节点个数置空
	mylist->size = 0;
}
//返回链表的长度
int size_List(LinkList list)
{
	if (list == NULL)
		return -1;
	LList* mylist =(LList*)list;
	return mylist->size;
}
//销毁链表
void destory_List(LinkList list)
{
	if (list == NULL)
		return;
	//清空链表
	clear_List(list);
	//释放链表结构体(这里头节点是结构体里面的属性,整个结构体创建在堆区)
	free(list);
	list = NULL;
}
int main()
{
	//用户只能在main函数里面拿到一个void*指针,该指针指向堆区开辟的链表结构体
	//但用户无法知晓void*指向的堆区开辟内存里面存放的数据类型,也就无法通过强制类型转换对堆区的链表结构体数据进行修改
	LinkList list = init_LinkList();
	int a = 5;
	int b = 10;
	int c = 20;
	int d = 30;
	insert_LinkList(list, 0,&a);
	insert_LinkList(list, 0, &b);
	insert_LinkList(list, 0, &c);
	printf("打印链表结果如下:n");
	foreach_LinkList(list, print);
	printf("n按值删除链表后:n");
	del_LinkList(list, &a, compare);
	foreach_LinkList(list, print);
	printf("n按位置删除链表后:n");
	del_LinkList(list, 0);
	foreach_LinkList(list, print);
	printf("n链表的长度:%dn", size_List(list));
	clear_List(list);
	printf("清空链表结果如下:n");
	foreach_LinkList(list, print);
	printf("n链表的长度:%dn", size_List(list));
	destory_List(list);
	printf("n链表的长度:%dn", size_List(list));
	return 0;
}

0 人点赞