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

循环链表详解（C语言）

作者：花生_TL007 | 2024-06-06 17:29:22

赞

踩

循环链表

文章目录

前言

一、循环链表基本概念

二、循环链表特点

三、循环链表运算

 1、创建循环链表

 2、插入头节点

3、插入尾节点

5、在指定位置插入元素

6、删除元素

7、输出链表长度

8、输出循环链表

四、循环链表的优缺点

1、优点

2、缺点

五、完整代码

1、代码实现

2、运行结果

六、总结

前言

本文主要讲述循环链表的基本定义特点以及一些常见操作并使用C语言代码对其进行实现。

一、循环链表基本概念

循环链表（Circular Linked List）是一种链表的变体，它与单向链表相似，但是最后一个节点的指针指向第一个节点，形成了一个环状结构。循环链表可以被看作是一个循环数组的链式表示形式。

在循环链表中，每个节点包含数据域和指针域。指针域中存储的是下一个节点的地址或位置。最后一个节点的指针指向第一个节点，形成一个闭环。在循环链表中，我们可以通过任意一个节点来遍历整个链表。

循环链表可以用来实现循环缓冲区等数据结构。例如，在操作系统中，我们可以用循环链表来实现一个环形缓冲区，用于存储进程的PCB（Process Control Block）信息。当缓冲区满时，新的进程可以覆盖旧的进程的信息，从而实现缓冲区的循环使用。

实现循环链表需要处理一些特殊情况，例如在插入和删除节点时需要更新相应的指针。在遍历循环链表时，我们需要特别注意不要陷入无限循环。

二、循环链表特点

  1. 循环链表中的最后一个结点的指针域指向头结点，整个链表形成一个环。
  2. 从循环链表中任一结点出发，都能访问到表中其他结点。
  3. 循环链表是将表中最后一个结点的指针域指向头结点，并不增加额外存储花销。
  4. 循环链表是单向链表的扩展，它保持了单向链表的所有特性。
  5. 循环链表首尾相接，从任何一个节点出发都能访问到表中其他所有节点。
  6. 循环链表可以用来实现循环缓冲区等数据结构。

三、循环链表运算

 1、创建循环链表

创建一个循环链表需要先定义一个节点结构体，包含数据域和指向下一个节点的指针。然后定义一个头节点，其指向下一个节点的指针指向自身，形成一个环。

代码实现：

  1. /*1. 初始化*/
  2. int init(SingleLinkList **Head)
  3. {
  4. 	if(1)
  5. 	{
  6. 		/*申请内存*/
  7. 		(*Head) = (SingleLinkList*)malloc(sizeof(SingleLinkList));
  8. 		/*判断内存申请是否成功*/
  9. 		if(*Head == NULL)
  10. 		{
  11. 			printf("申请内存错误， 初始化失败！[100001]\n");
  12. 			return 100001;
  13. 		}
  14. 		(*Head)->next = *Head;
  15.  
  16. 		return 0;
  17. 	}
  18. 	else
  19. 	{
  20. 		printf("该链表已经初始化！请删除后再执行此操作！[100002]\n");
  21. 		return 100002;
  22. 	}
  23. }
 2、插入头节点
  1. 创建一个新的节点，将要插入的数据存储在该节点中。
  2. 如果链表为空，则将新节点设置为头节点。
  3. 如果链表不为空，则将新节点的next指向原来的头节点。
  4. 将头节点更新为新节点。

代码实现：

  1. int insert_head(SingleLinkList **Head, DataType x)
  2. {
  3. 	SingleLinkNode *newNode;
  4.  
  5. 	if(0)
  6. 	{
  7. 		printf("链表未初始化！[100003]\n");
  8. 		return 100003;
  9. 	}
  10. 	
  11. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  12. 	if(!newNode)
  13. 	{
  14. 		printf("申请节点内存空间失败！[100004]\n");
  15. 		return 100004;
  16. 	}
  17. 	newNode->data = x;
  18. 	// 改变 newHead.next
  19. 	newNode->next = (*Head)->next;
  20. 	(*Head)->next = newNode;
  21.  
  22. 	return 0;
  23. }
3、插入尾节点
  1. 创建一个新的节点，将要插入的数据存储在该节点中。
  2. 如果链表为空，则将新节点设置为头节点，并将头节点的next指向新节点。
  3. 如果链表不为空，则将新节点的next指向当前最后一个节点（即头节点），并将最后一个节点的next指向新节点。
  4. 将头节点更新为新节点。

代码实现：

  1. int insert_tail(SingleLinkList **Head, DataType x)
  2. {
  3. 	SingleLinkNode *newNode;
  4. 	SingleLinkNode *p;
  5.  
  6. 	if(0)
  7. 	{
  8. 		printf("链表未初始化！[100003]\n");
  9. 		return 100003;
  10. 	}
  11. 	
  12. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  13. 	if(!newNode)
  14. 	{
  15. 		printf("申请节点内存空间失败！[100004]\n");
  16. 		return 100004;
  17. 	}
  18.  
  19. 	newNode->data = x;
  20. 	newNode->next = *Head;
  21.  
  22. 	p = (*Head);
  23.  
  24. 	while(p->next != (*Head))
  25. 	{
  26. 		p = p->next;
  27. 	}
  28.  
  29. 	p->next = newNode;
  30.  
  31. 	return 0;
  32. }
5、在指定位置插入元素
  1. 创建新节点：首先，创建一个新的节点，并将要插入的数据存储在该节点中。
  2. 找到插入位置：根据要插入的位置，找到循环链表中对应的前一个节点。如果插入位置为链表的头部，则直接找到头节点即可。如果插入位置为链表的尾部，则需要遍历整个链表直到找到最后一个节点。
  3. 插入新节点：将新节点的next指向当前位置的下一个节点。然后将前一个节点的next指向新节点。这样，新节点就被插入到了指定位置。

代码实现：

  1. int insert(SingleLinkList **Head, int i, DataType x)
  2. {
  3. 	int j;
  4. 	SingleLinkNode *p;
  5. 	SingleLinkNode *newNode;
  6.  
  7. 	if(i<1 || i>length(*Head)+1)
  8. 	{
  9. 		printf("位置i不是链表有效位置！[100005]\n");
  10. 		return 100005;
  11. 	}
  12. 	p = (*Head);
  13. 	j = 1;
  14.  
  15. 	while(j<i)
  16. 	{
  17. 		j++;
  18. 		p = p->next;
  19. 	}
  20.  
  21. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  22.  
  23. 	newNode->data = x;
  24. 	newNode->next = p->next;
  25. 	p->next = newNode;
  26. 	return 0;
  27. }
6、删除元素
  1. 找到要删除的节点的前一个节点。如果要删除的是头节点，则直接找到头节点即可。如果要删除的是尾节点，则需要遍历整个链表找到倒数第二个节点。
  2. 将要删除的节点的next指向下一个节点的next。如果要删除的是头节点，则直接将头节点的next指向第二个节点。
  3. 释放要删除的节点的内存。

代码实现：

  1. /*3. 删除元素, 删除值为x的元素*/
  2. int delete(SingleLinkList **Head, DataType x)
  3. {
  4. 	int i;
  5. 	int j;
  6.  
  7. 	SingleLinkNode *p;
  8. 	SingleLinkNode *q; /*要删除的元素x*/
  9.  
  10. 	i = find(*Head,x);
  11. 	if(!i)
  12. 	{
  13. 		printf("元素x【%d】不存在！100006\n", x);
  14. 		return 100006;
  15. 	}
  16. 	
  17. 	p = (*Head);
  18. 	j=1;
  19.  
  20. 	while(j<i)
  21. 	{
  22. 		j++;
  23. 		p = p->next;
  24. 	}
  25. 	
  26. 	q = p->next;
  27. 	p->next = q->next;
  28.  
  29. 	free(q); /*释放内存*/
  30.  
  31. 	return 0;
  32. }
7、输出链表长度

要输出循环链表的长度，需要遍历循环链表并计算链表中的节点数。以下是使用C语言输出循环链表长度的示例代码

代码实现：

  1. /*4. 链表长度*/
  2. int length(SingleLinkList *Head)
  3. {
  4. 	int len=0;
  5. 	SingleLinkNode *p;
  6.  
  7. 	p = Head->next;
  8. 	while(p!=Head)
  9. 	{
  10. 		len++;
  11. 		p = p->next;
  12. 	}
  13. 	return len;
  14. }
8、输出循环链表

代码实现：

  1. /*6.输出链表*/
  2. void print(SingleLinkList *Head)
  3. {
  4. 	SingleLinkNode *p;
  5. 	int i=0;
  6.  
  7. 	p = Head->next;
  8. 	if(p==Head)
  9. 	{
  10. 		printf("链表为空！\n");
  11. 		return;
  12. 	}
  13.  
  14. 	while(p!=Head)
  15. 	{
  16. 		printf("Node[%d]. = %d\n", ++i, p->data);
  17. 		p = p->next;
  18. 	}
  19. }

四、循环链表的优缺点

循环链表是一种特殊的链表，它的最后一个节点指向第一个节点，形成了一个循环。以下是循环链表的一些优缺点。

1、优点
  • 动态数据结构：循环链表是一种动态排列，可以通过分配和刷新内存在运行时增长和收缩。
  • 内存利用率：循环链表可以有效地使用内存，因为链表的大小动态增加或减少，不会浪费内存。
  • 易于数据操作：可以有效地处理循环链表的插入和删除，无需移动元素，只需更新下一个指针中存在的地址。
2、缺点
  • 不支持随机访问，缓存命中率相对低。
  • 设计数据结构时较为麻烦。
  • 占用更多的内存空间：空间换时间。
  • 数据结构复杂

总之，循环链表具有一定的优点和缺点，需要根据具体的应用场景和使用需求来选择是否使用循环链表。

五、完整代码

1、代码实现

SingleLinkList.c

  1. /*
  2. 	SingleLinkList.c
  3. 	
  4. */
  5. #include "SingleLinkList.h"
  6. #include <stdlib.h>
  7. #include <stdio.h>
  8.  
  9. /*1. 初始化*/
  10. int init(SingleLinkList **Head)
  11. {
  12. 	if(1)
  13. 	{
  14. 		/*申请内存*/
  15. 		(*Head) = (SingleLinkList*)malloc(sizeof(SingleLinkList));
  16. 		/*判断内存申请是否成功*/
  17. 		if(*Head == NULL)
  18. 		{
  19. 			printf("申请内存错误， 初始化失败！[100001]\n");
  20. 			return 100001;
  21. 		}
  22. 		(*Head)->next = *Head;
  23.  
  24. 		return 0;
  25. 	}
  26. 	else
  27. 	{
  28. 		printf("该链表已经初始化！请删除后再执行此操作！[100002]\n");
  29. 		return 100002;
  30. 	}
  31. }
  32.  
  33.  
  34. /*2. 插入元素,头插法  */
  35. int insert_head(SingleLinkList **Head, DataType x)
  36. {
  37. 	SingleLinkNode *newNode;
  38.  
  39. 	if(0)
  40. 	{
  41. 		printf("链表未初始化！[100003]\n");
  42. 		return 100003;
  43. 	}
  44. 	
  45. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  46. 	if(!newNode)
  47. 	{
  48. 		printf("申请节点内存空间失败！[100004]\n");
  49. 		return 100004;
  50. 	}
  51. 	newNode->data = x;
  52. 	// 改变 newHead.next
  53. 	newNode->next = (*Head)->next;
  54. 	(*Head)->next = newNode;
  55.  
  56. 	return 0;
  57. }
  58.  
  59.  
  60. /*2. 插入元素， 尾插法*/
  61. int insert_tail(SingleLinkList **Head, DataType x)
  62. {
  63. 	SingleLinkNode *newNode;
  64. 	SingleLinkNode *p;
  65.  
  66. 	if(0)
  67. 	{
  68. 		printf("链表未初始化！[100003]\n");
  69. 		return 100003;
  70. 	}
  71. 	
  72. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  73. 	if(!newNode)
  74. 	{
  75. 		printf("申请节点内存空间失败！[100004]\n");
  76. 		return 100004;
  77. 	}
  78.  
  79. 	newNode->data = x;
  80. 	newNode->next = *Head;
  81.  
  82. 	p = (*Head);
  83.  
  84. 	while(p->next != (*Head))
  85. 	{
  86. 		p = p->next;
  87. 	}
  88.  
  89. 	p->next = newNode;
  90.  
  91. 	return 0;
  92. }
  93.  
  94.  
  95. /*2. 插入元素，在位置i处插入元素x */
  96. int insert(SingleLinkList **Head, int i, DataType x)
  97. {
  98. 	int j;
  99. 	SingleLinkNode *p;
  100. 	SingleLinkNode *newNode;
  101.  
  102. 	if(i<1 || i>length(*Head)+1)
  103. 	{
  104. 		printf("位置i不是链表有效位置！[100005]\n");
  105. 		return 100005;
  106. 	}
  107. 	p = (*Head);
  108. 	j = 1;
  109.  
  110. 	while(j<i)
  111. 	{
  112. 		j++;
  113. 		p = p->next;
  114. 	}
  115.  
  116. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  117.  
  118. 	newNode->data = x;
  119. 	newNode->next = p->next;
  120. 	p->next = newNode;
  121. 	return 0;
  122. }
  123.  
  124.  
  125. /*3. 删除元素, 删除值为x的元素*/
  126. int delete(SingleLinkList **Head, DataType x)
  127. {
  128. 	int i;
  129. 	int j;
  130.  
  131. 	SingleLinkNode *p;
  132. 	SingleLinkNode *q; /*要删除的元素x*/
  133.  
  134. 	i = find(*Head,x);
  135. 	if(!i)
  136. 	{
  137. 		printf("元素x【%d】不存在！100006\n", x);
  138. 		return 100006;
  139. 	}
  140. 	
  141. 	p = (*Head);
  142. 	j=1;
  143.  
  144. 	while(j<i)
  145. 	{
  146. 		j++;
  147. 		p = p->next;
  148. 	}
  149. 	
  150. 	q = p->next;
  151. 	p->next = q->next;
  152.  
  153. 	free(q); /*释放内存*/
  154.  
  155. 	return 0;
  156. }
  157.  
  158.  
  159. /*5. 查找值为x的元素，返回位置i */
  160. int find(SingleLinkList *Head, DataType x)
  161. {
  162. 	int i;
  163. 	SingleLinkNode *p;
  164.  
  165. 	i = 1;
  166. 	p = Head->next;
  167.  
  168. 	while( p!= Head && p->data != x)
  169. 	{
  170. 		i++;
  171. 		p = p->next;
  172. 	}
  173.  
  174. 	if(p->next == Head)
  175. 	{
  176. 		return 0;
  177. 	}
  178. 	else
  179. 	{
  180. 		return i;
  181. 	}
  182.  
  183. }
  184.  
  185. /*4. 链表长度*/
  186. int length(SingleLinkList *Head)
  187. {
  188. 	int len=0;
  189. 	SingleLinkNode *p;
  190.  
  191. 	p = Head->next;
  192. 	while(p!=Head)
  193. 	{
  194. 		len++;
  195. 		p = p->next;
  196. 	}
  197. 	return len;
  198. }
  199.  
  200. /*6.输出链表*/
  201. void print(SingleLinkList *Head)
  202. {
  203. 	SingleLinkNode *p;
  204. 	int i=0;
  205.  
  206. 	p = Head->next;
  207. 	if(p==Head)
  208. 	{
  209. 		printf("链表为空！\n");
  210. 		return;
  211. 	}
  212.  
  213. 	while(p!=Head)
  214. 	{
  215. 		printf("Node[%d]. = %d\n", ++i, p->data);
  216. 		p = p->next;
  217. 	}
  218. }

 main.c

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "SingleLinkList.h"
  4. #include "welcome.h"
  5.  
  6.  
  7. int main(int argc, char* argv[])
  8. {
  9. 	SingleLinkList *Head;
  10. 	DataType x;
  11. 	int i,m,n,cmd;
  12.  
  13. 	for(i=0;i<strlen(welcome);i++)
  14. 	{
  15. 		printf("%c",welcome[i]);
  16. 		for(m=0;m<1000;m++)
  17. 			for(n=0;n<1000;n++)
  18. 			{
  19. 				;
  20. 			}
  21. 	}
  22.  
  23. 	printf("-----------简单链表演示程序----------\n");
  24. 	do
  25. 	{
  26. 		printf("1. 初始化链表表\n");
  27. 		printf("2. 插入元素（头插法）\n");
  28. 		printf("3. 插入元素（尾插法）\n");
  29. 		printf("4. 插入元素（在位置i插入）\n");
  30. 		printf("5. 查找元素x\n");
  31. 		printf("6. 求链表长度\n");
  32. 		printf("7. 输出链表\n");
  33. 		printf("8. 删除元素\n");
  34. 		printf("10. 帮助\n"); 
  35. 		printf("0. 退出\n");
  36. 		printf("请输入您要进行的操作（1~6,0退出）：");
  37. 		scanf("%d", &cmd);
  38. 		switch(cmd)
  39. 		{
  40. 		case 1:
  41. 			if(!init(&Head))
  42. 			{
  43. 				printf("链表已初始化！\n");
  44. 			}
  45. 			break;
  46. 		case 2:
  47. 			printf("请输入插入元素x：x=");
  48. 			scanf("%d",&x);
  49. 			if(!insert_head(&Head,x))
  50. 			{
  51. 				printf("元素（%d）已插入\n", x);
  52. 			}
  53. 			break;
  54. 		case 3:
  55. 			printf("请输入插入元素x：x=");
  56. 			scanf("%d",&x);
  57. 			if(!insert_tail(&Head,x))
  58. 			{
  59. 				printf("元素（%d）已插入\n", x);
  60. 			}
  61. 			break;
  62. 		case 4:
  63. 			printf("请输入插入元素位置i和元素x（i，x）：");
  64. 			scanf("%d,%d", &i, &x);
  65. 			if(!insert(&Head, i, x))
  66. 			{
  67. 				printf("已在位置（%d）插入元素（%d）！\n",i, x);
  68. 			}
  69. 			break;
  70. 		case 5:
  71. 			printf("请输入要查找的元素x：");
  72. 			scanf("%d", &x);
  73. 			if(i = find(Head,x))
  74. 			{
  75. 				printf("元素%d存在，在链表位置%d.\n", x, i);
  76. 			}
  77. 			else
  78. 			{
  79. 				printf("在链表中未找到元素x。\n");
  80. 			}
  81. 			break;
  82. 		case 6:
  83. 			printf("链表的长度为：%d\n", length(Head));
  84. 			break;
  85. 		case 7:
  86. 			print(Head);
  87. 			break;
  88. 		case 8:
  89. 			printf("请输入要删除的元素x：");
  90. 			scanf("%d", &x);
  91. 			if(!delete(&Head, x))
  92. 			{
  93. 				printf("元素x【%d】已删除!\n", x);
  94. 			}
  95. 			break;
  96. 		case 10:
  97. 			printf(" 本程序为链表的演示程序，有ZMQ设计开发，程序完成了。。。。功能！。。。\n");
  98. 			break;
  99. 			
  100. 		}
  101. 	}while(cmd != 0);
  102.  
  103. 	return 0;
  104. }
2、运行结果

六、总结

以上就是对循环链表的基本介绍，本文仅仅简单介绍了循环链表的概念、特点、运算以及循环链表的优缺点比较。特别注意当我们在实现循环连表时， 循环单链表没有明显的结束条件，很容易陷入死循环。此时，我们可以设置一个标记点作为循环的标记，当我们知道表长，我们也可以设置一个计数器来结束循环。

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

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

  

闽ICP备14008679号