大家好嵌入式开发本质上就是“数据结构”和“硬件资源”的互殴。你选错结构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 0x20000008CPU 一路爽读。链表0x20000000 0x20001234 0x20000088 0x20004567CPU所以链表遍历特别慢。但它有个数组没有的优势——动态。比如设备节点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 有限状态机 FSM3种嵌入式软件本质就是状态机的集合。按键消抖、协议解析、电机 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 数据别靠直觉。
大家好嵌入式开发本质上就是“数据结构”和“硬件资源”的互殴。你选错结构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 0x20000008CPU 一路爽读。链表0x20000000 0x20001234 0x20000088 0x20004567CPU所以链表遍历特别慢。但它有个数组没有的优势——动态。比如设备节点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 有限状态机 FSM3种嵌入式软件本质就是状态机的集合。按键消抖、协议解析、电机 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 数据别靠直觉。
)
