【链表】单向链表的C语言实现

avrbase_lei

代码没有在实际项目上用过。原理大概就是这么回事。代码贴出来，给大家围观。

1. #include "stdio.h"
   
2. 
   
3. struct node {
   
4. struct node *next;
   
5. int value;
   
6. };
   
7. 
   
8. #define NODE_MAX 100
   
9. 
   
10. struct node array[NODE_MAX] = {0};
    
11. struct node *root;
    
12. 
    
13. void delete_node(struct node *node);
    
14. void append_node(struct node *node);
    
15. int print_node(void);
    
16. struct node *alloc_node(void);
    
17. void free_node(struct node *node);
    
18. 
    
19. 
    
20. //删除指定的节点
    
21. void delete_node(struct node *node)
    
22. {
    
23. struct node **rootp = &root;
    
24. //从根节点开始，如果rootp里面的内容非空
    
25. //说明这个节点是有值的，我们就去比较
    
26. while(*rootp)
    
27. {
    
28. //这里比较的是节点的地址值
    
29. //实际运用中可能是其他的比较方式
    
30. //但是只要这里的if条件成立了，就说明节点被找到了
    
31. if (*rootp == node)
    
32. {
    
33. //找到节点后，把欲删除的节点所指向的下一个赋值给当前节点
    
34. //此刻的rootp实际就是当前欲删除的节点在其上一个节点中的next的指针
    
35. *rootp = (*rootp)->next;
    
36. break;
    
37. }
    
38. //当然，如果条件不成里，这里就继续找下一个节点
    
39. rootp = &(*rootp)->next;
    
40. }
    
41. 
    
42. //while循环结束，无论找到与否，我们都释放这个节点所占用的内存。
    
43. free_node(node);
    
44. }
    
45. 
    
46. //添加节点到链表的尾巴上
    
47. void append_node(struct node *node)
    
48. {
    
49. struct node **rootp = &root;
    
50. 
    
51. //很简单，一直找next，知道next所指向的内容为NULL
    
52. while(*rootp) rootp = &(*rootp)->next;
    
53. //然后把目标节点插入到next中
    
54. *rootp = node;
    
55. }
    
56. 
    
57. //打印整个链表，并统计链表节点的个数
    
58. //这个只是方便我们查看节点
    
59. int print_node(void)
    
60. {
    
61. int i = 0;
    
62. struct node *curr = root;
    
63. 
    
64. while(curr)
    
65. {
    
66. printf("%d,",curr->value);
    
67. curr = curr->next;
    
68. i ++;
    
69. }
    
70. 
    
71. printf("\r\n");
    
72. return i;
    
73. }
    
74. 
    
75. //为节点申请一段内存
    
76. //我这里是从一个数组分配一个元素来存储
    
77. //实际运用中一般不是这么做的
    
78. struct node *alloc_node(void)
    
79. {
    
80. int i;
    
81. 
    
82. //查找这个数组，如果哪个元素没有被占用
    
83. //我就取这个元素来为我用
    
84. for (i=0; i<NODE_MAX; i++)
    
85. {
    
86. if (!array[i].value)
    
87. return &array[i];
    
88. }
    
89. 
    
90. return NULL;
    
91. }
    
92. 
    
93. //释放节点占用的内存
    
94. //就是将数组元素的对应标志位清0了
    
95. //这样就表示没被占用了
    
96. void free_node(struct node *node)
    
97. {
    
98. memset(node, 0, sizeof(struct node));
    
99. }
    
100. 
     
101. //测试函数
     
102. void test(void)
     
103. {
     
104. int i, j;
     
105. const int times = 15;
     
106. struct node *node;
     
107. 
     
108. //先插入times个元素
     
109. for (i=0; i<times; i++)
     
110. {
     
111. //如果申请节点失败则停止插入
     
112. if (NULL == (node = alloc_node()))
     
113. break;
     
114. node->value = i +1;
     
115. node->next = NULL;
     
116. append_node(node);
     
117. }
     
118. 
     
119. //插入完毕，打印整个链表
     
120. i = print_node();
     
121. printf("total node is: %d.\r\n", i);
     
122. 
     
123. 
     
124. //随机删除链表中的节点
     
125. for (i=0; i<20; i++)
     
126. {
     
127. j = rand()%times;
     
128. 
     
129. printf("--\r\nwill delete array[%d].value=%d.\r\n", j, array[j].value);
     
130. delete_node(&array[j]);
     
131. 
     
132. //删除一个节点后，再打印一下链表，统计链表中的节点个数
     
133. j = print_node();
     
134. printf("after delete, total node is: %d.\r\n----\r\n", j);
     
135. }
     
136. }
     
137. 
     
138. 
     
139. int main(int argc, char **argv)
     
140. {
     
141. test();
     
142. 
     
143. getchar();
     
144. return 0;
     
145. }
     

复制代码

箫天

谢谢！
如果有注释就更完美了。

avrbase_lei

箫天 发表于 2014-5-6 20:25
谢谢！
如果有注释就更完美了。

这个单向链表太简单了，就没有特地去写注释了。
只要把C里面的指针运用灵活了，理解起来就非常简单了。

root节点是整个链表的根节点，我们取这个根节点的指针rootp。
你添加或者不添加，删除或者不删除，链表就在那里。我们要做的就是改变这个rootp的值，来使它每次都指向不同的节点，而获取当前节点的下一个几点的指针是非常简单的，即 rootp=&node->next 就可以了，至于根节点root，自然是 rootp=&root; 于是问题就开始变的简单了。一个wihle循环，rootp就开始逐个往下查询下去了。一切就是这么简单。

avrbase_lei

箫天 发表于 2014-5-6 20:25
谢谢！
如果有注释就更完美了。

这个单向链表太简单了，就没有特地去写注释了。
只要把C里面的指针运用灵活了，理解起来就非常简单了。

root节点是整个链表的根节点，我们取这个根节点的指针rootp。
你添加或者不添加，删除或者不删除，链表就在那里。我们要做的就是改变这个rootp的值，来使它每次都指向不同的节点，而获取当前节点的下一个几点的指针是非常简单的，即 rootp=&node->next 就可以了，至于根节点root，自然是 rootp=&root; 于是问题就开始变的简单了。一个wihle循环，rootp就开始逐个往下查询下去了。一切就是这么简单。

avrbase_lei

注释已经添加了。

箫天

嗯，有了注释和3楼解释，理解起来就简单多了。