246.1.4C语言_链表使用(下)

unsigned int rt_list_log(const rt_list_t *l) /* 课程自定义遍历打印函数；它不是 RT-Thread 官方 API。 */
{ /* 函数体开始。 */
    unsigned int len = 0; /* 记录 while 循环完成的次数；注意它最终少算循环外处理的最后一个结点。 */
    const rt_list_t *p = l; /* 游标从传入的链接结点 l 开始。 */
    struct info *sp=NULL; /* 保存由链接结点反推出的外围 struct info 指针。 */
    while (p->next != l) /* 后继还没有回到起点时，处理当前结点。 */
    { /* 循环体开始。 */
        sp = rt_list_entry(p, struct info, list); /* 由 p 指向的 list 成员地址反推所属 info 对象地址。 */
        LOG_D("person name:%s  age:%d",sp->name,sp->age); /* 打印当前业务对象的姓名和年龄。 */
        p = p->next; /* 沿 next 移动到循环链表的下一个链接结点。 */
        len ++; /* 只统计在 while 内处理的结点。 */
    } /* 当当前 p 是环中最后一个结点时退出循环。 */
    sp = rt_list_entry(p, struct info, list); /* 单独取回最后一个结点所属的 info 对象。 */
    LOG_D("person name:%s  age:%d",sp->name,sp->age); /* 补印未进入 while 的最后一个对象。 */
    return len; /* 返回值为实际打印数减一；本课调用者没有使用该返回值。 */
} /* 函数体结束。 */

这段代码与课程压缩包 02LIST/applications/main.c 一致。它是老师从 rt_list_len() 改出的实验函数，用于展示如何从 rt_list_t 找回外围业务对象。必须先看清它的特殊前提：传入的 l 本身就是 person1 的链接成员，也被当成数据结点；它不是通常意义上的独立哨兵头结点。

一、C语言链表

上一课已经完成初始化、插入、计数和删除，本课把“沿链接移动”与“读取业务数据”连接起来。next、prev 只知道 rt_list_t，而姓名和年龄属于外围的 struct info；关键问题是如何从内嵌成员地址反推出整个结构体地址。

1.1 例题: 链表遍历打印

遍历包含两个层次：

1. 用 p = p->next 沿 rt_list_t 组成的环逐结点移动。
2. 对每个 p 调用 rt_list_entry(p, struct info, list)，得到所属 struct info *，再访问 name 和 age。

只会初始化、插入和删除，还不能读取链上的业务对象；反过来，只会从一个成员地址计算外围对象，也不能保证链表遍历会正确终止。本课的学习重点是同时维护游标、终止条件和成员到容器的映射。

1.2 链表⻓度获取函数分析

RT-Thread 5.0.2 的 rt_list_len() 接收一个参数 const rt_list_t *l。它先令 p = l，随后反复判断 p->next != l；条件成立时前进到 p->next 并把计数加一。当下一跳重新指向 l 时，说明已经绕环一周。

这一实现把 l 当作不参与计数的链表头，因此初始化后的自指头结点长度为 0。它的实际顺序是“先看下一跳、再移动并计数”，不是原笔记所说的“每访问当前节点就计数”。对 head <-> A <-> B <-> head，它依次移动到 A、B，共计 2 次。

rt_list_len() 只需要链接关系，不关心结点属于哪种业务结构体；要打印 age 和 name，才需要额外恢复外围对象地址。

1.3 问题引入

在本例中，p 指向的是某个对象内部的 list 成员，而 sp->age、sp->name 的访问基准必须是整个 struct info 的起始地址。两者相差一个由结构体布局决定的固定偏移量。

这不是“传统链表一定指向数据块首地址、RT-Thread 链表才指向内部”的普遍区别。链表可以把链接放在对象开头、中间或结尾，也可以单独分配包装结点。RT-Thread 这里采用的是侵入式设计：链接成员嵌在对象内部，通用链表层只处理 rt_list_t。

不能把 rt_list_t * 直接强制转换为 struct info *，除非 list 恰好是结构体第一个成员；本例的 list 在 age、name 之后，地址明显不同。即便某次布局碰巧偏移为零，也应使用表达真实成员关系的接口，避免结构体成员调整后静默出错。

1.4 容器of函数介绍

课程口述的名称是 container_of，本工程实际宏名为 rt_container_of(ptr, type, member)。它不是普通函数，而是预处理宏。rt_list_entry(node, type, member) 又对它做了一层链表语义包装。

计算过程可以拆成三步：

1. 根据 type 与 member 求出该成员相对结构体起点的字节偏移。
2. 把已知成员指针 ptr 转为 char *，使指针减法按字节计算。
3. 用成员地址减去成员偏移，再把结果转回 type *。

可将它理解成公式：外围对象地址 = 成员地址 - 成员在结构体内的偏移。假设一个 struct info 从地址 0x20001000 开始，list 偏移 24 字节，那么 list 地址为 0x20001018；用该地址减 24，便回到 0x20001000。实际偏移必须由编译器依据类型布局计算，不能把示例数字写死。

宏无法在运行时验证三项信息是否匹配。node 必须真的指向某个 type 对象里的 member；类型或成员名虽然可能通过编译，组合错误仍会算出无效地址，随后解引用就可能产生未定义行为。

1.5 rt_list_len函数介绍

本节标题写的是 rt_list_len，但视频此处实际分析的是 rt_list_entry(node, type, member)。三个宏参数的含义为：

• node：输入的内嵌 rt_list_t 结点地址，例如当前游标 p。
• type：外围结构体类型，例如 struct info，不是“结构体起始地址类型”。
• member：该链接字段在外围结构体中的成员名，例如 list。

宏表达式的结果才是外围结构体指针。原笔记把 node 写成返回值，方向正好相反。正确调用 rt_list_entry(p, struct info, list) 的类型结果是 struct info *，所以能赋给 sp。

同一份 rtservice.h 还定义了 rt_list_for_each、rt_list_for_each_safe、rt_list_for_each_entry 等遍历宏。普通遍历、遍历中删除以及直接遍历外围对象有各自适用的宏；实际工程应先确认版本与宏的安全条件，而不是机械复制一种循环。

1.6 结构体定义

struct info 必须在 rt_list_log() 定义之前已经是完整类型，因为函数需要访问 sp->name 和 sp->age，宏也需要计算 list 的成员偏移。它在上一课已定义于文件作用域，本课没有在函数里重新定义一次。

视频最初把新函数也命名成 rt_list_len，编译器立即报告重定义，因为 rtservice.h 已经提供同名内联函数。后来改名为 rt_list_log 才消除冲突。函数名应避免冒充内核接口；这里保留课程名称以对应源码，但要知道它是应用自定义函数。

struct info *sp = NULL 只是创建一个用于接收结果的指针。它不分配新对象，也不是链表游标；每轮由 rt_list_entry() 计算后，sp 才指向当前 struct info。

1.7 while循环介绍

课程第一次尝试把 sp 传给 rt_list_entry()，却没有把宏的计算结果赋回 sp。编译器提示宏表达式“statement with no effect”，运行时仍通过空的或错误的 sp 读取成员，于是串口出现乱码姓名和 536874088 之类的错误年龄。

最终源码中的关键语句是 sp = rt_list_entry(p, struct info, list);。左侧接收返回的外围对象指针，右侧输入当前链表游标。随后 LOG_D 用 %s 读取以 \0 结尾的姓名，用 %d 读取 int 年龄，最后才让 p 前进。

这里的 const rt_list_t *p 表示代码不会通过 p 修改链接字段，但恢复出的 sp 类型不是 const struct info *。本函数只读业务字段，所以没有造成修改；若希望接口从类型层面承诺完全只读，外围对象指针的限定也应一致设计。

1.8 编译运行

只定义 rt_list_log() 不会自动执行。课程在链表构造完成后调用 rt_list_log(&(person1->list))，才从串口看到姓名和年龄。

删除语句仍启用时，环中保留 person1、person2、person4，补上循环外最后一次打印后，实际输出为 wfeng/8、lihua/15、liuchang/4。被摘除的 person3 不会被遍历到。后来注释删除语句，xiaohong/11 才重新出现在四个对象的输出中；它不是被重新插入，而是根本没有执行删除。

这段实验函数需要特别辨认两个问题：

• 循环条件是 p->next != l，所以最后一个 p 不进入循环。源码用循环后的两行补印最后一个对象。
• 循环外补印时没有执行 len++，因此环里有 N 个业务结点时，函数打印 N 个，返回值却是 N - 1。四个对象时返回 3，一个对象时返回 0。调用者当前忽略返回值，所以视频没有暴露这个计数错误。

另外，该函数把 l 当成业务结点。若传入惯用的独立空哨兵头，它会尝试用哨兵地址反推 struct info 并读取不存在的业务字段，行为无效。常规哨兵遍历应从 head->next 开始，在游标等于 head 时结束，不处理 head 自身。

“循环链表可从任意结点开始”只在所有结点都同质、起点也算业务数据、并且期望旋转后的完整顺序时成立。若链中有专用哨兵、不同角色结点，或业务顺序必须从固定表头开始，就不能随便选起点。遍历期间若其他线程或中断可修改同一链表，还要使用符合上下文的同步保护。

1.9 链表遍历

终止条件取决于是否循环，并不取决于“单向还是双向”：

• 线性单向链表通常沿 next 遍历到 NULL。
• 线性双向链表沿 next 向前遍历时同样可用 NULL 作为末端。
• 循环单向链表和循环双向链表都会重新遇到起点或哨兵，因此用“游标是否回到起点”终止。

原笔记把“循环链表”与“单向链表”作为对立项并不严谨。单向/双向描述链接方向，线性/循环描述末端连接方式，两组属性可以自由组合。

遍历中只读取结点时，保存一个当前游标即可；如果循环体会删除当前结点，应在删除前保存下一结点，或使用 RT-Thread 提供的安全遍历宏。因为 rt_list_remove() 会把当前结点改成自指，删除后再从它读取原来的 next 已经找不到后继。

1.10 链表和数组的区别

数组对象的元素连续排列，可由下标在 O(1) 时间定位，连续扫描也通常具有更好的缓存局部性。链表按链接定位第 k 个元素通常为 O(n)，每个结点还承担指针空间和可能的动态分配成本。

数组“长度不可变”应更准确地理解为：一个数组对象创建后不能原地改变元素个数。C 的部分版本支持块作用域变长数组，其长度可在创建时由运行时值决定，但创建后仍不能扩容；堆缓冲区可以用重新分配接口改变容量，却可能搬到新地址。标准 C++ 没有 C 风格变长数组，常见的可变长容器是 std::vector，它也不等同于语言内建数组。

链表能方便地插入、摘除已定位结点，但寻找位置仍可能为 O(n)。结点也只是“不要求连续”，并非必然分散。选择结构时要同时考虑访问模式、元素数量变化、内存碎片、分配时延、缓存行为和同步要求。

二、链表

带哨兵头的链表用一个不保存业务数据的专用结点统一表示空表与首尾边界；不带哨兵的链表通常让头指针直接指向第一个业务结点，空表则以空指针表示。课程把 person1->list 既当遍历起点又当业务结点，更接近“不带独立哨兵的循环链表”，却调用了按表头语义计数的 rt_list_len()，所以必须区分这两个口径。

“动态链表”通常指结点可在运行时分配和释放，但链表不一定来自 malloc。嵌入式系统常用静态对象、固定块内存池或预分配数组来避免堆碎片和不确定时延。无论存储从哪里来，建立链接、维护生命周期、选择正确终止条件和恢复外围对象的原则相同。

学完本节，应能解释 rt_list_entry(p, struct info, list) 的三个参数，能从成员偏移推导外围地址，能判断视频早期乱码输出的原因，并能指出课程版 rt_list_log() 的返回值与打印数量为什么相差 1。