首页 > 其他分享 >双向循环链表

双向循环链表

时间：2024-04-26 21:34:21浏览次数：25  
标签：结点 phead next 链表 循环 双向 New prev head

双向循链表

双向循环链表我是在双向循环链表上进行升级，就是双向循环链表首结点和尾结点相链接， 首结点的prev链接尾结点本身，尾结点的next链接首结点本身，在对头部或者尾部操作的时候与双向链表有区别，具体代码写在下面。
希望看完代码的你发现错误，请评论批评指正，非常感谢。
image

目录

新链表的初始化

创建结构体存储结点数据

  • /*****************************************************************
*
*      file name ：DoubleLinkedList.c
*      authour   ：[email protected]
*      date      ：2024/04/23
*      function  ：设计一个函数，实现对双向链表的增删改查的功能。
*      note      ：None
*      CopyRight (c)   2024   [email protected]   All Right Reseverd
*
******************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int DataType_t;

//定义一个链表结构体，分别存储数据域和指针域
typedef struct DoubleCirLinkedList
{
    DataType_t   data;                 // 数据域
    struct DoubleCirLinkedList *next;     // 指针域
    struct DoubleCirLinkedList *prev;
}DoubCirLList_t;

    创建空链表

    创建一个空的链表和头结点，并进行初始化，为表示“循环”概念所以Head在开始的时候指向自身

    /*******************************************************************
*
*	name	 :	doubleLinkedList_creat
*	function :  创建一个空链表并创建一个头结点，并进行初始化
*	argument :  
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  None
* 	
* *****************************************************************/
//创建空链表，并创建一个头结点
DoubCirLList_t * DoubleCirLinkedList_creat()
{
    DoubCirLList_t *head = (DoubCirLList_t *)calloc(1,sizeof(DoubCirLList_t));  //calloc来申请不需要初始化更方便
    if(NULL == head)
    {
        perror("calloc head  is error\n");     // 分配内存失败
        exit(1);
    }

    head->next = head;   //头结点next初始化,指向自身，表示循环
    head->prev = NULL;   //头结点prev初始化
}

    创建新结点

    在添加结点时候必然要创建新的结点，再进行添加，代码如下：

/*******************************************************************
*
*	name	 :	doubleLinkedList_NewNode
*	function :  创建一新的双向链表结点，并对新结点初始化
*	argument :  @data 新结点的数据域的数据
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  此函数不单独使用，需要配合Insert函数使用
* 	
* *****************************************************************/
DoubCirLList_t * DoubleCirLinkedList_NewNode(DataType_t data)
{
    DoubCirLList_t *New =(DoubCirLList_t *)malloc(sizeof(DoubCirLList_t));
     if(NULL== New)
    {
        perror("calloc NewNode  is error\n");     // 分配内存失败
        return NULL;
    }

    New->data = data;  //新结点数据域初始化
    New->next = NULL;  //新结点指针域next初始化
    New->prev = NULL;  //新结点指针域prev初始化
}

插入操作

头插

当在头部进行插入新结点动作的时候，可以先画出下图，方便更好的理解

  • /*******************************************************************
*
*	name	 :	DoubleCirLinkedList_HeadInsert
*	function :  结点在头部插入
*	argument :  @data 要插入的结点的数据域的数据
*	            @head 链表的头结点
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  要判断此链表是否为空，为空则直接在头结点后面插入
* 	
* *****************************************************************/
bool DoubleCirLinkedList_HeadInsert(DoubCirLList_t *head,DataType_t data)
{
    DoubCirLList_t *New = DoubleCirLinkedList_NewNode(data);       
    if(NULL== New)                                         //判断新节点是否创建成功
    {
        printf("calloc NewNode is failed\n");
        return false;
    }

    if(head == head->next)                         //判断链表是否为空，则直接插入
    {    
        head->next = New;                          //头结点next连接新结点
        New->next = New;                          //新结点next连接新结点本身
        New->prev = New;                          //新结点prev连接新结点本身
        return true;
    }
    
    New->next = head->next;                        //新结点的next连接原来的首结点              
    New->prev = head->next->prev;                  //新结点的prev连接原来的首结点的prev指向的尾结点
    head->next->prev = New;                        //原来的首结点的prev连接新结点        
    New->prev->next = New;                         //尾结点连接新结点 
    head->next = New;                              //头结点连接新结点

    return true;
}

尾插

当选择在尾部插入的时候，我们先画出下图，这样更有利于我们理解

/*******************************************************************
*
*	name	 :	DoubleCirLinkedList_TailInsert
*	function :  结点在尾部插入
*	argument :  @data 要插入的结点的数据域的数据
*	            @head 链表的头结点
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  要判断此链表是否为空，为空则直接在头结点后面插入，尾结点指向NULL
* 	
* *****************************************************************/
bool DoubleCirLinkedList_TailInsert(DoubCirLList_t *head,DataType_t data)
{
    DoubCirLList_t *phead = head;                                // 备份头结点
    DoubCirLList_t *New = DoubleCirLinkedList_NewNode(data);       
    if(NULL == New)                                         //判断新节点是否创建成功
    {
        printf("calloc NewNode is failed\n");
        return false;
    }

    if(head == head->next)                         //判断链表是否为空，则直接插入
    {    
        head->next = New;                          //头结点next连接新结点
        New->next = New;                          //新结点next连接新结点本身
        New->prev = New;                          //新结点prev连接新结点本身
        return true;
    }
    
    head->next->prev->next = New;                 //尾结点连接新结点
    New->prev = head->next->prev;                 //新结点连接尾结点
    New->next = head->next;                       //新结点连接首结点
    head->next->prev = New;                       //首结点连接新的尾结点

    return true;
}

中间插入

当进行中间插入时需要考虑多种情况，比如就一个首结点，目标结点在头结点，目标结点在尾结点，我们都需要考虑，也画了下图进行简单分析有利于理解

  • //中间插
/*******************************************************************
*
*	name	 :	DoubleCirLinkedList_DestInsert
*	function :  结点在指定位置后插入
*	argument :  @data  指定结点的数据域的数据
*               @value 要插入新的结点的数据域的数据
*	            @head  链表的头结点
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  None
* 	
* *****************************************************************/
bool DoubleCirLinkedList_DestInsert(DoubCirLList_t *head,DataType_t data,DataType_t value)
{
    DoubCirLList_t *phead = head;             // 备份头结点
    DoubCirLList_t *p = head;                // 备份头结点
    DoubCirLList_t *New = DoubleCirLinkedList_NewNode(value);     
    if(NULL == New)                                         //判断新节点是否创建成功
    {
        printf("calloc NewNode is failed\n");
        return false;
    }

    if(head == head->next)                         //判断链表是否为空，则直接插入
    {    
        head->next = New;                          //头结点next连接新结点
        New->next = New;                          //新结点next连接新结点本身
        New->prev = New;                          //新结点prev连接新结点本身
        return true;
    }
   
    while(phead->next  && phead->data != data)    //再循环再次到尾巴结点时退出，说明没有该数据   
    {
        phead = phead->next;       // 遍历链表，找到和data相同的节点时（phead）退出，或者当循环到尾结点结束
        if(head->next == phead->next)
        {
            break;
        }    
    }
    //头插
    if(phead->next == head->next && phead->data != data)              //当phead到尾结点时导致退出时，且没找该data，函数直接退出
    {
        printf("not found this data\n");
        return false;       
    }
    //如果遍历链表发现目标结点，分为三种可能（头插，尾插，中间插）,头插和中间插入相同
    //头插
    if(phead == phead->next)          //结点的next是本身时，说明只有一个首结点
    {
        phead->prev = New;
        New->next = phead;
        phead->next = New;
        New->prev = phead;
    }
    //中间插入
    else if(phead != phead->next && phead->next != NULL)
    {
        New->prev = phead->prev;         //将指定插入结点的直接后继的地址给新节点的next
        phead->prev->next = New;         //将New的地址给指定插入结点的直接后继的prev
        New->next = phead;               //将新节点的地址给指定插入结点的next         
        phead->prev = New;               //将指定插入结点的地址给新节点的prev
    }
    //尾插
    else if(phead->next == head->next)       //当找到的指定结点指向首结点时，就是尾结点了
    {
        New->next = phead->next;
        phead->next = New;
        New->prev = phead;
        New->next->prev = New;
    }

    return true;
}

删除操作

删除首节点

对于删除操作咱们先进行头部删除，尾部删除和中间指定删除

  • /*******************************************************************
*
*	name	 :	DoubleCirLinkedList_HeadDelete
*	function :  删除首结点
*	argument :  @data  指定结点的数据域的数据
*	            @head  链表的头结点
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  None
* 	
* *****************************************************************/
bool DoubleCirLinkedList_HeadDelete(DoubCirLList_t *head)
{
    DoubCirLList_t *phead = head->next;      // 备份首结点

    if(head == head->next)                         //判断链表是否为空,为空直接退出
    {    
        printf("doubleLinkedList is empty\n");
        return false;
    }


    if(phead->next != phead)               //当不是只有一个首结点的时候，phead不指向本身
    {
        head->next = phead->next;          //头结点next连接首结点的直接后继
        head->next->prev = phead->prev;    //首结点的直接后继prev连接尾结点
        phead->prev->next = head->next;    //尾结点的next连接新的首结点
    }
    else                                   //当只有一个首结点的时候
    {
        head->next = head;                 //头结点指向自身
    }

    phead->prev = NULL;                  //让原首结点的prev指向NULL
    phead->next = NULL;                  //让原首结点的next直接指向NULL
    free(phead);

    return true;
}

删除尾节点

删除尾结点较为简单，操作不复杂，主要就是断开就好，就像下图所示：

/*******************************************************************
*
*	name	 :	DoubleCirLinkedList_TailDelete
*	function :  删除尾结点
*	argument :  @data  指定结点的数据域的数据
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  None
* 	
* *****************************************************************/
bool DoubleCirLinkedList_TailDelete(DoubCirLList_t *head)
{
    DoubCirLList_t *phead = head->next->prev;      // 备份尾结点

    if(head == head->next)                         //判断链表是否为空,为空直接退出
    {    
        printf("doubLinkedList is empty\n");
        return false;
    }

    if(phead->next == phead)       //只有一个首结点
    {
        head->next = head;
    }
    else
    {
        phead->prev->next = phead->next;    //让尾结点的直接前驱的next连接首结点
        phead->next->prev = phead->prev;    //让首结点连接新的尾结点
    }

    phead->prev= NULL;                 //尾结点的next指向NULL，断开与首节点的连接
    phead->prev = NULL;               //尾结点的prev指向NULL，与直接前驱断开
    free(phead);                     //对删除的结点释放，防止内存泄漏，以及段错误

    return true;
}

中间删除指定结点

找到指定结点，但需要考虑多种情况，比如链表就一个首结点，链表为空，指定结点为首结点或者尾结点，简单图示如下：

  • /*******************************************************************
*
*	name	 :	DoubleCirLinkedList_DestDelete
*	function :  删除指定位置的结点
*	argument :  @data  指定结点的数据域的数据
*	            @head  链表的头结点
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  None
* 	
* *****************************************************************/
bool DoubleCirLinkedList_DestDelete(DoubCirLList_t *head,DataType_t data)
{
    if(head == head->next)                         //判断链表是否为空,为空直接退出
    {    
        printf("doubLinkedList is empty\n");
        return false;
    }

    DoubCirLList_t *phead = head->next;     // 备份头结点

    while(phead->next  && phead->data != data)      // 遍历链表，找到和data相同的节点时（phead）退出，
    {
        phead = phead->next;                        
        if(head->next == phead->next)                //循环到尾结点时退出 
        break;
    }

    if(phead->next == head->next && phead->data != data)              //当到达尾结点导致退出时，又没找该data，函数直接退出
    {
        printf("not found this data\n"); 
        return false;    
    }

    //头部删除，可能只有一个首结点的时候
    if(phead == head->next)                     //当目标结点为首结点
    {
        if(phead->next != phead)               //当不是只有一个首结点的时候，phead不指向本身
        {
            head->next = phead->next;          //头结点next连接首结点的直接后继
            head->next->prev = phead->prev;    //首结点的直接后继prev连接尾结点
            phead->prev->next = head->next;    //尾结点的next连接新的首结点
        }
        else                                   //当只有一个首结点的时候
        {
            head->next = head;                 //头结点指向自身
        }

        phead->prev = NULL;                  //让原首结点的prev指向NULL
        phead->next = NULL;                  //让原首结点的next直接指向NULL
        free(phead);                         //释放删除的结点
    }
    //尾部删除
    else if(phead->next == head->next)             //当phead == NULL导致退出时，找到该data
    {
        phead->prev->next = phead->next;        //尾结点的直接前驱的next指向首结点
        phead->next->prev = phead->prev;        //首结点的prev连接新的尾结点
        phead->next = NULL;
        phead->prev = NULL;
        free(phead);                     //释放删除的结点
    }
    else                                    //当删除中间结点的时候
    {
        phead->prev->next = phead->next;    //将指定的结点的next赋值给指定结点的直接前驱的next
        phead->next->prev = phead->prev;     //对删除的结点释放，防止内存泄漏，以及段错误
        phead->next = NULL;                  //将指定删除结点的next指向NULL；
        phead->prev = NULL;                  //将指定删除结点的prev指向NULL；
        free(phead);
    }

    return true;
}

打印操作

对于整个链表进行遍历，当然也有不同情况要考虑，链表为空等等，切尾结点也需要打印

  • /*******************************************************************
*
*	name	 :	DoubleCirLinkedList_Print
*	function :  遍历双向链表，并打印各结点的数据域
*	argument :  @data  指定结点的数据域的数据
*	retval	 :  None
*	author	 :  [email protected]
*	date	 :  2024/04/23
* 	note	 :  None
* 	
* *****************************************************************/
bool DoubleCirLinkedList_Print(DoubCirLList_t *head)
{
    DoubCirLList_t *phead = head;                   // 备份头结点

    if(head == head->next)                         //判断链表是否为空,为空直接退出
    {    
        printf("doubLinkedList is empty\n");
        return false;
    }

    while(phead->next)
    {
        phead = phead->next;       // 遍历链表
        if(phead->next == head->next)
        {
            printf(" %d",phead->data);      // 打印链表
            printf("\n");
            break;
        }

        printf(" %d",phead->data);      // 打印链表 
    }

    return true;
}

主函数测试

int main()
{
    DoubCirLList_t * Head =  DoubleCirLinkedList_creat();
    DoubleCirLinkedList_HeadInsert(Head,8);
    DoubleCirLinkedList_HeadInsert(Head,7);
    DoubleCirLinkedList_HeadInsert(Head,9);
    DoubleCirLinkedList_HeadInsert(Head,11);
    DoubleCirLinkedList_HeadInsert(Head,15);
    DoubleCirLinkedList_Print(Head);          //15 11 9 7 8
    DoubleCirLinkedList_TailInsert(Head,33);
    DoubleCirLinkedList_TailInsert(Head,67);
    DoubleCirLinkedList_TailInsert(Head,3);
    DoubleCirLinkedList_TailInsert(Head,22);
    DoubleCirLinkedList_Print(Head);          //15 11 9 7 8 33 67 3 22

    DoubleCirLinkedList_DestInsert(Head,22,52);
    DoubleCirLinkedList_DestInsert(Head,33,72);
    DoubleCirLinkedList_DestInsert(Head,7,1);
    DoubleCirLinkedList_Print(Head);          //15 11 9 1 7 8 72 33 67 3 52 22 

    DoubleCirLinkedList_HeadDelete(Head);
    DoubleCirLinkedList_TailDelete(Head);
    DoubleCirLinkedList_Print(Head);          //11 9 1 7 8 72 33 67 3 52

    DoubleCirLinkedList_DestDelete(Head,33); 
    DoubleCirLinkedList_DestDelete(Head,52);
    DoubleCirLinkedList_DestDelete(Head,11);
    DoubleCirLinkedList_Print(Head);   

    return 0;
}

已经经过测试验证并成功，测试结果如代码的测试结果一致，如图：

又是还剩不少作业呢，希望以上的代码能对同是初学者的你有所帮助，大家一起加油吧

标签：结点,phead,next,链表,循环,双向,New,prev,head
From： https://www.cnblogs.com/xiaobaibudongjiuwen/p/18160915

相关文章

  • 自定义单链表队列的基本接口函数（非循环队列）
    单链表构建队列的接口函数/********************************************************************文件名称: 单链表构建队列的接口函数文件作者:[email protected]创建日期:2024/04/26文件功能:对单链表循环队列的增删改查功能的定义注意事项:NoneCop......
  • 单链表根据尾插法建立
    include<stdio.h>include<stdlib.h>typedefstructslik{intdata;structslik*next;}sli;voidcreatesli(sli**head,inta[],intsize){for(inti=0;i<size;i++){sli*s=(sli*)malloc(sizeof(sli));s->data=a[i];s->next=NULL......
  • 循环顺序队以及链队
    数据结构线性结构--队链队相关接口程序设计/******************************************************************************filename:2024-04-26_ListQueue.c*author:[email protected]*date:2024-04-26*function:实现链队的接......
  • 队列_单向链表
    利用单向链表设计一个队列，实现“先进先出”的功能​ 队列的两端都允许操作，只不过要求数据只能从队列的一端插入，从队列的另一端删除，可以把队列理解为一根水管，水管有进水口和出水口。​ 一般把允许数据插入的一端称为队尾（Tail或者Rear），一般把允许删除数据的一端称为队头队首（Head或......
  • vue箭头函数、js-for循环、事件修饰符、摁键事件和修饰符、表单控制、完整购物车版本
    【箭头函数】1<!DOCTYPEhtml>2<htmllang="en">3<head>4<metacharset="UTF-8">5<title>Title</title>6<scriptsrc="https://cdn.jsdelivr.net/npm/vue/dist/vue.js">&l......
  • 以链表为基础实现链式队列
    数据结构链式队列以链表为基础实现链式队列1.思路：如果打算以链表作为基础来实现队列的操作，可以避免内存浪费以及避免内存成片移动，只需要确定队头和队尾即可，一般把链表头部作为队头，可以实现头删，把链表尾部作为队尾，可以实现尾插。2.图示：3.代码：/****************************......
  • 单链表队列
    单链表队列队列：遵循先进先出1.创建初始化队列/******************************************************************************函数名称:LinQue_Create*函数功能：创建头结点*函数参数：NONE*......
  • 查找链表倒数第k个数位置上的结点
    （1）描述算法的基本思想由题可知，该链表是个单向链表，如果要找到倒数第k个值，我们必须找到该链表的尾部，而单向链表从尾部向头部找倒数第k个值比较麻烦，所以我们可以从头部去找倒数第k个值（2）描述算法的详细实现步骤我们可以利用两个指针去遍历该链表，一个指针遍历完该链表计算出结点个数......
  • 单链表的头插法的实现
    /***@filename: 文件名称*@brief单链表的头插法的实现*@[email protected]*@date2024/04/26*@version1.0：版本*@property：属性介绍*@note补充注意说明*CopyRight(c)[email protected]*/#......
  • 数据结构—单链表队列头删尾插
    单链表队列的头删尾插/*************************************************/***@filename: 单链表队列的头删尾插.md*@brief实现对单链表队列的头删尾插*@[email protected]*@date2024/04/26*@version1.0：在下坂本，有何贵干*@property：no......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99