• C语言描述数据结构 —— 单链表

    前言

    对于链表这部分，在数据结构里面是非常重要的。链表的学习周期长一些，博客的内容会多一些，所以对于链表的描述我将分为多篇。基本概念、基本实现、基本习题、进阶习题我都会通过博客向大家分享。那么本篇是对链表有一个初步的认识，并且能够掌握最基本的单链表的增删查改。

    1. 顺序表的问题及思考

    在学习链表之前，我们回顾以下顺序表，那么我们来思考下面几个问题：

    1. 中间/头部的插入删除，时间复杂度为O(N)
    2. 增容需要申请空间，拷贝数据，释放旧空间。这就会造成不小的空间消耗
    3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 200 ，我们再继续插入 5 个数据，那么就浪费了 95 个数据空间。

    那么我们要解决上述问题，就必须学习链表。所以带着问题去学习，那么将事半功倍。

    2. 链表的基本概念和基本结构

    基本概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。  

    如何理解物理存储结构是不连续的呢？

     链表与顺序表不一样的是，顺序表它是一个数组，但是链表不是，所有的连续数据都是通过指针来链接的。那么现在又引出了一个问题，链表的每个数据都要链接下一个数据，而链接的方式是通过指针，那么如何做到呢？我们可以运用结构体来解决这个问题，并且提出结点的概念。

    可以看到，每个结点都有数据域和指针域，指针是指向下一个结点的地址，那么需要补充的是，第一个结点的地址需要用一个指针来保存，最后一个结点的指针是指向空指针。 保存第一个结点的地址的意义在于：可以找到链表的头结点，从而进一步访问结点之后的结点。最后一个结点的指针指向空指针的意义在于：避免野指针的问题，客观上增加一种链表的结束条件，例如字符串的结束标志 '\0' 。

    那么我们就得出了链表的三个特征：

    1. 链表的结构在逻辑上是连续的，但是在物理上不一定连续
    2. 现实中的结点一般都是从堆上申请出来的
    3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续 

    3. 链表的分类 

    链表的结构是有多种的，单向、双向、循环等等，但我们主要的侧重点在单向的不带哨兵卫的链表。

    4. 链表的实现

     结点的声明：

    1. //结点的声明
    2. typedef int LLDataType;
    3. typedef struct LinkList
    4. {
    5. 	LLDataType val;
    6. 	struct LinkList* next;
    7. }LL;

    存储头结点的指针在主函数中定义：

    1. #include "LinkList.h"
    2. int main()
    3. {
    4. 	LL* head = NULL;
    5. 	return 0;
    6. }

    头插的实现：

    1. //创建新结点
    2. static LL* CreateNode(LLDataType x)
    3. {
    4. 	LL* RetNode = (LL*)calloc(1, sizeof(LL));
    5. 	assert(RetNode);
    6. 	RetNode->val = x;
    7. 	RetNode->next = NULL;
    8. 	return RetNode;
    9. }
    10. //头插
    11. void ListPushHead(LL** phead, LLDataType x)
    12. {
    13. 	assert(phead);
    14. 	//此时我们还没有结点，需要创建一个结点
    15. 	LL* NewNode = CreateNode(x);
    16. 	//新结点的指针要指向以前的头结点
    17. 	NewNode->next = *phead;
    18. 	//头指针的内容更新为新结点的地址
    19. 	*phead = NewNode;
    20. }

    需要注意，即使存储头结点的指针是一个指针，但我们在函数内操作时，需要改变指针的指向位置，所以需要使用二级指针。我们可能对最后两条代码存在疑问，我在这里解释一下：

    链表打印实现：

    1. //打印
    2. void ListPrint(LL* phead)
    3. {
    4. 	LL* cur = phead;//使用临时变量来操作链表，但因为是传址调用，不使用也是可以的
    5. 	while (cur)
    6. 	{
    7. 		printf("%d->", cur->val);
    8. 		cur = cur->next;
    9. 	}
    10. 	printf("NULL\n");
    11. }

     测试：头插一个数据以及打印：

    1. #include "LinkList.h"
    2. int main()
    3. {
    4. 	LL* head = NULL;
    5. 	ListPushHead(&head, 5);
    6. 	ListPrint(head);
    7. 	return 0;
    8. }

    尾插的实现：

    1. //尾插
    2. void LIstPushBack(LL** phead, LLDataType x)
    3. {
    4. 	assert(phead);
    5. 	LL* newnode = CreateNode(x);
    6. 	//如果链表没有结点，新结点直接作为头结点
    7. 	if (*phead == NULL)
    8. 	{
    9. 		*phead = newnode;
    10. 	}
    11. 	else
    12. 	{
    13. 		LL* tail = *phead;
    14. 		//向后寻找链表的最后一个结点
    15. 		while (tail->next != NULL)
    16. 		{
    17. 			tail = tail->next;
    18. 		}
    19. 		tail->next = newnode;
    20. 	}
    21. }

    可以看到，我们尾插的情况是有两个的，一个链表里面没有结点，那么就让这个要尾插的结点直接为头。而另一种则是链表中存在结点，我们需要遍历找到最后一个结点，并让这个结点的指针指向新的结点。同时需要注意，我们传的参数是二级指针，我们要解引用才能找到存放头结点地址的指针。

    我们思考一个问题：我们能否像头插一样定义一个指针，专门用来存储最后一个结点的地址呢？当然可以，不过我们需要对函数的参数做出一些改变。

    头插更改：

    1. //头插
    2. void ListPushHead(LL** phead, LL** ptail,LLDataType x)
    3. {
    4. 	//assert(phead);
    5. 	此时我们还没有结点，需要创建一个结点
    6. 	//LL* NewNode = CreateNode(x);
    7. 	新结点的指针要指向以前的头结点
    8. 	//NewNode->next = *phead;
    9. 	头指针的内容更新为新结点的地址
    10. 	//*phead = NewNode;
    11.  
    12. 	assert(phead);
    13. 	//此时我们还没有结点，需要创建一个结点
    14. 	LL* NewNode = CreateNode(x);
    15. 	//链表为空时，第一个头插的结点就是尾结点
    16. 	if (*phead == NULL)
    17. 	{
    18. 		*ptail = NewNode;
    19. 	}
    20. 	//新结点的指针要指向以前的头结点
    21. 	NewNode->next = *phead;
    22. 	//头指针的内容更新为新结点的地址
    23. 	*phead = NewNode;
    24. }

    尾插更改：

    1. //尾插
    2. void LIstPushBack(LL** phead,LL** ptail, LLDataType x)
    3. {
    4. 	//assert(phead);
    5. 	//LL* NewNode = CreateNode(x);
    6. 	如果链表没有结点，新结点直接作为头结点
    7. 	//if (*phead == NULL)
    8. 	//{
    9. 	//	*phead = NewNode;
    10. 	//}
    11. 	//else
    12. 	//{
    13. 	//	LL* tail = *phead;
    14. 	//	//向后寻找链表的最后一个结点
    15. 	//	while (tail->next != NULL)
    16. 	//	{
    17. 	//		tail = tail->next;
    18. 	//	}
    19. 	//	tail->next = NewNode;
    20. 	//}
    21.  
    22. 	assert(phead && ptail);
    23. 	LL* NewNode = CreateNode(x);
    24. 	//如果链表为空，那么头尾指针都指向这个新结点
    25. 	if (*phead == NULL)
    26. 	{
    27. 		*ptail = *phead = NewNode;
    28. 	}
    29. 	else
    30. 	{
    31. 		(*ptail)->next = NewNode;//尾结点的指针指向新结点
    32. 		(*ptail) = (*ptail)->next;//尾指针指向新结点
    33. 	}
    34. }

    我们对修改之后的代码进行数据测试：

    1. #include "LinkList.h"
    2. int main()
    3. {
    4. 	LL* head = NULL;
    5. 	LL* tail = NULL;//专门用来存储最后一个结点的地址
    6. 	ListPushHead(&head,&tail, 5);
    7. 	ListPushHead(&head, &tail, 6);
    8. 	ListPushHead(&head, &tail, 7);
    9. 	ListPrint(head);
    10.  
    11. 	LIstPushBack(&head,&tail, 3);
    12. 	LIstPushBack(&head, &tail, 4);
    13. 	LIstPushBack(&head, &tail, 5);
    14. 	ListPrint(head);
    15.  
    16. 	return 0;
    17. }

     可以看到，输出结果正是我们想要的。那么修改之后的代码有什么优势呢？其一就是减少了时间复杂度，用循环的方式去找尾，如果数据量足够大，是非常消耗时间的。其二就是我们掌握了这个方法以后，在一些题目上面，我们能取得一些优势。

    头删的实现：

    1. //头删
    2. void ListPopHead(LL** phead, LL** ptail)
    3. {
    4. 	assert(phead && ptail);
    5. 	assert(*phead);//链表为空不需要删除，强制退出
    6. 	LL* cur = *phead;
    7. 	//如果链表仅有一个结点
    8. 	if (cur->next == NULL)
    9. 	{
    10. 		free(cur);//释放结点
    11. 		*phead = *ptail = NULL;//存储头尾结点地址的指针置空
    12. 	}
    13. 	//链表有两个或两个以上结点时
    14. 	else
    15. 	{
    16. 		*phead = cur->next;
    17. 		free(cur);
    18. 		//尾指针不需要变
    19. 	}
    20. }

    尾删的实现： 

    1. //尾删
    2. void ListPopBack(LL** phead, LL** ptail)
    3. {
    4. 	assert(phead && ptail);
    5. 	assert(*phead);//链表里面没有结点不需要删除 
    6. 	LL* cur = *ptail;
    7. 	LL* NewPtail = *phead;
    8. 	//找到倒数第二个结点
    9. 	while (NewPtail->next != *ptail)
    10. 	{
    11. 		NewPtail = NewPtail->next;
    12. 	}
    13. 	//对删除之前的尾结点释放
    14. 	free(cur);
    15. 	//存储尾结点地址的指针更新
    16. 	*ptail = NewPtail;
    17. 	(*ptail)->next = NULL;
    18. 	
    19. }

    测试：头删和尾删：

    1. #include "LinkList.h"
    2. int main()
    3. {
    4. 	LL* head = NULL;
    5. 	LL* tail = NULL;//专门用来存储最后一个结点的地址
    6. 	ListPushHead(&head,&tail, 5);
    7. 	ListPushHead(&head, &tail, 6);
    8. 	ListPushHead(&head, &tail, 7);
    9. 	ListPrint(head);
    10.  
    11. 	LIstPushBack(&head,&tail, 3);
    12. 	LIstPushBack(&head, &tail, 4);
    13. 	LIstPushBack(&head, &tail, 5);
    14. 	ListPrint(head);
    15.  
    16. 	ListPopHead(&head, &tail);
    17. 	ListPrint(head);
    18. 	ListPopBack(&head, &tail);
    19. 	ListPrint(head);
    20. 	return 0;
    21. }

     

    数据的查找：

    1. //查找
    2. LL* ListFind(LL* phead,LLDataType x)
    3. {
    4. 	LL* cur = phead;
    5. 	while (cur)
    6. 	{
    7. 		if (cur->val == x)
    8. 			return cur;
    9. 		cur = cur->next;
    10. 	}
    11. 	return NULL;
    12. }

    我们的目的是找到数据的结点地址，如果确实有结点存储这个数据，那么就返回结点地址，否则返回空。如果有多个结点存储同一个数据，那么返回第一个结点的地址。这是符合常理的设计方法。

    在 pos 位置插入数据：

    1. //在 pos 位置插入
    2. void ListInsert(LL** phead, LL** ptail, LL* pos, LLDataType x)
    3. {
    4. 	assert(phead && ptail);
    5. 	assert(*phead);//确保链表有结点
    6. 	//如果 pos 位置与头结点位置重合就头插
    7. 	if (pos == *phead)
    8. 	{
    9. 		ListPushHead(phead, ptail, x);
    10. 	}
    11. 	else
    12. 	{
    13. 		//在 pos 位置之前插入
    14. 		LL* cur = *phead;
    15. 		while (cur->next != pos)
    16. 		{
    17. 			cur = cur->next;
    18. 		}
    19. 		LL* NewNode = CreateNode(x);
    20. 		cur->next = NewNode;
    21. 		NewNode->next = pos;
    22. 	}
    23. }

    测试：在 pos 位置插入数据(与查找配合)：

    1. #include "LinkList.h"
    2. int main()
    3. {
    4. 	LL* head = NULL;
    5. 	LL* tail = NULL;//专门用来存储最后一个结点的地址
    6. 	ListPushHead(&head,&tail, 5);
    7. 	ListPushHead(&head, &tail, 6);
    8. 	ListPushHead(&head, &tail, 7);
    9. 	ListPrint(head);
    10.  
    11. 	LIstPushBack(&head,&tail, 3);
    12. 	LIstPushBack(&head, &tail, 4);
    13. 	LIstPushBack(&head, &tail, 5);
    14. 	ListPrint(head);
    15.  
    16. 	ListPopHead(&head, &tail);
    17. 	ListPrint(head);
    18. 	ListPopBack(&head, &tail);
    19. 	ListPrint(head);
    20.  
    21. 	ListInsert(&head, &tail, ListFind(head,5), 50);
    22. 	ListPrint(head);
    23.  
    24. 	return 0;
    25. }

     

    在 pos 位置删除结点：

    1. //在 pos 位置删除
    2. void ListPopInsert(LL** phead, LL** ptail, LL* pos)
    3. {
    4. 	assert(phead && ptail);
    5. 	assert(*phead);//确保链表有结点
    6. 	//如果 pos 位置是头结点就头删
    7. 	if (pos == *phead)
    8. 	{
    9. 		ListPopHead(phead, ptail);
    10. 	}
    11. 	//如果 pos 位置是尾结点就尾删
    12. 	else if (pos == *ptail)
    13. 	{
    14. 		ListPopBack(phead, ptail);
    15. 	}
    16. 	else
    17. 	{
    18. 		LL* cur = *phead;
    19. 		while (cur->next != pos)
    20. 		{
    21. 			cur = cur->next;
    22. 		}
    23. 		cur->next = pos->next;
    24. 		free(pos);
    25. 	}
    26. }

    测试：在 pos 位置删除结点：

    1. #include "LinkList.h"
    2. int main()
    3. {
    4. 	LL* head = NULL;
    5. 	LL* tail = NULL;//专门用来存储最后一个结点的地址
    6. 	ListPushHead(&head,&tail, 5);
    7. 	ListPushHead(&head, &tail, 6);
    8. 	ListPushHead(&head, &tail, 7);
    9. 	ListPrint(head);
    10.  
    11. 	LIstPushBack(&head,&tail, 3);
    12. 	LIstPushBack(&head, &tail, 4);
    13. 	LIstPushBack(&head, &tail, 5);
    14. 	ListPrint(head);
    15.  
    16. 	ListPopHead(&head, &tail);
    17. 	ListPrint(head);
    18. 	ListPopBack(&head, &tail);
    19. 	ListPrint(head);
    20.  
    21. 	ListInsert(&head, &tail, ListFind(head,5), 50);
    22. 	ListPrint(head);
    23.  
    24. 	ListPopInsert(&head, &tail, ListFind(head, 5));
    25. 	ListPrint(head);
    26.  
    27.  
    28. 	return 0;
    29. }

     

    5. 完整各文件代码

    test.c 源文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include "LinkList.h"
    4. int main()
    5. {
    6. 	LL* head = NULL;
    7. 	LL* tail = NULL;//专门用来存储最后一个结点的地址
    8. 	ListPushHead(&head,&tail, 5);
    9. 	ListPushHead(&head, &tail, 6);
    10. 	ListPushHead(&head, &tail, 7);
    11. 	ListPrint(head);
    12.  
    13. 	LIstPushBack(&head,&tail, 3);
    14. 	LIstPushBack(&head, &tail, 4);
    15. 	LIstPushBack(&head, &tail, 5);
    16. 	ListPrint(head);
    17.  
    18. 	ListPopHead(&head, &tail);
    19. 	ListPrint(head);
    20. 	ListPopBack(&head, &tail);
    21. 	ListPrint(head);
    22.  
    23. 	ListInsert(&head, &tail, ListFind(head,5), 50);
    24. 	ListPrint(head);
    25.  
    26. 	ListPopInsert(&head, &tail, ListFind(head, 5));
    27. 	ListPrint(head);
    28.  
    29.  
    30. 	return 0;
    31. }

     ListLink.c 源文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "LinkList.h"
    3.  
    4. //创建新结点
    5. static LL* CreateNode(LLDataType x)
    6. {
    7. 	LL* RetNode = (LL*)calloc(1, sizeof(LL));
    8. 	assert(RetNode);
    9. 	RetNode->val = x;
    10. 	RetNode->next = NULL;
    11. 	return RetNode;
    12. }
    13. //头插
    14. void ListPushHead(LL** phead, LL** ptail,LLDataType x)
    15. {
    16. 	//assert(phead);
    17. 	此时我们还没有结点，需要创建一个结点
    18. 	//LL* NewNode = CreateNode(x);
    19. 	新结点的指针要指向以前的头结点
    20. 	//NewNode->next = *phead;
    21. 	头指针的内容更新为新结点的地址
    22. 	//*phead = NewNode;
    23.  
    24. 	assert(phead);
    25. 	//此时我们还没有结点，需要创建一个结点
    26. 	LL* NewNode = CreateNode(x);
    27. 	//链表为空时，第一个头插的结点就是尾结点
    28. 	if (*phead == NULL)
    29. 	{
    30. 		*ptail = NewNode;
    31. 	}
    32. 	//新结点的指针要指向以前的头结点
    33. 	NewNode->next = *phead;
    34. 	//头指针的内容更新为新结点的地址
    35. 	*phead = NewNode;
    36. }
    37. //打印
    38. void ListPrint(LL* phead)
    39. {
    40. 	LL* cur = phead;//使用临时变量来操作链表，但因为是传址调用，不使用也是可以的
    41. 	while (cur)
    42. 	{
    43. 		printf("%d->", cur->val);
    44. 		cur = cur->next;
    45. 	}
    46. 	printf("NULL\n");
    47. }
    48. //尾插
    49. void LIstPushBack(LL** phead,LL** ptail, LLDataType x)
    50. {
    51. 	//assert(phead);
    52. 	//LL* NewNode = CreateNode(x);
    53. 	如果链表没有结点，新结点直接作为头结点
    54. 	//if (*phead == NULL)
    55. 	//{
    56. 	//	*phead = NewNode;
    57. 	//}
    58. 	//else
    59. 	//{
    60. 	//	LL* tail = *phead;
    61. 	//	//向后寻找链表的最后一个结点
    62. 	//	while (tail->next != NULL)
    63. 	//	{
    64. 	//		tail = tail->next;
    65. 	//	}
    66. 	//	tail->next = NewNode;
    67. 	//}
    68.  
    69. 	assert(phead && ptail);
    70. 	LL* NewNode = CreateNode(x);
    71. 	//如果链表为空，那么头尾指针都指向这个新结点
    72. 	if (*phead == NULL)
    73. 	{
    74. 		*ptail = *phead = NewNode;
    75. 	}
    76. 	else
    77. 	{
    78. 		(*ptail)->next = NewNode;//尾结点的指针指向新结点
    79. 		(*ptail) = (*ptail)->next;//尾指针指向新结点
    80. 	}
    81. }
    82. //头删
    83. void ListPopHead(LL** phead, LL** ptail)
    84. {
    85. 	assert(phead && ptail);
    86. 	assert(*phead);//链表为空不需要删除，强制退出
    87. 	LL* cur = *phead;
    88. 	//如果链表仅有一个结点
    89. 	if (cur->next == NULL)
    90. 	{
    91. 		free(cur);//释放结点
    92. 		*phead = *ptail = NULL;//存储头尾结点地址的指针置空
    93. 	}
    94. 	//链表有两个或两个以上结点时
    95. 	else
    96. 	{
    97. 		*phead = cur->next;
    98. 		free(cur);
    99. 		//尾指针不需要变
    100. 	}
    101. }
    102. //尾删
    103. void ListPopBack(LL** phead, LL** ptail)
    104. {
    105. 	assert(phead && ptail);
    106. 	assert(*phead);//链表里面没有结点不需要删除 
    107. 	LL* cur = *ptail;
    108. 	LL* NewPtail = *phead;
    109. 	//找到倒数第二个结点
    110. 	while (NewPtail->next != *ptail)
    111. 	{
    112. 		NewPtail = NewPtail->next;
    113. 	}
    114. 	//对删除之前的尾结点释放
    115. 	free(cur);
    116. 	//存储尾结点地址的指针更新
    117. 	*ptail = NewPtail;
    118. 	(*ptail)->next = NULL;
    119. }
    120. //查找
    121. LL* ListFind(LL* phead,LLDataType x)
    122. {
    123. 	LL* cur = phead;
    124. 	while (cur)
    125. 	{
    126. 		if (cur->val == x)
    127. 			return cur;
    128. 		cur = cur->next;
    129. 	}
    130. 	return NULL;
    131. }
    132. //在 pos 位置插入
    133. void ListInsert(LL** phead, LL** ptail, LL* pos, LLDataType x)
    134. {
    135. 	assert(phead && ptail);
    136. 	assert(*phead);//确保链表有结点
    137. 	//如果 pos 位置与头结点位置重合就头插
    138. 	if (pos == *phead)
    139. 	{
    140. 		ListPushHead(phead, ptail, x);
    141. 	}
    142. 	else
    143. 	{
    144. 		//在 pos 位置之前插入
    145. 		LL* cur = *phead;
    146. 		while (cur->next != pos)
    147. 		{
    148. 			cur = cur->next;
    149. 		}
    150. 		LL* NewNode = CreateNode(x);
    151. 		cur->next = NewNode;
    152. 		NewNode->next = pos;
    153. 	}
    154. }
    155. //在 pos 位置删除
    156. void ListPopInsert(LL** phead, LL** ptail, LL* pos)
    157. {
    158. 	assert(phead && ptail);
    159. 	assert(*phead);//确保链表有结点
    160. 	//如果 pos 位置是头结点就头删
    161. 	if (pos == *phead)
    162. 	{
    163. 		ListPopHead(phead, ptail);
    164. 	}
    165. 	//如果 pos 位置是尾结点就尾删
    166. 	else if (pos == *ptail)
    167. 	{
    168. 		ListPopBack(phead, ptail);
    169. 	}
    170. 	else
    171. 	{
    172. 		LL* cur = *phead;
    173. 		while (cur->next != pos)
    174. 		{
    175. 			cur = cur->next;
    176. 		}
    177. 		cur->next = pos->next;
    178. 		free(pos);
    179. 	}
    180. }

    ListLink.h 头文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include 
    4. #include 
    5. #include 
    6. //结点的声明
    7. typedef int LLDataType;
    8. typedef struct LinkList
    9. {
    10. 	LLDataType val;
    11. 	struct LinkList* next;
    12. }LL;
    13. //存放头结点地址的指针
    14.  
    15.  
    16. void ListPushHead(LL** phead, LL** ptail,LLDataType x);//头插
    17. void ListPrint(LL* phead);//打印
    18. void LIstPushBack(LL** phead,LL** ptail ,LLDataType x);//尾插 
    19. void ListPopHead(LL** phead, LL** ptail);//头删
    20. void ListPopBack(LL** phead, LL** ptail);//尾删
    21. LL* ListFind(LL* phead,LLDataType x);//查找
    22. void ListInsert(LL** phead, LL** ptail, LL* pos, LLDataType x);//在 pos 位置插入
    23. void ListPopInsert(LL** phead, LL** ptail, LL* pos);//删除 pos 位置的数据

  • 相关阅读:
    ruoyi（若依）接口拦截路径配置，接口访问要授权，放开授权直接访问
    每日一文(第一天)
    vivo大数据日志采集Agent设计实践
    matlab实现MCMC的马尔可夫转换MS- ARMA - GARCH模型估计
    Docker Compose安装部署Jenkins
    Study Git - Data Model
    机器学习(十七）：网格搜索（Grid Search）和SVM
    第一季：1自增变量【Java面试题】
    Spring Cloud Alibaba —— 分布式事务组件
    海思3559万能平台搭建：OSD功能的优化
  • 原文地址：https://blog.csdn.net/weixin_59913110/article/details/126103367