• 【数据结构初阶】四、线性表里的链表（带头+双向+循环 链表）

    =========================================================================

    相关代码gitee自取：

    C语言学习日记: 加油努力 (gitee.com)

     =========================================================================

    接上期：

    【数据结构初阶】三、 线性表里的链表（无头+单向+非循环链表 -- C语言实现）-CSDN博客

     =========================================================================

                         

     引言 

    通过上期对单链表（无头+单向+非循环链表）的介绍和使用

    我们可以知道顺序表和链表的区别：

                  

                  

    顺序表和链表的一些区别：

                  

    • 单链表（无头+单向+非循环链表）只有一个后继指针next指向下一个结点，
      而双向链表不仅有后继指针next还有一个前驱指针prev指向上一个结点
                           
    • 上篇单链表只能顺着往后遍历，不能倒着往回走，
      会造成一些操作很困难（回文、逆置等操作），
      而双向链表能顺着往后遍历也能倒着往回遍历

    更多区别图示：

    不同点（方面）顺序表链表
    存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
    随机访问支持 -- O(1)不支持 -- O(N)
    任意位置插入或者删除可能需要搬移元素，效率低 -- O(N)只需修改指针指向
    插入时的容量（空间）动态顺序表，空间不够时需要扩容没有容量的概念（分成一个个结点）
    应用场景元素高效存储+频繁访问频繁在任意位置插入和删除
    缓存利用率高低
    注：缓存利用率 参考 存储体系结构 以及 局部原理性

                   

                    

    回顾上期中提到的带头双向循环链表：

               

    带头双向循环链表

    简介：

    结构最复杂，一般用在单独存储数据。

    实际中使用的链表数据结构，都是带头双向循环链表。

    另外这个结构虽然结构复杂，

    但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

    图示：

             

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                 

    1 . 双向链表的实现
    （带头+双向+循环 链表）

    （详细解释在图片的注释中，代码分文件放最后）
                      

    实现具体功能前的准备工作

    • 包含之后会用到的头函数
                                 
    • 创建双向链表数据类型 -- 链表结点中数据域里存储的数据的类型
                   
    • 创建双向链表结点结构体(类型) -- 结点中应有 数据域 和 指针域
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    BuyLTNode函数 -- 创建双向循环链表结点

    • 为创建结点开辟动态空间，并检查是否开辟成功
                            
    • 开辟成功后，初始化结点数据域和指针域
                     
    • 最后返回开辟的空间地址
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    LTInit函数 -- 带头双向循环链表初始化函数

    • 初始化时先使用BuyLTNode函数创建哨兵位
                  
    • 因为要实现循环，
      所以让哨兵位后继指针next和前驱指针prev都指向自己
                      
    • 初始化后返回链表哨兵位
    图示

                

                

    ---------------------------------------------------------------------------------------------

                

    LTPrint函数 -- 打印双向链表各结点数据域数据

    • assert断言头指针（哨兵位地址）不为空
                  
    • 创建结点指针cur进行遍历
                      
    • 使用while循环进行遍历打印

    图示

    测试 -- LTPrint函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTPushBack函数 -- 向链表尾部插入一个结点（尾插）

    • assert断言头指针（哨兵位地址）不为空
                  
    • 通过哨兵位配合前驱指针prev获得尾结点地址
                      
    • 调用BuyLTNode函数为尾插操作创建尾插结点newnode

                       

    • 将尾插结点和原尾部结点连接
                       

    • 将尾插结点和哨兵位进行连接

    图示

    测试 -- LTPushBack函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTPopBack函数 -- 删除链表尾部结点（尾删）

    • assert断言 头指针(哨兵位地址)不为空 和 双向链表不为空链表
                  
    • 通过哨兵位的前驱指针prev获得尾结点tail，
      再通过尾结点tail获得倒数第二个结点tailPrev
                      
    • 释放（删除）尾结点tail

                       

    • 让倒数第二个结点tailPrev成为新的尾结点，
      为保持循环，把tailPrev和哨兵位连接起来

    图示

    测试 -- LTPopBack函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTPushFront函数 -- 向链表头部插入一个结点（头插）

    • assert断言头指针（哨兵位地址）不为空
                  
    • 调用BuyLTNode函数为头插操作创建头插结点newnode
                      
    • 创建一个first指针保存原本第一个结点地址

                       

    • 哨兵位后继指针next指向头插结点newnode，
      头插结点newnode前驱指针prev指向哨兵位
                       

    • 头插结点newnode后继指针next指向原本头结点first，
      原本头结点first前驱指针prev指向头插结点newnode

    图示

    测试 -- LTPushFront函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTPopFront函数 -- 删除链表头部结点（头删）

    • assert断言 头指针(哨兵位地址)不为空 和 双向链表不为空链表
                  
    • 通过哨兵位后继结点next获得头结点地址，
      再通过first结点获得第二个结点
                      
    • 释放头结点first

                       

    • 让哨兵位后继结点next指向第二个结点second，
      第二个结点的前驱指针prev指向哨兵位

    图示

    测试 -- LTPopFront函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTSize函数 -- 求链表有效结点个数（求链表长度）

    • assert断言头指针（哨兵位地址）不为空
                  
    • 创建变量size存放链表长度，
      创建结点指针cur进行遍历
                      
    • 使用while循环遍历链表，计算链表长度

                       

    • 最后返回链表长度size

    图示

    测试 -- LTSize函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTFind函数 -- 在双向链表中查找数据域数据为x的结点地址

    • assert断言头指针（哨兵位地址）不为空
                  
    • 创建遍历指针cur，保存第一个结点地址
                      
    • 使用while循环进行遍历查找

                       

    • 未找到则返回空指针

    图示

    测试 -- LTFind函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTInsert函数 -- 在pos结点之前插入数据域数据为x的结点

    • assert断言头指针（哨兵位地址）不为空
                  
    • 通过pos结点获得前一个结点posPrev地址
                      
    • 使用BuyLTNode函数为插入结点开辟空间

                       

    • posPrev结点的后继指针next指向newnode，
      newnode前驱指针prev指向posPrev
                       

    • newnode后继指针next指向pos，
      pos结点前驱指针prev指向newnode

    图示

    测试 -- LTInsert函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTErase函数 -- 删除pos结点

    • assert断言删除位置结点pos不为空
                  
    • 保存要删除结点pos的前一个结点posPrev地址，
      保存要删除结点pos的后一个结点posNext地址
                      
    • 释放掉pos结点

                       

    • 将pos前结点posPrev的后继指针指向posNext，
      将pos后结点posNext的前驱指针指向posPrev

    图示

    测试 -- LTErase函数

                

                

    ---------------------------------------------------------------------------------------------

                

    LTDestroy函数 -- 销毁链表

    • assert断言头指针（哨兵位地址）不为空
                  
    • 创建遍历指针cur，保存第一个结点地址
                      
    • 使用while循环遍历释放有效结点

                       

    • 最后释放哨兵位

    图示

             

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                 

    2 . 对应代码

    List.h -- 双向链表头文件

    1. #pragma once
    2.  
    3. //双向链表头文件：
    4.  
    5. //包含之后需要用到的头文件：
    6. #include
    7. #include
    8. #include
    9.  
    10. //定义双向链表数据域数据类型：
    11. typedef int LTDataType;
    12.  
    13. //创建双向链表结点类型：
    14. typedef struct ListNode
    15. {
    16. 	//数据域：
    17. 	LTDataType data;
    18.  
    19. 	//双向链表指针域：
    20. 	 //后继指针--指向后一个结点：
    21. 	struct ListNode* next;
    22. 	 //前驱指针--指向前一个结点：
    23. 	struct ListNode* prev;
    24.  
    25. }LTNode; //类型简称LTNode
    26.  
    27.  
    28.  
    29. //函数声明：
    30.  
    31. //创建链表结点--创建双向循环链表结点
    32. //接收要插入创建结点数据域的数据
    33. //返回创建结点的地址
    34. LTNode* BuyLTNode(LTDataType x);
    35.  
    36. //双向链表初始化--带头双向循环链表初始化函数
    37. //返回初始化结点的地址
    38. LTNode* LTInit();
    39.  
    40. //打印链表--打印双向链表各结点数据域数据
    41. //接收链表头指针（phead）
    42. LTNode* LTPrint(LTNode* phead);
    43.  
    44. //双向链表尾插函数--向链表尾部插入一个结点（尾插）:
    45. //接收链表头指针（phead）、要尾插进链表的值（x）
    46. void LTPushBack(LTNode* phead, LTDataType x);
    47.  
    48. //双向链表尾删函数--删除链表尾部结点（尾删）
    49. //接收链表头指针（phead）
    50. void LTPopBack(LTNode* phead);
    51.  
    52. //双向链表头插函数--向链表头部插入一个结点（头插）:
    53. //接收链表头指针（phead）、要头插进链表的值（x）
    54. void LTPushFront(LTNode* phead, LTDataType x);
    55.  
    56. //双向链表头删函数--删除链表头部结点（头删）
    57. //接收链表头指针（phead）
    58. void LTPopFront(LTNode* phead);
    59.  
    60. //求链表结点个数函数--求链表有效结点个数（求链表长度）
    61. //接收链表头指针（phead）
    62. int LTSize(LTNode* phead);
    63.  
    64. //双向链表查找函数--在双向链表中查找数据域数据为x的结点地址
    65. //接收链表头指针（phead）、要在链表中查找的值（x）
    66. LTNode* LTFind(LTNode* phead, LTDataType x);
    67.  
    68. //双向链表插入函数--在pos结点之前插入数据域数据为x的结点
    69. //接收插入位置(pos)、要插入链表的值（x）
    70. void LTInsert(LTNode* pos, LTDataType x);
    71.  
    72. //双向链表删除函数--删除pos结点
    73. //接收要删除结点地址（pos）
    74. void LTErase(LTNode* pos);
    75.  
    76. //双向链表销毁函数--销毁链表
    77. //接收要销毁链表头系欸但（phead）
    78. void LTDestroy(LTNode* phead);

                

                

    ---------------------------------------------------------------------------------------------

                    

    List.c -- 双向链表函数实现文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. //双向链表函数实现文件：
    4.  
    5. //包含双向链表头文件：
    6. #include "List.h"
    7.  
    8. //函数实现：
    9.  
    10. //创建链表结点--创建双向循环链表结点
    11. //接收要插入创建结点数据域的数据
    12. LTNode* BuyLTNode(LTDataType x)
    13. {
    14. 	//为创建结点开辟动态空间：
    15. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    16. 	//检查是否开辟失败：
    17. 	if (node == NULL)
    18. 		//返回NULL，开辟失败
    19. 	{
    20. 		//打印错误信息：
    21. 		perror("malloc fail");
    22. 		//终止程序：
    23. 		exit(-1);
    24. 	}
    25.  
    26. 	//把x放入结点数据域：
    27. 	node->data = x;
    28. 	//设置双向链表指针域：
    29. 	node->next = NULL;
    30. 	node->prev = NULL;
    31. 	
    32. 	//开辟成功则返回开辟空间地址
    33. 	return node;
    34. }
    35.  
    36.  
    37.  
    38. //链表初始化--带头双向循环链表初始化函数
    39. //接收链表头指针（phead）
    40. LTNode* LTInit()
    41. {
    42. 	//初始化时先使用BuyLTNode函数创建哨兵位：
    43. 	LTNode* phead = BuyLTNode(-1); //返回哨兵位指针
    44.  
    45. 	//因为要实现循环，
    46. 	//所以让哨兵位后继指针next和前驱指针prev都指向自己：
    47. 	phead->next = phead;
    48. 	phead->prev = phead;
    49. 	//这样即使链表为空，它也是有头有尾的，即哨兵位phead
    50.  
    51. 	//初始化后返回链表哨兵位：
    52. 	return phead;
    53. }
    54.  
    55.  
    56.  
    57. //打印链表--打印双向链表各结点数据域数据
    58. //接收链表头指针（phead）
    59. LTNode* LTPrint(LTNode* phead)
    60. {
    61. 	//assert断言头指针（哨兵位地址）不为空:
    62. 	assert(phead != NULL);
    63.  
    64. 	//创建结点指针cur进行遍历：
    65. 	//指针cur应该从哨兵位（头指针）下一个结点开始
    66. 	LTNode* cur = phead->next;
    67. 	
    68. 	printf("phead <==> ");
    69. 	//因为是循环链表，不是以NULL空指针结尾
    70. 	//所以应该是当指针cur遍历回到哨兵位就终止遍历：
    71. 	while (cur != phead)
    72. 	//如果只用哨兵位，链表为空，
    73. 	//phead->next还是phead，不会进行打印
    74. 	{
    75. 		//打印数据域内容：
    76. 		printf("%d <=> ", cur->data);
    77.  
    78. 		//打印完当前结点数据域数据后cur移向下个结点：
    79. 		cur = cur->next;
    80. 	}
    81.  
    82. 	//打印完一个链表后换行：
    83. 	printf("\n");
    84. }
    85.  
    86.  
    87.  
    88. //向链表尾部插入一个结点（尾插）:
    89. //接收结点头指针（phead）、要尾插进链表的值（x）
    90. void LTPushBack(LTNode* phead, LTDataType x)
    91. {
    92. 	//assert断言头指针（哨兵位地址）不为空:
    93. 	assert(phead != NULL);
    94.  
    95. 	//通过哨兵位找到尾结点：
    96. 	//因为是循环链表：
    97. 	//所以哨兵位（带头链表）的前一个结点就是尾结点
    98. 	LTNode* tail = phead->prev; 
    99. 	//调用前驱指针获得尾结点
    100.  
    101. 	//调用BuyLTNode函数为尾插创建尾插结点newnode：
    102. 	LTNode* newnode = BuyLTNode(x);
    103.  
    104. 	//尾插结点前驱指针prev指向原本的尾结点：
    105. 	newnode->prev = tail;
    106. 	//原本尾结点后继指针next指向尾插结点：
    107. 	tail->next = newnode;
    108.  
    109. 	//尾插结点后继指针next指向头结点：
    110. 	newnode->next = phead;
    111. 	//头结点前驱指针指向尾插结点：
    112. 	phead->prev = newnode;
    113.  
    114. 	//带头+双向+循环 链表:
    115. 	//对比单链表，因为有哨兵位不用考虑链表为空的情况，
    116. 	//且不需要二级指针，通过操纵哨兵位这个结构体，
    117. 	//替换用二级指针操作头指针的操作
    118.  
    119.  
    120. 	/*
    121. 	//第二种方法：复用LTInsert函数
    122. 	//在哨兵位前插入一个值x就是尾插了：
    123. 	LTInsert(phead, x);
    124. 	*/
    125. }
    126.  
    127.  
    128.  
    129. //双向链表尾删函数--删除链表尾部结点（尾删）
    130. //接收链表头指针（phead）
    131. void LTPopBack(LTNode* phead)
    132. {
    133. 	//assert断言头指针（哨兵位地址）不为空:
    134. 	assert(phead != NULL);
    135. 	
    136. 	//assert断言双向链表不是空链表：
    137. 	assert(phead->next != phead);
    138. 	//如果哨兵位的下一个结点还是哨兵位说明是空链表
    139.  
    140. 	//通过哨兵位的前驱指针prev获得尾结点tail：
    141. 	LTNode* tail = phead->prev;
    142.  
    143. 	//再通过尾结点tail获得倒数第二个结点tailPrev：
    144. 	LTNode* tailPrev = tail->prev;
    145.  
    146. 	//释放（删除）尾结点tail：
    147. 	free(tail);
    148.  
    149. 	//这时就让倒数第二个结点tailPrev成为新的尾结点
    150. 	//为保持循环，把tailPrev和哨兵位连接起来：
    151. 	tailPrev->next = phead; //tailPrev后继指针指向哨兵位
    152. 	phead->prev = tailPrev; //哨兵位前驱指针指向tailPrev
    153.  
    154. 	//带头+双向+循环 链表:
    155. 	//对比单链表，这里双向链表在尾删时因为有哨兵位的存在
    156. 	//即使链表只剩一个结点，也不用进行判断单独处理进行置空
    157. 	//这一个结点删掉后，还有哨兵位存在
    158.  
    159. 	/*
    160. 	//第二种方法：复用LTErase函数
    161. 	//传尾结点地址给LTErase函数即可：
    162. 	LTErase(phead->prev);
    163. 	*/
    164. }
    165.  
    166.  
    167.  
    168. //双向链表头插函数--向链表头部插入一个结点（头插）：
    169. //接收链表头指针（phead）、要头插进链表的值（x）
    170. void LTPushFront(LTNode* phead, LTDataType x)
    171. {
    172. 	//第二种方法：多定义一个指针
    173. 	
    174. 	//assert断言头指针（哨兵位地址）不为空:
    175. 	assert(phead != NULL);
    176.  
    177. 	//调用BuyLTNode函数为头插创建头插结点newnode：
    178. 	LTNode* newnode = BuyLTNode(x);
    179.  
    180. 	//创建一个first指针保存原本第一个结点地址：
    181. 	LTNode* first = phead->next;
    182.  
    183. 	//哨兵位后继指针next指向头插结点newnode：
    184. 	phead->next = newnode;
    185.  
    186. 	//头插结点newnode前驱指针prev指向哨兵位：
    187. 	newnode->prev = phead;
    188.  
    189. 	//头插结点newnode后继指针next指向原本头结点first:
    190. 	newnode->next = first;
    191.  
    192. 	//原本头结点first前驱指针prev指向头插结点newnode：
    193. 	first->prev = newnode;
    194.  
    195.  
    196. 	/*
    197. 	//assert断言头指针（哨兵位地址）不为空:
    198. 	assert(phead != NULL);
    199. 	
    200. 	//第一种方法：需要注意连接的顺序
    201. 	
    202. 	//调用BuyLTNode函数为头插创建头插结点newnode：
    203. 	LTNode* newnode = BuyLTNode(x);
    204. 	
    205. 	//先将头插结点的后继节点next连接上原本头结点：
    206. 	newnode->next = phead->next;
    207. 	//哨兵位的后继指针指向的就是头结点
    208. 	
    209. 	//再将原本头结点的前驱指针prev指向头插结点newnode：
    210. 	phead->next->prev = newnode;
    211. 	
    212. 	//哨兵位连接上头插节点newnode：
    213. 	phead->next = newnode;
    214. 	
    215. 	//头插结点newnode的前驱指针指向哨兵位：
    216. 	newnode->prev = phead;
    217. 	*/
    218.  
    219.  
    220. 	/*
    221. 	//第三种方法：复用LTInsert函数
    222. 	//在哨兵位后一个结点前插入一个值x就是头插了：
    223. 	LTInsert(phead->next, x);
    224. 	*/
    225. }
    226.  
    227.  
    228.  
    229. //双向链表头删函数--删除链表头部结点（头删）
    230. //接收链表头指针（phead）
    231. void LTPopFront(LTNode* phead)
    232. {
    233. 	//assert断言头指针（哨兵位地址）不为空:
    234. 	assert(phead != NULL);
    235.  
    236. 	//assert断言双向链表不是空链表：
    237. 	assert(phead->next != phead);
    238. 	//如果哨兵位的下一个结点还是哨兵位说明是空链表
    239.  
    240. 	//通过哨兵位后继结点next获得头结点地址：
    241. 	LTNode* first = phead->next;
    242.  
    243. 	//再通过first结点获得第二个结点：
    244. 	LTNode* second = first->next;
    245.  
    246. 	//释放头结点first：
    247. 	free(first);
    248.  
    249. 	//让哨兵位后继结点next指向第二个结点second：
    250. 	phead->next = second;
    251.  
    252. 	//第二个结点的前驱指针prev指向哨兵位：
    253. 	second->prev = phead;
    254.  
    255. 	//带头+双向+循环 链表:
    256. 	//对比单链表，这里双向链表在头删时因为有哨兵位的存在
    257. 	//即使链表只剩一个结点，也不用进行判断单独处理进行置空
    258. 	//这一个结点删掉后，还有哨兵位存在
    259. 	
    260. 	/*
    261. 	//第二种方法：复用LTErase函数
    262. 	//传第一个结点地址给LTErase函数即可：
    263. 	LTErase(phead->next);
    264. 	*/
    265. }
    266.  
    267.  
    268.  
    269. //求链表结点个数函数
    270. //接收链表头指针（phead）
    271. int LTSize(LTNode* phead)
    272. {
    273. 	//assert断言头指针（哨兵位地址）不为空:
    274. 	assert(phead != NULL);
    275.  
    276. 	int size = 0; //存放链表长度
    277.  
    278. 	//创建结点指针cur进行遍历：
    279. 	//指针cur应该从哨兵位（头指针）下一个结点开始
    280. 	LTNode* cur = phead->next;
    281.  
    282. 	//因为是循环链表，不是以NULL空指针结尾
    283. 	//所以应该是当指针cur遍历回到哨兵位就终止遍历：
    284. 	while (cur != phead)
    285. 		//如果只有哨兵位，链表为空，
    286. 		//phead->next还是phead，不会进行打印
    287. 	{
    288. 		++size; //遍历一遍长度+1
    289.  
    290. 		//cur移向下个结点：
    291. 		cur = cur->next;
    292. 	}
    293.  
    294. 	//返回链表长度：
    295. 	return size;
    296. }
    297.  
    298.  
    299.  
    300. //双向链表查找函数--在双向链表中查找数据域数据为x的结点地址
    301. //接收链表头指针（phead）、要在链表中查找的值（x）
    302. LTNode* LTFind(LTNode* phead, LTDataType x)
    303. {
    304. 	//assert断言头指针（哨兵位地址）不为空:
    305. 	assert(phead != NULL);
    306.  
    307. 	//创建遍历指针cur，从第一个结点开始：
    308. 	LTNode* cur = phead->next;
    309.  
    310. 	//使用while循环进行遍历：
    311. 	while (cur != phead)
    312. 		//如果只有哨兵位，链表为空，
    313. 		//phead->next还是phead，不会进行打印
    314. 	{
    315. 		if (cur->data == x)
    316. 			//找到要找的值了：
    317. 		{
    318. 			return cur; //返回该值结点
    319. 		}
    320.  
    321. 		//调整指针：
    322. 		cur = cur->next;
    323. 	}
    324.  
    325. 	//未找到则返回空指针：
    326. 	return NULL;
    327. }
    328.  
    329.  
    330.  
    331. //双向链表插入函数--在pos结点之前插入数据域数据为x的结点
    332. //接收插入位置(pos)、要插入链表的值（x）
    333. void LTInsert(LTNode* pos, LTDataType x)
    334. {
    335. 	//assert断言插入位置pos不为空：
    336. 	assert(pos != NULL);
    337.  
    338. 	//通过pos结点获得前一个结点posPrev地址：
    339. 	LTNode* posPrev = pos->prev;
    340.  
    341. 	//使用BuyLTNode函数为插入结点开辟空间：
    342. 	LTNode* newnode = BuyLTNode(x);
    343.  
    344. 	//posPrev结点的后继指针next指向newnode：
    345. 	posPrev->next = newnode;
    346.  
    347. 	//newnode前驱指针prev指向posPrev:
    348. 	newnode->prev = posPrev;
    349.  
    350. 	//newnode后继指针next指向pos：
    351. 	newnode->next = pos;
    352.  
    353. 	//pos结点前驱指针prev指向newnode:
    354. 	pos->prev = newnode;
    355. }
    356.  
    357.  
    358.  
    359. //双向链表删除函数--删除pos结点
    360. //接收要删除结点地址（pos）
    361. void LTErase(LTNode* pos)
    362. {
    363. 	//assert断言删除位置结点pos不为空：
    364. 	assert(pos != NULL);
    365.  
    366. 	//保存要删除结点pos的前一个结点posPrev地址：
    367. 	LTNode* posPrev = pos->prev;
    368.  
    369. 	//保存要删除结点pos的后一个结点posNext地址：
    370. 	LTNode* posNext = pos->next;
    371.  
    372. 	//释放掉pos结点：
    373. 	free(pos);
    374.  
    375. 	//将pos前结点posPrev的后继指针指向posNext：
    376. 	posPrev->next = posNext;
    377.  
    378. 	//将pos后结点posNext的前驱指针指向posPrev：
    379. 	posNext->prev = posPrev;
    380. }
    381.  
    382.  
    383.  
    384. //双向链表销毁函数--销毁链表
    385. //接收要销毁链表头系欸但（phead）
    386. void LTDestroy(LTNode* phead)
    387. {
    388. 	//assert断言头指针（哨兵位地址）不为空:
    389. 	assert(phead != NULL);
    390.  
    391. 	//创建遍历指针cur，从第一个结点开始：
    392. 	LTNode* cur = phead->next;
    393.  
    394. 	//使用while循环进行遍历释放：
    395. 	while (cur != phead)
    396. 	{
    397. 		//释放前先存储下一个结点地址：
    398. 		LTNode* next = cur->next;
    399.  
    400. 		//释放当前结点：
    401. 		free(cur);
    402.  
    403. 		//调整指针：
    404. 		cur = next;
    405. 	}
    406. 	
    407. 	//删除完有效结点后，最后再释放哨兵位：
    408. 	free(phead);
    409. }

                

                

    ---------------------------------------------------------------------------------------------

                    

    Test.c -- 双向链表测试文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. //双向链表函数测试文件：
    4.  
    5. //包含双向链表头文件：
    6. #include "List.h"
    7.  
    8. //测试函数--
    9. //LTInit、LTPushBack、LTPrintf函数
    10. void TestList1()
    11. {
    12. 	//初始化一个双向链表：
    13. 	LTNode* plist = LTInit();
    14.  
    15. 	//初始化后使用尾插函数插入数据：
    16. 	LTPushBack(plist, 1);
    17. 	LTPushBack(plist, 2);
    18. 	LTPushBack(plist, 3);
    19. 	LTPushBack(plist, 4);
    20. 	LTPushBack(plist, 5);
    21. 	  
    22. 	//打印当前双向链表：
    23. 	LTPrint(plist);
    24. }
    25.  
    26.  
    27. //测试函数--LTPopBack函数
    28. void TestList2()
    29. {
    30. 	//初始化一个双向链表：
    31. 	LTNode* plist = LTInit();
    32. 	//初始化后使用尾插函数插入数据：
    33. 	LTPushBack(plist, 1);
    34. 	LTPushBack(plist, 2);
    35. 	LTPushBack(plist, 3);
    36. 	//打印当前双向链表：
    37. 	LTPrint(plist);
    38.  
    39. 	//进行尾删：
    40. 	LTPopBack(plist);
    41. 	//打印当前双向链表：
    42. 	LTPrint(plist);
    43.  
    44. 	//进行尾删：
    45. 	LTPopBack(plist);
    46. 	//打印当前双向链表：
    47. 	LTPrint(plist);
    48.  
    49. 	//进行尾删：
    50. 	LTPopBack(plist);
    51. 	//打印当前双向链表：
    52. 	LTPrint(plist);
    53. }
    54.  
    55.  
    56. //测试函数--LTPushFront函数
    57. void TestList3()
    58. {
    59. 	//初始化一个双向链表：
    60. 	LTNode* plist = LTInit();
    61. 	//初始化后使用尾插函数插入数据：
    62. 	LTPushBack(plist, 1);
    63. 	LTPushBack(plist, 2);
    64. 	LTPushBack(plist, 3);
    65. 	//打印当前双向链表：
    66. 	LTPrint(plist);
    67.  
    68. 	//进行头插：
    69. 	LTPushFront(plist, 1000);
    70. 	//打印当前双向链表：
    71. 	LTPrint(plist);
    72. }
    73.  
    74.  
    75. //测试函数--LTPopFront函数
    76. void TestList4()
    77. {
    78. 	//初始化一个双向链表：
    79. 	LTNode* plist = LTInit();
    80. 	//初始化后使用尾插函数插入数据：
    81. 	LTPushBack(plist, 1);
    82. 	LTPushBack(plist, 2);
    83. 	LTPushBack(plist, 3);
    84. 	//打印当前双向链表：
    85. 	LTPrint(plist);
    86.  
    87. 	//进行头删：
    88. 	LTPopFront(plist);
    89. 	//打印当前双向链表：
    90. 	LTPrint(plist);
    91. }
    92.  
    93.  
    94. //测试函数--LTSize函数
    95. void TestList5()
    96. {
    97. 	//初始化一个双向链表：
    98. 	LTNode* plist = LTInit();
    99. 	//初始化后使用尾插函数插入数据：
    100. 	LTPushBack(plist, 1);
    101. 	LTPushBack(plist, 2);
    102. 	LTPushBack(plist, 3);
    103. 	//打印当前双向链表：
    104. 	LTPrint(plist);
    105.  
    106. 	//计算链表长度：
    107. 	int size = LTSize(plist);
    108. 	//打印当前双向链表：
    109. 	printf("链表长度为：%d", size);
    110. }
    111.  
    112.  
    113. //测试函数--LTFind函数
    114. void TestList6()
    115. {
    116. 	//初始化一个双向链表：
    117. 	LTNode* plist = LTInit();
    118. 	//初始化后使用尾插函数插入数据：
    119. 	LTPushBack(plist, 1);
    120. 	LTPushBack(plist, 2);
    121. 	LTPushBack(plist, 3);
    122. 	//打印当前双向链表：
    123. 	LTPrint(plist);
    124.  
    125. 	//使用查找函数：
    126. 	LTNode* find = LTFind(plist, 2);
    127. 	//打印找到的地址
    128. 	printf("0x%xn", find);
    129. }
    130.  
    131.  
    132. //测试函数--LTInsert函数
    133. void TestList7()
    134. {
    135. 	//初始化一个双向链表：
    136. 	LTNode* plist = LTInit();
    137. 	//初始化后使用尾插函数插入数据：
    138. 	LTPushBack(plist, 1);
    139. 	LTPushBack(plist, 2);
    140. 	LTPushBack(plist, 3);
    141. 	//打印当前双向链表：
    142. 	LTPrint(plist);
    143.  
    144. 	//使用插入函数：
    145. 	LTInsert(plist->next->next, 100);
    146. 	//打印当前双向链表：
    147. 	LTPrint(plist);
    148. }
    149.  
    150.  
    151. //测试函数--LTErase函数
    152. void TestList8()
    153. {
    154. 	//初始化一个双向链表：
    155. 	LTNode* plist = LTInit();
    156. 	//初始化后使用尾插函数插入数据：
    157. 	LTPushBack(plist, 1);
    158. 	LTPushBack(plist, 2);
    159. 	LTPushBack(plist, 3);
    160. 	//打印当前双向链表：
    161. 	LTPrint(plist);
    162.  
    163. 	//使用删除函数：
    164. 	LTErase(plist->next->next);
    165. 	//打印当前双向链表：
    166. 	LTPrint(plist);
    167. }
    168.  
    169. //主函数：
    170. int main()
    171. {
    172. 	//调用测试函数：
    173. 	//TestList1();
    174. 	//TestList2();
    175. 	//TestList3();
    176. 	//TestList4();
    177. 	//TestList5();
    178. 	//TestList6();
    179. 	//TestList7();
    180. 	TestList8();
    181.  
    182. 	return 0;
    183. }
    184.
  • 相关阅读:
    北斗导航 | RAIM算法之最小二乘残差法（原理讲解，附代码链接：可用性判定）
    YOLO算法(You Only Look Once)系列讲解与实现（待完善）
    Spring-AOP入门
    手撕IP核系列——Xilinx FIFO IP核-同步FIFO
    Vue 实现拖拽模块(二)自定义拖拽组件位置
    Hexagon_V65_Programmers_Reference_Manual （50）
    书店系统的设计与实现
    win下搭建php环境的方法
    c语言进阶部分详解（指针进阶1）
    【蓝桥杯真题练习】STEMA科技素养练习题库 答案版012 持续更新中~
  • 原文地址：https://blog.csdn.net/weixin_63176266/article/details/133018982