devbox
寸_铁
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（学习）2024.8.9（双向链表）

作者：寸_铁 | 2024-08-10 16:35:16

赞

踩

数据结构（学习）2024.8.9（双向链表）

今天学习的是线性表里面的最后一部分双向链表

栈和队列的相关知识可以查看http://t.csdnimg.cn/R1ls3

链表的相关知识可以查看http://t.csdnimg.cn/NX464

顺序表的相关知识可以查看http://t.csdnimg.cn/5IMAZ

目录

双向链表

结构体

操作函数

1.创建一个空的双向链表

2.向双向链表的指定位置插入数据

3.遍历双向链表

4.删除双向链表指定位置的数据

5.删除双向链表中的指定数据

双向链表的相关操作案例

双向链表

1.逻辑结构：线性结构
2.存储结构：链式存储
3.操作：增、删、改、查

结构体

typedef struct node_t
{
    datatype data;          // 数据域
    struct node_t *next;  // 指向下一个节点的指针 next 下一个
    struct node_t *prior; // 指向前一个节点的指针 prior 前一个
} link_node_t, *link_list_t;

// 将双向链表的头指针和尾指针封装到一个结构体里，有点像学的链式队列

typedef struct doublelinklist
{
    link_list_t head; // 指向双向链表的头指针
    link_list_t tail; // 指向双向链表的尾指针
    int len;
} double_node_t, *double_list_t;

操作函数

1.创建一个空的双向链表

  1. double_list_t createEmptyDoubleLinkList()
  2. {
  3.     double_list_t p = (double_list_t)malloc(sizeof(double_node_t));
  4.     if (p == NULL)
  5.     {
  6.         perror("createEmptyDoubleLinkList函数创建结构体出错\n");
  7.         return NULL;
  8.     }
  9.     p->len = 0;
  10.     p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));
  11.     if (p->head == NULL)
  12.     {
  13.         perror("createEmptyDoubleLinkList创建链表节点出错\n");
  14.         return NULL;
  15.     }
  16.     p->head->next = NULL;
  17.     p->head->prior = NULL;
  18.     return p;
  19. }

2.向双向链表的指定位置插入数据

  1. int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
  2. {
  3.     // 1.容错判断
  4.     if (post < 0 || post > p->len)
  5.     {
  6.         perror("insertIntoDoubleLinkList函数出错\n");
  7.         return -1;
  8.     }
  9.  
  10.     // 2.开辟一个新节点空间存放数据
  11.     link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
  12.     if (pnew == NULL)
  13.     {
  14.         perror("insertIntoDoubleLinkList函数创建新节点出错\n");
  15.         return -1;
  16.     }
  17.     pnew->data = data;
  18.     pnew->next = NULL;
  19.     pnew->prior = NULL;
  20.  
  21.     link_list_t temp = NULL;
  22.     // 3.将结点插入链表
  23.     //  (1).先对插入的位置进行判断
  24.     if (post == p->len) // 尾插
  25.     {
  26.         p->tail->next = pnew;
  27.         pnew->prior = p->tail;
  28.         p->tail = pnew; // 移动尾指针
  29.     }
  30.     else // 中间插
  31.     {
  32.         // (1)将temp移动到被插入的位置
  33.         if (post < p->len / 2) // 前半段
  34.         {
  35.             temp = p->head;
  36.             for (int i = 0; i <= post; i++)
  37.             {
  38.                 temp = temp->next;
  39.             }
  40.         }
  41.         else // 后半段
  42.         {
  43.             temp = p->tail;
  44.             for (int i = 0; i < p->len - 1 - post; i++)
  45.             {
  46.                 temp = temp->prior;
  47.             }
  48.         }
  49.         // (2)进行插入操作(先连前面，再连后面)
  50.         temp->prior->next = pnew;
  51.         pnew->prior = temp->prior;
  52.         pnew->next = temp;
  53.         temp->prior = pnew;
  54.     }
  55.  
  56.     // 长度+1
  57.     p->len++;
  58.  
  59.     return 0;
  60. }

3.遍历双向链表

  1. void showDoubleLinkList(double_list_t p)
  2. {
  3.     link_list_t temp = NULL;
  4.     printf("正向遍历:\n");
  5.     temp = p->head;
  6.     while (temp->next != NULL)
  7.     {
  8.         temp = temp->next;
  9.         printf("%d ", temp->data);
  10.     }
  11.     printf("\n");
  12.  
  13.     printf("反向遍历:\n");
  14.     temp = p->tail;
  15.     while (temp != p->head)
  16.     {
  17.         printf("%d ", temp->data);
  18.         temp = temp->prior;
  19.     }
  20.     printf("\n");
  21. }

4.删除双向链表指定位置的数据

  1. int deletePostDoubleLinkList(double_list_t p, int post)
  2. {
  3.     // 1.容错判断
  4.     if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p))
  5.     {
  6.         perror("deletePostDoubleLinkList函数出错\n");
  7.         return -1;
  8.     }
  9.     // 2.对删除的位置进行判断
  10.     link_list_t temp = NULL;
  11.     if (post == p->len - 1) // 尾删
  12.     {
  13.         // 向前移动尾指针
  14.         p->tail = p->tail->prior;
  15.  
  16.         // 释放被删除的节点
  17.         free(p->tail->next);
  18.         p->tail->next = NULL;
  19.     }
  20.     else // 中间删
  21.     {
  22.         // (1)将temp移动到要删除的位置
  23.         if (post < p->len / 2) // 前半段
  24.         {
  25.             temp = p->head;
  26.             for (int i = 0; i <= post; i++)
  27.             {
  28.                 temp = temp->next;
  29.             }
  30.         }
  31.         else // 后半段
  32.         {
  33.             temp = p->tail;
  34.             for (int i = 0; i < p->len - 1 - post; i++)
  35.             {
  36.                 temp = temp->prior;
  37.             }
  38.         }
  39.         // (2)进行删除
  40.         temp->prior->next = temp->next;
  41.         temp->next->prior = temp->prior;
  42.  
  43.         free(temp);
  44.         temp = NULL;
  45.     }
  46.  
  47.     // 长度-1
  48.     p->len--;
  49.     return 0;
  50. }

5.删除双向链表中的指定数据

  1. int deleteDataDoubleLinkList(double_list_t p, datatype data)
  2. {
  3.     if (isEmptyDoubleLinkList(p))
  4.     {
  5.         perror("deleteDataDoubleLinkList函数出错\n");
  6.         return -1;
  7.     }
  8.     link_list_t q = p->head->next;
  9.     while (q != NULL)
  10.     {
  11.         if (q->data == data) // 删除
  12.         {
  13.             if (q == p->tail) // 尾删
  14.             {
  15.                 p->tail = p->tail->prior;
  16.                 free(p->tail->next);
  17.                 p->tail->next = NULL;
  18.                 q = NULL;
  19.             }
  20.             else // 中间删
  21.             {
  22.                 q->prior->next = q->next;
  23.                 q->next->prior = q->prior;
  24.                 link_list_t pdel = q;
  25.                 q = q->next;
  26.                 free(pdel);
  27.                 pdel = NULL;
  28.             }
  29.             p->len--;
  30.         }
  31.         else // 不相等
  32.         {
  33.             q = q->next;
  34.         }
  35.     }
  36.     return 0;
  37. }

双向链表的相关操作案例

头文件doublelinklist.h：

  1. #ifndef _DOUBLELINKLIST_H_
  2. #define _DOUBLELINKLIST_H_
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. typedef int datatype;
  6. typedef struct node_t
  7. {
  8. 	datatype data;		  // 数据域
  9. 	struct node_t *next;  // 指向下一个节点的指针 next 下一个
  10. 	struct node_t *prior; // 指向前一个节点的指针 prior 前一个
  11. } link_node_t, *link_list_t;
  12.  
  13. // 将双向链表的头指针和尾指针封装到一个结构体里
  14. // 思想上有点像学的链式队列
  15. typedef struct doublelinklist
  16. {
  17. 	link_list_t head; // 指向双向链表的头指针
  18. 	link_list_t tail; // 指向双向链表的尾指针
  19. 	int len;
  20. } double_node_t, *double_list_t;
  21.  
  22. // 1.创建一个空的双向链表
  23. double_list_t createEmptyDoubleLinkList();
  24. // 2.向双向链表的指定位置插入数据 post位置， data数据
  25. int insertIntoDoubleLinkList(double_list_t p, int post, datatype data);
  26. // 3.遍历双向链表
  27. void showDoubleLinkList(double_list_t p);
  28. // 4.删除双向链表指定位置的数据
  29. int deletePostDoubleLinkList(double_list_t p, int post);
  30. // 5.判断双向链表是否为空
  31. int isEmptyDoubleLinkList(double_list_t p);
  32. // 6.求双向链表的长度
  33. int lengthDoubleLinkList(double_list_t p);
  34. // 7.查找指定数据出现的位置 data被查找的数据
  35. int searchPostDoubleLinkList(double_list_t p, datatype data);
  36. // 8.修改指定位置的数据,post修改的位置 data被修改的数据
  37. int changeDataDoubleLinkList(double_list_t p, int post, datatype data);
  38. // 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
  39. int deleteDataDoubleLinkList(double_list_t p, datatype data);
  40. #endif

双向链表函数doublelinklist.c：

  1. #include "doublelinklist.h"
  2. // 1.创建一个空的双向链表
  3. double_list_t createEmptyDoubleLinkList()
  4. {
  5.     double_list_t p = (double_list_t)malloc(sizeof(double_node_t));
  6.     if (p == NULL)
  7.     {
  8.         perror("createEmptyDoubleLinkList函数创建结构体出错\n");
  9.         return NULL;
  10.     }
  11.     p->len = 0;
  12.     p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));
  13.     if (p->head == NULL)
  14.     {
  15.         perror("createEmptyDoubleLinkList创建链表节点出错\n");
  16.         return NULL;
  17.     }
  18.     p->head->next = NULL;
  19.     p->head->prior = NULL;
  20.     return p;
  21. }
  22.  
  23. // 2.向双向链表的指定位置插入数据 post位置， data数据
  24. int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
  25. {
  26.     // 1.容错判断
  27.     if (post < 0 || post > p->len)
  28.     {
  29.         perror("insertIntoDoubleLinkList函数出错\n");
  30.         return -1;
  31.     }
  32.  
  33.     // 2.开辟一个新节点空间存放数据
  34.     link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));
  35.     if (pnew == NULL)
  36.     {
  37.         perror("insertIntoDoubleLinkList函数创建新节点出错\n");
  38.         return -1;
  39.     }
  40.     pnew->data = data;
  41.     pnew->next = NULL;
  42.     pnew->prior = NULL;
  43.  
  44.     link_list_t temp = NULL;
  45.     // 3.将结点插入链表
  46.     //  (1).先对插入的位置进行判断
  47.     if (post == p->len) // 尾插
  48.     {
  49.         p->tail->next = pnew;
  50.         pnew->prior = p->tail;
  51.         p->tail = pnew; // 移动尾指针
  52.     }
  53.     else // 中间插
  54.     {
  55.         // (1)将temp移动到被插入的位置
  56.         if (post < p->len / 2) // 前半段
  57.         {
  58.             temp = p->head;
  59.             for (int i = 0; i <= post; i++)
  60.             {
  61.                 temp = temp->next;
  62.             }
  63.         }
  64.         else // 后半段
  65.         {
  66.             temp = p->tail;
  67.             for (int i = 0; i < p->len - 1 - post; i++)
  68.             {
  69.                 temp = temp->prior;
  70.             }
  71.         }
  72.         // (2)进行插入操作(先连前面，再连后面)
  73.         temp->prior->next = pnew;
  74.         pnew->prior = temp->prior;
  75.         pnew->next = temp;
  76.         temp->prior = pnew;
  77.     }
  78.  
  79.     // 长度+1
  80.     p->len++;
  81.  
  82.     return 0;
  83. }
  84.  
  85. // 3.遍历双向链表
  86. void showDoubleLinkList(double_list_t p)
  87. {
  88.     link_list_t temp = NULL;
  89.     printf("正向遍历:\n");
  90.     temp = p->head;
  91.     while (temp->next != NULL)
  92.     {
  93.         temp = temp->next;
  94.         printf("%d ", temp->data);
  95.     }
  96.     printf("\n");
  97.  
  98.     printf("反向遍历:\n");
  99.     temp = p->tail;
  100.     while (temp != p->head)
  101.     {
  102.         printf("%d ", temp->data);
  103.         temp = temp->prior;
  104.     }
  105.     printf("\n");
  106. }
  107.  
  108. // 4.删除双向链表指定位置的数据
  109. int deletePostDoubleLinkList(double_list_t p, int post)
  110. {
  111.     // 1.容错判断
  112.     if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p))
  113.     {
  114.         perror("deletePostDoubleLinkList函数出错\n");
  115.         return -1;
  116.     }
  117.     // 2.对删除的位置进行判断
  118.     link_list_t temp = NULL;
  119.     if (post == p->len - 1) // 尾删
  120.     {
  121.         // 向前移动尾指针
  122.         p->tail = p->tail->prior;
  123.  
  124.         // 释放被删除的节点
  125.         free(p->tail->next);
  126.         p->tail->next = NULL;
  127.     }
  128.     else // 中间删
  129.     {
  130.         // (1)将temp移动到要删除的位置
  131.         if (post < p->len / 2) // 前半段
  132.         {
  133.             temp = p->head;
  134.             for (int i = 0; i <= post; i++)
  135.             {
  136.                 temp = temp->next;
  137.             }
  138.         }
  139.         else // 后半段
  140.         {
  141.             temp = p->tail;
  142.             for (int i = 0; i < p->len - 1 - post; i++)
  143.             {
  144.                 temp = temp->prior;
  145.             }
  146.         }
  147.         // (2)进行插入删除
  148.         temp->prior->next = temp->next;
  149.         temp->next->prior = temp->prior;
  150.  
  151.         free(temp);
  152.         temp = NULL;
  153.     }
  154.  
  155.     // 长度-1
  156.     p->len--;
  157.     return 0;
  158. }
  159. // 5.判断双向链表是否为空
  160. int isEmptyDoubleLinkList(double_list_t p)
  161. {
  162.     return p->len == 0;
  163. }
  164. // 6.求双向链表的长度
  165. int lengthDoubleLinkList(double_list_t p)
  166. {
  167.     return p->len;
  168. }
  169.  
  170. // 7.查找指定数据出现的位置 data被查找的数据
  171. int searchPostDoubleLinkList(double_list_t p, datatype data)
  172. {
  173.     link_list_t q = p->head;
  174.     int post = 0;
  175.     while (q->next != NULL)
  176.     {
  177.         q = q->next;
  178.         if (q->data == data)
  179.         {
  180.             return post;
  181.         }
  182.         post++;
  183.     }
  184.     return -1;
  185. }
  186.  
  187. // 8.修改指定位置的数据,post修改的位置 data被修改的数据
  188. int changeDataDoubleLinkList(double_list_t p, int post, datatype data)
  189. {
  190.     // 1.容错判断
  191.     if (post < 0 || post >= p->len)
  192.     {
  193.         perror("changeDataDoubleLinkList函数出错\n");
  194.         return -1;
  195.     }
  196.  
  197.     // 2.移动指针
  198.     link_list_t temp = NULL;
  199.     if (post < p->len / 2) // 前半段
  200.     {
  201.         temp = p->head;
  202.         for (int i = 0; i <= post; i++)
  203.         {
  204.             temp = temp->next;
  205.         }
  206.     }
  207.     else // 后半段
  208.     {
  209.         temp = p->tail;
  210.         for (int i = 0; i < p->len - 1 - post; i++)
  211.         {
  212.             temp = temp->prior;
  213.         }
  214.     }
  215.     // 3.修改数据
  216.     temp->data = data;
  217.     return 0;
  218. }
  219.  
  220. // 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
  221. int deleteDataDoubleLinkList(double_list_t p, datatype data)
  222. {
  223.     if (isEmptyDoubleLinkList(p))
  224.     {
  225.         perror("deleteDataDoubleLinkList函数出错\n");
  226.         return -1;
  227.     }
  228.     link_list_t q = p->head->next;
  229.     while (q != NULL)
  230.     {
  231.         if (q->data == data) // 删除
  232.         {
  233.             if (q == p->tail) // 尾删
  234.             {
  235.                 p->tail = p->tail->prior;
  236.                 free(p->tail->next);
  237.                 p->tail->next = NULL;
  238.                 q = NULL;
  239.             }
  240.             else // 中间删
  241.             {
  242.                 q->prior->next = q->next;
  243.                 q->next->prior = q->prior;
  244.                 link_list_t pdel = q;
  245.                 q = q->next;
  246.                 free(pdel);
  247.                 pdel = NULL;
  248.             }
  249.             p->len--;
  250.         }
  251.         else // 不相等
  252.         {
  253.             q = q->next;
  254.         }
  255.     }
  256.     return 0;
  257. }

主函数main.c：

  1. #include "doublelinklist.h"
  2.  
  3. int main(int argc, char const *argv[])
  4. {
  5.     int post;
  6.     int data;
  7.     double_list_t p = createEmptyDoubleLinkList();
  8.  
  9.     insertIntoDoubleLinkList(p, 0, 1);
  10.     insertIntoDoubleLinkList(p, 1, 2);
  11.     insertIntoDoubleLinkList(p, 2, 3);
  12.     insertIntoDoubleLinkList(p, 3, 4);
  13.     printf("双向链表为:\n");
  14.     showDoubleLinkList(p);
  15.     printf("双向链表的长度为：\n");
  16.     printf("%d\n", lengthDoubleLinkList(p));
  17.  
  18.     printf("请输入你要插入的数据的位置和数据:\n");
  19.     scanf(" %d %d", &post, &data);
  20.     insertIntoDoubleLinkList(p, post, data);
  21.     printf("插入数据以后的双向链表为:\n");
  22.     showDoubleLinkList(p);
  23.  
  24.     printf("请输入你要删除的数据的位置:\n");
  25.     scanf(" %d", &post);
  26.     deletePostDoubleLinkList(p, post);
  27.     printf("删除以后的双向链表为:\n");
  28.     showDoubleLinkList(p);
  29.  
  30.     printf("双向链表的长度为：\n");
  31.     printf("%d\n", lengthDoubleLinkList(p));
  32.  
  33.     printf("请输入你要查询的数据：\n");
  34.     scanf(" %d", &data);
  35.     printf("该数据的位置为：%d\n", searchPostDoubleLinkList(p, data));
  36.  
  37.     printf("请输入你要修改的数据的位置和数据:\n");
  38.     scanf(" %d %d", &post, &data);
  39.     changeDataDoubleLinkList(p, post, data);
  40.     printf("修改数据以后的双向链表为:\n");
  41.     showDoubleLinkList(p);
  42.  
  43.     printf("请输入你要删除的数据:\n");
  44.     scanf(" %d", &data);
  45.     deleteDataDoubleLinkList(p, data);
  46.     printf("删除数据以后的双向链表为:\n");
  47.     showDoubleLinkList(p);
  48.  
  49.     printf("双向链表的长度为：\n");
  50.     printf("%d\n", lengthDoubleLinkList(p));
  51.  
  52.     return 0;
  53. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/959370
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号