• 【双向链表】带头双向循环（1）

    目录

    链表的分类

    Test.c主函数

    test1头插

    test2头删

    test3尾插

    test4尾删

    test5查询

    test6插入pos位置后一个

    test7删除pos

    Test.c总代码 

    DList.h头文件&函数声明

    头文件

    函数声明

    DList.h总代码

    DList.c函数实现

    Createnode创建节点

    LTInit初始化

    LTPrint打印

    LTPushFront头插

    LTPopFron头删

    LTPushBack尾插

    LTPopBack尾删

    LTFind查询

    LTInsertAfter在pos后面插入

    LTErase删除pos数据

    LTDestroy销毁释放

    DList.c总代码

    今天实现一个带头双向循环链表。

    • 🙂判断为NULL的情况
    • 🙂判断二级指针&一级指针（想要改变实参不仅可以用指针，而且可以用return
    • 🙂判断先实现哪一步
    • ❌野指针的出现
    • ❌修改指针用二级指针
    • ❌修改结构体用一级指针
    • ❌内存泄露的问题，需要释放
    • ❌释放完空间，指针需要置NULL
    • 🆗无头单项不循环链表适用OJ链表比较多
    • 🆗带头双向不循环适用生活工作场景比较多
    • 🆗C++是兼容C
    • ❌【单链表】一般都不带头//需要二级指针处理//除了！链表分割
    • ❌【双向链表】需要带头
    • 🙂【单链表】Singly linked list（SLT）
    • 🙂【双链表】Double linked list（LT）
    • 🙂【顺序表】Sequention table list（SL)

    链表的分类

    前面我们学习了单链表。但是链表并不仅限只有【单链表】。【链表】是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

     单向或者双向

    带头或者不带头

     

    循环或者非循环

     

     这些特征组合起来可以构成：8种形态的链表。

     

     虽然有这么多的链表的结构，但是我们实际中最常用的还是有两种结构。

    【无头单项非循环链表】&【带头双向循环链表】

    • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。实际生活中使用很多。

    在前面我们已经学过 无头单项不循环链表，这里我们来实现 带头双向循环链表 

    Test.c主函数

    1. int main()
    2. {
    3. 	LTNode* phead = LTInit();//初始化
    4. 	test1(phead);//头插
    5. 	test2(phead);//头删
    6. 	test3(phead);//尾插
    7. 	test4(phead);//尾删
    8.     test5(phead);//查询某个数字
    9.  
    10. 	test6(phead);//插入pos位置的前一个/后一个元素
    11. 	test7(phead);//删除pos位置的元素
    12. 	LTDestroy(phead);//空间释放/防止内存泄露
    13. 	return 0;
    14. }

    test1头插

    1. #include"DList.h"
    2. void test1(LTNode* phead)//头插
    3. {
    4. 	LTPushFront(phead, 7);
    5. 	LTPushFront(phead, 3);
    6. 	LTPushFront(phead, 4);
    7. 	LTPushFront(phead, 7);
    8. 	LTPushFront(phead, 8);
    9. 	LTPushFront(phead, 9);
    10. 	LTPrint(phead);
    11. }

    test2头删

    1. void test2(LTNode* phead)//头删
    2. {
    3. 	LTPopFront(phead);
    4. 	LTPopFront(phead);
    5. 	LTPopFront(phead);
    6. 	LTPrint(phead);
    7. }

    test3尾插

    1. void test3(LTNode* phead)//尾插
    2. {
    3. 	LTPushBack(phead, 77);
    4. 	LTPushBack(phead, 99);
    5. 	LTPrint(phead);
    6. }

    test4尾删

    1. void test4(LTNode* phead)//尾删
    2. {
    3. 	LTPopBack(phead);
    4. 	LTPopBack(phead);
    5. 	LTPopBack(phead);
    6. 	LTPopBack(phead);
    7. 	LTPrint(phead);
    8. }

    test5查询

    1. void test5(LTNode* phead)//查询
    2. {
    3. 	LTNode* node = LTFind(phead, 4);
    4. 	if (node == NULL)
    5. 	{
    6. 		printf("没找到");
    7. 	}
    8. 	else
    9. 	{
    10. 		printf("%d", node->val);
    11. 	}
    12. }

    test6插入pos位置后一个

    1. void test6(LTNode* phead)//插入pos位置的前一个/后一个元素
    2. {
    3. 	LTNode* pos = LTFind(phead, 4);
    4. 	LTInsertAfter(phead, pos, 77);
    5. 	LTInsertAfter(phead, pos, 66);
    6. 	LTInsertAfter(phead, pos, 99);
    7. 	LTPrint(phead);
    8. }

    test7删除pos

    1. //删除pos位置的元素
    2. void test7(LTNode* phead)
    3. {
    4. 	LTNode* pos = LTFind(phead, 4);
    5.     if(pos)//查询成功才进入
    6.     {
    7. 	  LTErase(phead, pos);
    8.       pos=NULL;
    9.     }
    10. 	LTPrint(phead);
    11. }

    Test.c总代码 

    1. #include"DList.h"
    2. void test1(LTNode* phead)//头插
    3. {
    4. 	LTPushFront(phead, 7);
    5. 	LTPushFront(phead, 3);
    6. 	LTPushFront(phead, 4);
    7. 	LTPushFront(phead, 7);
    8. 	LTPushFront(phead, 8);
    9. 	LTPushFront(phead, 9);
    10. 	LTPrint(phead);
    11. }
    12.  
    13. void test2(LTNode* phead)//头删
    14. {
    15. 	LTPopFront(phead);
    16. 	LTPopFront(phead);
    17. 	LTPopFront(phead);
    18. 	LTPrint(phead);
    19. }
    20.  
    21. void test3(LTNode* phead)//尾插
    22. {
    23. 	LTPushBack(phead, 77);
    24. 	LTPushBack(phead, 99);
    25. 	LTPrint(phead);
    26. }
    27.  
    28. void test4(LTNode* phead)//尾删
    29. {
    30. 	LTPopBack(phead);
    31. 	LTPopBack(phead);
    32. 	LTPopBack(phead);
    33. 	LTPopBack(phead);
    34. 	LTPrint(phead);
    35. }
    36.  
    37. void test5(LTNode* phead)//查询
    38. {
    39. 	LTNode* node = LTFind(phead, 4);
    40. 	if (node == NULL)
    41. 	{
    42. 		printf("没找到");
    43. 	}
    44. 	else
    45. 	{
    46. 		printf("%d", node->val);
    47. 	}
    48. }
    49.  
    50. void test6(LTNode* phead)//插入pos位置的前一个/后一个元素
    51. {
    52. 	LTNode* pos = LTFind(phead, 4);
    53. 	LTInsertAfter(phead, pos, 77);
    54. 	LTInsertAfter(phead, pos, 66);
    55. 	LTInsertAfter(phead, pos, 99);
    56. 	LTPrint(phead);
    57. }
    58.  
    59. //删除pos位置的元素
    60. void test7(LTNode* phead)
    61. {
    62. 	LTNode* pos = LTFind(phead, 4);
    63.     if(pos)//查询成功才进入
    64.     {
    65. 	  LTErase(phead, pos);
    66.       pos=NULL;
    67.     }
    68. 	LTPrint(phead);
    69. }
    70.  
    71.  
    72. int main()
    73. {
    74. 	LTNode* phead = LTInit();//已经被初始化了
    75. 	test1(phead);//头插
    76. 	test2(phead);//头删
    77. 	test3(phead);//尾插
    78. 	test4(phead);//尾删
    79.     test5(phead);//查询某个数字
    80.  
    81. 	test6(phead);//插入pos位置的前一个/后一个元素
    82. 	test7(phead);//删除pos位置的元素
    83. 	LTDestroy(phead);//空间释放/防止内存泄露
    84.     phead=NULL;
    85. 	return 0;
    86. }

    DList.h头文件&函数声明

    头文件

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. assert(//)//括号里是可以出现的情况为真 若括号里的表达式为假那就❌

    函数声明

    • 声明节点 
    1. typedef int LTDateType;
    2. //声明节点
    3. typedef struct DListNode
    4. {
    5. 	LTDateType val;
    6. 	struct DListNode* prev;
    7. 	struct DListNode* next;
    8. }LTNode;
    •  初始化（可以用指针修改实参/也可以用返回值改变实参）
    LTNode* LTInit();
    • 头插
    void LTPushFront(LTNode*phead, LTDateType x);
    • 头删
    void LTPopFront(LTNode* phead);
    • 尾插
    void LTPushBack(LTNode* phead,LTDateType x);
    • 尾删
    void LTPopBack(LTNode* phead);
    • 打印
    void LTPrint(LTNode* phead);
    • 查询
    LTNode* LTFind(LTNode* phead);
    • 在pos的后面插入一个元素
    void LTInsertAfter(LTNode* phead, LTNode* pos, LTDateType x);
    • 删除pos位置的元素
    void LTErase(LTNode* phead, LTNode* pos);
    • 销毁释放 
    void LTDestroy(LTNode* phead);

    DList.h总代码

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int LTDateType;
    7.  
    8. //定义节点
    9. typedef struct DListNode
    10. {
    11. 	LTDateType val;
    12. 	struct DListNode* prev;
    13. 	struct DListNode* next;
    14. }LTNode;
    15.  
    16. //初始化
    17. LTNode* LTInit();//不用二级指针/用返回值改变实参
    18. void LTPushFront(LTNode*phead, LTDateType x);//头插
    19. void LTPopFront(LTNode* phead);//头删
    20. void LTPushBack(LTNode* phead,LTDateType x);//尾插
    21. void LTPopBack(LTNode* phead);//尾删
    22. void LTPrint(LTNode* phead);//打印
    23. LTNode* LTFind(LTNode* phead);//查询
    24. void LTInsertAfter(LTNode* phead, LTNode* pos, LTDateType x);//在pos的后面插入一个元素
    25. void LTErase(LTNode* phead, LTNode* pos);//删除pos位置的元素
    26. void LTDestroy(LTNode* phead);//销毁释放
    27.

    DList.c函数实现

    1. //初始化
    2. LTNode* LTInit()
    3. {
    4. 	LTNode* phead = Createnode(-1);
    5. 	phead->prev = phead;
    6. 	phead->next = phead;
    7. 	return phead;
    8. }

    Createnode创建节点

    1. #include"DList.h"
    2. //创造节点
    3. LTNode* Createnode(LTDateType x)
    4. {
    5. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    6. 	if (newnode == NULL)
    7. 	{
    8. 		perror("malloc");
    9. 		exit(-1);//程序停止
    10. 	}
    11. 	newnode->val = x;
    12. 	newnode->prev = NULL;
    13. 	newnode->next = NULL;
    14. 	return newnode;
    15. }

    LTInit初始化

    • 通过形参改变实参可以使用 【指正】
    • 通过形参改变实参可以使用 【return】
    1. //初始化
    2. LTNode* LTInit()
    3. {
    4. 	LTNode* phead = Createnode(-1);
    5. 	phead->prev = phead;
    6. 	phead->next = phead;
    7. 	return phead;
    8. }

     

    LTPrint打印

    1. //打印
    2. void LTPrint(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	LTNode* cur = phead;
    6. 	printf("<=>");
    7.     printf("%d<=>", cur->val);
    8. 	cur = cur->next;
    9. 	while (cur != phead)
    10. 	{
    11. 		printf("%d<=>", cur->val);
    12. 		cur = cur->next;
    13. 	}
    14. 	printf("\n");
    15. }

    LTPushFront头插

    1. //头插
    2. void LTPushFront(LTNode* phead,LTDateType x)
    3. {
    4. 	assert(phead);
    5. 	LTNode* newnode = Createnode(x);
    6. 	newnode->next = phead->next;
    7. 	phead->next->prev = newnode;
    8. 	phead->next = newnode;
    9. 	newnode->prev = phead;
    10. }

    LTPopFron头删

    • 一定不能把头节点哨兵位给删除了会出现野指针的问题❌ 
    1. //头删
    2. void LTPopFront(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	LTNode* cur = phead->next;
    6. 	LTNode* next = cur->next;
    7. 	assert(cur != phead);	//考虑如果链表为NULL
    8. 	phead->next = next;
    9. 	next->prev = phead;
    10. 	free(cur);
    11. 	cur = NULL;
    12. }

     

    LTPushBack尾插

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

     

    LTPopBack尾删

    • 一定不能把头节点哨兵位给删除了会出现野指针的问题❌  
    1. //尾删
    2. void LTPopBack(LTNode* phead)
    3. {
    4. 	assert(phead);
    5. 	LTNode* cur = phead->prev;
    6. 	LTNode* next = cur->prev;
    7. 	assert(cur != phead);
    8. 	phead->prev = next;
    9. 	next->next = phead;
    10. 	free(cur);
    11. 	cur = NULL;
    12. }

     

    LTFind查询

    • 查询到某个数据的位置意味着可以修改这个位置前后的数据 
    1. //查询
    2. //查询某个数，存在返回节点地址，不存在返回NULL
    3. LTNode* LTFind(LTNode* phead, LTDateType x)
    4. {
    5. 	assert(phead);
    6. 	LTNode* cur = phead->next;
    7. 	while (cur != phead)
    8. 	{
    9. 		if (cur->val == x)
    10. 		{
    11. 			return cur;
    12. 		}
    13. 		cur = cur->next;
    14. 	}
    15. 	return NULL;
    16. }

    LTInsertAfter在pos后面插入

    1. //在pos的后面插入一个元素
    2. void LTInsertAfter(LTNode* phead, LTNode*pos, LTDateType x)
    3. {
    4. 	assert(phead);
    5. 	LTNode* newnode = Createnode(x);
    6. 	newnode->next = pos->next;
    7. 	pos->next->prev = newnode;
    8. 	pos->next = newnode;
    9. 	newno

     

    LTErase删除pos数据

    1. //删除pos位置的元素//
    2. void LTErase(LTNode* phead, LTNode* pos)
    3. {
    4. 	assert(phead);
    5. 	assert(phead->next != phead);
    6. 	LTNode* cur = pos->prev;
    7. 	LTNode* next = pos->next;
    8. 	cur->next = next;
    9. 	next->prev = cur;
    10. 	free(pos);
    11. 	pos = NULL;
    12. }

     

    LTDestroy销毁释放

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

    DList.c总代码

    1. #include"DList.h"
    2. //创造节点
    3. LTNode* Createnode(LTDateType x)
    4. {
    5. 	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    6. 	if (newnode == NULL)
    7. 	{
    8. 		perror("malloc");
    9. 		exit(-1);//程序停止
    10. 	}
    11. 	newnode->val = x;
    12. 	newnode->prev = NULL;
    13. 	newnode->next = NULL;
    14. 	return newnode;
    15. }
    16. //初始化
    17. LTNode* LTInit()
    18. {
    19. 	LTNode* phead = Createnode(-1);
    20. 	phead->prev = phead;
    21. 	phead->next = phead;
    22. 	return phead;
    23. }
    24. //打印
    25. void LTPrint(LTNode* phead)
    26. {
    27. 	assert(phead);
    28. 	LTNode* cur = phead;
    29. 	printf("<=>");
    30.     printf("%d<=>", cur->val);
    31. 	cur = cur->next;
    32. 	while (cur != phead)
    33. 	{
    34. 		printf("%d<=>", cur->val);
    35. 		cur = cur->next;
    36. 	}
    37. 	printf("\n");
    38. }
    39. //头插
    40. void LTPushFront(LTNode* phead,LTDateType x)
    41. {
    42. 	assert(phead);
    43. 	LTNode* newnode = Createnode(x);
    44. 	newnode->next = phead->next;
    45. 	phead->next->prev = newnode;
    46. 	phead->next = newnode;
    47. 	newnode->prev = phead;
    48. }
    49. //头删
    50. void LTPopFront(LTNode* phead)
    51. {
    52. 	assert(phead);
    53. 	LTNode* cur = phead->next;
    54. 	LTNode* next = cur->next;
    55. 	assert(cur != phead);	//考虑如果链表为NULL
    56. 	phead->next = next;
    57. 	next->prev = phead;
    58. 	free(cur);
    59. 	cur = NULL;
    60. }
    61. //尾插
    62. void LTPushBack(LTNode* phead, LTDateType x)
    63. {
    64. 	assert(phead);
    65. 	LTNode* newnode = Createnode(x);
    66. 	newnode->prev = phead->prev;
    67. 	phead->prev->next = newnode;
    68. 	newnode->next = phead;
    69. 	phead->prev = newnode;
    70. }
    71. //尾删
    72. void LTPopBack(LTNode* phead)
    73. {
    74. 	assert(phead);
    75. 	LTNode* cur = phead->prev;
    76. 	LTNode* next = cur->prev;
    77. 	assert(cur != phead);
    78. 	phead->prev = next;
    79. 	next->next = phead;
    80. 	free(cur);
    81. 	cur = NULL;
    82. }
    83. //查询
    84. //查询某个数，存在返回节点地址，不存在返回NULL
    85. LTNode* LTFind(LTNode* phead, LTDateType x)
    86. {
    87. 	assert(phead);
    88. 	LTNode* cur = phead->next;
    89. 	while (cur != phead)
    90. 	{
    91. 		if (cur->val == x)
    92. 		{
    93. 			return cur;
    94. 		}
    95. 		cur = cur->next;
    96. 	}
    97. 	return NULL;
    98. }
    99. //在pos的后面插入一个元素
    100. void LTInsertAfter(LTNode* phead, LTNode*pos, LTDateType x)
    101. {
    102. 	assert(phead);
    103. 	LTNode* newnode = Createnode(x);
    104. 	newnode->next = pos->next;
    105. 	pos->next->prev = newnode;
    106. 	pos->next = newnode;
    107. 	newnode->prev = pos;
    108. }
    109. //删除pos位置的元素//
    110. void LTErase(LTNode* phead, LTNode* pos)
    111. {
    112. 	assert(phead);
    113. 	assert(phead->next != phead);
    114. 	LTNode* cur = pos->prev;
    115. 	LTNode* next = pos->next;
    116. 	cur->next = next;
    117. 	next->prev = cur;
    118. 	free(pos);
    119. 	pos = NULL;
    120. }
    121. //销毁
    122. void LTDestroy(LTNode* phead)
    123. {
    124. 	assert(phead);
    125. 	assert(phead->next != phead);
    126. 	LTNode* cur = phead->next;
    127. 	while (cur != phead)
    128. 	{
    129. 		LTNode* tmp = cur->next;
    130. 		free(cur);
    131. 		cur = tmp;
    132. 	}
    133.     cur=NULL;
    134. }
    135. //形式参数这里就可以置NULL 
    136. //实际参数到主函数里面置NULL
    137.  
    138.

     

    ✔✔✔✔✔最后感谢大家的阅读，若有错误和不足，欢迎指正!乖乖敲代码哦！ 

    代码---------→【唐棣棣 (TSQXG) - Gitee.com】

    联系---------→【邮箱：2784139418@qq.com】

  • 相关阅读:
    python3GUI--详细讲解一个QQ音乐组件的制作By:PyQt5（详细介绍、附源代码）
    基于vue和nodejs毕业设计酒店预约管理系统
    UI设计是什么意思？一文给你讲清楚
    如何做好外贸独立站
    电子邮件营销初学者指南（二）：如何开始与撰写
    ctfshow 反序列化篇（下）
    Proteus 新建工程
    Windows系统的——终端命令行进入文件夹、打开程序或文件、返回路径、切换磁盘、查看路径包含的所有内容和配置环境变量操作
    Python 知识：检查图中是否存在哈密顿循环
    哪些城市有PMP考试考点？PMP考试考场都在哪？
  • 原文地址：https://blog.csdn.net/m0_74841364/article/details/134358767