• 数据结构之循环链表（C语言）

    循环链表概念：

           循环链表是一种特殊的链表结构。它与普通链表不同的地方在于，最后一个节点指向第一个节点，形成了一个环。这也就意味着，在循环链表中，每个节点都有前驱节点和后继节点。循环链表既可以向前遍历，也可以向后遍历。循环链表的应用场景主要是在需要循环处理数据的场合，例如游戏中的玩家列表、环形缓存等。

    循环单链表的操作

    基本代码：

    1. struct Node {
    2. 	int data;
    3. 	struct Node* next;
    4. };
    5.  
    6. struct Node* head = NULL;//头指针
    7.  
    8. int count = 0; //统计节点数量
    9.  
    10. struct Node* new(int x) //新节点的建立
    11. {
    12. 	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    13.     temp->data = x;
    14. 	temp->next = NULL;
    15. 	return temp;
    16. }


    1、循环单链表的建立

    头插法

    1. void headList(int x)
    2. {
    3. 	struct Node* temp = new(x);
    4. 	struct Node* header = head; //用header来代替头指针来遍历
    5. 	if (head == NULL) //链表为空
    6. 	{
    7. 		head = temp;
    8. 		temp->next = head;
    9. 		count++;
    10. 		return;
    11. 	}
    12. 	temp->next = head; //新节点指向head
    13. 	while (header->next != temp->next) //header移动到最后的节点
    14. 		header = header->next;
    15. 	header->next = temp; //header指向开头
    16. 	head = temp; //头指针更新
    17. 	count++;
    18. }

    尾插法

    1. void lastList(int x)
    2. {
    3. 	struct Node* temp = new(x);
    4. 	struct Node* header = head;
    5. 	if (head == NULL)
    6. 	{
    7. 		head = temp;
    8. 		temp->next = head;
    9. 		count++;
    10. 		return;
    11. 	}
    12. 	while (header->next != head) //header移动到尾节点
    13. 		header = header->next;
    14. 	temp->next = header->next; //新节点指向头指针
    15. 	header->next = temp; //header指向新节点
    16. 	count++;
    17. }

    2、链表的按位插入

    插入时应注意插入位置为开头或结尾，应进行特殊处理。

    1. void Insert(int x, int data)
    2. {
    3. 	struct Node* temp = new(data);
    4. 	struct Node* header = head;
    5. 	if (x == 1) //插入位置为1
    6. 	{
    7. 		temp->next = head;
    8. 		while (header->next != temp->next) //header移动到最后节点
    9. 			header = header->next;
    10. 		header->next = temp; //header指向新节点
    11. 		head = temp; //head更新
    12. 		count++;
    13. 		return;
    14. 	}
    15. 	if (x == count) //插入位置为count
    16. 	{
    17. 		while(header->next != head) //移动到最后节点
    18. 			header = header->next;
    19. 		temp->next = header->next; //新节点指向开头
    20. 		header->next = temp; //header指向新节点
    21. 		count++; 
    22. 		return; 
    23. 	}
    24. 	if (x<1 || x>count) //判断插入位置是否非法
    25. 	{
    26. 		printf("error!");
    27. 		return;
    28. 	}
    29. 	for (int i = 1; i < x-1; i++) //header移动到插入位置前节点
    30. 		header = header->next;
    31. 	temp->next = header->next; //新节点指向header指向的节点
    32. 	header->next = temp; //header指向新节点
    33. 	count++;
    34. }

    3、按位删除

    注意删除节点位置为1时，应特殊处理；

    1. void delete(int x)
    2. {
    3. 	struct Node* header = head;
    4. 	if (x<1 || x>count) //判断删除位置是否合法
    5. 	{
    6. 		printf("error!\n");
    7. 		return;
    8. 	}
    9. 	if (head == NULL) //链表为空
    10. 	{
    11. 		printf("empty!\n");
    12. 		return;
    13. 	}
    14. 	if (x == 1) //删除节点位置为开头
    15. 	{
    16. 		while (header->next != head) //header移动到最后节点
    17. 			header = header->next;
    18. 		struct Node* A = head; //保存head节点
    19. 		head = head->next; //head移动
    20. 		printf("delete a number is %d\n", A->data); //打印
    21. 		header->next = head; //将header指向新的head
    22. 		free(A); //释放内存
    23. 		count--; //数量-1
    24. 		return;
    25. 	}
    26. 	for (int i = 1; i < x - 1; i++) //header移动到删除位置前节点
    27. 		header = header->next;
    28. 	struct Node* A = header->next; //保存删除节点地址
    29. 	header->next = A->next; // header指向删除节点的后节点
    30. 	printf("delete a number is %d\n", A->data);
    31. 	free(A);
    32. 	count--;
    33. }

    完整代码：
     

    1. struct Node {
    2. 	int data;
    3. 	struct Node* next;
    4. };
    5.  
    6. struct Node* head = NULL;//头指针
    7.  
    8. int count = 0; //统计节点数量
    9.  
    10. struct Node* new(int x) //新节点的建立
    11. {
    12. 	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    13.     temp->data = x;
    14. 	temp->next = NULL;
    15. 	return temp;
    16. }
    17. //头插法
    18. void headList(int x)
    19. {
    20. 	struct Node* temp = new(x);
    21. 	struct Node* header = head; //用header来代替头指针来遍历
    22. 	if (head == NULL)
    23. 	{
    24. 		head = temp;
    25. 		temp->next = head;
    26. 		count++;
    27. 		return;
    28. 	}
    29. 	temp->next = head; //新节点指向head
    30. 	while (header->next != temp->next) //header移动到最后的节点
    31. 		header = header->next;
    32. 	header->next = temp; //header指向开头
    33. 	head = temp; //头指针更新
    34. 	count++;
    35. }
    36. //尾插法
    37. void lastList(int x)
    38. {
    39. 	struct Node* temp = new(x);
    40. 	struct Node* header = head;
    41. 	if (head == NULL)
    42. 	{
    43. 		head = temp;
    44. 		temp->next = head;
    45. 		count++;
    46. 		return;
    47. 	}
    48. 	while (header->next != head) //header移动到尾节点
    49. 		header = header->next;
    50. 	temp->next = header->next; //新节点指向头指针
    51. 	header->next = temp; //header指向新节点
    52. 	count++;
    53. } 
    54.  
    55. //按位插入
    56. void Insert(int x, int data)
    57. {
    58. 	struct Node* temp = new(data);
    59. 	struct Node* header = head;
    60. 	if (x == 1) //插入位置为1
    61. 	{
    62. 		temp->next = head;
    63. 		while (header->next != temp->next) //header移动到最后节点
    64. 			header = header->next;
    65. 		header->next = temp; //header指向新节点
    66. 		head = temp; //head更新
    67. 		count++;
    68. 		return;
    69. 	}
    70. 	if (x == count) //插入位置为count
    71. 	{
    72. 		while(header->next != head) //移动到最后节点
    73. 			header = header->next;
    74. 		temp->next = header->next; //新节点指向开头
    75. 		header->next = temp; //header指向新节点
    76. 		count++; 
    77. 		return; 
    78. 	}
    79. 	if (x<1 || x>count) //判断插入位置是否非法
    80. 	{
    81. 		printf("error!");
    82. 		return;
    83. 	}
    84. 	for (int i = 1; i < x-1; i++) //header移动到插入位置前节点
    85. 		header = header->next;
    86. 	temp->next = header->next; //新节点指向header指向的节点
    87. 	header->next = temp; //header指向新节点
    88. 	count++;
    89. }
    90. //删除
    91. void delete(int x)
    92. {
    93. 	struct Node* header = head;
    94. 	if (x<1 || x>count) //判断删除位置是否合法
    95. 	{
    96. 		printf("error!\n");
    97. 		return;
    98. 	}
    99. 	if (head == NULL) //链表为空
    100. 	{
    101. 		printf("empty!\n");
    102. 		return;
    103. 	}
    104. 	if (x == 1) //删除节点位置为开头
    105. 	{
    106. 		while (header->next != head) //header移动到最后节点
    107. 			header = header->next;
    108. 		struct Node* A = head; //保存head节点
    109. 		head = head->next; //head移动
    110. 		printf("delete a number is %d\n", A->data); //打印
    111. 		header->next = head; //将header指向新的head
    112. 		free(A); //释放内存
    113. 		count--; //数量-1
    114. 		return;
    115. 	}
    116. 	for (int i = 1; i < x - 1; i++) //header移动到删除位置前节点
    117. 		header = header->next;
    118. 	struct Node* A = header->next; //保存删除节点地址
    119. 	header->next = A->next; // header指向删除节点的后节点
    120. 	printf("delete a number is %d\n", A->data);
    121. 	free(A);
    122. 	count--;
    123. }
    124.  
    125.  
    126. void Print()
    127. {
    128. 	struct Node* header = head;
    129. 	for (int i = 0; i < 5; i++)
    130. 	{
    131. 		printf("%d ", header->data);
    132. 		header = header->next;
    133. 	}
    134. 	printf("\n");
    135. }
    136.  
    137. int main()
    138. {
    139. 	lastList(3);
    140. 	lastList(5);
    141. 	lastList(2);
    142. 	lastList(4);
    143. 	Insert(1,8);
    144. 	Print();
    145. 	delete(1);
    146. 	Print();
    147. 	return 0;
    148. }

    循环双链表的操作

    基本代码：

    1. struct Node {
    2. 	int data;
    3. 	struct Node* left;
    4. 	struct Node* right;
    5. };
    6.  
    7. struct Node* head = NULL;
    8.  
    9. int count = 0;
    10.  
    11. struct Node* new(int x)
    12. {
    13. 	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    14.     temp->data = x;
    15. 	temp->left = NULL;
    16. 	temp->right = NULL;
    17. 	return temp;
    18. }

    1、循环双链表的建立

    头插法

    1. void headList(int x)
    2. {
    3. 	struct Node* temp = new(x);
    4. 	struct Node* header = head;
    5. 	if (head == NULL) //链表为空
    6. 	{
    7. 		head = temp;
    8. 		temp->right = head; //指向新节点
    9. 		temp->left = head; //指向新节点
    10. 		count++;
    11. 		return;
    12. 	}
    13. 	while (header->right != head) //header指向最后节点
    14. 		header = header->right;
    15. 	temp->right = head; //新节点右指针指向head
    16. 	head->left = temp; //head指向节点的左节点指向新节点
    17. 	temp->left = header; //新节点左指针指向header
    18. 	header->right = temp; //header右指针指向新节点
    19. 	head = temp; //头指针更新
    20. 	count++;
    21. }

    尾插法

    1. void lastList(int x)
    2. {
    3. 	struct Node* header = head;
    4. 	struct Node* temp = new(x);
    5. 	if (head == NULL)
    6. 	{
    7. 		head = temp;
    8. 		temp->right = head;
    9. 		temp->left = temp;
    10. 		count++;
    11. 		return;
    12. 	}
    13. 	while (header->right != head) //header指向尾节点
    14. 		header = header->right;
    15. 	temp->right = header->right; //新节点右指针指向head
    16. 	head->left = temp; //head的左指针指向新节点
    17. 	header->right = temp; //header的右指针指向新节点
    18. 	temp->left = header; //新节点的左指针指向header
    19. 	count++;
    20. }

    2、按位插入

    应对插入位置为1的情况进行特殊处理；

    1.  
    2. void Insert(int x, int data)
    3. {
    4. 	struct Node* header = head;
    5. 	struct Node* temp = new(data);
    6. 	if (head == NULL) 
    7. 	{
    8. 		printf("error!/n");
    9. 		return;
    10. 	}
    11. 	if (x<1 || x>count)
    12. 	{
    13. 		printf("error!\n");
    14. 		return;
    15. 	}
    16. 	if (x == 1) //插入位置为开头
    17. 	{
    18. 		while (header->right != head) //移动到尾节点
    19. 			header = header->right;
    20. 		temp->right = head; //新节点的右指针指向头节点
    21. 		header->right = temp; //header的右指针指向新节点
    22. 		temp->left = header; //新节点的左指针指向尾节点
    23. 		head->left = temp; //头节点的左指针指向新节点
    24. 		head = temp; //头指针的更新
    25. 		count++;
    26. 		return;
    27. 	}
    28. 	for (int i = 1; i <= x - 1; i++)
    29. 		header = header->right;
    30. 	temp->right = header->right;
    31. 	header->right->left = temp;
    32. 	header->right = temp;
    33. 	temp->left = header;
    34. 	count++;
    35. }

    3、按位删除

    对删除位置为开头和删除位置为结尾的情况进行特殊处理；

    1. void delete(int x)
    2. {
    3. 	struct Node* header = head;
    4. 	if (x<1 || x>count)
    5. 	{
    6. 		printf("error!\n");
    7. 		return;
    8. 	}
    9. 	if (x == 1) 
    10. 	{
    11. 		struct Node* A = head;
    12. 		head = head->right;
    13. 		head->left = A->left;
    14. 		A->left->right = head;
    15. 		free(A);
    16. 		count--;
    17. 		return;
    18. 	}
    19. 	if (x == count)
    20. 	{
    21. 		struct Node* A = head->left;
    22. 		header = A->left;
    23. 		header->right = head;
    24. 		head->left = header;
    25. 		free(A);
    26. 		count--;
    27. 		return;
    28. 	}
    29. 	for (int i = 1; i < x - 1; i++)
    30. 		header = header->right;
    31. 	struct Node* A = header->right;
    32. 	header->right = A->right;
    33. 	A->right->left = header;
    34. 	free(A);
    35. 	count--;
    36. }

    4、遍历（打印）

    1. void Print()
    2. {
    3. 	int falg = 0;
    4. 	struct Node* header = head;
    5. 	while (header != head || falg == 0)
    6. 	{
    7. 		printf("%d ", header->data);
    8. 		if (header->right == head)
    9. 		{
    10. 			falg = 1;
    11. 			break;
    12. 		}
    13. 		header = header->right;
    14. 	}
    15. 	printf("\n");
    16. 	struct Node* last = header;
    17. 	while (header != last|| falg == 1)
    18. 	{
    19. 		printf("%d ", header->data);
    20. 		if (header->left == last)
    21. 		{
    22. 			falg = 0;
    23. 			break;
    24. 		}
    25. 		header = header->left;
    26. 	}
    27. 	printf("\n");
    28. }

    完整代码：

    1. struct Node {
    2. 	int data;
    3. 	struct Node* left;
    4. 	struct Node* right;
    5. };
    6.  
    7. struct Node* head = NULL;
    8.  
    9. int count = 0;
    10.  
    11. struct Node* new(int x)
    12. {
    13. 	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    14.     temp->data = x;
    15. 	temp->left = NULL;
    16. 	temp->right = NULL;
    17. 	return temp;
    18. }
    19.  
    20. //头插法
    21. void headList(int x)
    22. {
    23. 	struct Node* temp = new(x);
    24. 	struct Node* header = head;
    25. 	if (head == NULL) //链表为空
    26. 	{
    27. 		head = temp;
    28. 		temp->right = head; //指向新节点
    29. 		temp->left = head; //指向新节点
    30. 		count++;
    31. 		return;
    32. 	}
    33. 	while (header->right != head) //header指向最后节点
    34. 		header = header->right;
    35. 	temp->right = head; //新节点右指针指向head
    36. 	head->left = temp; //head指向节点的左节点指向新节点
    37. 	temp->left = header; //新节点左指针指向header
    38. 	header->right = temp; //header右指针指向新节点
    39. 	head = temp; //头指针更新
    40. 	count++;
    41. }
    42.  
    43. //尾插法
    44. void lastList(int x)
    45. {
    46. 	struct Node* header = head;
    47. 	struct Node* temp = new(x);
    48. 	if (head == NULL)
    49. 	{
    50. 		head = temp;
    51. 		temp->right = head;
    52. 		temp->left = temp;
    53. 		count++;
    54. 		return;
    55. 	}
    56. 	while (header->right != head) //header指向尾节点
    57. 		header = header->right;
    58. 	temp->right = header->right; //新节点右指针指向head
    59. 	head->left = temp; //head的左指针指向新节点
    60. 	header->right = temp; //header的右指针指向新节点
    61. 	temp->left = header; //新节点的左指针指向header
    62. 	count++;
    63. }
    64.  
    65. //按位插入
    66. void Insert(int x, int data)
    67. {
    68. 	struct Node* header = head;
    69. 	struct Node* temp = new(data);
    70. 	if (head == NULL) 
    71. 	{
    72. 		printf("error!/n");
    73. 		return;
    74. 	}
    75. 	if (x<1 || x>count)
    76. 	{
    77. 		printf("error!\n");
    78. 		return;
    79. 	}
    80. 	if (x == 1) //插入位置为开头
    81. 	{
    82. 		while (header->right != head) //移动到尾节点
    83. 			header = header->right;
    84. 		temp->right = head; //新节点的右指针指向头节点
    85. 		header->right = temp; //header的右指针指向新节点
    86. 		temp->left = header; //新节点的左指针指向尾节点
    87. 		head->left = temp; //头节点的左指针指向新节点
    88. 		head = temp; //头指针的更新
    89. 		count++;
    90. 		return;
    91. 	}
    92. 	for (int i = 1; i <= x - 1; i++)
    93. 		header = header->right;
    94. 	temp->right = header->right;
    95. 	header->right->left = temp;
    96. 	header->right = temp;
    97. 	temp->left = header;
    98. 	count++;
    99. }
    100. //删除
    101. void delete(int x)
    102. {
    103. 	struct Node* header = head;
    104. 	if (x<1 || x>count)
    105. 	{
    106. 		printf("error!\n");
    107. 		return;
    108. 	}
    109. 	if (x == 1) 
    110. 	{
    111. 		struct Node* A = head;
    112. 		head = head->right;
    113. 		head->left = A->left;
    114. 		A->left->right = head;
    115. 		free(A);
    116. 		count--;
    117. 		return;
    118. 	}
    119. 	if (x == count)
    120. 	{
    121. 		struct Node* A = head->left;
    122. 		header = A->left;
    123. 		header->right = head;
    124. 		head->left = header;
    125. 		free(A);
    126. 		count--;
    127. 		return;
    128. 	}
    129. 	for (int i = 1; i < x - 1; i++)
    130. 		header = header->right;
    131. 	struct Node* A = header->right;
    132. 	header->right = A->right;
    133. 	A->right->left = header;
    134. 	free(A);
    135. 	count--;
    136. }
    137. //打印
    138. void Print()
    139. {
    140. 	int falg = 0;
    141. 	struct Node* header = head;
    142. 	while (header != head || falg == 0)
    143. 	{
    144. 		printf("%d ", header->data);
    145. 		if (header->right == head)
    146. 		{
    147. 			falg = 1;
    148. 			break;
    149. 		}
    150. 		header = header->right;
    151. 	}
    152. 	printf("\n");
    153. 	struct Node* last = header;
    154. 	while (header != last|| falg == 1)
    155. 	{
    156. 		printf("%d ", header->data);
    157. 		if (header->left == last)
    158. 		{
    159. 			falg = 0;
    160. 			break;
    161. 		}
    162. 		header = header->left;
    163. 	}
    164. 	printf("\n");
    165. }
    166. int main()
    167. {
    168. 	lastList(3);
    169. 	lastList(5);
    170. 	lastList(8);
    171. 	lastList(9);
    172. 	lastList(4);
    173. 	Print();
    174. 	Insert(1, 88);
    175. 	Insert(6, 99);
    176. 	Print();
    177. 	delete(5);
    178. 	Print();
    179. 	return 0;
    180. }

    链表章节完结！

  • 相关阅读:
    webpack优化系列三：vue子目录路径更改---publicPath
    人工智能行业源代码防数据防泄密需求分析
    使用群晖实现Videostation电影的大容量存储及分享教程
    什么是智慧型人格？智慧型性格的优缺点和职业规划
    Python程序流程控制结构
    sass安装步骤、概述、基本语法等
    C语言练习之消失的数字（两种解法）
    [SDN]Mininet中的miniedit问题汇总
    23种设计模式之代理模式（动态代理）
    游戏陪玩小程序怎么开发-游戏陪玩小程序功能
  • 原文地址：https://blog.csdn.net/sskdspdl/article/details/132652155