• 双向链表（带头双向循环链表）的实现

    前言：前面实现的单向链表，全称是不带头单向不循环链表。这里实现带头双向不循环链表，比单向链表好实现一点。

    目录

    链表的分类

    单向链表与双向链表的比较：

     双向链表的节点的定义：

    多文件实现：

    List.h来看一下需要实现的函数接口：

    List.c的各个函数的实现：

    创建节点的函数：

    链表的初始化：

    尾插：

    头插：

    打印链表：

    尾删： 

    头删：

    查找

    插入（在指定位置之后插入）：

    删除指定位置的数据：

    销毁链表：

    实现双链表的全部源码：

    List.h：

    List.c：

    test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！

    结语：

    链表的分类

    将是否带头，单向还是双向，是否循环，随机组合一共有八种类型，只要会写不带头单向不循环链表和带头双向循环链表这两个链表，其他的链表实现起来就简单多了。

    单向链表与双向链表的比较：

    单向链表双向链表
    是否带头不带头带头（有哨兵位）
    单向还是双向单向双向
    是否循环不循环循环

    逻辑图解比较：

     双向链表的节点的定义：

    1. typedef int LTTypeData;
    2. typedef struct ListNode
    3. {
    4. 	LTTypeData data;
    5. 	struct ListNode* prev;
    6. 	struct ListNode* next;
    7. }LTNode;

    prev指向前一个节点

    next指向下一个节点

    data存储数据

    为什么tydef一个新的数据类型是为了方便以后修改存储的数据类型。

    多文件实现：

    文件名称负责的功能
    List.h链表的定义，需要用到库里的头文件的包含，链表需要实现函数的声明。
    List.c链表函数的实现
    test.c测试接口（这里大家可以自己测，自己写）

    这里的建议是每写一个接口就测试一个接口，省得全写完在测试，有一堆麻烦，还没开始解决麻烦，就先把自己的心态搞崩了。

    List.h来看一下需要实现的函数接口：

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. typedef int LTTypeData;
    7. typedef struct ListNode
    8. {
    9. 	LTTypeData data;
    10. 	struct ListNode* prev;
    11. 	struct ListNode* next;
    12. }LTNode;
    13.  
    14. //初始化链表
    15. void LTInite(LTNode** pphead);
    16. //尾插
    17. void LTPushBack(LTNode* phead, LTTypeData x);
    18. //头插
    19. void LTPushFront(LTNode* phead, LTTypeData x);
    20. //头删
    21. void LTPopFront(LTNode* phead);
    22. //尾删
    23. void LTPopBack(LTNode* phead);
    24. //打印链表中的数据
    25. void LTPrint(LTNode* phead);
    26. //查找
    27. LTNode* LTFind(LTNode* phead, LTTypeData x);
    28. //在指定位置之后插入
    29. void LTInsert(LTNode* pos, LTTypeData x);
    30. //删除指定位置的数据
    31. void LTErase(LTNode* pos);
    32. //销毁链表
    33. void LTDestroy(LTNode* phead);

    List.c的各个函数的实现：

    因为会频繁的创建新的节点，这里直接将创建新的节点分装成一个函数。

    创建节点的函数：

    1. LTNode* LTBuyNode(LTTypeData x)
    2. {
    3. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    4. 	if (newnode == NULL)
    5. 	{
    6. 		perror("malloc");
    7. 		exit(1);
    8. 	}
    9. 	newnode->data = x;
    10. 	newnode->next = newnode;
    11. 	newnode->prev = newnode;
    12. 	return newnode;
    13. }

    注意这里创建出的节点的next和prev指针都指向自己。

    图解：

    链表的初始化：

    1. void LTInite(LTNode** pphead)
    2. {
    3. 	assert(pphead);//链表不能无效
    4. 	*pphead = LTBuyNode(-1);
    5. }

    这里*pphead指向的节点为头结点（哨兵位），哨兵位的数据为无用的数据。

    尾插：

    1. void LTPushBack(LTNode* phead, LTTypeData x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* newnode = LTBuyNode(x);
    5. 	newnode->prev = phead->prev;
    6. 	newnode->next = phead;
    7.  
    8. 	phead->prev->next = newnode;
    9. 	phead->prev = newnode;
    10. }

    为什么参数是一级指针而不是二级指针？

    在单链表时尾插需要传二级指针是因为需要改变指针变量phead的值；而在双向链表中有哨兵位，改变的是哨兵位的prev和next指针的值，所以不需要传二级指针。

    注意修改顺序：先改newnode的prev和next，再改原链表的尾节点的next（指向新的节点）和头节点的prev（指向新的节点）

     图解：

    注意这里2和3不能调换顺序，如果调换顺序，那么prev->next就找不到原来链表的尾节点了。

    头插：

    1. void LTPushFront(LTNode* phead, LTTypeData x)
    2. {
    3. 	assert(phead);//防止链表无效
    4. 	LTNode* newnode = LTBuyNode(x);
    5. 	newnode->next = phead->next;
    6. 	newnode->prev = phead;
    7. 	phead->next->prev = newnode;
    8. 	phead->next = newnode;
    9. }

     注意：还是顺序问题：最后两句不能调换顺序，否则，phead->next就指向的不是原链表的第一个节点，就找不到原链表的第一个节点了。

    打印链表：

    1. void LTPrint(LTNode* phead)
    2. {
    3. 	assert(phead);//防止链表无效
    4. 	LTNode* pcur = phead->next;
    5. 	while (pcur != phead)
    6. 	{
    7. 		printf("%d->", pcur->data);
    8. 		pcur = pcur->next;
    9. 	}
    10. 	printf("\n");
    11. }

    这里注意循环结束的标志：

    当pcur指向哨兵位时，循环结束。

    看一下打印效果：

    1. #include "List.h"
    2. void test1()
    3. {
    4. 	LTNode* plist = NULL;
    5. 	LTInite(&plist);
    6. 	LTPushBack(plist, 1);
    7. 	LTPrint(plist);
    8. 	LTPushBack(plist, 2);
    9. 	LTPrint(plist);
    10. 	LTPushBack(plist, 3);
    11. 	LTPrint(plist);
    12. 	LTPushFront(plist, 4);
    13. 	LTPrint(plist);
    14. 	LTPopFront(plist);
    15. 	LTPrint(plist);
    16. }
    17. int main()
    18. {
    19. 	test1();
    20. }

    效果展示： 

    尾删： 

    1. void LTPopBack(LTNode* phead)
    2. {
    3.     //链表不能为空，不能无效
    4. 	assert(phead && phead->next != NULL);
    5. 	LTNode* del = phead->prev;
    6. 	del->prev->next = phead;
    7. 	phead->prev = del->prev;
    8. 	free(del);
    9. 	del = NULL;
    10. }

    这里需要修改的链表的地方：尾节点的前一个节点的next和头节点的prev

    步骤图解：

    注意：这里需要保存下尾节点的地址，防止到最后释放的时候找不到。

    头删：

    1. void LTPopFront(LTNode* phead)
    2. {
    3. 	assert(phead && phead->next != NULL);
    4. 	LTNode* del = phead->next;
    5. 	del->next->prev = del->prev;
    6. 	phead->next = del->next;
    7. 	free(del);
    8. 	del = NULL;
    9. }

     跟尾删一样，需要注意的一点就是，需要创建一个新的变量（del）存储需要删除的节点的地址。

    查找：

    1. LTNode* LTFind(LTNode* phead, LTTypeData x)
    2. {
    3. 	assert(phead);
    4. 	LTNode* pcur = phead->next;
    5. 	while (pcur != phead)
    6. 	{
    7. 		if (pcur->data == x)
    8. 		{
    9. 			return pcur;
    10. 		}
    11. 		pcur = pcur->next;
    12. 	}
    13. 	return NULL;
    14. }

    注意下循环结束的条件：跟上面的打印函数一样，需要遍历一遍链表。

    返回值：如果没找到返回NULL，找到了就返回那个节点的地址。

    插入（在指定位置之后插入）：

    1. void LTInsert(LTNode* pos, LTTypeData x)
    2. {
    3. 	assert(pos);
    4. 	LTNode* newnode = LTBuyNode(x);
    5. 	newnode->next = pos->next;
    6. 	newnode->prev = pos;
    7. 	
    8. 	pos->next->prev = newnode;
    9. 	pos->next = newnode;
    10. }

    注意：最后两句的顺序不能交换。这里的原因上面的头插尾插的原因一样，若交换就找不到pos指向的节点的下一个节点。

    删除指定位置的数据：

    1. void LTErase(LTNode* pos)
    2. {
    3. 	assert(pos);
    4. 	pos->prev->next = pos->next;
    5. 	pos->next->prev = pos->prev;
    6. 	free(pos);
    7. 	pos = NULL;
    8. }

    这里没啥好注意的 。

    销毁链表：

    1. void LTDestroy(LTNode* phead)
    2. {
    3. 	assert(phead);
    4. 	LTNode* pcur = phead->next;
    5. 	LTNode* next = phead->next;
    6. 	while (pcur!=phead)
    7. 	{
    8. 		next = pcur->next;
    9. 		free(pcur);
    10. 		pcur = next;
    11. 	}
    12. 	free(phead);
    13. 	phead = NULL;
    14. }

    注意：这里用到前后指针：防止释放完一个节点找不到之后的节点。

    最后哨兵位释放，因为这里传的是一级指针不会修改test.c 文件中的phead的值，所以调用完该函数后，需要手动的将test.c中的phNULL.

    那么,这里为什么不传二级指针呢？

    保证接口的一致性，所以传的二级指针。

    实现双链表的全部源码：

    List.h：

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. typedef int LTTypeData;
    7. typedef struct ListNode
    8. {
    9. 	LTTypeData data;
    10. 	struct ListNode* prev;
    11. 	struct ListNode* next;
    12. }LTNode;
    13.  
    14. //初始化链表
    15. void LTInite(LTNode** pphead);
    16. //尾插
    17. void LTPushBack(LTNode* phead, LTTypeData x);
    18. //头插
    19. void LTPushFront(LTNode* phead, LTTypeData x);
    20. //头删
    21. void LTPopFront(LTNode* phead);
    22. //尾删
    23. void LTPopBack(LTNode* phead);
    24. //打印链表中的数据
    25. void LTPrint(LTNode* phead);
    26. //查找
    27. LTNode* LTFind(LTNode* phead, LTTypeData x);
    28. //在指定位置之后插入
    29. void LTInsert(LTNode* pos, LTTypeData x);
    30. //删除指定位置的数据
    31. void LTErase(LTNode* pos);
    32. //销毁链表
    33. void LTDestroy(LTNode* phead);

    List.c：

    1. #include "List.h"
    2.  
    3.  
    4. LTNode* LTBuyNode(LTTypeData x)
    5. {
    6. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    7. 	if (newnode == NULL)
    8. 	{
    9. 		perror("malloc");
    10. 		exit(1);
    11. 	}
    12. 	newnode->data = x;
    13. 	newnode->next = newnode;
    14. 	newnode->prev = newnode;
    15. 	return newnode;
    16. }
    17. void LTInite(LTNode** pphead)
    18. {
    19. 	assert(pphead);
    20. 	*pphead = LTBuyNode(-1);
    21. }
    22.  
    23. void LTPushBack(LTNode* phead, LTTypeData x)
    24. {
    25. 	assert(phead);
    26. 	LTNode* newnode = LTBuyNode(x);
    27. 	newnode->prev = phead->prev;
    28. 	newnode->next = phead;
    29.  
    30. 	phead->prev->next = newnode;
    31. 	phead->prev = newnode;
    32. }
    33.  
    34. void LTPrint(LTNode* phead)
    35. {
    36. 	assert(phead);
    37. 	LTNode* pcur = phead->next;
    38. 	while (pcur != phead)
    39. 	{
    40. 		printf("%d->", pcur->data);
    41. 		pcur = pcur->next;
    42. 	}
    43. 	printf("\n");
    44. }
    45.  
    46.  
    47. void LTPushFront(LTNode* phead, LTTypeData x)
    48. {
    49. 	assert(phead);
    50. 	LTNode* newnode = LTBuyNode(x);
    51. 	newnode->next = phead->next;
    52. 	newnode->prev = phead;
    53. 	phead->next->prev = newnode;
    54. 	phead->next = newnode;
    55. }
    56.  
    57.  
    58.  
    59. void LTPopFront(LTNode* phead)
    60. {
    61. 	assert(phead && phead->next != NULL);
    62. 	LTNode* del = phead->next;
    63. 	del->next->prev = del->prev;
    64. 	phead->next = del->next;
    65. 	free(del);
    66. 	del = NULL;
    67. }
    68.  
    69.  
    70. void LTPopBack(LTNode* phead)
    71. {
    72. 	assert(phead && phead->next != NULL);
    73. 	LTNode* del = phead->prev;
    74. 	del->prev->next = phead;
    75. 	phead->prev = del->prev;
    76. 	free(del);
    77. 	del = NULL;
    78. }
    79.  
    80.  
    81. LTNode* LTFind(LTNode* phead, LTTypeData x)
    82. {
    83. 	assert(phead);
    84. 	LTNode* pcur = phead->next;
    85. 	while (pcur != phead)
    86. 	{
    87. 		if (pcur->data == x)
    88. 		{
    89. 			return pcur;
    90. 		}
    91. 		pcur = pcur->next;
    92. 	}
    93. 	return NULL;
    94. }
    95.  
    96. void LTInsert(LTNode* pos, LTTypeData x)
    97. {
    98. 	assert(pos);
    99. 	LTNode* newnode = LTBuyNode(x);
    100. 	newnode->next = pos->next;
    101. 	newnode->prev = pos;
    102. 	
    103. 	pos->next->prev = newnode;
    104. 	pos->next = newnode;
    105. }
    106.  
    107.  
    108. void LTErase(LTNode* pos)
    109. {
    110. 	assert(pos);
    111. 	pos->prev->next = pos->next;
    112. 	pos->next->prev = pos->prev;
    113. 	free(pos);
    114. 	pos = NULL;
    115. }
    116.  
    117.  
    118. void LTDestroy(LTNode* phead)
    119. {
    120. 	assert(phead);
    121. 	LTNode* pcur = phead->next;
    122. 	LTNode* next = phead->next;
    123. 	while (pcur!=phead)
    124. 	{
    125. 		next = pcur->next;
    126. 		free(pcur);
    127. 		pcur = next;
    128. 	}
    129. 	free(phead);
    130. 	phead = NULL;
    131. }

    test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！

    1. #include "List.h"
    2. void test1()
    3. {
    4. 	LTNode* plist = NULL;
    5. 	LTInite(&plist);
    6. 	LTPushBack(plist, 1);
    7. 	LTPrint(plist);
    8. 	LTPushBack(plist, 2);
    9. 	LTPrint(plist);
    10. 	LTPushBack(plist, 3);
    11. 	LTPrint(plist);
    12. 	LTPushFront(plist, 4);
    13. 	LTPrint(plist);
    14. 	LTPopFront(plist);
    15. 	LTPrint(plist);
    16. 	//LTPopBack(plist);
    17. 	//LTPrint(plist);
    18. 	//LTNode* find = LTFind(plist, 4);
    19. 	//if (find == NULL)
    20. 	//	printf("没找到\n");
    21. 	//else
    22. 	//	printf("找到了\n");
    23. 	//LTInsert(find, 5);
    24. 	//LTPrint(plist);
    25. 	//LTErase(find);
    26. 	//LTPrint(plist);
    27. 	//LTDestroy(plist);
    28. 	//plist = NULL;
    29. }
    30. int main()
    31. {
    32. 	test1();
    33. 	return 0;
    34. }

    结语：

    继单链表后的又一个数据结构的实现。

    cheers！

  • 相关阅读:
    用结构体数组，完成宠物信息登记管理。
    如何备份VMware虚拟机
    外设篇：触摸屏
    使用代码产生标准的软件架构图之C4
    Taurus.MVC WebAPI 入门开发教程2：添加控制器输出Hello World。
    聊一聊我的第一个开源项目
    Java SDK下沉：解决SDK治理痛点
    ES7升级、jar包升级、工具类封装，代码改造
    关于磁盘空间不够，导致报错 springboot内置tomcat相关的临时目录无法创建等问题，如何自定义配置 tomcat 缓存文件路径
    yolact 环境配置
  • 原文地址：https://blog.csdn.net/2402_82658387/article/details/137839290