圣龙扬特-AVR电子

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 472|回复: 5

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

[复制链接]

6

主题

0

好友

627

积分

高级会员

Rank: 4

UID
43
帖子
33
精华
0
注册时间
2013-2-27
在线时间
8 小时
发表于 2014-5-6 16:37:58 |显示全部楼层
本帖最后由 avrbase_lei 于 2014-5-6 22:29 编辑

代码没有在实际项目上用过。原理大概就是这么回事。代码贴出来,给大家围观。
  1. #include "stdio.h"

  2. struct node {
  3. struct node *next;
  4. int value;
  5. };

  6. #define NODE_MAX 100

  7. struct node array[NODE_MAX] = {0};
  8. struct node *root;

  9. void delete_node(struct node *node);
  10. void append_node(struct node *node);
  11. int print_node(void);
  12. struct node *alloc_node(void);
  13. void free_node(struct node *node);


  14. //删除指定的节点
  15. void delete_node(struct node *node)
  16. {
  17. struct node **rootp = &root;
  18. //从根节点开始,如果rootp里面的内容非空
  19. //说明这个节点是有值的,我们就去比较
  20. while(*rootp)
  21. {
  22. //这里比较的是节点的地址值
  23. //实际运用中可能是其他的比较方式
  24. //但是只要这里的if条件成立了,就说明节点被找到了
  25. if (*rootp == node)
  26. {
  27. //找到节点后,把欲删除的节点所指向的下一个赋值给当前节点
  28. //此刻的rootp实际就是当前欲删除的节点在其上一个节点中的next的指针
  29. *rootp = (*rootp)->next;
  30. break;
  31. }
  32. //当然,如果条件不成里,这里就继续找下一个节点
  33. rootp = &(*rootp)->next;
  34. }

  35. //while循环结束,无论找到与否,我们都释放这个节点所占用的内存。
  36. free_node(node);
  37. }

  38. //添加节点到链表的尾巴上
  39. void append_node(struct node *node)
  40. {
  41. struct node **rootp = &root;

  42. //很简单,一直找next,知道next所指向的内容为NULL
  43. while(*rootp) rootp = &(*rootp)->next;
  44. //然后把目标节点插入到next中
  45. *rootp = node;
  46. }

  47. //打印整个链表,并统计链表节点的个数
  48. //这个只是方便我们查看节点
  49. int print_node(void)
  50. {
  51. int i = 0;
  52. struct node *curr = root;

  53. while(curr)
  54. {
  55. printf("%d,",curr->value);
  56. curr = curr->next;
  57. i ++;
  58. }

  59. printf("\r\n");
  60. return i;
  61. }

  62. //为节点申请一段内存
  63. //我这里是从一个数组分配一个元素来存储
  64. //实际运用中一般不是这么做的
  65. struct node *alloc_node(void)
  66. {
  67. int i;

  68. //查找这个数组,如果哪个元素没有被占用
  69. //我就取这个元素来为我用
  70. for (i=0; i<NODE_MAX; i++)
  71. {
  72. if (!array[i].value)
  73. return &array[i];
  74. }

  75. return NULL;
  76. }

  77. //释放节点占用的内存
  78. //就是将数组元素的对应标志位清0了
  79. //这样就表示没被占用了
  80. void free_node(struct node *node)
  81. {
  82. memset(node, 0, sizeof(struct node));
  83. }

  84. //测试函数
  85. void test(void)
  86. {
  87. int i, j;
  88. const int times = 15;
  89. struct node *node;

  90. //先插入times个元素
  91. for (i=0; i<times; i++)
  92. {
  93. //如果申请节点失败则停止插入
  94. if (NULL == (node = alloc_node()))
  95. break;
  96. node->value = i +1;
  97. node->next = NULL;
  98. append_node(node);
  99. }

  100. //插入完毕,打印整个链表
  101. i = print_node();
  102. printf("total node is: %d.\r\n", i);


  103. //随机删除链表中的节点
  104. for (i=0; i<20; i++)
  105. {
  106. j = rand()%times;

  107. printf("--\r\nwill delete array[%d].value=%d.\r\n", j, array[j].value);
  108. delete_node(&array[j]);

  109. //删除一个节点后,再打印一下链表,统计链表中的节点个数
  110. j = print_node();
  111. printf("after delete, total node is: %d.\r\n----\r\n", j);
  112. }
  113. }


  114. int main(int argc, char **argv)
  115. {
  116. test();

  117. getchar();
  118. return 0;
  119. }
复制代码
回复

使用道具 举报

66

主题

4

好友

1万

积分

管理员

Rank: 9Rank: 9Rank: 9

UID
2
帖子
339
精华
0
注册时间
2013-2-20
在线时间
348 小时
发表于 2014-5-6 20:25:30 |显示全部楼层
谢谢!
如果有注释就更完美了。
回复

使用道具 举报

6

主题

0

好友

627

积分

高级会员

Rank: 4

UID
43
帖子
33
精华
0
注册时间
2013-2-27
在线时间
8 小时
发表于 2014-5-6 22:18:38 |显示全部楼层
箫天 发表于 2014-5-6 20:25
谢谢!
如果有注释就更完美了。

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

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

回复

使用道具 举报

6

主题

0

好友

627

积分

高级会员

Rank: 4

UID
43
帖子
33
精华
0
注册时间
2013-2-27
在线时间
8 小时
发表于 2014-5-6 22:18:41 |显示全部楼层
箫天 发表于 2014-5-6 20:25
谢谢!
如果有注释就更完美了。

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

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

回复

使用道具 举报

6

主题

0

好友

627

积分

高级会员

Rank: 4

UID
43
帖子
33
精华
0
注册时间
2013-2-27
在线时间
8 小时
发表于 2014-5-6 22:30:56 |显示全部楼层
注释已经添加了。
回复

使用道具 举报

66

主题

4

好友

1万

积分

管理员

Rank: 9Rank: 9Rank: 9

UID
2
帖子
339
精华
0
注册时间
2013-2-20
在线时间
348 小时
发表于 2014-5-6 23:09:15 |显示全部楼层
嗯,有了注释和3楼解释,理解起来就简单多了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

Archiver|手机版|圣龙扬特-AVR电子 ( 鲁ICP备05022832号 )

GMT+8, 2020-11-26 22:34 , Processed in 0.223802 second(s), 18 queries .

Powered by Discuz! X2.5

© 2001-2012 Comsenz Inc.

回顶部