首页 > 其他分享 >双向循环链表的增删改查

双向循环链表的增删改查

时间：2024-04-25 11:12:47浏览次数：21  
标签：Head LHead DoubleCirLList 改查 next 链表 PHead 增删 New

数据结构

双向循环链表

双向循环链表的增删改查

/*************************************************************************************
 *
 *  file name:  1.c
 *  author   : 	[email protected]
 *  date     :  2024/04/24
 *  function : 	双向循环链表的增删改查
 *  note     :  None
 *  CopyRight (c)   2024    [email protected]   All Right Reserved
 *
 ************************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>


//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int  DataType_t;

//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
	DataType_t  		     data; //结点的数据域
	struct DoubleLinkedList	*prev; //直接前驱的指针域
	struct DoubleLinkedList	*next; //直接后继的指针域

}DoubleLList_t;

/**
  * @name:		DoubleCirLList_Create
  * @brief 		创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
  * @retval 	DoubleLList_t *
  * @date 		2024/04/23
  * @note   	补充 注意 说明
  */
DoubleLList_t * DoubleCirLList_Create(void)
{
	//1.创建一个头结点并对头结点申请内存
	DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

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

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

/**
  * @name:		DoubleCirLList_NewNode
  * @brief  	创建新的结点，并对新结点进行初始化（数据域 + 指针域）
  * @param  
  				@data
  * @retval 	DoubleLList_t * 
  * @date 		2024/04/23
  * @note   	补充 注意 说明
  */
DoubleLList_t * DoubleCirLList_NewNode(DataType_t data)
{
	//1.创建一个新结点并对新结点申请内存
	DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	//2.对新结点的数据域和指针域（2个）进行初始化,指针域指向结点自身，体现“循环”
	New->data = data;
	New->prev = New;
	New->next = New;

	return New;
}
/**
  * @name:		DoubleCirLList_HeadInsert
  * @brief  	头插
  * @param  
  				@data
  				@Head
  * @retval 	bool
  * @date 		2024/04/24
  * @note   	补充 注意 说明
  */
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head,DataType_t data)
{
	DoubleLList_t *PHead =Head;
	DoubleLList_t *New =  DoubleCirLList_NewNode(data);	
	//如果申请内存失败
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return false;
	}
	//如果是空链表,直接插入
	if (Head == Head->next)
	{
		Head->next = New;
		New->next = New;
		return true;
	}

	while(PHead->next)
	{
		PHead = PHead->next;
		if(PHead->next == Head->next)
			break;
	}
	PHead->next = New;
	New->prev = PHead ;
	New->next = Head->next;
	Head->next->prev = New;
	Head->next = New; 
	return true;
}

/**
  * @name:		DoubleCirLList_TailInsert
  * @brief  	尾插
  * @param  
  				@data
  				@Head
  * @retval 	bool
  * @date 		2024/04/24
  * @note   	补充 注意 说明
  */
bool DoubleCirLList_TailInsert(DoubleLList_t *Head,DataType_t data)
{
	DoubleLList_t *PHead = Head;
	DoubleLList_t *New = DoubleCirLList_NewNode(data);	
	//如果申请内存失败
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return false;
	}
	//如果是空链表,直接插入
	if (Head->next == Head)
	{
		Head->next = New;
		New->next = New;
		return true;
	}
	//遍历获取最后的值
	while(PHead->next)
	{
		PHead = PHead ->next;
		if(PHead->next == Head->next)
			break;
	}

	New->prev = PHead;
	PHead->next = New;
	New->next = Head->next;
	Head->next->prev = New;
	return true;
}
/**
  * @name:		DoubleCirLList_DestInsert
  * @brief  	指定位置插入
  * @param  
  				@data
  				@Head
  				@destval
  * @retval 	bool
  * @date 		2024/04/23
  * @note   	补充 注意 说明
  */

bool DoubleCirLList_DestInsert(DoubleLList_t *Head,DataType_t destval,DataType_t data)
{
	DoubleLList_t *LHead = Head->next;
	DoubleLList_t *PHead = Head;
	DoubleLList_t *New = DoubleCirLList_NewNode(data);	
	//如果申请内存失败
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return false;
	}
	//如果是空链表,直接插入
	if (Head->next == Head)
	{
		Head->next = New;
		New->next = New;
		return true;
	}
	//遍历获取目标值
	while(PHead->next)
	{
		PHead = PHead ->next;
		if(destval == PHead->data)
			break;
		//如果遍历链表之后发现没有目标结点，则退出即可
		if(PHead->next == PHead && PHead->data != destval)
		{
			printf("dest node is not found\n");
			return false;
		}
	}

//如果链表中发现目标结点，此时分为(头部 or 尾部 or 中间)
	if(LHead == PHead->prev)//尾部
	{  
		New->next = PHead;
		PHead->next = New;
		LHead->next = New;
		New->prev = LHead;
	}
	else//头部和中间
	{
		New->next = PHead->next;
		PHead->next->prev = New;
		New->prev = PHead;
		PHead->next = New;
	}


	return true;
}

/**
  * @name:		DoubleCirLList_HeadDel
  * @brief  	头删
  * @param  
  				@Head
  * @retval 	bool
  * @date 		2024/04/24
  * @note   	补充 注意 说明
  */
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
	//对双向循环链表的头结点的地址进行备份
	DoubleLList_t *PHead = Head->next;
	DoubleLList_t *LHead = Head;
	//链表为空
	if (Head == Head->next)
        return false;
	// 链表内只有一个节点
	if(PHead->next == PHead)
	{
		PHead->next = NULL;
		PHead->prev = NULL;
		Head->next = Head;
		free(PHead);
		return true;
	}

	//遍历获取最后的值
	while(LHead->next)
	{
		LHead = LHead ->next;
		if(LHead->next == Head->next)
			break;
	}

	LHead->next = PHead->next;
	PHead ->next->prev = LHead;
	PHead->next = NULL;
	Head->next = LHead->next;
	PHead->prev = NULL;
	free(PHead);
	return true;
}
/**
  * @name:		DoubleCirLList_TailDel
  * @brief  	尾删
  * @param  
  				@Head
  * @retval 	bool
  * @date 		2024/04/24
  * @note   	补充 注意 说明
  */

bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
	//对双向循环链表的头结点的地址进行备份
	DoubleLList_t *PHead = Head->next;
	DoubleLList_t *LHead = Head;
	//链表为空
	if (Head == Head->next)
        return false;
	// //链表内只有一个节点
	if(PHead->next == PHead)
	{
		PHead->next = NULL;
		PHead->prev = NULL;
		Head->next = Head;
		free(PHead);
		return true;
	}

	//遍历获取最后的值
	while(LHead->next)
	{
		LHead = LHead ->next;
		if(LHead->next == Head->next)
		{
			break;
		}
	}
	LHead->prev->next = PHead;
	PHead ->prev = LHead->prev;
	LHead->next = NULL;
	LHead->prev = NULL;
	free(LHead);
	return true;
}

/**
  * @name:		DoubleLList_DestDel
  * @brief  	指定位置删
  * @param  
  				@Head
  				@destval
  * @retval 	bool
  * @date 		2024/04/23
  * @note   	补充 注意 说明
  */
bool DoubleCirLList_DestDel(DoubleLList_t *Head,DataType_t destval)
{
	//对双向循环链表的头结点的地址进行备份
	DoubleLList_t *PHead = Head->next;
	DoubleLList_t *LHead = Head;
	//链表为空
	if (Head == Head->next)
        return false;
	// 链表内只有一个节点
	if(PHead->next == PHead && PHead->data == destval)
	{
		PHead->next = NULL;
		PHead->prev = NULL;
		Head->next = Head;
		free(PHead);
		return true;
	}
	//遍历获取目标的值
	while(Head->next)
	{
		LHead = LHead->next;
		if(destval == LHead->data)
			break;
		//如果遍历链表之后发现没有目标结点，则退出即可
		if(destval != LHead->data && LHead->next == PHead)
		{
			printf("dest node is not found\n");
			break;
		}
	}

	//如果链表中发现目标结点，此时分为(头部 or 尾部 or 中间)
	if(LHead == PHead)//头部
	{

		LHead->prev->next = LHead->next; 
		LHead->next->prev = LHead->prev;
		Head->next = LHead->next;
		LHead->next= NULL;
		LHead->prev = NULL;
		free(LHead);
	}
	else if(LHead == PHead->prev)//尾部
	{  
		LHead->prev->next = PHead;
		PHead ->prev = LHead->prev;
		LHead->next = NULL;
		LHead->prev = NULL;
		free(LHead);
	}
else
{
	LHead->next->prev = LHead->prev;
	LHead->prev->next = LHead->next;
	LHead->next = NULL;
	LHead->prev = NULL;
	free(LHead);
}
	return true;
}
/**
  * @name:		CircLList_Print
  * @brief  	遍历链表
  * @param  
  				@Head
  * @retval 	bool
  * @date 		2024/04/24
  * @note   	补充 注意 说明
  */
bool DoubleLList_Print(DoubleLList_t *Head)
{
	//对单向循环链表的头结点的地址进行备份
	DoubleLList_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;
}
//调用函数进行测试
int main(int argc, char const *argv[])
{
	DoubleLList_t  * Head = DoubleCirLList_Create();
	// DoubleCirLList_HeadInsert(Head,8);
	// DoubleCirLList_HeadInsert(Head,7);
	// DoubleCirLList_HeadInsert(Head,6);
	// DoubleCirLList_HeadInsert(Head,5);
	DoubleCirLList_TailInsert(Head,5);
	DoubleCirLList_TailInsert(Head,6);
	DoubleCirLList_TailInsert(Head,7);
	DoubleCirLList_TailInsert(Head,8);
	// DoubleCirLList_TailInsert(Head,9);
	// DoubleCirLList_TailInsert(Head,10);
	DoubleCirLList_DestInsert(Head,8,77);
	// DoubleCirLList_DestInsert(Head,2,77);
	// DoubleCirLList_HeadDel(Head);
	// DoubleCirLList_HeadDel(Head);
	// DoubleCirLList_TailDel(Head);
	// DoubleCirLList_TailDel(Head);
	// DoubleCirLList_DestDel(Head,6);
	// DoubleCirLList_DestDel(Head,7);

	DoubleLList_Print(Head);
	return 0;
}

标签：Head,LHead,DoubleCirLList,改查,next,链表,PHead,增删,New
From： https://www.cnblogs.com/lu-ciana/p/18157169

相关文章

  • C语言数据结构：双向循环链表的增删操作
    /***********************************************************************************************************设计双向循环链表的接口****Copyright(c)[email protected]**********************************************......
  • 双向循环链表的接口
    双向循环链表的接口头文件#include<stdbool.h>#include<stdio.h>#include<string.h>#include<stdlib.h>​```创建链表、节点//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改hjtypedefintDataType_t;//构造双向循环链表的结点,链表中所有结......
  • 数据结构：双向循环链表的创建·插入·删除
    数据结构：双向循环链表的创建·插入·删除/***@filename:数据结构：双向循环链表的创建·插入·删除*@brief:实现双向循环链表的创建·插入·删除*@author :[email protected]*@date ：2024/04/24*@version：1.0*@note:none*CopyRig......
  • 双向循环链表
    双向循环链表原理与应用双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。双向循环链表各功能实现（1）为了管理双向循环链表，需要构造头结点......
  • 数据结构：双向链表的创建·插入·删除
    数据结构：双向链表的创建·插入·删除/***@filename:数据结构：双向链表的创建·插入·删除*@brief:实现双向链表的创建·插入·删除*@author :[email protected]*@date ：2024/04/23*@version：1.0*@note:none*CopyRight(c......
  • 反转链表
    packagemainimport"fmt"typeListNodestruct{ValintNext*ListNode}funcreverseList(head*ListNode)*ListNode{ifhead==nil||head.Next==nil{returnhead}newHead:=reverseList(head.Next)he......
  • 双向循环链表
    /**********************************************************************************************************设计双向链表的接口******************************************************************************************************/include<stdio.h>i......
  • 双向链表和双向循环链表的(创建、插入、删除、遍历)
    V1.02024年4月24日发布于博客园目录目录目录双向链表和双向循环链表的(创建、插入、删除、遍历)设计双向链表的接口创建一个空的双向链表，空链表应该有一个头结点，对链表进行初始化创建新的结点，并对新结点进行初始化（数据域+指针域）创建一个新的结点进行头部插入创建一个新的......
  • 用一个尽可能高效的算法，查找单向链表（有头结点）中倒数第k个位置上的结点
    思路  定义两个指向链表首结点的指针变量，第一个指针变量向后移动k个位置后，第二个指针变量也开始跟着一起向后移动，直到第一个指针变量指向尾结点为止，第二个指针变量指向的位置结点就是倒数第k个结点。实现步骤及参考代码（C语言）intLList_FindLK(LList_t*Head,DataType_tda......
  • 自定义双向循环链表基本函数接口
    自定义双向循环链表的函数接口/********************************************************************* 文件名称: 双向循环链表的函数接口* 文件作者:[email protected]* 创建日期:2024/04/24* 文件功能:对双向链表的增删改查功能的定义* 注意事项:No......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99