数据结构-单向循环链表

28天前发布

对于单向链表来说，只能从头结点遍历到尾结点，而没有办法从尾结点直接访问首节点，基于单链表的弊端，引入单向循环链表

构造单向循环链表的结点

typedef struct CircularLinkedList
{
	DataType_t  		 data; //结点的数据域
	struct CircularLinkedList	*next; //结点的指针域

}CircLList_t;

创建一个空单向循环链表

CircLList_t * CircLList_Create(void)
{
	//1.创建一个头结点并对头结点申请内存
	CircLList_t *Head = (CircLList_t *)calloc(1,sizeof(CircLList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
	Head->next = Head;

	//3.把头结点的地址返回即可
	return Head;
}

创建新的结点

CircLList_t * CircLList_NewNode(DataType_t data)
{
	//1.创建一个新结点并对新结点申请内存
	CircLList_t *New = (CircLList_t *)calloc(1,sizeof(CircLList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	//2.对新结点的数据域和指针域进行初始化
	New->data = data;
	New->next = NULL;

	return New;
}

头部插入元素

bool CircLList_HeadInsert(CircLList_t *Head,DataType_t data)
{
	CircLList_t *New = CircLList_NewNode(data);
	CircLList_t *Phead=Head->next;
	//判断新结点创建是否成功
	if(New == NULL){
		printf("create new node false\n");
		return false;
	}
	//判断链表是否为空
	if(Head->next == Head){
		Head->next = New;
		New->next = New;
		return true;
	}
	 //链表不为空则执行
	
	while(Phead->next != Head->next){
		Phead = Phead->next;
	}
	New->next = Head->next;
	Head->next = New;
	Phead->next = New;
	return true;

}

尾部插入结点

bool CircLList_TailInsert(CircLList_t *Head,DataType_t data)
{
	CircLList_t *New = CircLList_NewNode(data);
	CircLList_t *Phead=Head->next;
	//判断新结点创建是否成功
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}
	//判断链表是否为空
	if(Head->next == Head){
		Head->next = New;
		New->next = New;
		return true;
	}
	//寻找尾节点
	while(Phead->next != Head->next){
		Phead = Phead->next;
	}
	
	Phead->next = New;
	New->next = Head->next;
	return true;
}

指定元素后边插入

bool CircLList_DestInsert(CircLList_t *Head,DataType_t destval,DataType_t data)
{
	CircLList_t *New = CircLList_NewNode(data);
	CircLList_t *Phead=Head->next;
	//判断新结点创建是否成功
	if (NULL == New){
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}
	//判断链表是否为空
	if(Head->next == Head){
		Head->next = New;
		New->next = New;
		return true;
	}
	//寻找目标结点
	while(Phead->next != Head->next && Phead->data != destval){
		Phead = Phead->next;
	}
	//判断循环终止条件是否是寻找到的尾节点
	if(Phead->next == Head->next){
		if(Phead->data != destval){
			printf("can not find this value\n");
			return false;
		}
		//CircLList_TailInsert(Head,data);
		
	}
	//Phead = Phead->next;
	New->next = Phead->next;
	Phead->next = New;
	return true;
}

遍历打印链表

bool CircLList_Print(CircLList_t *Head)
{
	//对单向循环链表的头结点的地址进行备份
	CircLList_t *Phead = Head;
	
	//判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}

	//从首结点开始遍历
	while(Phead->next)
	{
		//把头结点的直接后继作为新的头结点
		Phead = Phead->next;

		//输出头结点的直接后继的数据域
		printf("data = %d\n",Phead->data);

		//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
		if (Phead->next == Head->next)
		{
			break;
		}	
	}

	return true;
}

删除首结点

bool LList_HeadDel(CircLList_t *Head)
{
	//对单向循环链表的头尾结点的地址进行备份
	CircLList_t *Phead = Head->next;
	CircLList_t *Pphead = Head->next;
	//判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}
	//遍历链表找到尾结点
	while(Phead->next != Head->next){
		Phead = Phead->next;
	}
	//进行删除操作，重新连接
	Phead->next = Pphead->next;
	Head->next = Pphead->next;
	Pphead->next = NULL;
	free(Pphead);
	return true;

	
}

删除尾结点

bool LList_TailDel(CircLList_t *Head)
{
	//对单向循环链表的头尾结点的地址进行备份
	CircLList_t *Phead = Head->next;
	CircLList_t *Pphead = Head->next;
	//判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}
	//遍历链表找到尾结点
	while(Phead->next != Head->next){
		Pphead = Phead;
		Phead = Phead->next;
	}
	Pphead->next = Head->next;
	Phead->next = NULL;
	free(Phead);
	return true;

}

删除指定元素

bool CircLList_DestDel(CircLList_t *Head,DataType_t destval)
{
	//对单向循环链表的目标结点和直接前驱结点的地址进行备份
	CircLList_t *Pphead = Head;//直接前驱的地址
	CircLList_t *Phead = Head->next;
	//判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}
	//寻找目标结点
	while(Phead->next != Head->next && Phead->data != destval){
		Pphead = Phead;
		Phead = Phead->next;
	}
	//判断尾结点的data是不是目标值
	if(Phead->data == destval && Phead->next == Head->next){
		LList_TailDel(Head);
		return true;
	}
	//判断首结点的data是不是目标值
	else if(Pphead->next == Head->next){
		LList_HeadDel(Head);
		return true;
	}
	//到达链表尾但是没有找到目标元素
	else if(Phead->next == Head->next){
		printf("do not find this value,do not delete\n");
		return false;
	}
	Pphead->next = Phead->next;
	Phead->next = NULL;
	free(Phead);
	return true;
}

来源链接：https://www.cnblogs.com/lradian/p/18801093

评分

欢迎为Ta评分