【链表】单向链表的C语言实现
本帖最后由 avrbase_lei 于 2014-5-6 22:29 编辑代码没有在实际项目上用过。原理大概就是这么回事。代码贴出来，给大家围观。#include "stdio.h"
struct node {
struct node *next;
int value;
};
#define NODE_MAX 100
struct node array = {0};
struct node *root;
void delete_node(struct node *node);
void append_node(struct node *node);
int print_node(void);
struct node *alloc_node(void);
void free_node(struct node *node);
//删除指定的节点
void delete_node(struct node *node)
{
struct node **rootp = &root;
//从根节点开始，如果rootp里面的内容非空
//说明这个节点是有值的，我们就去比较
while(*rootp)
{
//这里比较的是节点的地址值
//实际运用中可能是其他的比较方式
//但是只要这里的if条件成立了，就说明节点被找到了
if (*rootp == node)
{
//找到节点后，把欲删除的节点所指向的下一个赋值给当前节点
//此刻的rootp实际就是当前欲删除的节点在其上一个节点中的next的指针
*rootp = (*rootp)->next;
break;
}
//当然，如果条件不成里，这里就继续找下一个节点
rootp = &(*rootp)->next;
}
//while循环结束，无论找到与否，我们都释放这个节点所占用的内存。
free_node(node);
}
//添加节点到链表的尾巴上
void append_node(struct node *node)
{
struct node **rootp = &root;
//很简单，一直找next，知道next所指向的内容为NULL
while(*rootp) rootp = &(*rootp)->next;
//然后把目标节点插入到next中
*rootp = node;
}
//打印整个链表，并统计链表节点的个数
//这个只是方便我们查看节点
int print_node(void)
{
int i = 0;
struct node *curr = root;
while(curr)
{
printf("%d,",curr->value);
curr = curr->next;
i ++;
}
printf("\r\n");
return i;
}
//为节点申请一段内存
//我这里是从一个数组分配一个元素来存储
//实际运用中一般不是这么做的
struct node *alloc_node(void)
{
int i;
//查找这个数组，如果哪个元素没有被占用
//我就取这个元素来为我用
for (i=0; i<NODE_MAX; i++)
{
if (!array.value)
return &array;
}
return NULL;
}
//释放节点占用的内存
//就是将数组元素的对应标志位清0了
//这样就表示没被占用了
void free_node(struct node *node)
{
memset(node, 0, sizeof(struct node));
}
//测试函数
void test(void)
{
int i, j;
const int times = 15;
struct node *node;
//先插入times个元素
for (i=0; i<times; i++)
{
//如果申请节点失败则停止插入
if (NULL == (node = alloc_node()))
break;
node->value = i +1;
node->next = NULL;
append_node(node);
}
//插入完毕，打印整个链表
i = print_node();
printf("total node is: %d.\r\n", i);
//随机删除链表中的节点
for (i=0; i<20; i++)
{
j = rand()%times;
printf("--\r\nwill delete array[%d].value=%d.\r\n", j, array.value);
delete_node(&array);
//删除一个节点后，再打印一下链表，统计链表中的节点个数
j = print_node();
printf("after delete, total node is: %d.\r\n----\r\n", j);
}
}
int main(int argc, char **argv)
{
test();
getchar();
return 0;
}
谢谢！
如果有注释就更完美了。 箫天 发表于 2014-5-6 20:25 static/image/common/back.gif
谢谢！
如果有注释就更完美了。
这个单向链表太简单了，就没有特地去写注释了。
只要把C里面的指针运用灵活了，理解起来就非常简单了。
root节点是整个链表的根节点，我们取这个根节点的指针rootp。
你添加或者不添加，删除或者不删除，链表就在那里。我们要做的就是改变这个rootp的值，来使它每次都指向不同的节点，而获取当前节点的下一个几点的指针是非常简单的，即 rootp=&node->next 就可以了，至于根节点root，自然是 rootp=&root; 于是问题就开始变的简单了。一个wihle循环，rootp就开始逐个往下查询下去了。一切就是这么简单。
箫天 发表于 2014-5-6 20:25 static/image/common/back.gif
谢谢！
如果有注释就更完美了。
这个单向链表太简单了，就没有特地去写注释了。
只要把C里面的指针运用灵活了，理解起来就非常简单了。
root节点是整个链表的根节点，我们取这个根节点的指针rootp。
你添加或者不添加，删除或者不删除，链表就在那里。我们要做的就是改变这个rootp的值，来使它每次都指向不同的节点，而获取当前节点的下一个几点的指针是非常简单的，即 rootp=&node->next 就可以了，至于根节点root，自然是 rootp=&root; 于是问题就开始变的简单了。一个wihle循环，rootp就开始逐个往下查询下去了。一切就是这么简单。
注释已经添加了。 嗯，有了注释和3楼解释，理解起来就简单多了。
页:
[1]