首页 > 其他分享 >双向循环链表的删除、插入

双向循环链表的删除、插入

时间：2024-04-25 21:58:26浏览次数：12  
标签：Head 结点 DoubleLList next 链表 插入 Phead 双向

双向循环链表

双向循环链表是一种特殊的链表结构，它结合了双向链表和循环链表的特点。在双向循环链表中，每个节点都有两个指针，一个指向前一个节点，另一个指向后一个节点，从而形成双向链接。同时，链表的头节点和尾节点相互链接，形成一个循环结构。

这种结构使得双向循环链表在遍历和操作上具有更高的灵活性。由于存在双向链接，可以从链表的任何节点开始向前或向后遍历。而循环结构则使得链表在到达尾部时可以自动回到头部，形成一个闭合的环，无需额外的处理即可实现循环遍历。

双向循环链表在实际应用中具有广泛的用途。例如，它可以用于实现循环队列、循环双向队列等数据结构，以支持循环访问和操作。此外，双向循环链表还可以用于实现某些特定的算法和数据结构，如约瑟夫环问题等。

需要注意的是，双向循环链表在插入和删除节点时需要考虑更多的边界条件和指针操作，因此相对于单向链表或简单的双向链表，其实现可能会更为复杂。然而，这种复杂性也带来了更高的灵活性和功能性，使得双向循环链表在某些特定场景下非常有用。

本文将展示双向循环链表的插入与删除（最后附上完整代码）。

双向循环链表头部插入

/*******************************************************************
*
*	函数名称:	DoubleCirLList_HeadInsert
*	函数功能:   在双向循环链表头部插入新的结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*  				@b :DataType_t data 新结点的数据域
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head,DataType_t data)
{
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	DoubleLList_t *Phead = Head;

	if (Head->next == Head)
	{

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

双向循环链表尾部插入

/*******************************************************************
*
*	函数名称:	DoubleCirLList_TailInsert
*	函数功能:   在双向循环链表尾部插入新的结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*  				@b :DataType_t data 新结点的数据域
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_TailInsert(DoubleLList_t *Head,DataType_t data)
{
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	DoubleLList_t *Phead = Head;

	if (Head->next == Head)
	{

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

双向循环链表指定部位插入

/*******************************************************************
*
*	函数名称:	DoubleCirLList_DestInsert
*	函数功能:   在双向循环链表指定部位插入新的结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*  				@b :DataType_t data 新结点的数据域
*  				@c :DataType_t dest 目标结点的数据域
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_DestInsert(DoubleLList_t *Head,DataType_t dest,DataType_t data)
{
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	DoubleLList_t *Phead = Head->next;

	if (Head->next == Head)
	{

		Head->next=New;
		return true;
	}
  	
    while(Phead->next!=Head->next)
    {
        Phead=Phead->next;
        if(Phead->data==dest)
        {
            break;
        }
    }
    if(Phead->next == NULL && Phead->data != dest)
    {
        printf("dest node is not found\n");
        return false;
    }
    New->next=Phead->next;
    Phead->next->prev=New;
    Phead->next=New;
    New->prev=Phead;
    return true;
}

双向循环链表头部删除

/*******************************************************************
*
*	函数名称:	DoubleCirLList_HeadDel
*	函数功能:	删除双向循环链表头部结点
* 	函数参数:
*  			@a :DoubleLList_t *Head  头结点 
*   返回结果:   
* 	注意事项:	None
* 	函数作者:	[email protected]
*	创建日期:	2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
	
	DoubleLList_t *Phead = Head->next;
    DoubleLList_t *Temp = Head->next;
	if (Head->next == Head)
	{

		printf("current linkeflist is empty!\n");
		return true;
	}
  	
   while(Phead->next!=Head->next)
    {
        Phead=Phead->next;
        
    }
    Phead->next=Head->next->next;
    Temp->next->prev=Phead;
    Head->next=Head->next->next;
    Temp->next=NULL;
    Temp->prev=NULL;
    free(Temp);
	return true;
}

双向循环链表尾部删除

/*******************************************************************
*
*	函数名称:	DoubleCirLList_TailDel
*	函数功能:   删除双向循环链表尾部结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
	
	DoubleLList_t *Phead = Head->next;
    DoubleLList_t *Temp = Head->next;
	if (Head->next == Head)
	{

		printf("current linkeflist is empty!\n");
		return true;
	}
  	
   while(Phead->next!=Head->next)
    {
        
        Phead=Phead->next;
        
    }
   Phead->prev->next=Head->next;
   Phead->next=NULL;
   Temp->prev=Phead->prev;
   Phead->prev=NULL;
   free(Phead);
	return true;
}

双向循环链表指定部位删除

/*******************************************************************
*
*	函数名称:	DoubleCirLList_DestDel
*	函数功能::	删除双向循环链表指定部位结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点
*  				@b:DataType_t dest 目标结点的数据域 
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_DestDel(DoubleLList_t *Head,DataType_t dest)
{
	
	DoubleLList_t *Phead = Head->next;
	if (Head->next == Head)
	{

		printf("current linkeflist is empty!\n");
		return true;
	}
  	
   while(Phead->next!=Head->next)
    {  
        Phead=Phead->next;
       
        if(Phead->data==dest)
        {
            break;
        } 
    }
  Phead->next->prev=Phead->prev;
  Phead->prev->next=Phead->next;
  Phead->next=NULL;
  Phead->prev=NULL;
  free(Phead);
	return true;
}

完整代码

/*******************************************************************
*
*	file name:	DoubleCirLList.c
*	author	 :	[email protected]
*	date	 :	2024/04/25
*	function :	双向循环链表的插，删
* 	note	 :	None
*
*	CopyRight (c)  2023-2024   [email protected]  All Right Reseverd 
*
* *****************************************************************/
#include<stdio.h>
#include <stdlib.h>
#include <stdbool.h>


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

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

}DoubleLList_t;


//创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
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;
}

//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
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;
}


/*******************************************************************
*
*	函数名称:	DoubleCirLList_HeadInsert
*	函数功能:   在双向循环链表头部插入新的结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*  				@b :DataType_t data 新结点的数据域
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head,DataType_t data)
{
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	DoubleLList_t *Phead = Head;

	if (Head->next == Head)
	{

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


/*******************************************************************
*
*	函数名称:	DoubleCirLList_TailInsert
*	函数功能:   在双向循环链表尾部插入新的结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*  				@b :DataType_t data 新结点的数据域
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_TailInsert(DoubleLList_t *Head,DataType_t data)
{
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	DoubleLList_t *Phead = Head;

	if (Head->next == Head)
	{

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


/*******************************************************************
*
*	函数名称:	DoubleCirLList_DestInsert
*	函数功能:   在双向循环链表指定部位插入新的结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*  				@b :DataType_t data 新结点的数据域
*               @c:DataType_t dest 目标结点的数据域
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_DestInsert(DoubleLList_t *Head,DataType_t dest,DataType_t data)
{
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	DoubleLList_t *Phead = Head->next;

	if (Head->next == Head)
	{

		Head->next=New;
		return true;
	}
  	
    while(Phead->next!=Head->next)
    {
        Phead=Phead->next;
        if(Phead->data==dest)
        {
            break;
        }
    }
    if(Phead->next == NULL && Phead->data != dest)
    {
        printf("dest node is not found\n");
        return false;
    }
    New->next=Phead->next;
    Phead->next->prev=New;
    Phead->next=New;
    New->prev=Phead;
    return true;
}


/*******************************************************************
*
*	函数名称:	DoubleCirLList_HeadDel
*	函数功能:   删除双向循环链表头部结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
	
	DoubleLList_t *Phead = Head->next;
    DoubleLList_t *Temp = Head->next;
	if (Head->next == Head)
	{

		printf("current linkeflist is empty!\n");
		return true;
	}
  	
   while(Phead->next!=Head->next)
    {
        Phead=Phead->next;
        
    }
    Phead->next=Head->next->next;
    Temp->next->prev=Phead;
    Head->next=Head->next->next;
    Temp->next=NULL;
    Temp->prev=NULL;
    free(Temp);
	return true;
}


/*******************************************************************
*
*	函数名称:	DoubleCirLList_TailDel
*	函数功能:   删除双向循环链表尾部结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点 
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
	
	DoubleLList_t *Phead = Head->next;
    DoubleLList_t *Temp = Head->next;
	if (Head->next == Head)
	{

		printf("current linkeflist is empty!\n");
		return true;
	}
  	
   while(Phead->next!=Head->next)
    {
        
        Phead=Phead->next;
        
    }
   Phead->prev->next=Head->next;
   Phead->next=NULL;
   Temp->prev=Phead->prev;
   Phead->prev=NULL;
   free(Phead);
	return true;
}

/*******************************************************************
*
*	函数名称:	DoubleCirLList_DestDel
*	函数功能:   删除双向循环链表指定部位结点
* 	函数参数:
*  				@a :DoubleLList_t *Head  头结点
*               @b:DataType_t dest 目标结点的数据域 
*   返回结果:   
* 	注意事项:   None
* 	函数作者:  [email protected]
*	创建日期:   2024/04/25
*	修改历史:
*	函数版本:	V1.0
* *****************************************************************/
bool DoubleCirLList_DestDel(DoubleLList_t *Head,DataType_t dest)
{
	
	DoubleLList_t *Phead = Head->next;
	if (Head->next == Head)
	{

		printf("current linkeflist is empty!\n");
		return true;
	}
  	
   while(Phead->next!=Head->next)
    {  
        Phead=Phead->next;
       
        if(Phead->data==dest)
        {
            break;
        } 
    }
  Phead->next->prev=Phead->prev;
  Phead->prev->next=Phead->next;
  Phead->next=NULL;
  Phead->prev=NULL;
  free(Phead);
	return true;
}



//遍历链表
bool DoubleCirLList_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 && Head->next->prev==Phead)
		{
			break;
		}	
	}

	return true;
}


int main(int argc, char const *argv[])
{
	DoubleLList_t *phe=DoubleCirLList_Create();
    DoubleCirLList_HeadInsert(phe,20);
    DoubleCirLList_HeadInsert(phe,10);
    DoubleCirLList_TailInsert(phe,30);
    DoubleCirLList_TailInsert(phe,50);
    DoubleCirLList_DestInsert(phe,30,40);
    DoubleCirLList_HeadDel(phe);
    DoubleCirLList_TailDel(phe);
    DoubleCirLList_DestDel(phe,40);
    DoubleCirLList_Print(phe);
	return 0;
}

该代码成功运行后，可以在终端肯定data的值为20，30,代码可供各位惨考移植。
image

如果该程序双向循环链表的代码有什么问题，请将问题发至网易邮箱 [email protected]，作者将及时改正，欢迎各位老爷提出意见。

麻烦三连加关注！！！！

比心！

标签：Head,结点,DoubleLList,next,链表,插入,Phead,双向
From： https://www.cnblogs.com/zkbklink/p/18158686

相关文章

  • 双向循环链表的插入处理函数接口
    //方便访问，创建一个带头结点的双向循环链表//链表数据域取别名方便修改typedefintDataType_t;//构造双向循环链表的结点typedefstructDoubleCircularLList{DataType_tdata;//数据域structDoublLingkedList*prev;//直接前驱指针域......
  • 关于双向循环列表的插入、删除、遍历
    目录双向循环链表公式初始化双向循环链表构建双向循环链表结构体//双向循环链表节点定义typedefstructdouble_loop_node{chardata[DATA_LEN];//数据域，存储数据长度structdouble_loop_node*next;......
  • 02-属性事件过滤双向绑定
    es6的对象写法//正常的写法letarr=['逃课','打游戏','欺负小满']lethobbyDetail={name:"大乔",age:4,hobby:arr}console.log(hobbyDetail)//简写//正常的写法letarr=['逃课','打游戏','欺负小满'......
  • 单向循环链表实现头插、尾插、中间插、头删、尾删、中间删
    *name:单向循环链表*author:[email protected]*data:2024/04/23*function:设计一个单向循环链表，实现头插、尾插、中间插、头删、尾删、中间删*noto:None**CopyRight(c)[email protected]******......
  • 以链表作为基础实现栈空间（链式栈）
    数据结构以链表作为基础实现栈空间（链式栈）/****************************************************************************************************************** * filename : LinkedStack.c* author : [email protected]* data : 2024/04/25* function : 链式栈......
  • 单链表的头插、尾插、中间插、头删、尾删、中间删
    //指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改typedefintDataType_t;//构造链表的结点,链表中所有结点的数据类型应该是相同的typedefstructLinkedList{ DataType_t data;//结点的数据域 structLinkedList *next;//结点的指针域}LList_t;......
  • 单向链表的学习
    单向链表的学习链表：链式存储的线性表。单向链表的优缺点优点插入、删除时只需要调整几个指针，无需移动任何数据当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快缺点在节点中，需要多余的指......
  • 双向链表的学习
    双向链表的学习经过单链表、双链表的学习，可以总结链表的适用场合：适合用于节点数目不固定，动态变化较大的场合适合用于节点需要频繁插入、删除的场合适合用于对节点查找效率不十分敏感的场合双向链表的增删改查实现双向链表的初始化//指的是双向链表中的节点有效数据......
  • 双向循环链表的增删改查功能
    数据结构双向循环链表双向循环链表的增删改查/****************************************************************************************************************** * filename : DoubleCirLinkedList.c* author : [email protected]* data : 2024/04/24* funct......
  • 基于c语言数据结构-双循环链表
    DoubleCircularLinkedList双循环链表/**************************************************************函数名称:*函数功能:设计双向循环链表的接口*函数参数:*返回结果:*注意事项:None*函数作者:zcx982795194@[email protected]*创建日期:2024/04/25*修......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99