剑指offer之C语言实现链表(两种方式)

举报
chenyu 发表于 2021/07/27 01:31:23 2021/07/27
【摘要】 1 问题 用C语言实现链表       2 代码实现 #include <stdio.h>#include <stdlib.h> #define true 0#define false -1 typedef struct Node{ int value; struct Node *next;} List; /*...

1 问题

用C语言实现链表

 

 

 

2 代码实现


  
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define true 0
  4. #define false -1
  5. typedef struct Node
  6. {
  7. int value;
  8. struct Node *next;
  9. } List;
  10. /**
  11. *初始化链表
  12. */
  13. struct Node* init_list()
  14. {
  15. struct Node *head = (struct Node*)malloc(sizeof(struct Node));
  16. if (head)
  17. {
  18. head->next = NULL;
  19. return head;
  20. }
  21. return NULL;
  22. }
  23. /*
  24. *创建节点
  25. */
  26. struct Node* create_node(int value)
  27. {
  28. struct Node *node = (struct Node*)malloc(sizeof(struct Node));
  29. if (node)
  30. {
  31. node->value = value;
  32. return node;
  33. }
  34. return NULL;
  35. }
  36. /*
  37. *第一种方法插入节点
  38. */
  39. int insert_list(struct Node **head, List* node)
  40. {
  41. if (*head == NULL || node == NULL)
  42. {
  43. printf("head or node is NULL");
  44. return false;
  45. }
  46. node->next = *head;
  47. *head = node;
  48. return true;
  49. }
  50. /*
  51. *第二种方法插入节点
  52. */
  53. int insert_list1(struct Node *head, List* node)
  54. {
  55. if (head == NULL || node == NULL)
  56. {
  57. printf("head or node is NULL");
  58. return false;
  59. }
  60. node->next = head->next;
  61. head->next = node;
  62. return true;
  63. }
  64. /*
  65. *第一种方法打印
  66. */
  67. void print_list(List *head)
  68. {
  69. if (head == NULL)
  70. {
  71. printf("head is NULL\n");
  72. return;
  73. }
  74. while (head->next != NULL)
  75. {
  76. printf("value is %d\n", head->value);
  77. head = head->next;
  78. }
  79. }
  80. /*
  81. *第二种方法打印
  82. */
  83. void print_list1(List *head)
  84. {
  85. if (head == NULL)
  86. {
  87. printf("head is NULL\n");
  88. return;
  89. }
  90. struct Node *p = head->next;
  91. while (p != NULL)
  92. {
  93. printf("value is %d\n", p->value);
  94. p = p->next;
  95. }
  96. }
  97. /*
  98. *更具这个值能否能到节点
  99. */
  100. struct Node* get_node(List *head, int value)
  101. {
  102. if (head == NULL)
  103. return NULL;
  104. struct Node *p = head;
  105. while (p != NULL)
  106. {
  107. if (p->value == value)
  108. {
  109. return p;
  110. }
  111. p = p->next;
  112. }
  113. return NULL;
  114. }
  115. /*
  116. *第一种方法删除节点
  117. */
  118. int delete_node(struct Node **head, struct Node *node)
  119. {
  120. if (*head == NULL)
  121. return false;
  122. if ((*head) == node)
  123. {
  124. *head = (*head)->next;
  125. return true;
  126. }
  127. struct Node *p = *head;
  128. while ((*head)->next != NULL)
  129. {
  130. if ((*head)->next == node)
  131. {
  132. (*head)->next =(*head)->next->next;
  133. *head = p;
  134. return true;
  135. }
  136. *head = (*head)->next;
  137. }
  138. *head = p;
  139. return false;
  140. }
  141. /*
  142. *第二种方法删除节点
  143. */
  144. int delete_node1(struct Node *head, struct Node *node)
  145. {
  146. if (head == NULL)
  147. return false;
  148. while (head->next != NULL)
  149. {
  150. if (head->next == node)
  151. {
  152. head->next = head->next->next;
  153. return true;
  154. }
  155. head = head->next;
  156. }
  157. return false;
  158. }
  159. /*
  160. *释放链表
  161. */
  162. int free_list(List *head)
  163. {
  164. if (head == NULL)
  165. return false;
  166. struct Node *p = NULL;
  167. while(head != NULL)
  168. {
  169. p = head;
  170. head = head->next;
  171. free(p);
  172. }
  173. return true;
  174. }
  175. int main()
  176. {
  177. struct Node* head = NULL;
  178. struct Node* node1 = NULL, *node2 = NULL, *node3 = NULL;
  179. struct Node* node4 = NULL, *node5 = NULL, *node6 = NULL;
  180. head = init_list();
  181. if (!head)
  182. {
  183. printf("init head fail\n");
  184. }
  185. node1 = create_node(5);
  186. node2 = create_node(4);
  187. node3 = create_node(3);
  188. node4 = create_node(2);
  189. node5 = create_node(1);
  190. node6 = create_node(3);
  191. insert_list1(head, node1);
  192. insert_list1(head, node2);
  193. insert_list1(head, node3);
  194. insert_list1(head, node4);
  195. insert_list1(head, node5);
  196. insert_list1(head, node6);
  197. print_list1(head);
  198. printf("first print_list---------------\n");
  199. delete_node1(head, node1);
  200. print_list1(head);
  201. printf("second print_list--------------\n");
  202. free_list(head);
  203. head = NULL;
  204. head = init_list();
  205. if (!head)
  206. {
  207. printf("init head fail\n");
  208. }
  209. node1 = create_node(5);
  210. node2 = create_node(4);
  211. node3 = create_node(3);
  212. node4 = create_node(2);
  213. node5 = create_node(1);
  214. node6 = create_node(3);
  215. insert_list(&head, node1);
  216. insert_list(&head, node2);
  217. insert_list(&head, node3);
  218. insert_list(&head, node4);
  219. insert_list(&head, node5);
  220. insert_list(&head, node6);
  221. print_list(head);
  222. printf("third print_list---------------\n");
  223. delete_node(&head, node4);
  224. print_list(head);
  225. printf("four print_list---------------\n");
  226. struct Node *result = get_node(head, 4);
  227. if (result)
  228. {
  229. printf("list contain node and the value of node is %d\n", result->value);
  230. }
  231. else
  232. {
  233. printf("list do not contain the node\n");
  234. }
  235. free_list(head);
  236. head = NULL;
  237. return 0;
  238. }

 

 

 

3 运行结果


  
  1. value is 3
  2. value is 1
  3. value is 2
  4. value is 3
  5. value is 4
  6. value is 5
  7. first print_list---------------
  8. value is 3
  9. value is 1
  10. value is 2
  11. value is 3
  12. value is 4
  13. second print_list--------------
  14. value is 3
  15. value is 1
  16. value is 2
  17. value is 3
  18. value is 4
  19. value is 5
  20. third print_list---------------
  21. value is 3
  22. value is 1
  23. value is 3
  24. value is 4
  25. value is 5
  26. four print_list---------------
  27. list contain node and the value of node is 4

 

 

4 总结

很明显第二种方式更换简单好理解,在函数里面如果我们传递指针进去,然后想修改这个指针的话,我们直接给这个指针赋值来改变这个指针是不可以的,因为是停时变量,我们直接可以返回新malloc的指针或者函数传递二级指针作为参数,在函数里面修改这个指针,同时我们把头结点传递函数里面去,我们直接操作head->next = head->next->next;这些都会有效.

用C语言实现的话,我们喜欢搞个头结点,然后每个函数里面传入头结点,我们函数里面改变的是head->next的值,但是我们就算移动了head节点,比如head = head->next; 但是实际上没有影响,因为是零时变量,最后的head的位置还是没有动

文章来源: chenyu.blog.csdn.net,作者:chen.yu,版权归原作者所有,如需转载,请联系作者。

原文链接:chenyu.blog.csdn.net/article/details/86515602

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。