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

【数据结构】（C语言）：链表

作者：码创造者 | 2024-07-05 11:39:20

赞

踩

【数据结构】（C语言）：链表

链表：

  • 基本单位是节点。节点至少两部分：数据，下一个数据的地址。
  • 头指针head，始终指向链表的第一个节点。若没有节点，则head=NULL。
  • 链表在内存中是非连续的。不能使用索引（下标）查找元素。只能从头遍历。
  • 链表有单链表、循环单链表、双链表、循环双链表。本文以单链表举例。

添加节点：（注意指向顺序，避免数据丢失）

  • 在链表头部添加：先新节点指向第一个节点，再头指针指向新节点。
  • 在链表尾部添加：最后一个节点指向新节点。
  • 在链表指定位置添加：找到指定位置，先新节点指向下一个节点，再上一个节点指向新节点。

 删除节点：

  • 删除链表头部节点：头指针指向第二个节点。
  • 删除链表尾部节点：倒数第二个节点指向NULL。
  • 删除链表指定位置节点：找到指定位置，上一个节点指向该节点的下一个节点。

 C语言代码：

创建节点（结构体数据类型），并创建具体节点实例的函数：

  1. // 节点(结构体数据类型)
  2. typedef struct Node
  3. {
  4.     int data;                 // 数据为整数
  5.     struct Node *next;        // 指针指向下一个节点
  6. } LinkNode;                   // 别名LinkNode
  1. // 创建具体节点实例的函数
  2. LinkNode * createNode(int data)
  3. {
  4. 	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));   // 给节点分配内存空间
  5. 	if(node == NULL)
  6. 	{
  7. 		perror("Memory allocation failed");
  8. 		exit(-1);
  9. 	}
  10. 	node->data = data;
  11. 	node->next = NULL;
  12. 	return node;
  13. }

本文将头指针和链表长度作为全局变量：

  1. LinkNode *header = NULL;		// 头指针，初始化指向NULL
  2. int length = 0;				    // 统计链表元素个数

添加节点：

  1. // 添加节点(链表头部添加)
  2. void addtop(int data)
  3. {
  4. 	LinkNode *node = createNode(data);       // 调用createNode函数,创建具体节点
  5. 	node->next = header;                     // 先新节点指向头指针指向的节点
  6. 	header = node;                           // 再头指针指向新节点
  7. 	length++;                                // 每添加一个数据,length+1
  8. }
  1. // 添加节点(链表尾部添加)
  2. void append(int data)
  3. {
  4. 	if(length == 0)        // 若空链表,在链表头部添加
  5. 	{
  6. 		addtop(data);
  7. 		return ;
  8. 	}
  9.  
  10. 	LinkNode *node = createNode(data);
  11.  
  12. 	LinkNode *cur = header;         // 从头遍历元素，找到最后
  13. 	while(cur->next != NULL)
  14. 	{
  15. 		cur = cur->next;
  16. 	}
  17. 	cur->next = node;
  18. 	length++;
  19. }
  1. // 添加节点(在指定位置,位置从0开始)
  2. void insert(int location, int data)
  3. {
  4. 	if(length == 0)    // 若空链表,在链表头部添加
  5. 	{
  6. 		addtop(data);
  7. 		return ;
  8. 	}
  9. 	if(length <= location)    // 若链表长度<=指定位置,在链表尾部添加
  10. 	{
  11. 		append(data);
  12. 		return ;
  13. 	}
  14.  
  15. 	LinkNode *node = createNode(data);
  16.  
  17. 	LinkNode *prev, *cur = header;      // 使用两个指针,遍历链表,找到指定位置
  18. 	while(location > 0)
  19. 	{	
  20. 		prev = cur;
  21. 		cur = cur->next;
  22. 		location--;
  23. 	}
  24. 	
  25. 	node->next = cur;
  26. 	prev->next = node;
  27. 	length++;
  28. }

删除节点：

  1. // 删除节点（删除链表头部节点）
  2. void deltop(void)
  3. {
  4. 	if(length == 0) return ;   // 空链表,直接退出程序
  5.  
  6. 	header = header->next;
  7. 	length--;                  // 每删除一个元素,length-1
  8. }
  1. // 删除节点（删除链表尾部节点）
  2. void pop(void)
  3. {	
  4. 	if(length == 0) return ;       // 空链表,直接退出程序
  5. 	if(length == 1)                // 一个元素,头指针直接指向NULL
  6. 	{
  7. 		header = NULL;
  8. 		return ;
  9. 	}
  10.  
  11. 	LinkNode *prev, *cur = header;     // 使用两个指针,遍历链表,直到最后的位置
  12. 	while(cur->next != NULL)
  13. 	{
  14. 		prev = cur;
  15. 		cur = cur->next;
  16. 	}
  17. 	prev->next = NULL;
  18. 	length--;
  19. }
  1. // 删除节点（删除链表指定位置的节点,位置从0开始）
  2. void delat(int location)
  3. {
  4. 	if(length == 0) return ;          // 空链表,直接退出程序
  5. 	if(length - 1 <= location)        // 链表长度-1<=指定位置,删除链表尾部节点
  6. 	{
  7. 		pop();
  8. 		return ;
  9. 	}
  10.  
  11. 	LinkNode *prev, *cur = header;     // 使用两个指针,遍历链表,直到指定位置
  12. 	while(location > 0)
  13. 	{
  14. 		prev = cur;
  15. 		cur = cur->next;
  16. 		location--;
  17. 	}
  18. 	prev->next = cur->next;
  19. 	length--;
  20. }
  1. // 删除节点(删除指定数据)
  2. void del(int data)
  3. {
  4. 	LinkNode *prev, *cur = header;      // 使用两个指针,遍历链表,比对数据内容
  5. 	while(cur != NULL)
  6. 	{
  7. 		if(cur->data == data)
  8. 		{
  9. 			if(header == cur)       // 若是第一个节点,头指针直接跳过该节点指向下一个节点
  10. 			{
  11. 				header = cur->next;
  12. 			}
  13. 			else                    // 否则 该节点上一个节点,直接跳过该节点指向下一个节点
  14. 			{
  15. 				prev->next = cur->next;
  16. 			}
  17.  
  18. 			length--;
  19. 			return ;
  20. 		}
  21. 		prev = cur;
  22. 		cur = cur->next;
  23. 	}
  24. 	return ;
  25. }

遍历节点：

  1. void travel(void)
  2. {
  3. 	if(length == 0) return ;       // 空链表,直接退出程序
  4.  
  5. 	printf("linklist elements: ");
  6. 	LinkNode *cur = header;
  7. 	while(cur != NULL)
  8. 	{
  9. 		printf("%d \t", cur->data);
  10. 		cur = cur->next;
  11. 	}
  12. 	printf("\n");
  13. }

完整代码：（linklist.c）

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /* structure */
  5. typedef struct Node			   // node structure
  6. {
  7. 	int data;
  8. 	struct Node *next;
  9. } LinkNode;
  10.  
  11. /* global variables */
  12. LinkNode *header = NULL;		// header pointer
  13. int length = 0;				    // the number of linklist elements
  14.  
  15. /* function prototype */
  16. void addtop(int data);			// add element to the top of the linklist
  17. void append(int data);			// add element to the end of the linklist
  18. void insert(int location, int data);	// add element to the specify location (start with 0)
  19. void travel(void);			// show element one by one
  20. void deltop(void);			// delete element from the top of the linklist
  21. void pop(void);			    // delete element from the end of the linklist
  22. void delat(int location);   // delete element from the specify location (start with 0)
  23. void del(int data);			// delete the specify data
  24.  
  25. /* main function */
  26. int main(void)
  27. {
  28. 	addtop(5);
  29. 	printf("length is %d \n", length);		
  30. 	travel();
  31.  
  32. 	append(9);
  33. 	printf("length is %d \n", length);		
  34. 	travel();
  35.  
  36. 	insert(1,8);
  37. 	printf("length is %d \n", length);		
  38. 	travel();
  39.  
  40. 	addtop(3);
  41. 	printf("length is %d \n", length);		
  42. 	travel();
  43.  
  44. 	deltop();	
  45. 	printf("length is %d \n", length);		
  46. 	travel();
  47.  
  48. 	pop();
  49. 	printf("length is %d \n", length);		
  50. 	travel();
  51.  
  52. 	delat(1);
  53. 	printf("length is %d \n", length);		
  54. 	travel();
  55.  
  56. 	del(7);
  57. 	printf("length is %d \n", length);		
  58. 	travel();
  59.  
  60. 	del(5);
  61. 	printf("length is %d \n", length);		
  62. 	travel();
  63. }
  64.  
  65. /* subfunction */
  66. LinkNode * createNode(int data)		// create a node
  67. {
  68. 	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
  69. 	if(node == NULL)
  70. 	{
  71. 		perror("Memory allocation failed");
  72. 		exit(-1);
  73. 	}
  74. 	node->data = data;
  75. 	node->next = NULL;
  76. 	return node;
  77. }
  78.  
  79. void addtop(int data)			// add element to the top of the linklist
  80. {
  81. 	LinkNode *node = createNode(data);
  82. 	node->next = header;
  83. 	header = node;
  84. 	length++;
  85. }
  86.  
  87. void append(int data)			// add element to the end of the linklist
  88. {
  89. 	if(length == 0)
  90. 	{
  91. 		addtop(data);
  92. 		return ;
  93. 	}
  94.  
  95. 	LinkNode *node = createNode(data);
  96.  
  97. 	LinkNode *cur = header;
  98. 	while(cur->next != NULL)
  99. 	{
  100. 		cur = cur->next;
  101. 	}
  102. 	cur->next = node;
  103. 	length++;
  104. }	
  105.  
  106. void insert(int location, int data)	  // add element to the specify location (start with 0)
  107. {
  108. 	if(length == 0)
  109. 	{
  110. 		addtop(data);
  111. 		return ;
  112. 	}
  113. 	if(length <= location)
  114. 	{
  115. 		append(data);
  116. 		return ;
  117. 	}
  118.  
  119. 	LinkNode *node = createNode(data);
  120.  
  121. 	LinkNode *prev, *cur = header;
  122. 	while(location > 0)
  123. 	{	
  124. 		prev = cur;
  125. 		cur = cur->next;
  126. 		location--;
  127. 	}
  128. 	
  129. 	node->next = cur;
  130. 	prev->next = node;
  131. 	length++;
  132. }
  133.  
  134. void travel(void)			// show element one by one
  135. {
  136. 	if(length == 0) return ;
  137.  
  138. 	printf("linklist elements: ");
  139. 	LinkNode *cur = header;
  140. 	while(cur != NULL)
  141. 	{
  142. 		printf("%d \t", cur->data);
  143. 		cur = cur->next;
  144. 	}
  145. 	printf("\n");
  146. }
  147.  
  148. void deltop(void)				// delete element from the top of the linklist
  149. {
  150. 	if(length == 0) return ;
  151.  
  152. 	header = header->next;
  153. 	length--;
  154. }
  155.  
  156. void pop(void)			// delete element from the end of the linklist
  157. {	
  158. 	if(length == 0) return ;
  159. 	if(length == 1)
  160. 	{
  161. 		header = NULL;
  162. 		return ;
  163. 	}
  164.  
  165. 	LinkNode *prev, *cur = header;
  166. 	while(cur->next != NULL)
  167. 	{
  168. 		prev = cur;
  169. 		cur = cur->next;
  170. 	}
  171. 	prev->next = NULL;
  172. 	length--;
  173. }
  174.  
  175. void delat(int location)		// delete element from the specify location (start with 0)
  176. {
  177. 	if(length == 0) return ;
  178. 	if(length - 1 <= location)
  179. 	{
  180. 		pop();
  181. 		return ;
  182. 	}
  183.  
  184. 	LinkNode *prev, *cur = header;
  185. 	while(location > 0)
  186. 	{
  187. 		prev = cur;
  188. 		cur = cur->next;
  189. 		location--;
  190. 	}
  191. 	prev->next = cur->next;
  192. 	length--;
  193. }
  194.  
  195. void del(int data)			// delete the specify data
  196. {
  197. 	LinkNode *prev, *cur = header;
  198. 	while(cur != NULL)
  199. 	{
  200. 		if(cur->data == data)
  201. 		{
  202. 			if(header == cur)
  203. 			{
  204. 				header = cur->next;
  205. 			}
  206. 			else
  207. 			{
  208. 				prev->next = cur->next;
  209. 			}
  210.  
  211. 			length--;
  212. 			return ;
  213. 		}
  214. 		prev = cur;
  215. 		cur = cur->next;
  216. 	}
  217. 	return ;
  218. }

编译链接： gcc -o linklist linklist.c

执行可执行文件： ./linklist

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

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

  

闽ICP备14008679号