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

CSDN热搜

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

数据结构-双向链表

涅牵 2025-6-7 16:14:54
单向链表只能找它的直接后继，而不能找到直接前驱，而双向链表不仅能找到直接后继，而且也能找到直接前驱
  1. /*******************************************************************************
  2. *
  3. *
  4. * 设计双向链表的接口
  5. * author：jindouliu2024@163.com
  6. * date：2025.3.29
  7. *
  8. *
  9. * Copyright (c)  2024-2025   jindouliu2024@163.com   All right Reserved
  10. * *******************************************************************************/
复制代码
配置双向链表的头首节点
  1. typedef struct DoubleLinkedList
  2. {
  3.         DataType_t                       data; //结点的数据域
  4.         struct DoubleLinkedList        *prev; //直接前驱的指针域
  5.         struct DoubleLinkedList        *next; //直接后继的指针域
  7. }DoubleLList_t;
复制代码
创建一个空的链表
  1. //创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
  2. DoubleLList_t * DoubleLList_Create(void)
  3. {
  4.         //1.创建一个头结点并对头结点申请内存
  5.         DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
  6.         if (NULL == Head)
  7.         {
  8.                 perror("Calloc memory for Head is Failed");
  9.                 exit(-1);
  10.         }
  12.         //2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
  13.         Head->prev = NULL;
  14.         Head->next = NULL;
  16.         //3.把头结点的地址返回即可
  17.         return Head;
  18. }
复制代码
创建一个新的结点
  1. DoubleLList_t * DoubleLList_NewNode(DataType_t data)
  2. {
  3.         //1.创建一个新结点并对新结点申请内存
  4.         DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
  5.         if (NULL == New)
  6.         {
  7.                 perror("Calloc memory for NewNode is Failed");
  8.                 return NULL;
  9.         }
  11.         //2.对新结点的数据域和指针域（2个）进行初始化
  12.         New->data = data;
  13.         New->prev = NULL;
  14.         New->next = NULL;
  16.         return New;
  17. }
复制代码
头插结点
  1. bool DoubleLList_HeadInsert(DoubleLList_t * Head,DataType_t data)
  2. {
  3.         //创建新结点
  4.         DoubleLList_t * New= DoubleLList_NewNode(data);
  5.         //判断新结点创建是否成功
  6.         if(NULL == New){
  7.                 printf("HeadInsert create new node failed\n ");
  8.                 return false;
  9.         }
  10.         //判断链表是否为空
  11.         if(Head->next == NULL){
  12.                 Head->next = New;
  13.                
  14.                 return true;
  15.         }
  16.         New->next = Head->next;
  17.         Head->next->prev = New;
  18.         Head->next = New;
  19.         return true;
  21. }
复制代码
尾插结点
  1. bool DoubleLList_TailInsert(DoubleLList_t * Head,DataType_t data)
  2. {
  3.         DoubleLList_t * Phead = Head;
  4.         //创建新结点
  5.         DoubleLList_t * New= DoubleLList_NewNode(data);
  6.         //判断新结点创建是否成功
  7.         if(NULL == New){
  8.                 printf("HeadInsert create new node failed\n ");
  9.                 return false;
  10.         }
  11.         //判断链表是否为空
  12.         if(Head->next == NULL){
  13.                 Head->next = New;
  14.                 return true;
  15.         }
  16.         //遍历找到尾结点
  17.         while(Phead->next != NULL){
  18.                 Phead = Phead->next;
  19.         }
  20.         Phead->next = New;
  21.         New->prev = Phead;
  22.         return true;
  23. }
复制代码
指定目标结点后边插入
  1. bool DoubleLList_DestInsert(DoubleLList_t * Head,DataType_t destval,DataType_t data)
  2. {
  3.         DoubleLList_t * Phead = Head->next;
  4.         //创建新结点
  5.         DoubleLList_t * New= DoubleLList_NewNode(data);
  6.         //判断新结点创建是否成功
  7.         if(NULL == New){
  8.                 printf("HeadInsert create new node failed\n ");
  9.                 return false;
  10.         }
  11.         //判断链表是否为空
  12.         if(Head->next == NULL){
  13.                 Head->next = New;
  14.                 return true;
  15.         }
  16.         //循环找到目标结点
  17.         while(Phead->next != NULL && Phead->data != destval){
  18.                 Phead = Phead->next;
  19.         }
  20.         //如果目标不是尾结点
  21.         if(Phead->next == NULL && Phead->data != destval){
  22.                 printf("do not find destval\n");
  23.                 return false;
  24.         }
  25.         //如果目标是尾结点
  26.         if(Phead->next == NULL && Phead->data == destval){
  27.                 Phead->next = New;
  28.                 New->prev = Phead;
  29.         }
  30.         else{
  31.         New->next = Phead->next;
  32.         Phead->next->prev = New;
  33.         New->prev = Phead;
  34.         Phead->next = New;
  35.         }
  36.         return true;
  38. }
复制代码
头删结点
  1. bool DoubleLList_HeadDel(DoubleLList_t * Head)
  2. {
  3.         DoubleLList_t * Phead = Head->next;
  4.         //判断链表是否为空
  5.         if(Head->next == NULL){
  6.                 printf("this is empty list,do not delete head\n");
  7.                 return false;
  8.         }
  9.         Head->next = Phead->next;
  10.         Phead->next = NULL;
  11.         Head->next->prev = NULL;
  12.         free(Phead);
  13.         return true;
  15. }
复制代码
尾删结点
  1. bool DoubleLList_TailDel(DoubleLList_t * Head)
  2. {
  3.         DoubleLList_t * Phead = Head->next;
  4.         //判断链表是否为空
  5.         if(Head->next == NULL){
  6.                 printf("this is empty list,do not delete head\n");
  7.                 return false;
  8.         }
  9.         //遍历找到尾结点
  10.         while(Phead->next != NULL){
  11.                 Phead = Phead->next;
  12.         }       
  13.         Phead->prev->next = NULL;
  14.         Phead->prev = NULL;
  15.         free(Phead);
  16.         return true;
  17. }
复制代码
指定目标结点删除
  1. bool DoubleLList_DestDel(DoubleLList_t * Head,DataType_t destval)
  2. {
  3.         DoubleLList_t * Phead = Head->next;
  4.         //判断链表是否为空
  5.         if(Head->next == NULL){
  6.                 printf("this is empty list,do not delete head\n");
  7.                 return false;
  8.         }
  9.         //循环遍历查找目标元素
  10.         while(Phead->next != NULL && Phead->data != destval){
  11.                 Phead = Phead->next;
  12.         }
  13.         //查找到链表尾部，还没有找到destval，则直接退出
  14.         if(Phead->next == NULL && Phead->data != destval){
  15.                 printf("can not find this destval,do not delete\n");
  16.                 return false;
  17.         }
  18.         //只有头结点和首节点
  19.         if(Head->next->next == NULL && Head->next->data == destval)
  20.         {
  21.                 Head->next = NULL;
  22.                 Phead->prev = NULL;
  23.                 free(Phead);
  24.         }
  25.         //最后一个结点是目标结点
  26.         else if(Phead->next == NULL && Phead->data == destval){
  27.                 Phead->prev->next = NULL;
  28.                 Phead->prev = NULL;
  29.                 free(Phead);
  30.                 //return true;
  31.         }
  32.         //目标结点在首结点
  33.         else if(Head->next == Phead){
  34.                 Head->next = Phead->next;
  35.                 Phead->next = NULL;
  36.                 Head->next->prev = NULL;
  37.                 free(Phead);
  38.                 //return true;
  39.         }
  40.         //目标结点不在首尾结点
  41.         else{
  42.                 Phead->prev->next = Phead->next;
  43.                  Phead->next->prev = Phead->prev;
  44.                 Phead->next = NULL;
  45.                  Phead->prev = NULL;
  46.                 free(Phead);
  47.         }
  48.          // Phead->prev->next = Phead->next;
  49.          // Phead->next->prev = Phead->prev;
  50.          // Phead->next = NULL;
  51.          // Phead->prev = NULL;
  52.          // free(Phead);
  53.          return true;
  54. }
复制代码
循环打印
  1. bool DoubleLList_Print(DoubleLList_t * Head)
  2. {
  3.         DoubleLList_t * Phead = Head;
  4.         //判断链表是否为空
  5.         if(Head->next == NULL){
  6.                 printf("this is empty DoubleList\n");
  7.                 return false;
  8.         }
  9.         //循环遍历链表
  10.         while(Phead != NULL){
  11.                 Phead = Phead->next;
  12.                 printf("data = %d\n",Phead->data);
  13.                 if(Phead->next == NULL){
  14.                         break;
  15.                 }
  16.                
  17.         }
  18.         return true;
  19. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

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

0

粉丝关注

13

主题发布

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