登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›数据结构-双向循环链表

数据结构-双向循环链表

梢疠 2025-6-7 16:15:53
双向循环链表和双向链表相比，可以直接从首结点找到尾结点，不需要再通过遍历来查找尾结点了，方便数据的增删，降低了程序的时间复杂度，其在插入删除的时候不需要定义太多的变量，减少了程序的空间复杂度。
  1. /*********************************************************************************
  2. *
  3. *
  4. * 设计双向循环链表的接口
  5. * author：jindouliu2024@163.com
  6. * date：2025.4.1
  7. *
  8. *
  9. * Copyright (c)  2024-2025   jindouliu2024@163.com   All right Reserved
  10. * *********************************************************************************/
复制代码
创建一个头结点
  1. //构造双向链表的结点,链表中所有结点的数据类型应该是相同的
  2. typedef struct DoubleCriLinkedList
  3. {
  4.         DataType_t                       data; //结点的数据域
  5.         struct DoubleCriLinkedList        *prev; //直接前驱的指针域
  6.         struct DoubleCriLinkedList        *next; //直接后继的指针域
  8. }DoubleCriLList_t;
复制代码
创建双向循环空链表
  1. //创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
  2. DoubleCriLList_t * DoubleCriLList_Create(void)
  3. {
  4.         //1.创建一个头结点并对头结点申请内存
  5.         DoubleCriLList_t *Head = (DoubleCriLList_t *)calloc(1,sizeof(DoubleCriLList_t));
  6.         if (NULL == Head)
  7.         {
  8.                 perror("Calloc memory for Head is Failed");
  9.                 exit(-1);
  10.         }
  12.         //2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
  13.         Head->prev = Head;
  14.         Head->next = Head;
  16.         //3.把头结点的地址返回即可
  17.         return Head;
  18. }
复制代码
创建新结点
  1. //创建新的结点，并对新结点进行初始化（数据域 + 指针域）
  4. DoubleCriLList_t * DoubleCriLList_NewNode(DataType_t data)
  5. {
  6.         //1.创建一个新结点并对新结点申请内存
  7.         DoubleCriLList_t *New = (DoubleCriLList_t *)calloc(1,sizeof(DoubleCriLList_t));
  8.         if (NULL == New)
  9.         {
  10.                 perror("Calloc memory for NewNode is Failed");
  11.                 return NULL;
  12.         }
  14.         //2.对新结点的数据域和指针域（2个）进行初始化
  15.         New->data = data;
  16.         New->prev = New;
  17.         New->next = New;
  19.         return New;
  20. }
复制代码
在链表头部插入元素
  1. bool DoubleCriLList_HeadInsert(DoubleCriLList_t * Head,DataType_t data)
  2. {
  3.         DoubleCriLList_t *Phead=Head->next;
  4.         //创建新结点
  5.         DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
  6.         //判断新结点创建是否成功
  7.         if(NULL == New){
  8.                 printf("HeadInsert create new node failed\n ");
  9.                 return false;
  10.         }
  11.         //判断链表是否为空
  12.         if(Head->next == Head){
  13.                 Head->next = New;
  14.                 New->next = New;
  15.                 New->prev = New;
  16.                 return true;
  17.         }
  18.         New->prev = Head->next->prev;
  19.         Head->next->prev->next = New;
  20.         New->next = Phead;
  21.         Phead->prev = New;
  22.         Head->next = New;
  23.         return true;
  25. }
复制代码
在链表尾部插入
  1. bool DoubleCriLList_TailInsert(DoubleCriLList_t * Head,DataType_t data)
  2. {
  3.         DoubleCriLList_t *Phead=Head->next;
  4.         //创建新结点
  5.         DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
  6.         //判断新结点创建是否成功
  7.         if(NULL == New){
  8.                 printf("TailInsert create new node failed\n ");
  9.                 return false;
  10.         }
  11.         //判断链表为空
  12.         if(Head->next == Head){
  13.                 Head->next = New;
  14.                 New->next = New;
  15.                 New->prev = New;
  16.                 return true;
  17.         }
  18.         New->prev = Head->next->prev;
  19.         Head->next->prev->next = New;
  20.         New->next = Head->next;
  21.         Head->next->prev = New;
  22.         return true;
  23. }
复制代码
在链表指定元素后边插入
  1. bool DoubleCriLList_DestInsert(DoubleCriLList_t * Head,DataType_t destval,DataType_t data)
  2. {
  3.         DoubleCriLList_t * Phead = Head->next;
  4.         //创建新结点
  5.         DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
  6.         //判断新结点创建是否成功
  7.         if(NULL == New){
  8.                 printf("DestInsert create new node failed\n ");
  9.                 return false;
  10.         }
  11.         //链表为空
  12.         if(Head->next == Head){
  13.                 Head->next = New;
  14.                 New->next = New;
  15.                 New->prev = New;
  16.                 return true;
  17.         }
  18.         //循环遍历查找目标结点 在中间的情况
  19.         while(Phead->next != Head->next){
  20.                 if(Phead->data == destval){
  21.                         New->next = Phead->next;
  22.                         New->prev = Phead;
  23.                         Phead->next->prev = New;
  24.                         Phead->next = New;
  25.                         return true;
  26.                 }
  27.                 Phead = Phead->next;
  28.         }
  29.         //尾结点是目标结点时
  30.         if(Phead->data == destval){
  31.                 New->prev = Head->next->prev;
  32.                 Head->next->prev->next = New;
  33.                 New->next = Head->next;
  34.                 Head->next->prev = New;
  35.         }
  36.         return true;
  37. }
复制代码
在链表头部删除元素
  1. bool DoubleCriLList_HeadDel(DoubleCriLList_t * Head)
  2. {
  3.         DoubleCriLList_t * Phead = Head->next;
  4.         //判断链表是否为空
  5.         if(Head->next == Head){
  6.                 printf("this is empty list,do not delete head\n");
  7.                 return false;
  8.         }
  9.         //只有头首结点时
  10.         if(Head->next->next == Head->next){
  11.                 Head->next->next = NULL;
  12.                 Head->next->prev = NULL;
  13.                 free(Head->next);
  14.                 Head->next = Head;
  15.         }
  16.         else{
  17.                 Head->next->prev->next = Head->next->next;
  18.                 Head->next->next->prev = Head->next->prev;
  19.                 Head->next = Head->next->next;
  20.                 Phead->next = NULL;
  21.                 Phead->prev = NULL;
  22.                 free(Phead);
  23.         }
  24.         return true;
  26. }
复制代码
在链表尾部删除元素
  1. bool DoubleCriLList_TailDel(DoubleCriLList_t * Head)
  2. {
  3.         DoubleCriLList_t * Phead = Head->next->prev;//记录尾结点
  4.         //判断链表是否为空
  5.         if(Head->next == Head){
  6.                 printf("this is empty list,do not delete tail\n");
  7.                 return false;
  8.         }
  9.         //只有头首结点时
  10.         if(Head->next->next == Head->next){
  11.                 Head->next->next = NULL;
  12.                 Head->next->prev = NULL;
  13.                 free(Head->next);
  14.                 Head->next = Head;
  15.         }
  16.         else{
  17.                 Phead->prev->next = Head->next;//Head->next->prev->prev->next = Head->next;
  18.                 Head->next->prev = Phead->prev;//Head->next->prev = Head->next->prev->prev;
  19.                 Phead->prev = NULL;
  20.                 Phead->next = NULL;
  21.                 free(Phead);
  22.         }
  23.         return true;
  25. }
复制代码
删除指定元素
  1. bool DoubleCriLList_DestDel(DoubleCriLList_t * Head,DataType_t destval)
  2. {
  3.         DoubleCriLList_t * Phead = Head->next;
  4.         //判断链表是否为空
  5.         if(Head->next == Head){
  6.                 printf("this is empty list,do not delete tail\n");
  7.                 return false;
  8.         }
  9.         //只有头首结点,首结点为目标结点时
  10.         if(Head->next->next == Head->next && Phead->data == destval){
  11.                 Head->next->next = NULL;
  12.                 Head->next->prev = NULL;
  13.                 free(Head->next);
  14.                 Head->next = Head;
  15.         }
  16.         //目标元素在首结点
  17.         else if(Phead->data == destval){
  18.                 Head->next->prev->next = Head->next->next;
  19.                 Head->next->next->prev = Head->next->prev;
  20.                 Head->next = Head->next->next;
  21.                 Phead->next = NULL;
  22.                 Phead->prev = NULL;
  23.                 free(Phead);
  24.         }
  25.         else{
  26.                 //目标元素在中间时
  27.                 while(Phead->next != Head->next){
  28.                         if(Phead->data == destval){
  29.                                 Phead->next->prev = Phead->prev;
  30.                                 Phead->prev->next = Phead->next;
  31.                                 Phead->next = NULL;
  32.                                 Phead->prev = NULL;
  33.                                 free(Phead);
  34.                                 return true;
  35.                         }
  36.                         Phead = Phead->next;
  37.                 }
  38.         }
  39.         //目标元素在尾结点
  40.         if(Phead->data == destval){
  41.                 Phead->prev->next = Head->next;//Head->next->prev->prev->next = Head->next;
  42.                 Head->next->prev = Phead->prev;//Head->next->prev = Head->next->prev->prev;
  43.                 Phead->prev = NULL;
  44.                 Phead->next = NULL;
  45.                 free(Phead);
  46.         }
  47.         else if(Phead->data != destval){
  48.                 printf("do not find this value\n");
  49.         }
  50.         return true;
  51. }
复制代码
循环遍历打印链表
  1. bool DoubleCriLList_Print(DoubleCriLList_t * Head)
  2. {
  3.         DoubleCriLList_t * Phead = Head;
  4.         //判断链表是否为空
  5.         if(Head->next == Head){
  6.                 printf("this is empty DoubleCriList\n");
  7.                 return false;
  8.         }
  9.         //循环遍历链表
  10.         while(Phead->next)
  11.         {
  12.                 //把头结点的直接后继作为新的头结点
  13.                 Phead = Phead->next;
  15.                 //输出头结点的直接后继的数据域
  16.                 printf("data = %d\n",Phead->data);
  18.                 //判断是否到达尾结点，尾结点的next指针是指向首结点的地址
  19.                 if (Phead->next == Head->next)
  20.                 {
  21.                         break;
  22.                 }       
  23.         }
  25.         return true;
  26. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
梢疠
2025-6-7 16:15:53

0

粉丝关注

12

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫