当前位置:   article > 正文

【数据结构】(C语言):链表

【数据结构】(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. LinkNode *node = createNode(data);
  10. LinkNode *cur = header; // 从头遍历元素,找到最后
  11. while(cur->next != NULL)
  12. {
  13. cur = cur->next;
  14. }
  15. cur->next = node;
  16. length++;
  17. }
  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. LinkNode *node = createNode(data);
  15. LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,找到指定位置
  16. while(location > 0)
  17. {
  18. prev = cur;
  19. cur = cur->next;
  20. location--;
  21. }
  22. node->next = cur;
  23. prev->next = node;
  24. length++;
  25. }

删除节点:

  1. // 删除节点(删除链表头部节点)
  2. void deltop(void)
  3. {
  4. if(length == 0) return ; // 空链表,直接退出程序
  5. header = header->next;
  6. length--; // 每删除一个元素,length-1
  7. }
  1. // 删除节点(删除链表尾部节点)
  2. void pop(void)
  3. {
  4. if(length == 0) return ; // 空链表,直接退出程序
  5. if(length == 1) // 一个元素,头指针直接指向NULL
  6. {
  7. header = NULL;
  8. return ;
  9. }
  10. LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,直到最后的位置
  11. while(cur->next != NULL)
  12. {
  13. prev = cur;
  14. cur = cur->next;
  15. }
  16. prev->next = NULL;
  17. length--;
  18. }
  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. LinkNode *prev, *cur = header; // 使用两个指针,遍历链表,直到指定位置
  11. while(location > 0)
  12. {
  13. prev = cur;
  14. cur = cur->next;
  15. location--;
  16. }
  17. prev->next = cur->next;
  18. length--;
  19. }
  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. length--;
  18. return ;
  19. }
  20. prev = cur;
  21. cur = cur->next;
  22. }
  23. return ;
  24. }

遍历节点:

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


完整代码:(linklist.c)

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

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

执行可执行文件: ./linklist

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

闽ICP备14008679号