圣龙扬特-AVR电子

标题: [源代码] C语言单向链表 [打印本页]

---

作者: avrbase_lei    时间: 2013-4-12 18:36
标题: [源代码] C语言单向链表


再贴点儿工作用到的代码。单向链表。

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include <stdlib.h>
   
4. #include <assert.h>
   
5. 
   
6. 
   
7. typedef unsigned char snl_u8;
   
8. typedef signed char snl_s8;
   
9. 
   
10. typedef unsigned short int snl_u16;
    
11. typedef signed short int snl_s16;
    
12. 
    
13. typedef unsigned int snl_u32;
    
14. typedef signed int snl_s32;
    
15. 
    
16. typedef char snl_char;
    
17. typedef unsigned short snl_wchar;
    
18. 
    
19. typedef enum {snl_false, snl_true} snl_bool;
    
20. 
    
21. 
    
22. typedef struct single_node_list{
    
23. struct single_node_list *next;
    
24. void *vp;
    
25. }SingleNodeList_t;
    

复制代码

在定义些函数接口，方便调试。

1. #define snl_trace printf
   
2. #define snl_malloc malloc
   
3. #define snl_mfree free
   
4. #define snl_assert assert
   
5. #define snl_memset memset
   
6. #define snl_memcpy memcpy
   
7. #define snl_memcmp memcmp
   

复制代码

接着就是源代码了。

1. /*******************************************************************************
   
2. ** 函数: snl_alloc_new
   
3. ** 功能: 申请一个新的节点内存
   
4. ** 作者: avrbase_lei
   
5. *******/
   
6. static SingleNodeList_t *snl_alloc_new(void)
   
7. {
   
8. SingleNodeList_t *newnode = NULL;
   
9. 
   
10. newnode = (SingleNodeList_t*)snl_malloc(sizeof(SingleNodeList_t));
    
11. snl_assert(NULL != newnode);
    
12. snl_memset((void*)newnode, 0, sizeof(SingleNodeList_t));
    
13. 
    
14. return newnode;
    
15. }
    

复制代码

1. /*******************************************************************************
   
2. ** 函数: snl_insert
   
3. ** 功能: 在链表上插入一个新的节点.
   
4. ** 入参: rootpp 指向根节点的指针.
   
5. ** addvp 需要插入链表的数据地址.
   
6. ** front_insert 是否插入在匹配到的节点的前面.
   
7. ** private_compare 比较函数, 比较成功后依front_insert决定插入位置.
   
8. ** 若直到链表尾都未匹配成功则默认插入链表为尾.
   
9. ** 若private_compare为空则插入链表尾.
   
10. ** 返回: 返回插入结果.
    
11. ** 作者: avrbase_lei
    
12. *******/
    
13. static snl_bool snl_insert(
    
14. SingleNodeList_t **rootpp,
    
15. void *addvp,
    
16. void *compare_vp,
    
17. snl_bool front_insert,
    
18. snl_bool (*private_compare)(void *, void *))
    
19. {
    
20. snl_bool inserted = snl_false;
    
21. snl_bool is_root_pos = snl_true;
    
22. SingleNodeList_t *newnode = NULL;
    
23. SingleNodeList_t *currnode = NULL, *prevnode = NULL;
    
24. 
    
25. do{
    
26. if(NULL == rootpp)
    
27. break;
    
28. 
    
29. newnode = snl_alloc_new();
    
30. if(NULL == newnode)
    
31. break;
    
32. newnode->vp = addvp;
    
33. 
    
34. if(NULL == private_compare || NULL == compare_vp)
    
35. {
    
36. if(NULL == *rootpp)
    
37. {
    
38. *rootpp = newnode;
    
39. }
    
40. else
    
41. {
    
42. currnode = *rootpp;
    
43. while(NULL != currnode->next)
    
44. {
    
45. currnode = currnode->next;
    
46. }
    
47. 
    
48. currnode->next = newnode;
    
49. }
    
50. 
    
51. inserted = snl_true;
    
52. break;
    
53. }
    
54. currnode = *rootpp;
    
55. is_root_pos = snl_true;
    
56. inserted = snl_false;
    
57. while(NULL != currnode && !inserted)
    
58. {
    
59. if(private_compare(currnode->vp, compare_vp))
    
60. {
    
61. //如果是根节点匹配到了, 则根节点要指向下一个节点
    
62. if(is_root_pos)
    
63. {
    
64. if(front_insert)
    
65. {
    
66. newnode->next = *rootpp;
    
67. *rootpp = newnode;
    
68. }
    
69. else
    
70. {
    
71. newnode->next = (*rootpp)->next;
    
72. (*rootpp)->next = newnode;
    
73. }
    
74. }
    
75. else
    
76. {
    
77. if(front_insert)
    
78. {
    
79. newnode->next = currnode;
    
80. prevnode->next = newnode;
    
81. }
    
82. else
    
83. {
    
84. newnode->next = currnode->next;
    
85. currnode->next = newnode;
    
86. }
    
87. }
    
88. 
    
89. inserted = snl_true;
    
90. }
    
91. else
    
92. {
    
93. prevnode = currnode;
    
94. currnode = currnode->next;
    
95. is_root_pos = snl_false;
    
96. }
    
97. }
    
98. 
    
99. if(!inserted)
    
100. {
     
101. prevnode->next = newnode;
     
102. inserted = snl_true;
     
103. }
     
104. 
     
105. }while(0);
     
106. 
     
107. return inserted;
     
108. }
     

复制代码

1. /*******************************************************************************
   
2. ** 函数: snl_delete
   
3. ** 功能: 删除链表上snl_compare匹配到的指定的节点
   
4. ** 如果比较函数为空则执行全部删除功能.
   
5. ** 入参: rootpp 根节点
   
6. ** com_node_data_p 用于参与匹配的数据
   
7. ** traval_del 是否遍历删除链表中的节点. 否则删除离根节点最近的节点
   
8. ** private_compare 数据匹配函数, 其返回值用于决定是否删除
   
9. ** private_delete 数据删除函数, 本参数必须非空, 否则无法删除任何数据
   
10. ** 返回: 返回删除的节点个数
    
11. ** 作者: avrbase_lei
    
12. *******/
    
13. static snl_u32 snl_delete(
    
14. SingleNodeList_t **rootpp,
    
15. void *cmp_node_data_p,
    
16. snl_bool travel_del,
    
17. snl_bool (*private_compare)(void *, void *),
    
18. void (*private_delete)(void *))
    
19. {
    
20. snl_u32 deleted_ct = 0;
    
21. snl_bool is_del_root = snl_true;
    
22. SingleNodeList_t *currnode = NULL, *prevnode = NULL, *delnode = NULL;
    
23. 
    
24. do{
    
25. if(NULL == rootpp)
    
26. break;
    
27. 
    
28. if(NULL == private_delete)
    
29. break;
    
30. 
    
31. if(NULL == private_compare)
    
32. {
    
33. currnode = *rootpp;
    
34. while(NULL != currnode)
    
35. {
    
36. delnode = currnode;
    
37. currnode = currnode->next;
    
38. private_delete(delnode->vp);
    
39. snl_mfree(delnode);
    
40. deleted_ct ++;
    
41. }
    
42. 
    
43. *rootpp = NULL;
    
44. 
    
45. break;
    
46. }
    
47. 
    
48. if(NULL == cmp_node_data_p)
    
49. break;
    
50. 
    
51. currnode = *rootpp;
    
52. is_del_root = snl_true;
    
53. while(NULL != currnode)
    
54. {
    
55. if(private_compare(currnode->vp, cmp_node_data_p))
    
56. {
    
57. //如果是根节点匹配到了, 则根节点要指向下一个节点
    
58. if(is_del_root)
    
59. {
    
60. *rootpp = prevnode = currnode->next;
    
61. }
    
62. else
    
63. {
    
64. prevnode->next = currnode->next;
    
65. is_del_root = snl_false;
    
66. }
    
67. 
    
68. //当前节点指向下一个节点
    
69. delnode = currnode;
    
70. currnode = currnode->next;
    
71. 
    
72. //删除节点
    
73. private_delete(delnode->vp);
    
74. snl_mfree(delnode);
    
75. deleted_ct ++;
    
76. 
    
77. //非遍历删除则中断循环
    
78. if(!travel_del)
    
79. break;
    
80. }
    
81. else
    
82. {
    
83. prevnode = currnode;
    
84. currnode = currnode->next;
    
85. is_del_root = snl_false;
    
86. }
    
87. }
    
88. 
    
89. }while(0);
    
90. 
    
91. return deleted_ct;
    
92. }
    
93. 
    

复制代码

估计排版很恶心。

---

作者: avrbase_lei    时间: 2013-4-12 18:41
还要自己测试下。

1. 
   
2. <P>/*******************************************************************************
   
3. ** 函数: test_print_list
   
4. ** 功能: 测试用的打印链表所有数据信息的函数
   
5. ** 入参: rootpp 根节点指针
   
6. ** 返回:
   
7. ** 作者: avrbase_lei
   
8. *******/
   
9. static void test_print_list(SingleNodeList_t **rootpp)
   
10. {
    
11. SingleNodeList_t *tmpnode = *rootpp;</P>
    
12. <P>    snl_trace("print list:\r\n  value: ");
    
13. while(NULL != tmpnode)
    
14. {
    
15.         snl_trace("%d ", (snl_u32)tmpnode->vp);
    
16.         
    
17.   tmpnode = tmpnode->next;
    
18. }
    
19.     snl_trace("\r\nprint end.\r\n");
    
20. }
    
21. </P>

复制代码

这排版，毫无美观可言。

1. /*******************************************************************************
   
2. ** 函数: test_delete
   
3. ** 功能: 测试用的节点数据删除函数. 函数体可以为空
   
4. ** 入参: nodevp 节点指针所指向的数据地址
   
5. ** 返回:
   
6. ** 作者: avrbase_lei
   
7. *******/
   
8. static void test_delete(void *nodevp)
   
9. {
   
10. /* do nothing. */
    
11. }
    
12. 
    

复制代码

1. /*******************************************************************************
   
2. ** 函数: test_compare
   
3. ** 功能: 测试用的比较函数
   
4. ** 入参: node 节点指针
   
5. ** cpdt 参与匹配的数据
   
6. ** 返回: 返回匹配结果
   
7. ** 作者: avrbase_lei
   
8. *******/
   
9. static snl_bool test_compare(void *nodevp, void *cpdtp)
   
10. {
    
11. if(NULL == cpdtp || NULL == nodevp)
    
12. return snl_false;
    
13. 
    
14. return (snl_bool)((snl_u32)(nodevp) == (snl_u32)cpdtp);
    
15. }
    

复制代码

1. /*******************************************************************************
   
2. ** 函数: test_main
   
3. ** 功能: 测试入口函数
   
4. ** 入参:
   
5. ** 返回:
   
6. ** 作者: avrbase_lei
   
7. *******/
   
8. void test_main(void)
   
9. {
   
10. const snl_u32 test_loop_ct = 5;
    
11. snl_u32 i, total, cmpdat;
    
12. SingleNodeList_t *rootp = NULL;
    
13. 
    
14. //insert
    
15. for(i=0; i<test_loop_ct; i++)
    
16. {
    
17. total = snl_insert(&rootp, (void*)i, NULL, snl_false, NULL);
    
18. }
    
19. 
    
20. //print
    
21. test_print_list(&rootp);
    
22. 
    
23. //delete
    
24. for(i=0; i<test_loop_ct; i++)
    
25. {
    
26. cmpdat = rand()%test_loop_ct;
    
27. snl_trace("%dst delete, to be delete value is %d. \r\n", i, cmpdat);
    
28. cmpdat = snl_delete(&rootp, (void *)cmpdat, snl_false, test_compare, test_delete);
    
29. snl_trace("snl_delete return %d.\r\n", cmpdat);
    
30. 
    
31. test_print_list(&rootp);
    
32. }
    
33. 
    
34. //free all
    
35. snl_delete(&rootp, NULL, snl_true, NULL, test_delete);
    
36. test_print_list(&rootp);
    
37. 
    
38. }
    

复制代码

1. int main(int argc, char **argv)
   
2. {
   
3. test_main();
   
4. 
   
5. printf("程序运行结束！\r\n");
   
6. getchar();
   
7. return 0;
   
8. }

复制代码

---

欢迎光临 圣龙扬特-AVR电子 (http://avr.cnta.net/)

Powered by Discuz! X2.5