RT-Thread-RT-Thread隐藏的宝藏之单链表RT-Thread问答社区

RT-Thread隐藏的宝藏之单链表

发布于 2021-01-30 17:19:13 浏览：1831 订阅该版

[tocm]

### 1. 链表与数组
[链表](https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8/9794473?fr=aladdin) ，[数组](https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097?fr=aladdin) ，先看看百度怎么说。

上面的说法太专业，用简单的话来讲就是：链表和数组都是用来存储数据的一种数据结构，各有利弊。
**数组**：线性数据结构，存放的数据的类型是一样的，而且他们在内存中的排布是有序排列的。因此数组的优势就是数据连续，随机访问速度快，定义好了就不好在改变大小.
**单链表**：由一个个节点(node)组成，每个节点都有指向下一个节点的指针。节点的连接方向是单向的，节点之间用指针连起来，所有结构体类型可以不一样，链表的大小也可以动态变化。但是不能随机访问数据，只能遍历。

举一个栗子：一个班的学生的信息要存储起来，用数组肯定不太方便，学生的属性很多如：
```
sturct stu{
char name[10];
uint8_t math;
uint8_t  physics;
float height;
}
```
这里就可以用链表把一个班的学生整整齐齐的放在一起，考试出成绩的时候，就可以遍历了。

在 **RT-Thread** 的内核中就使用到了链表，所以这些 API 我们都是可以直接使用的，而不需要自己再去造轮子。

### 2. 单链表怎么使用
```
struct rt_slist_node
{
    struct rt_slist_node *next;                         /**< point to next node. */
};
typedef struct rt_slist_node rt_slist_t;                /**< Type for single list. */
```
结构体只有指向下一个节点的指针。

1. 初始化一个单链表
```
rt_slist_t list;
rt_slist_init(&list);
```

2. 在单链表的末尾插入新的链表
```
rt_slist_t nlist1;
rt_slist_append(&list, &nlist1)
```
3. 在节点 `L` 之后插入一个新的节点
```
rt_slist_t nlist2;
rt_slist_insert(&list, &nlist2)
```

4. 获取链表的长度
```
unsigned int len = 0;
len = rt_slist_len(&list);
```

5. 移除一个节点
```
rt_slist_t nlist3;
nlist3 = rt_slist_remove(&list,&nlist2);
```
6. 获取第一个节点
```
rt_slist_t nlist4;
nlist4 = rt_slist_insert(&list);
```

7. 获取下一个节点
```
rt_slist_t nlist5;
nlist5 = rt_slist_insert(&list);
```

8. 判断单链表是否为空,为空返回 1
```
int res;
res = rt_slist_isempty(&list);
```

9. 获取节点所在结构体的类型
```
rt_slist_entry(node(节点), struct (结构体), list(链表所在结构体成员中的名字))
```

10. 遍历链表
```
rt_slist_for_each(node(节点)，head(头结点))
```

11. 遍历链表中的结构体成员
```
rt_slist_for_each_entry(node(节点), struct (结构体), list(链表所在结构体成员中的名字))
```

### 3. 单链表的实现
1. 初始化链表
```
rt_inline void rt_slist_init(rt_slist_t *l)
{
    l->next = RT_NULL;
}
```
指针指向下一个节点 `RT_NULL`

2. rt_slist_append
```
rt_inline void rt_slist_append(rt_slist_t *l, rt_slist_t *n)
{
    struct rt_slist_node *node;

node = l;
    while (node->next) node = node->next;

/* append the node to the tail */
    node->next = n;
    n->next = RT_NULL;
}
```
遍历到最后一个节点，然后把插入新的节点，新的节点的 `next` 指向 `RT_NULL`

3. 插入一个新的节点
```
rt_inline void rt_slist_insert(rt_slist_t *l, rt_slist_t *n)
{
    n->next = l->next;
    l->next = n;
}
```
在 `l` 节点后面插入 `n` 节点

4. 获取链表的长度
```
rt_inline unsigned int rt_slist_len(const rt_slist_t *l)
{
    unsigned int len = 0;
    const rt_slist_t *list = l->next;
    while (list != RT_NULL)
    {
        list = list->next;
        len ++;
    }

return len;
}
```
遍历节点求出链表的长度

5. 移除一个节点
```
rt_inline rt_slist_t *rt_slist_remove(rt_slist_t *l, rt_slist_t *n)
{
    /* remove slist head */
    struct rt_slist_node *node = l;
    while (node->next && node->next != n) node = node->next;

/* remove node */
    if (node->next != (rt_slist_t *)0) node->next = node->next->next;

return l;
}
```
把 `l` 的 next 指向 `n` 的next

6. 获取链表头
```
rt_inline rt_slist_t *rt_slist_first(rt_slist_t *l)
{
    return l->next;
}
```
找到 `l` 的 next

7. 获取最后一个节点
```
rt_inline rt_slist_t *rt_slist_tail(rt_slist_t *l)
{
    while (l->next) l = l->next;

return l;
}
```
遍历链表找到最后一个节点

8. 获取下一个节点
```
rt_inline rt_slist_t *rt_slist_next(rt_slist_t *n)
{
    return n->next;
}
```
找到 `n` 的 next

9. 判断链表是否为空
```
rt_inline int rt_slist_isempty(rt_slist_t *l)
{
    return l->next == RT_NULL;
}
```
直接判断 `l -> next` 是否为 `RT_NULL`

10. 获取链表所在的结构体
```
#define rt_slist_entry(node, type, member) \
    rt_container_of(node, type, member)
```
这是一个宏
```
#define rt_container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
```
这个展开分析一下
` (char *)  (ptr) - (unsigned long)(&((type *)0)->member)`
再分成两部分 
- `(char *)  (ptr)`: `ptr` 本来的类型是`rt_slist_t *` ,把 `ptr` 强转成 `char*`
-  `(&((type *)0)->member)`: `(type *)0)`假设地址0处存放的是一个`type`类型的结构体变量，`member` 是 `list` 所在的位置，这样就知道了 `member` 在 `type` 的偏移量

这样就可以知道结构体的地址往前移动 `member` 在 `type` 的偏移量 就得到了，`type` 的首地址
最后强转成 `(type *)`, 这样就得到了结构体类型指针的首地址，这样就得到了节点所在的结构体

11. 遍历链表
```
#define rt_slist_for_each(pos, head) \
    for (pos = (head)->next; pos != RT_NULL; pos = pos->next)
```
通过 `next` 不为空来遍历链表

12. 遍历链表获取结构体
```
#define rt_slist_for_each_entry(pos, head, member) \
    for (pos = rt_slist_entry((head)->next, typeof(*pos), member); \
         &pos->member != (RT_NULL); \
         pos = rt_slist_entry(pos->member.next, typeof(*pos), member))
```
上面两个宏的结合。

### 4. 最后
作为一名合格的程序员一定要熟练的掌握链表。
如果上面的 插入 移除 `API` 没看明白的建议自己画个图，一下就明白了。