大家好，嵌入式开发，本质上就是“数据结构”和“硬件资源”的互殴。

你选错结构，CPU 就炸。

你结构设计不对，中断就丢。

你不会控制内存，系统迟早跑飞。

数据结构这东西就像地基，搭不好后面全是豆腐渣工程，选对数据结构，能省一半的调试时间。

我习惯把这部分按逻辑形态能分成四大类：线性结构、树形结构、哈希结构和图形结构。不过图形结构基本就活在论文和极端复杂的工业组网协议栈里，九成九的项目你一辈子都碰不到一次。

一、线性结构（7种）

在低端和中端MCU里，线性结构绝对是顶梁柱，它的特点就是元素前后一一对应，不仅资源开销小，而且实时性非常可控。

1.1 数组

这东西真的是最基础、最无聊，但又最不可或缺的。你翻开任何一个嵌入式项目，寄存器映射、状态表、参数表、甚至中断向量表…… 哪个离得开数组？

大家好，嵌入式开发，本质上就是“数据结构”和“硬件资源”的互殴。

你选错结构，CPU 就炸。

你结构设计不对，中断就丢。

你不会控制内存，系统迟早跑飞。

数据结构这东西就像地基，搭不好后面全是豆腐渣工程，选对数据结构，能省一半的调试时间。

我习惯把这部分按逻辑形态能分成四大类：线性结构、树形结构、哈希结构和图形结构。不过图形结构基本就活在论文和极端复杂的工业组网协议栈里，九成九的项目你一辈子都碰不到一次。

一、线性结构（7种）

在低端和中端MCU里，线性结构绝对是顶梁柱，它的特点就是元素前后一一对应，不仅资源开销小，而且实时性非常可控。

1.1 数组

这东西真的是最基础、最无聊，但又最不可或缺的。你翻开任何一个嵌入式项目，寄存器映射、状态表、参数表、甚至中断向量表…… 哪个离得开数组？

你在 STM32 里见到的那堆 __IO uint32_t 寄存器定义，本质上就是编译器帮你把绝对地址映射成数组下标。

// 典型的寄存器映射，数组思想 #define GPIOA_BASE 0x40020000 #define GPIOA_MODER ((volatile uint32_t *)(GPIOA_BASE + 0x00))

你看，GPIOA_MODER 就是个指向数组元素一样的指针。中断向量表更直白，直接就是一个函数指针数组，Cortex-M 核一上电就从 0x00000004 那里取复位向量的地址。这玩意要是没理解，你 Bootloader 都写不明白。

这玩意儿好用是好用——内存连续，Cache 命中率高，访问时间 O(1)，绝无内存碎片。但有个致命的硬伤，它的大小是死分配的。编译完之后，那块内存就雷打不动了，灵活度差了点。可很多时候我们就是需要固定啊，一片 256 字节的串口接收 buffer，你要是用动态分配，每次 malloc 出来物理地址不连续，DMA 直接罢工给你看。

1.2 单链表

链表这玩意儿吧，上学时教科书里吹得天花乱坠——“插入删除效率高！” 。

结果很多人真上项目后，疯狂滥用， 最后系统性能稀烂，

单链表最大的问题是 CPU 不喜欢它。 因为它不连续。

现代 MCU 虽然没 PC Cache 那么猛，但预取机制还是有的。

数组：

0x20000000 0x20000004 0x20000008

CPU 一路爽读。

链表：

0x20000000 0x20001234 0x20000088 0x20004567

CPU：？？？，所以链表遍历特别慢。

但它有个数组没有的优势——动态。

比如设备节点：

typedef struct DEVICE { uint8_t id; struct DEVICE *next; }DEVICE;

热插拔设备特别适合。

新增节点：

new_node->next = head; head = new_node;

O(1)，舒服，很多设备管理系统都这么干，但问题来了，malloc，又是 malloc，嵌入式里最怕频繁申请和频繁释放了，因为碎片一定会出现，只是时间问题。

所以老司机后来搞了对象池，提前静态分配。

DEVICE device_pool[32];

再自己维护空闲链表，这才是真·嵌入式思维。

1.3 双向链表

如果你只学一种链表，一定要把双向链表啃透。

FreeRTOS、RT-Thread、uC/OS 的内核，任务就绪链表、延时链表、阻塞链表，全部都是双向链表。为啥是双向？因为任务可能在任何位置被阻塞或唤醒，必须能在 O(1) 时间把自己从链表里摘掉，双向链表恰好满足这一点。

Linux 内核里的 list_head 那种侵入式设计在嵌入式圈简直就是教科书级的实现，它不把数据挂在链表上，而是让链表节点嵌在数据结构里，通用到令人发指。

// 典型的侵入式双向链表节点 struct list_node { struct list_node *prev; struct list_node *next; }; // 你的任务控制块里包含这个节点 typedef struct { uint32_t *stack_ptr; uint8_t priority; struct list_node task_node; // 用来挂到各种链表上 } tcb_t;

插入操作：

void list_insert(struct list_node *prev, struct list_node *node) { node->next = prev->next; node->prev = prev; prev->next->prev = node; prev->next = node; }

删除操作：

void list_remove(struct list_node *node) { node->prev->next = node->next; node->next->prev = node->prev; node->prev = node->next = NULL; // 可选 }

就这两段代码，撑起了无数 RTOS 的内核调度。我在移植 FreeRTOS 到一款 RISC-V 芯片上时，才真正理解了 vListInsert 和 uxListRemove 的妙处。每次任务切换，SysTick 中断里硬件自动压栈，然后调度器从就绪链表里挑出优先级最高的任务，把它的栈指针加载到 SP，上下文切换就这么顺滑地完成了。RT-Thread 更骚，直接用了小根堆管理线程定时器，但它的线程就绪表还是依赖双向链表和位图。这东西写得好用，真的能让你对“软件工程”四个字肃然起敬。

1.4 循环链表

双向链表的首尾相连，形成了一个闭环，就是循环链表。

这个在需要周期性遍历的场景里特别好使，比如你要做一个简单的轮询调度，没有任何优先级，所有任务手拉手转圈，时间片到了就切到下一个。有些低端 RTOS 的任务队列就是这么简陋但有效。

还记得用 51 单片机做个简单的分时任务调度吗？在一个死循环里依次检查几个任务标志，不就是个逻辑上的循环链表？当然，真正的循环链表是显式维护的。比如某些低功耗无线传感器网络里，节点需要轮流唤醒采集数据，谁都不该被落下，这时候循环链表就能保证每个节点周期性地得到 CPU 的临幸。

1.5 栈

栈是先进后出的典型，每个写 C 的嵌入式码农都应该明白，你每一次函数调用、每一次中断，硬件都会自动把返回地址压进栈里。

栈就是那个默默帮你保存上下文的东西，你自己也可能显式用到栈，比如解析数学表达式、做括号匹配，或者处理 AT 指令的响应。逆序输出场景下栈是天选之子。

最典型的就是 GPS NMEA 解析里校验码的计算，有些工程师会把接收到的字符逐个压栈，等收到 * 后弹出对比。当然更高效的做法是直接异或，但栈的清晰逻辑有时候比那一点点性能重要。还有做固件升级 Bootloader 时，很多方案会把接收到的升级包暂时存在外部 Flash，然后用栈来记录每个数据块的写入顺序，这样即便写入过程被打断，也能逆序回溯。

1.6 普通队列

普通队列就是先进先出，跟我们在食堂排队打饭一模一样，通常用数组加头尾指针实现，或者用链表。低并发场景，比如按键扫描后的消息通知、简易的打印日志缓冲，普通队列完全够用。但如果你的队列是跨中断和主循环用的，那就得小心翼翼了，因为不做保护的话，数据竞争会让你 debug 到怀疑人生。

普通队列理论上很好，现实中嵌入式并不特别爱它，因为出队后会产生“空洞”。比如：

[1][2][3][4]

出了两个：

[ ][ ][3][4]

你得memmove搬运数据，CPU 血压直接上来了，所以普通队列很多时候只是教学意义，真正工程里，大家都用环形队列。

1.7 循环队列

循环队列，作为嵌入式 IO 通信的标配结构，这个必须重点讲。

串口接收、CAN 收发、SPI DMA 双缓冲，只要是 IO 通信，嵌入式工程师脑子里的第一反应十有八九是环形缓冲区。

为啥？

因为它在没有动态内存分配的情况下，完美地抽象出了一条无穷无尽的流，还天然避免了内存碎片。更妙的是，如果设计成单生产者单消费者模式，甚至可以不关中断实现无锁操作（借助内存屏障或 volatile 约束），这对于中断延迟敏感的系统来说简直是福音。

实现环形队列的难点在于如何区分“满”和“空”——头和尾指针相遇时，到底是空了还是满了？

常规三招：第一种，浪费一个元素空间，当 (tail + 1) % size == head 时判满。第二种，单独用一个计数变量 count。第三种，用镜像索引在指针上编码圈数。嵌入式里第一种最普及，简单可靠，牺牲一个字节的 RAM 换来逻辑清晰，值。

下面这段代码是我自己的“祖传” ring buffer，拿走不谢。

#define RING_BUF_SIZE 128 typedef struct { uint8_t buffer[RING_BUF_SIZE]; volatile uint32_t head; // 读位置 volatile uint32_t tail; // 写位置 } ring_buf_t; void ring_buf_init(ring_buf_t *rb) { rb->head = 0; rb->tail = 0; } int ring_buf_put(ring_buf_t *rb, uint8_t data) { uint32_t next_tail = (rb->tail + 1) % RING_BUF_SIZE; if (next_tail == rb->head) { return -1; // 满 } rb->buffer[rb->tail] = data; rb->tail = next_tail; return 0; } int ring_buf_get(ring_buf_t *rb, uint8_t *data) { if (rb->head == rb->tail) { return -1; // 空 } *data = rb->buffer[rb->head]; rb->head = (rb->head + 1) % RING_BUF_SIZE; return 0; }

串口中断服务里：

void USART1_IRQHandler(void) { if (USART_GetITStatus(USART1, USART_IT_RXNE)) { uint8_t ch = USART_ReceiveData(USART1); ring_buf_put(&uart_rx_ring, ch); } }

主循环里慢慢取出来解析，爽歪歪。

二、树形结构（3种）

树这个东西，理论上特别高级，查找快、 结构优雅、 层级清晰。

但 MCU 不喜欢， 为什么呢？

因为指针多、栈消耗大、旋转复杂、Cache 不友好，尤其低端单片机，你在 8 位 MCU 上玩红黑树？ 属于有点想不开。

但当你的 MCU 有 32 位核、几十 KB 以上的 SRAM，再跑个带完整网络协议栈的系统，树形和哈希结构就开始发光发热了。

嵌入式里真正用的树形结构，大概就三种：普通二叉树、二叉搜索树，还有红黑树。

你可能会问，AVL 树呢？

那玩意儿平衡旋转太频繁，每次插入都极有可能调整，开销不够稳定，在实时系统里不讨喜，所以嵌入式领域，红黑树几乎一统江湖。

2.1 普通二叉树

每个节点最多两个孩子，在嵌入式里，普通的二叉树我们其实很少直接拿来存数据。顶多在做一些简易的分层配置，或者层级设备管理的时候，用它的逻辑概念来做个映射。因为如果它不平衡，退化成一条线的话，那它和链表就没什么区别了。

它不是用来高效查找的，而是一种自然的层级组织。比如你要管理一个多层级的设备配置菜单——系统配置下面分网络配置、外设配置，网络配置下面又分 WiFi、以太网——一棵普通的多叉树（通常用左孩子右兄弟表示法转成二叉树）就能清晰地组织。

在嵌入式 GUI 里，控件树的组织也是二叉或普通树结构。LittlevGL 用的就是对象树，每个对象有 parent 和 children，本质上就是一棵树。这没太多高深算法，就是利用其层级特性。这种树直接用指针实现即可，节点是静态分配好的，基本不用动态插入删除。

2.2 二叉搜索树（BST）

左子树的值都比根节点小，右子树的值都比根节点大。这东西就是为了有序数据查找而生的。

虽然想法很好，但在实际的工程中，我们也很少直接用纯粹的BST。为什么呢？因为如果我们插入的数据本来就是有序的，它就会一路往一边长，最后变成一个大链表。这时候它的查找优势荡然无存，完全失去了树的意义。

不过如果你是做 CANopen 这样的协议栈，对象字典的索引就是个动态过程，一些开源实现就用了 BST，查找 O(log n) 在节点数上千时比遍历强得多，平衡的问题就交给红黑树。

2.3 红黑树

它是自平衡的二叉搜索树，不管你怎么插入删除，它都能通过复杂的旋转和变色，保证树的高度在一个合理的范围内。这样查找、插入的时间复杂度都能稳定在很高水平。

Linux 内核的 CFS 调度器用红黑树管理进程，嵌入式 TCP/IP 协议栈（像 lwIP 的某些扩展，或者商业 RTOS 的 socket 管理）也用红黑树组织定时器或者路由表。FreeRTOS 的任务延时链表虽然没有直接用红黑树（它们用链表+时间差实现），但不少复杂中间件，比如文件系统里的 inode 管理，或者一些高级日志系统，用红黑树来加速索引。

有人可能会问，那为什么不用AVL树？

原因很简单。AVL树追求的是绝对的平衡，导致你每次插入删除都要进行大量的旋转调整，这个开销对嵌入式来说太奢侈了。红黑树的旋转最多三次就能恢复平衡，这点比 AVL 树强，所以实时性更好。

三、哈希（1种）

哈希其实就是通过一个算法，把你想找的键值直接映射到内存的一个具体位置，实现一枪命中，查找时间接近 。

举个例子，AT 指令解析器里需要根据命令字符串找到对应的处理函数，一个简单的字符串哈希表能避免大量 strcmp。Modbus 网关里，需要把寄存器地址映射到对应的数据源结构体，哈希表也是一把好手。嵌入式里实现哈希表，普遍采用链地址法，桶数组固定大小，冲突了就在桶后挂链表。Hash 函数别整太复杂，像 DJB2 或简单模运算就行。同样，所有节点必须提前静态分配，确保哈希表填充因子可控，否则实时性会退化。我个人习惯在系统初始化时把静态节点全部预插入到空闲链表，用时从空闲池取，用完归还。哈希虽然好用，但占用 RAM 比较大，如果只有几百字节可用，那还是用排序数组加二分吧。

四、图结构（1种）

至于图形结构，在绝大多数嵌入式项目里就是传说。

我在这行干了这么多年，除了在做复杂的工业组网协议、Mesh网络路由算法查找、或者是复杂的机器人路径规划时碰过几次，绝大多数普通的嵌入式项目，你一辈子也接触不到。这东西对RAM的消耗是个无底洞，普通的单片机直接告退，普通应用层工程师根本不用操心。

所以，以上这 12 种通用结构你心里有个谱就行，图可以打入冷宫。

五、嵌入式专属与衍生数据结构

上面这些好歹是计算机系课本里教过的，只不过嵌入式有自己的用法讲究。

接下来要说的这些，是真正的行业壁垒——它们从具体工程需求中孵化，大量存在于 RTOS 内核、驱动、协议栈和 Flash 存储里。这些结构你哪怕搞懂了理论，不亲手撸两遍，面试都过不了。这一部分大类十几种，细分形态超过三十种，我挑些重点讲。

5.1 缓冲区

做嵌入式通信、AD采样、屏幕显示，搞不定缓冲区，你的程序就等着卡死或者数据满天飞吧。

环形缓冲区 (RingBuffer)

这绝对是嵌入式IO通信的第一核心。不管是单字节的串口接收，还是按帧处理的CAN、LoRa通信，少它不行。

写这个东西的时候有个小技巧：把缓冲区的大小设置成2的幂次方。比如 64、128、256 字节。为什么要这么做？因为这样我们在处理指针回绕的时候，就可以用位运算来代替极其消耗CPU权重的取模（ % ）运算。

#define RING_BUFFER_SIZE 256 // 必须是2的幂 typedef struct { uint8_t buffer[RING_BUFFER_SIZE]; volatile uint16_t head; volatile uint16_t tail; } RingBuffer_t; void ring_buffer_queue(RingBuffer_t *rb, uint8_t data) { uint16_t next = (rb->tail + 1) & (RING_BUFFER_SIZE - 1); // 妙用位运算 if (next != rb->head) { rb->buffer[rb->tail] = data; rb->tail = next; } }

看到那个 & (RING_BUFFER_SIZE - 1) 了没？这效率，比写 if 判断或者 % 运算不知道高到哪里去了。有点东西吧？

双缓冲区 (Double Buffer)

在做显示屏刷新或者高速ADC采样的时候，如果你用一个缓冲区，经常会遇到一个尴尬的情况：这边正在拼命往里面写新数据，那边显示芯片已经开始读出来刷屏了。结果就是屏幕上出现一道恶心的断层，俗称数据撕裂。

双缓冲区就是专门来治这个病的。

块缓冲区、多阶缓冲、分包重组缓冲

当你需要通过蓝牙或者Wi-Fi传输一个大文件，或者在做OTA固件升级的时候。一个包几百个字节，你不可能在内存里开辟一个几十KB的连续空间来等它全部收完。这时候就要用到块缓冲区。

把内存切成一块块固定大小的格子。来一个包占一个格子，最后通过链表或者索引把这些格子串起来进行分包重组。这样既利用了零散的内存，又搞定了大数据传输。

5.2 位图

八个状态，你拿一个 uint8_t 存八个 bool 还是直接用它的每一个 bit？显然位图才是正确答案。嵌入式里 RAM 是按字节计较的，一个任务就绪表如果用 32 位整型数组的每一位代表一个优先级，那在 32 个优先级下只需要一个 uint32_t。FreeRTOS 的优先级位图就是如此：用一个 uint32_t 变量 uxTopReadyPriority 的某一位置位，再配合前导零指令 __clz 在 O(1) 时间找到最高优先级。

我自己写按键驱动的时候，也会用一个 uint16_t 的位图记录八个按键的按下状态和消抖状态，中断里只负责置位，主循环扫位图，完全不用关中断，原子操作就够了。

#define KEY1 (1 << 0) #define KEY2 (1 << 1) volatile uint16_t key_status = 0; void EXTI_IRQHandler(void) { if (EXTI_GetITStatus(EXTI_Line0)) { key_status |= KEY1; EXTI_ClearITPendingBit(EXTI_Line0); } } // 主循环里 if (key_status & KEY1) { key_status &= ~KEY1; // 处理按键 }

权限管理、资源标记、内存页空闲指示，到处都是位图的身影。说句实在话，刚转行那会儿我觉得位图是老古董，后来写 RTOS 任务调度被逼着读内核代码，才发现人家一个 bit 一个坑，太优雅了。

5.3 有限状态机 FSM（3种）

嵌入式软件，本质就是状态机的集合。按键消抖、协议解析、电机 FOC 控制、电源管理，万物皆可状态机。形态主要有三种：

简易跳转型状态机

最直观、最好写的状态机，全靠 if/switch 一条龙服务。

typedef enum { STATE_IDLE, STATE_CONNECTING, STATE_CONNECTED, STATE_ERROR } State_t; void fsm_update(State_t *current_state) { switch (*current_state) { case STATE_IDLE: if (user_action) *current_state = STATE_CONNECTING; break; case STATE_CONNECTING: if (connect_ok) *current_state = STATE_CONNECTED; else if (timeout) *current_state = STATE_ERROR; break; // ... 其他状态处理 } }

这种结构写起来顺手，一目了然。但是，如果你的业务逻辑特别复杂，状态有几十个，跳转条件错综复杂，那这个 switch-case 会长到让你怀疑人生。后期维护的时候，多加一个状态能让你改到崩溃。

状态转移矩阵

为了解决上面的痛点，对于多状态的复杂场景，我们会采用查表式的状态转移矩阵。

把状态跳转关系定义成一个二维数组（矩阵）。横坐标是当前状态，纵坐标是触发事件，格子里填的是下一个状态和要执行的回调函数。

typedef struct { State_t next_state; void (*action)(void); } Transition_t; // 状态转移矩阵表 Transition_t fsm_matrix[STATE_MAX][EVENT_MAX] = { [STATE_IDLE][EVENT_START] = {STATE_CONNECTING, start_action}, [STATE_CONNECTING][EVENT_SUCCESS] = {STATE_CONNECTED, success_action}, };

这样一搞，核心的执行代码变得异常干净，只需要根据当前状态和发生的事件去查这个表就行了。想增加或者修改状态？直接改这个矩阵表，根本不用动逻辑代码。

分层状态机 (HSM)

有些设备逻辑复杂到爆。比如一个智能家电，在“工作状态”下，又细分为“加热中”、“制冷中”、“保持温度”等子状态。如果把这些全部平铺开来，状态转移会乱成一团麻。

这时候就需要分层状态机。子状态可以继承父状态的默认行为。如果子状态不处理某个事件，它会自动向上抛给父状态处理。这种设计思想在复杂的人机交互界面（HUI）或者复杂的工业控制逻辑里非常常见。不过自己手写一个HSM挺费劲的，通常会借助一些开源的框架。

5.4 RTOS 实时操作系统专属结构（3种）

如果你用 FreeRTOS 或者 RT-Thread，自己写的应用层代码可能就一个 xQueueSend，有没有想过它们的内部是怎么运转的？它们的核心全部是基于链表和数组封装出来的专属结构，这些结构体里嵌着各种链表节点、事件记录、锁状态。

任务控制块 (TCB) 与线程栈

每个任务或者线程，在内核眼里其实就是一个结构体，叫任务控制块（Task Control Block）。这里面记录了任务的名字、优先级、当前的栈指针（SP）、任务的状态（运行、就绪、阻塞等）。

typedef struct tskTaskControlBlock { volatile StackType_t *pxTopOfStack; // 栈顶指针，切任务全靠它 ListItem_t xStateListItem; // 任务状态列表节点 UBaseType_t uxPriority; // 任务优先级 StackType_t *pxStack; // 栈的起始地址 char pcTaskName[16]; // 任务名字 } tskTCB;

而线程栈则是任务自己的一亩三分地。当任务被切走的时候，CPU的寄存器内容全部压入这个栈里；轮到它运行的时候，再从这里弹出来。任务切换的本质，其实就是改写汇编级的栈指针寄存器。

IPC 控制块

信号量、互斥量、消息邮箱、消息队列。这些用来做线程间通信和同步的东西，底层都有一个控制块。

这个控制块里除了存数据或者计数器之外，最核心的就是挂载着一个等待链表。当一个任务去拿一个已经被占用的互斥量时，这个任务的TCB就会被从就绪链表里剥离出来，塞进这个互斥量的等待链表里，然后引发系统调度。直到互斥量被释放，内核才把它捞出来重新放回就绪链表。

定时器与调度链表

• •就绪链表：一个由双向链表组成的数组，数组的下标就是优先级。内核调度器永远去瞅当前最高优先级的那个链表，把头部的任务拿出来跑。
• •延时链表：当任务调用了类似 vTaskDelay() 的函数，它就会被放到延时链表里。这个链表一般是按唤醒时间先后顺序排好序的。
• •优先级位图：有些RTOS（比如uC/OS或者RT-Thread）为了实现 的调度，会用一个位图来标记哪些优先级有任务就绪。调度器找最高优先级时，不需要遍历数组，直接用一条硬件汇编指令（比如 Cortex-M 内核的 CLZ 指令）就能在一两个时钟周期内算出最高优先级在哪一位。这设计真的令人拍案叫绝。

5.5 硬件驱动 & 外设专用结构

每个外设的驱动库都在向你展示什么叫“配置即结构体”。STM32 HAL 库的 GPIO_InitTypeDef、UART_HandleTypeDef，就是典型的硬件专用结构。

这些结构体把寄存器位域抽象成人类可读的成员，初始化时填好，然后一口气写入寄存器。做驱动开发的人，常常要对着 Reference Manual 自己定义寄存器映射结构体，比如一个 DMA 描述符：

typedef struct { uint32_t SRC; uint32_t DST; uint32_t LEN; uint32_t CTRL; struct dma_desc *next; // 链表模式 } dma_desc_t;

老一点的工程师甚至会用位域去映射控制寄存器，像这样：

typedef struct { uint32_t mode : 2; uint32_t ie : 1; uint32_t reserved : 29; } ctrl_reg_t;

虽然位域的可移植性有争议，但在资源固定的小 MCU 上非常直观。中断向量表本身就是函数指针数组，Bootloader 跳转时直接利用这个数组跳转，靠的就是对这块特殊数据结构的深刻理解。

5.6 通信协议专用结构

串口来了一堆字节，你怎么把它变成有意义的数据包？

你一定会定义一个帧结构体，例如一个私有协议：

#pragma pack(1) typedef struct { uint8_t head; uint8_t cmd; uint16_t len; uint8_t payload[256]; uint16_t crc; } packet_t; #pragma pack()

为了避免对齐带来的解析错误，通常要加 pack。解析的过程，则必然伴随着状态机。解析状态机存着当前已接收字节数、缓冲区索引、校验值等。比如一个典型的环形队列 + 状态机解析器，状态在“找帧头”、“收长度”、“收载荷”、“校验”之间流转。这块属于业务逻辑和数据结构高度融合，能把帧结构定义好，你的协议栈就成功了一半。

5.7 Flash & 文件存储类结构

在 MCU 内部 Flash 或外部 SPI Flash 上存参数、存日志，不能像写内存那样随意。Flash 有擦写寿命、需要按页擦除，所以衍生出了一系列存储结构。最简单的参数存储就是一个键值对结构，在 Flash 里存成一条条记录，每条记录带魔术字、长度和 CRC。

typedef struct { uint32_t magic; uint16_t id; uint16_t len; uint8_t data[64]; uint32_t crc; } flash_record_t;

上电时遍历 Flash 区域，找出所有有效记录加载到 RAM 的哈希表或数组里，修改时则写入新的记录并使旧的失效（磨损均衡的简易实现）。如果记录多了，还得搞个迷你文件系统，像 LittleFS、SPIFFS，它们在底层会维护块链表、元数据目录等复杂结构。不过这些一般直接移植成熟的库，自己从零写一个文件系统，不是一般人干的事。我干过一次，把 16MB 的 SPI Flash 做成日志存储，模仿了环形缓冲区的思想—— Flash 空间当作环形使用，满了一块擦除一块，配合一个索引表记录每条日志的偏移，效果凑合但擦写均衡并不完美，后来老老实实上了 LittleFS，内存多消耗了点，但稳。

5.8 排序 / 查找衍生结构

很多人以为在嵌入式里排序就是冒泡和插入，其实不然，这里不得不提一个在嵌入式里非常实用的奇技：时间轮（Timing Wheel）。

如果你要管理成百上千个定时任务（比如物联网网关要管理很多节点的超时检测），如果每个定时器都搞一个倒计时变量，然后每隔1ms去遍历一遍，CPU能给你烧出个窟窿来。

时间轮借鉴了钟表的原理。搞一个固定大小的循环数组（轮子），数组的每个格子代表一个时间刻度（比如1ms）。格子里挂载着一个链表，链表上全是需要在这一毫秒触发的任务。

一个硬件定时器每隔1ms把指针往前挪一格，挪到哪一格，就只执行那一格链表里的任务。不需要遍历所有人，时间复杂度直接从 暴跌到 。这个衍生出来的结构，在大型嵌入式联网项目里极度实用。

六、选型原则

说了这么多，你不可能每个项目把所有结构都堆上去，嵌入式选型，得先摸摸自己口袋里的硬件资源，再结合实时性要求做取舍。

如果你的 MCU 只有 8 位核、2KB RAM、32KB Flash，那就别想树和哈希了。数组、环形缓冲区、位图，外加一个简单的状态机，足够你做一个小家电控制器。甚至连动态分配的念头都不要有，所有节点全部静态。函数调用深度控制好，千万别没事儿就递归。这种平台上，代码简单就等于可靠。

到了 Cortex-M0/M3 这种主流 32 位机，SRAM 有 20-64 KB，能跑 FreeRTOS 了。这时候双向链表、队列、信号量这些 RTOS 结构就是你的日常。外部通信多，环形队列和双缓冲放心用。如果需要存储少量参数，Flash 上的键值对结构完全可以自己折腾一套。红黑树么，省着点用，节点数控制在几百以内，并且测好最坏执行时间。实在不确定，就用数组加二分，cache 友好度秒杀链表。

再往上，Cortex-M7 甚至带 MMU 的应用处理器，内存上 MB 级别，Linux 内核都跑起来了。这时候你用啥都行，但要考虑可维护性和团队平均水平。很多从互联网转过来的小伙伴一上来就 malloc 加 STL 容器，分分钟给你搞出内存泄漏和实时卡顿。我劝你还是按嵌入式的规矩来，能用静态池就用静态池，把动态内存的滥用扼杀在设计阶段。

还有一点容易被忽略——Cache 和 MPU 的存在会改变数据结构的选择哲学。链表遍历在带 Cache 的平台上可能因为访存跳跃导致大量的 Cache miss，而数组顺序访问则高效得多。所以即便你有能力写个红黑树，如果只是偶尔查那么几次，用有序数组二分可能更快更省电。嵌入式里选结构，得看真实 profiling 数据，别靠直觉。