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

数据结构 -- 链表详解_数据结构链表

作者：我家小花儿 | 2024-07-02 07:10:11

赞

踩

数据结构链表

一、链表的概念及结构

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

链表的结构可以形象的看作是一辆火车，每块空间独立存在并且通过指针链接在一起。

在数据结构中：

注意：1、从上图可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。

           2、现实的节点一般都是从堆上申请出来的。

           3、在堆上申请的空间是按一定策略来分配的，两次申请的空间可能连续也可能不连续。

二、链表的分类

实际上链表的结构非常多样，以下情况组合起来就有八种链表结构

1、单向或者双向

2、带头（哨兵位）或者不带头

3、循环或者非循环

虽然链表中存在这么多结构，但是在实际中最常用的就只有两种结构：

1、无头单向非循环链表：结构简单，一般不会单独用来存储数据，实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等。

2、带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表，这个结构虽然结构较为复杂，但是使用代码实现反而因为结构的原因更加简单了，这一点在后续代码实现过程中会体现出来。

三、链表的实现

在代码实现过程中，我们依然为两个链表分别建立三个文件

无头单向非循环链表：SList.h（函数声明）、SList.c（函数定义）、4.c（测试函数功能）

带头双向循环链表：List.h（函数声明）、List.c（函数定义）、5.c（测试函数功能）

3.1 无头单向非循环链表

1）创建结构体

首先我们需要创建一个结构体，其中一个存放数据，另一个指向下一个空间。

  1. typedef int SLTDateType;
  2.  
  3. typedef struct SListNode
  4. {
  5. 	SLTDateType data;
  6. 	struct SListNode* next;
  7. }SListNode;

2）尾插/头插

尾插需要先判断链表是否为空，为空则直接建立一个节点就行，不为空则需要遍历到最后一个节点后插入

  1. // 单链表的尾插
  2. void SListPushBack(SListNode** pplist, SLTDateType x)
  3. {
  4. 	assert(pplist);
  5. 	assert(*pplist);
  6.  
  7. 	SListNode* newnode = BuySListNode(x);
  8. 	
  9. 	if (*pplist == NULL)
  10. 	{
  11. 		*pplist = newnode;
  12. 	}
  13. 	else
  14. 	{
  15. 		SListNode* tail = *pplist;
  16. 		while (tail->next != NULL)
  17. 		{
  18. 			tail = tail->next;
  19. 		}
  20. 		tail->next = newnode;
  21. 	}
  22. }

头插的实现较为简单，只需要在链表头插入即可

  1. // 单链表的头插
  2. void SListPushFront(SListNode** pplist, SLTDateType x)
  3. {
  4. 	assert(pplist);
  5.  
  6. 	SListNode* newnode = BuySListNode(x);
  7. 	newnode->next = *pplist;
  8. 	*pplist = newnode;
  9. }

测试结果

3）尾删/头删

尾删和尾插的思路刚好相反，注意需要判空

  1. // 单链表的尾删
  2. void SListPopBack(SListNode** pplist)
  3. {
  4. 	assert(pplist);
  5. 	assert(*pplist);
  6.  
  7. 	if ((*pplist)->next == NULL)
  8. 	{
  9. 		free(*pplist);
  10. 		*pplist = NULL;
  11. 	}
  12. 	else
  13. 	{
  14. 		SListNode* tail = *pplist;
  15. 		while (tail->next->next)
  16. 		{
  17. 			tail = tail->next;
  18. 		}
  19.  
  20. 		free(tail->next);
  21. 		tail->next = NULL;
  22. 	}
  23. }
  1. // 单链表的头删
  2. void SListPopFront(SListNode** pplist)
  3. {
  4. 	assert(pplist);
  5. 	assert(*pplist);
  6.  
  7. 	if ((*pplist)->next == NULL)
  8. 	{
  9. 		free(*pplist);
  10. 		*pplist = NULL;
  11. 	}
  12. 	else
  13. 	{
  14. 		SListNode* del = *pplist;
  15. 		*pplist = (*pplist)->next;
  16. 		free(del);
  17. 	}
  18. }

测试结果

4）查找

  1. // 单链表查找
  2. SListNode* SListFind(SListNode* plist, SLTDateType x)
  3. {
  4. 	SListNode* cur = plist;
  5. 	while (cur)
  6. 	{
  7. 		if (cur->data == x)
  8. 		{
  9. 			return cur;
  10. 		}
  11. 		cur = cur->next;
  12. 	}
  13. 	return NULL;
  14. }

3.2 带头双向循环链表

1）创建结构体

这里我们依然创建一个结构体，其中一个存放数据，另外两个分别指向前一片空间和后一片空间

  1. typedef int LTDataType;
  2.  
  3. typedef struct ListNode
  4. {
  5. 	LTDataType _data;
  6. 	struct ListNode* _next;
  7. 	struct ListNode* _prev;
  8. }ListNode;

2）创建头结点（哨兵位）

创建哨兵位时只有这一个元素，该元素的前后指针都指向自己，已到达循环的目的

  1. // 创建头结点（哨兵位）
  2. ListNode* ListCreate()
  3. {
  4. 	ListNode* pHead = BuyNode(-1);
  5. 	pHead->_next = pHead;
  6. 	pHead->_prev = pHead;
  7. 	return pHead;
  8. }

3）尾插/头插

  1. // 双链表的尾插
  2. void ListPushBack(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5.  
  6. 	ListNode* tail = pHead->_prev;
  7. 	ListNode* newnode = BuyNode(x);
  8.  
  9. 	tail->_next = newnode;
  10. 	newnode->_prev = tail;
  11. 	newnode->_next = pHead;
  12. 	pHead->_prev = newnode;
  13. }
  1. // 双链表的头插
  2. void ListPushFront(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5.  
  6. 	ListNode* newnode = BuyNode(x);
  7. 	ListNode* first = pHead->_next;
  8.  
  9. 	pHead->_next = newnode;
  10. 	newnode->_prev = pHead;
  11. 	newnode->_next = first;
  12. 	first->_prev = newnode;
  13. }

测试结果

4）尾删/头删

  1. // 双链表的尾删
  2. void ListPopBack(ListNode* pHead)
  3. {
  4. 	assert(pHead);
  5.  
  6. 	ListNode* tail = pHead->_prev;
  7. 	ListNode* tailprev = tail->_prev;
  8. 	free(tail);
  9. 	tailprev->_next = pHead;
  10. 	pHead->_prev = tailprev;
  11. }
  1. // 双链表的头删
  2. void ListPopFront(ListNode* pHead)
  3. {
  4. 	assert(pHead);
  5.  
  6. 	ListNode* first = pHead->_next;
  7. 	ListNode* second = first->_next;
  8.  
  9. 	pHead->_next = second;
  10. 	second->_prev = pHead;
  11. 	free(first);
  12. }

测试结果

5）查找

  1. // 双链表的查找
  2. ListNode* ListFind(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5.  
  6. 	ListNode* cur = pHead->_next;
  7. 	while (cur != pHead)
  8. 	{
  9. 		if (cur->_data == x)
  10. 		{
  11. 			return cur;
  12. 		}
  13. 		cur = cur->_next;
  14. 	}
  15. 	return NULL;
  16. }

6）在指定位置前插入

  1. // 在pos位置的前面插入
  2. void ListInsert(ListNode* pos, LTDataType x)
  3. {
  4. 	assert(pos);
  5.  
  6. 	ListNode* prev = pos->_prev;
  7. 	ListNode* newnode = BuyNode(x);
  8.  
  9. 	prev->_next = newnode;
  10. 	newnode->_prev = prev;
  11. 	newnode->_next = pos;
  12. 	pos->_prev = newnode;
  13. }

7）删除指定位置的节点

  1. // 删除pos位置的节点
  2. void ListErase(ListNode* pos)
  3. {
  4. 	assert(pos);
  5.  
  6. 	ListNode* posprev = pos->_prev;
  7. 	ListNode* posnext = pos->_next;
  8.  
  9. 	posprev->_next = posnext;
  10. 	posnext->_prev = posprev;
  11. 	free(pos);
  12. }

四、源码

4.1 无头单向非循环链表

SList.h（函数声明）

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>
  4.  
  5.  
  6.  
  7. typedef int SLTDateType;
  8. typedef struct SListNode
  9. {
  10. 	SLTDateType data;
  11. 	struct SListNode* next;
  12. }SListNode;
  13.  
  14. // 动态申请一个节点
  15. SListNode* BuySListNode(SLTDateType x);
  16. // 单链表打印
  17. void SListPrint(SListNode* plist);
  18. // 单链表尾插
  19. void SListPushBack(SListNode** pplist, SLTDateType x);
  20. // 单链表的头插
  21. void SListPushFront(SListNode** pplist, SLTDateType x);
  22. // 单链表的尾删
  23. void SListPopBack(SListNode** pplist);
  24. // 单链表头删
  25. void SListPopFront(SListNode** pplist);
  26. // 单链表查找
  27. SListNode* SListFind(SListNode* plist, SLTDateType x);

SList.c（函数定义）

  1. #include"SList.h"
  2.  
  3. SListNode* BuySListNode(SLTDateType x)
  4. {
  5. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  6. 	if (newnode == NULL)
  7. 	{
  8. 		perror("malloc fail");
  9. 		return;
  10. 	}
  11. 	newnode->data = x;
  12. 	newnode->next = NULL;
  13.  
  14. 	return newnode;
  15. }
  16.  
  17.  
  18. void SListPrint(SListNode* plist)
  19. {
  20. 	SListNode* cur = plist;
  21. 	while (cur != NULL)
  22. 	{
  23. 		printf("%d->", cur->data);
  24. 		cur = cur->next;
  25. 	}
  26. 	printf("NULL\n");
  27. }
  28.  
  29.  
  30. void SListPushBack(SListNode** pplist, SLTDateType x)
  31. {
  32. 	assert(pplist);
  33. 	assert(*pplist);
  34.  
  35. 	SListNode* newnode = BuySListNode(x);
  36. 	
  37. 	if (*pplist == NULL)
  38. 	{
  39. 		*pplist = newnode;
  40. 	}
  41. 	else
  42. 	{
  43. 		SListNode* tail = *pplist;
  44. 		while (tail->next != NULL)
  45. 		{
  46. 			tail = tail->next;
  47. 		}
  48. 		tail->next = newnode;
  49. 	}
  50. }
  51.  
  52. void SListPushFront(SListNode** pplist, SLTDateType x)
  53. {
  54. 	assert(pplist);
  55.  
  56. 	SListNode* newnode = BuySListNode(x);
  57. 	newnode->next = *pplist;
  58. 	*pplist = newnode;
  59. }
  60.  
  61. void SListPopBack(SListNode** pplist)
  62. {
  63. 	assert(pplist);
  64. 	assert(*pplist);
  65.  
  66. 	if ((*pplist)->next == NULL)
  67. 	{
  68. 		free(*pplist);
  69. 		*pplist = NULL;
  70. 	}
  71. 	else
  72. 	{
  73. 		SListNode* tail = *pplist;
  74. 		while (tail->next->next)
  75. 		{
  76. 			tail = tail->next;
  77. 		}
  78.  
  79. 		free(tail->next);
  80. 		tail->next = NULL;
  81. 	}
  82. }
  83.  
  84. void SListPopFront(SListNode** pplist)
  85. {
  86. 	assert(pplist);
  87. 	assert(*pplist);
  88.  
  89. 	if ((*pplist)->next == NULL)
  90. 	{
  91. 		free(*pplist);
  92. 		*pplist = NULL;
  93. 	}
  94. 	else
  95. 	{
  96. 		SListNode* del = *pplist;
  97. 		*pplist = (*pplist)->next;
  98. 		free(del);
  99. 	}
  100. }
  101.  
  102. SListNode* SListFind(SListNode* plist, SLTDateType x)
  103. {
  104. 	SListNode* cur = plist;
  105. 	while (cur)
  106. 	{
  107. 		if (cur->data == x)
  108. 		{
  109. 			return cur;
  110. 		}
  111. 		cur = cur->next;
  112. 	}
  113. 	return NULL;
  114. }

4.c（测试函数功能）

  1. #include"SList.h"
  2.  
  3.  
  4. void TestSList1()
  5. {
  6. 	SListNode* plist = NULL;
  7. 	SListPushFront(&plist, 1);
  8. 	SListPushFront(&plist, 2);
  9. 	SListPushFront(&plist, 3);
  10. 	SListPushFront(&plist, 4);
  11.  
  12.     SListPrint(plist);
  13.  
  14. 	SListPushBack(&plist, 5);
  15. 	SListPushBack(&plist, 6);
  16. 	SListPushBack(&plist, 7);
  17. 	SListPushBack(&plist, 8);
  18.  
  19. 	SListPrint(plist);
  20.  
  21. 	SListPopBack(&plist);
  22. 	SListPopBack(&plist);
  23. 	SListPopBack(&plist);
  24. 	SListPrint(plist);
  25.  
  26. 	SListPopBack(&plist);
  27. 	SListPrint(plist);
  28.  
  29. 	SListPopBack(&plist);
  30. 	SListPrint(plist);
  31.  
  32. 	SListPopBack(&plist);
  33. 	SListPrint(plist);
  34.  
  35. 	SListPopBack(&plist);
  36. 	SListPrint(plist);
  37.  
  38. 	SListPopBack(&plist);
  39. 	SListPrint(plist);
  40.  
  41. 	/*SListPopBack(&plist);
  42. 	SListPrint(plist);*/
  43.  
  44. 	/*SListPopFront(&plist);
  45. 	SListPrint(plist);
  46.  
  47. 	SListPopFront(&plist);
  48. 	SListPrint(plist);
  49.  
  50. 	SListPopFront(&plist);
  51. 	SListPrint(plist);
  52.  
  53. 	SListPopFront(&plist);
  54. 	SListPrint(plist);
  55.  
  56. 	SListPopFront(&plist);
  57. 	SListPrint(plist);*/
  58.  
  59. }
  60.  
  61.  
  62.  
  63. int main()
  64. {
  65. 	TestSList1();
  66.  
  67. 	return 0;
  68. }

4.2 带头双向循环链表

List.h（函数声明）

  1. #include<stdio.h>
  2. #include<assert.h>
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5.  
  6.  
  7. typedef int LTDataType;
  8. typedef struct ListNode
  9. {
  10. 	LTDataType _data;
  11. 	struct ListNode* _next;
  12. 	struct ListNode* _prev;
  13. }ListNode;
  14.  
  15. // 创建返回链表的头结点.
  16. ListNode* ListCreate();
  17. // 双向链表销毁
  18. void ListDestory(ListNode* pHead);
  19. // 双向链表打印
  20. void ListPrint(ListNode* pHead);
  21. // 双向链表尾插
  22. void ListPushBack(ListNode* pHead, LTDataType x);
  23. // 双向链表尾删
  24. void ListPopBack(ListNode* pHead);
  25. // 双向链表头插
  26. void ListPushFront(ListNode* pHead, LTDataType x);
  27. // 双向链表头删
  28. void ListPopFront(ListNode* pHead);
  29. // 双向链表查找
  30. ListNode* ListFind(ListNode* pHead, LTDataType x);
  31. // 双向链表在pos的前面进行插入
  32. void ListInsert(ListNode* pos, LTDataType x);
  33. // 双向链表删除pos位置的节点
  34. void ListErase(ListNode* pos);

List.c（函数定义）

  1. #include"List.h"
  2.  
  3.  
  4. ListNode* BuyNode(LTDataType x)
  5. {
  6. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  7. 	if (newnode == NULL)
  8. 	{
  9. 		perror("malloc fail");
  10. 		return NULL;
  11. 	}
  12.  
  13. 	newnode->_data = x;
  14. 	newnode->_next = NULL;
  15. 	newnode->_prev = NULL;
  16. }
  17.  
  18. ListNode* ListCreate()
  19. {
  20. 	ListNode* pHead = BuyNode(-1);
  21. 	pHead->_next = pHead;
  22. 	pHead->_prev = pHead;
  23. 	return pHead;
  24. }
  25.  
  26. void ListPrint(ListNode* pHead)
  27. {
  28. 	assert(pHead);
  29.  
  30. 	printf("sentinel<==>");
  31. 	ListNode* cur = pHead->_next;
  32. 	while (cur != pHead)
  33. 	{
  34. 		printf("%d<==>", cur->_data);
  35. 		cur = cur->_next;
  36. 	}
  37. 	printf("\n");
  38. }
  39.  
  40. bool LTEmpty(ListNode* pHead)
  41. {
  42. 	assert(pHead);
  43.  
  44. 	return pHead->_next == pHead;
  45. }
  46.  
  47. void ListPushBack(ListNode* pHead, LTDataType x)
  48. {
  49. 	assert(pHead);
  50.  
  51. 	ListNode* tail = pHead->_prev;
  52. 	ListNode* newnode = BuyNode(x);
  53.  
  54. 	tail->_next = newnode;
  55. 	newnode->_prev = tail;
  56. 	newnode->_next = pHead;
  57. 	pHead->_prev = newnode;
  58. }
  59.  
  60. void ListPopBack(ListNode* pHead)
  61. {
  62. 	assert(pHead);
  63.  
  64. 	ListNode* tail = pHead->_prev;
  65. 	ListNode* tailprev = tail->_prev;
  66. 	free(tail);
  67. 	tailprev->_next = pHead;
  68. 	pHead->_prev = tailprev;
  69. }
  70.  
  71. void ListPushFront(ListNode* pHead, LTDataType x)
  72. {
  73. 	assert(pHead);
  74.  
  75. 	ListNode* newnode = BuyNode(x);
  76. 	ListNode* first = pHead->_next;
  77.  
  78. 	pHead->_next = newnode;
  79. 	newnode->_prev = pHead;
  80. 	newnode->_next = first;
  81. 	first->_prev = newnode;
  82. }
  83.  
  84. void ListPopFront(ListNode* pHead)
  85. {
  86. 	assert(pHead);
  87.  
  88. 	ListNode* first = pHead->_next;
  89. 	ListNode* second = first->_next;
  90.  
  91. 	pHead->_next = second;
  92. 	second->_prev = pHead;
  93. 	free(first);
  94. }
  95.  
  96. ListNode* ListFind(ListNode* pHead, LTDataType x)
  97. {
  98. 	assert(pHead);
  99.  
  100. 	ListNode* cur = pHead->_next;
  101. 	while (cur != pHead)
  102. 	{
  103. 		if (cur->_data == x)
  104. 		{
  105. 			return cur;
  106. 		}
  107. 		cur = cur->_next;
  108. 	}
  109. 	return NULL;
  110. }
  111.  
  112. void ListInsert(ListNode* pos, LTDataType x)
  113. {
  114. 	assert(pos);
  115.  
  116. 	ListNode* prev = pos->_prev;
  117. 	ListNode* newnode = BuyNode(x);
  118.  
  119. 	prev->_next = newnode;
  120. 	newnode->_prev = prev;
  121. 	newnode->_next = pos;
  122. 	pos->_prev = newnode;
  123. }
  124.  
  125. void ListErase(ListNode* pos)
  126. {
  127. 	assert(pos);
  128.  
  129. 	ListNode* posprev = pos->_prev;
  130. 	ListNode* posnext = pos->_next;
  131.  
  132. 	posprev->_next = posnext;
  133. 	posnext->_prev = posprev;
  134. 	free(pos);
  135. }
  136.  
  137. void ListDestory(ListNode* pHead)
  138. {
  139. 	assert(pHead);
  140.  
  141. 	ListNode* cur = pHead->_next;
  142. 	while (cur != pHead)
  143. 	{
  144. 		ListNode* next = cur->_next;
  145. 		free(cur);
  146. 		cur = next;
  147. 	}
  148. 	free(pHead);
  149. }

5.c（测试函数功能）

  1. #include"List.h"
  2.  
  3. TestList()
  4. {
  5. 	ListNode* plist = ListCreate();
  6. 	ListPushBack(plist, 1);
  7. 	ListPushBack(plist, 2);
  8. 	ListPushBack(plist, 3);
  9. 	ListPushBack(plist, 4);
  10. 	ListPrint(plist);
  11.  
  12. 	ListPushFront(plist, 5);
  13. 	ListPushFront(plist, 6);
  14. 	ListPushFront(plist, 7);
  15. 	ListPushFront(plist, 8);
  16. 	ListPrint(plist);
  17.  
  18. 	ListPopBack(plist);
  19. 	ListPopBack(plist);
  20. 	ListPopBack(plist);
  21. 	ListPrint(plist);
  22.  
  23. 	ListPopFront(plist);
  24. 	ListPopFront(plist);
  25. 	ListPopFront(plist);
  26. 	ListPrint(plist);
  27.  
  28. }
  29.  
  30. int main()
  31. {
  32. 	TestList();
  33.  
  34. 	return 0;
  35. }

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

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

  

闽ICP备14008679号