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

《循环链表》详解_数据结构循环链表必须有几个元素

作者：不正经 | 2024-06-06 17:24:38

赞

踩

数据结构循环链表必须有几个元素

循环链表的定义及特点：

定义：

循环链表是一种头尾相接的链表，表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的任意元素都有一个前驱和一个后继，所有数据元素在关系上构成逻辑上的环。在循环链表中，从任意一个节点出发都能访问到链表的其他所有节点。循环链表的节点通常由数据域和指针域组成，数据域存储节点的数据，指针域存储指向下一个节点的指针。与单向链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。


特点：

1、循环链表的最后一个节点的指针指向第一个节点，形成一个闭环。

2、无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。

3、循环链表可以通过任意节点进行遍历，因为每个节点都有下一个节点的指针。

4、循环链表是一个循环的结构，在遍历时可以无限循环下去，不会出现尾部节点的空指针错误。

5、循环链表可以从任意节点开始遍历，因此可以选择一个合适的起始节点来提高操作效率。

循环链表的实现过程：

定义链表：

  1. typedef struct node
  2. {
  3. 	DataType		data;	/*数据域*/
  4. 	struct node		*next;	/*指针域*/
  5. }SingleLinkList, SingleLinkNode;

链表初始化：

  1. int init(SingleLinkList **Head)
  2. {
  3. 	if(1)    /*利用if语句进行内存判断*/
  4. 	{
  5. 		/*申请内存*/
  6. 		(*Head) = (SingleLinkList*)malloc(sizeof(SingleLinkList));
  7. 		/*判断内存申请是否成功*/
  8. 		if(*Head == NULL)
  9. 		{
  10. 			printf("申请内存错误， 初始化失败！[100001]\n");
  11. 			return 100001;
  12. 		}
  13. 		(*Head)->next = *Head;/*指针指向*/
  14. 		/*循环链表*/
  15. 		/*
  16. 			(*Head)->next = *Head;
  17. 		*/
  18. 		return 0;
  19. 	}
  20. 	else
  21. 	{
  22. 		printf("该链表已经初始化！请删除后再执行此操作！[100002]\n");
  23. 		return 100002;
  24. 	}
  25. }

插入元素

头插法：

  1. int insert_head(SingleLinkList **Head, DataType x)
  2. {
  3. 	SingleLinkNode *newNode;
  4.  
  5. 	if(0)/*利用if语句链表初始化判断*/
  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. 	newNode->next = (*Head)->next;
  19.  
  20. 	(*Head)->next = newNode;
  21.  
  22. 	return 0;
  23. }

尾插法：

  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. 	  循环链表
  23. 	  newNode->next = *Head;
  24. 	*/
  25.  
  26. 	p = (*Head);
  27.  
  28. 	while(p->next!=*Head)/*将尾节点循环遍历*/
  29. 	{
  30. 		p = p->next;
  31. 	}
  32.  
  33. 	p->next = newNode;
  34.  
  35. 	return 0;
  36. }

在位置i处插入元素：

  1. int insert(SingleLinkList **Head, int i, DataType x)
  2. {
  3. 	int j;
  4. 	SingleLinkNode *p;
  5. 	SingleLinkNode *newNode;
  6.  
  7. 	
  8. 	/*利用if语句进行判断*/
  9. 	if(i<1 || i>length(*Head)+1)   
  10. 	{
  11. 		printf("位置i不是链表有效位置！[100005]\n");
  12. 		return 100005;
  13. 	}
  14. 	p = (*Head);
  15. 	j = 1;
  16.  
  17. 	while(j<i)
  18. 	{
  19. 		j++;
  20. 		p = p->next;
  21. 	}
  22.  
  23. 	newNode = (SingleLinkNode*)malloc(sizeof(SingleLinkNode));
  24. 	/*此处省略检测newNode是否申请成功*/
  25.  
  26. 	newNode->data = x;
  27. 	newNode->next = p->next;
  28. 	p->next = newNode;
  29. 	return 0;
  30. }

删除元素：

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

查找元素：

  1. int find(SingleLinkList *Head, DataType x)
  2. {
  3. 	int i;
  4. 	SingleLinkNode *p;
  5.  
  6. 	i = 1;
  7. 	p = Head->next;
  8.  
  9. 	while(p!= Head && p->data != x)  /*while( p!= Head && p->data != x) */
  10. 	{
  11. 		i++;
  12. 		p = p->next;
  13. 	}
  14.  
  15. 	if(p==Head)  /* if(p->next == Head) */
  16. 	{
  17. 		return 0;
  18. 	}
  19. 	else
  20. 	{
  21. 		return i;
  22. 	}
  23.  
  24. }

输出链表长度：

  1. int length(SingleLinkList *Head) /*链表长度length*/
  2. {
  3. 	int len=0;      
  4. 	SingleLinkNode *p;
  5.  
  6. 	p = Head->next;
  7. 	while(p!=Head)	/* while循环语句进行链表的遍历 */
  8. 	{
  9. 		len++;
  10. 		p = p->next;
  11. 	}
  12. 	return len;
  13. }

完整的代码演示：

1、main.c 

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

2、SingleLinkList.c 

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

3、SingleLinkList.h

  1. /*
  2. 	SingleLinkList.h
  3. */
  4.  
  5. typedef int DataType;
  6.  
  7. /*简单链表的定义*/
  8. typedef struct node
  9. {
  10. 	DataType		data;	/*数据域*/
  11. 	struct node		*next;	/*指针域*/
  12. }SingleLinkList, SingleLinkNode;
  13.  
  14.  
  15. /*1. 初始化*/
  16. int init(SingleLinkList **Head);
  17.  
  18. /*2. 插入元素,头插法*/
  19. int insert_head(SingleLinkList **Head, DataType x);
  20.  
  21. /*2. 插入元素， 尾插法*/
  22. int insert_tail(SingleLinkList **Head, DataType x);
  23.  
  24. /*2. 插入元素，在位置i处插入元素x */
  25. int insert(SingleLinkList **Head, int i, DataType x);
  26.  
  27. /*3. 删除元素, 删除值为x的元素*/
  28. int delete(SingleLinkList **Head, DataType x);
  29.  
  30. /*5. 查找值为x的元素，返回位置i */
  31. int find(SingleLinkList *Head, DataType x);
  32.  
  33. /*6. 求链表的长度 */
  34. int length(SingleLinkList *Head);
  35.  
  36. /*7.输出链表*/
  37. void print(SingleLinkList *Head);
  38.  
  39.

4、welcome.h 

  1. char welcome[] = "\n\
  2.            /\ \n\
  3.           ( *)======/\==== \n\
  4.            )(      /  \ \n\
  5. __________/  )    /    \ \n\
  6. \___         /   / \"\"   \ \n\
  7.   \____    _/   / (**)   \ \n\
  8.      / \__/    (----------) \n\
  9.     /____|__//_ ( 本程序 ) \n\
  10.          |       ( 由cm) \n\
  11.          |       ( 开发 )\n\
  12.          |        (____)\n\
  13.         _|__\n\
  14.          \\   ☆\n\n";

 

代码运行结果：

小结：

循环链表需要更多的注意，避免出现死循环。循环链表具有很好的灵活性和高效性，可以方便地实现很多操作。总之，循环链表是一种特殊的链表结构，在实际应用中需要根据具体场景和需求进行选择。需要注意的是在使用时需要综合考虑其优点和缺点，并选择合适的数据结构和算法。

参考文献：

1.季老师的代码

2.csnd博客

3.百度百科

4、同学帮助指导

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

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

  

闽ICP备14008679号