Toggle navigation
首页
问答
文章
积分商城
专家
专区
更多专区...
文档中心
返回主站
搜索
提问
会员
中心
登录
注册
C++_cpp
数据结构
双链表
RT-Thread 隐藏的宝藏之双链表
发布于 2021-02-18 21:50:38 浏览:1720
订阅该版
[tocm] ### 1. 单链表与双链表 单链表: 由一个个节点(node)组成,每个节点都有指向下一个节点的指针。节点的连接方向是单向的,节点之间用指针连起来,所有结构体类型可以不一样,链表的大小也可以动态变化。但是不能随机访问数据,只能遍历。 双链表:由一个个节点(node)组成,每个节点都有指向下一个节点的指针,每个节点都有一个指向上一个节点的指针。所以节点的连接方向是双向的,节点之间用指针连起来,所有结构体类型可以不一样,链表的大小也可以动态变化。但是不能随机访问数据,只能遍历。 可以得出结论:单链表和双链表主要的区别就是双链表多了一个指向上一节点的指针。 循环链表:普通的节点(node) 的 头节点的`prev`指向 `null`,尾节点的`next` 指向 `null`。循环链表的头节点的 `prev` 指向 尾节点,尾节点的 `next` 的 指向头节点。简单理解就是头尾相连。 **重点** : RT-Thread 的双链表实现的就是循环链表。 ### 2. 怎么使用双链表 ``` struct rt_list_node { struct rt_list_node *next; /**< point to next node. */ struct rt_list_node *prev; /**< point to prev node. */ }; typedef struct rt_list_node rt_list_t; /**< Type for lists. */ ``` 结构体有两个指针分别指向下一个节点和上一个节点。 1. 初始化链表 ``` rt_list_t list; rt_list_init(&list); ``` 2. 在节点(list)后面插入一个新的节点 ``` rt_list_t nlist1; rt_list_insert_after(&list,&nlist1); ``` 3. 在节点(list)前面插入一个新的节点 ``` rt_list_t nlist2; rt_list_insert_before(&list,&nlist2); ``` 4. 移除一个节点 ``` rt_list_t nlist3; rt_list_remove(&nlist3); ``` 5. 判断链表是否为空 ``` rt_list_isempty(&list); ``` 6. 求单链表的长度 ``` rt_list_len(&list); ``` 7. 获取链表所在结构体的类型 ``` rt_list_entry(node(节点), type(结构体类型), 链表所在结构体成员的名字) ``` 8. 遍历链表 ``` rt_list_for_each(pos(节点), head(头节点)) ``` 9. 安全遍历链表 ``` rt_list_for_each_safe(pos, n, head) ``` 10. 遍历链表中的结构体成员 ··· rt_list_for_each_entry(node(节点), struct (结构体), list(链表所在结构体成员中的名字)) ··· 11. 安全遍历链表中的结构体成员 ``` rt_list_for_each_entry_safe(pos, n, head, member) ``` 12. 第一个节点的结构体 ``` rt_list_first_entry(ptr, type, member) ``` ### 3. 双链表的实现 1. 初始化链表 ``` rt_inline void rt_list_init(rt_list_t *l) { l->next = l->prev = l; } ``` 初始化的时候 `next` 和 `prev` 都指向了 `L`, 即实现了首尾相连的循环链表 2. 在节点后面插入一个节点 ``` rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n) { l->next->prev = n; n->next = l->next; l->next = n; n->prev = l; } ``` 3. 在节点前面插入一个节点 ``` rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n) { l->prev->next = n; n->prev = l->prev; l->prev = n; n->next = l; } ``` 4. 移除一个节点 ``` rt_inline void rt_list_remove(rt_list_t *n) { n->next->prev = n->prev; n->prev->next = n->next; n->next = n->prev = n; } ``` 5. 判断节点是否为空 ``` rt_inline int rt_list_isempty(const rt_list_t *l) { return l->next == l; } ``` 如果 `next` 指向了本身即判断链表为空。 6. 求链表的长度 ``` rt_inline unsigned int rt_list_len(const rt_list_t *l) { unsigned int len = 0; const rt_list_t *p = l; while (p->next != l) { p = p->next; len ++; } return len; } ``` 通过 `next` 是否指向链表的头节点,来确定是否遍历完链表。 7. 获取链表所在的结构体 ``` #define rt_list_entry(node, type, member) \ rt_container_of(node, type, member) ``` 具体的分析可以查看[单链表的分析](https://blog.csdn.net/whj123999/article/details/113435099) 8. 遍历链表 ``` #define rt_list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) ``` 9. 遍历边表并获取结构体 ``` #define rt_list_for_each_entry(pos, head, member) \ for (pos = rt_list_entry((head)->next, typeof(*pos), member); \ &pos->member != (head); \ pos = rt_list_entry(pos->member.next, typeof(*pos), member)) ``` 10. 安全遍历链表 ``` #define rt_list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) ``` 11. 安全遍历链表并获取结构体 ``` #define rt_list_for_each_entry_safe(pos, n, head, member) \ for (pos = rt_list_entry((head)->next, typeof(*pos), member), \ n = rt_list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = rt_list_entry(n->member.next, typeof(*n), member)) ``` **重点**: `rt_list_for_each` 与 `rt_list_for_each_safe` ```#define rt_list_for_each(pos(节点), head(头节点)) \ for (pos = (head)->next; pos != (head); pos = pos->next) ``` 从 `head` 开始遍历,如果这个时候改变了 `pos->next`,指向了 `NULL`, 那么这里将会导致死循环 ``` #define rt_list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) ``` `rt_list_for_each_safe` 多了一个参数 `n` , `n` 用来缓存 `pos->next` ,那么就可以避免死循环的情况 所以只做遍历操作用 `rt_list_for_each`,涉及到对节点的移除操作是就需要使用 `rt_list_for_each_safe` #### 4. 最后 作为一名合格的程序员一定要熟练的掌握链表,RT-Thread 的内核中提供了很方便的 API。RT-Thread 的内核源码中也是通过链表来实现了所有 `object` 连在了一起,掌握链表后,对分析,学习 RT-Thread 的思想一定会事半功倍。
2
条评论
默认排序
按发布时间排序
登录
注册新账号
关于作者
whj467467222
开源,分享,交流,共同进步
文章
32
回答
1222
被采纳
149
关注TA
发私信
相关文章
1
RT-STUDIO下加入TOUCHGFX?
2
有没有人在RTT上使用C++编程
3
nano c++ 报错如何处理
4
让成员函数能作为rt_device中的回调函数
5
成员函数作为回调函数
6
C++编译问题 undefined reference to `_exit'
7
开启C++功能后,rt_kprintf和单步调试功能无法使用
8
RT-Thread Studio C++ 异常处理 (与预期不一致)
9
C++继承Thread类报错怎么办?
10
STM32使用C++ 编译报错
推荐文章
1
RT-Thread应用项目汇总
2
玩转RT-Thread系列教程
3
国产MCU移植系列教程汇总,欢迎查看!
4
机器人操作系统 (ROS2) 和 RT-Thread 通信
5
五分钟玩转RT-Thread新社区
6
【技术三千问】之《玩转ART-Pi》,看这篇就够了!干货汇总
7
关于STM32H7开发板上使用SDIO接口驱动SD卡挂载文件系统的问题总结
8
STM32的“GPU”——DMA2D实例详解
9
RT-Thread隐藏的宝藏之completion
10
【ART-PI】RT-Thread 开启RTC 与 Alarm组件
热门标签
RT-Thread Studio
串口
Env
LWIP
SPI
AT
Bootloader
Hardfault
CAN总线
FinSH
ART-Pi
USB
DMA
文件系统
RT-Thread
SCons
RT-Thread Nano
线程
MQTT
STM32
RTC
FAL
rt-smart
I2C_IIC
ESP8266
UART
WIZnet_W5500
ota在线升级
cubemx
PWM
flash
freemodbus
BSP
packages_软件包
潘多拉开发板_Pandora
定时器
ADC
flashDB
GD32
socket
编译报错
中断
Debug
rt_mq_消息队列_msg_queue
SFUD
msh
keil_MDK
ulog
C++_cpp
MicroPython
本月问答贡献
出出啊
1518
个答案
343
次被采纳
小小李sunny
1444
个答案
290
次被采纳
张世争
813
个答案
177
次被采纳
crystal266
547
个答案
161
次被采纳
whj467467222
1222
个答案
149
次被采纳
本月文章贡献
出出啊
1
篇文章
5
次点赞
小小李sunny
1
篇文章
1
次点赞
张世争
1
篇文章
3
次点赞
crystal266
2
篇文章
2
次点赞
whj467467222
2
篇文章
2
次点赞
回到
顶部
发布
问题
投诉
建议
回到
底部