第3章 数据结构与算法在嵌入式中的应用
嵌入式系统资源受限，数据结构与算法的选择直接影响内存占用、执行效率和实时性能。本章聚焦常见数据结构（链表、队列、栈）和排序、查找算法在MCU环境下的空间复杂度权衡，帮助你在面试中展现扎实的底层思维。
▲ 嵌入式数据结构选型回答框架：从约束到实现
面试问答卡片
Q1：在嵌入式系统中，链表和数组应如何选择？
面试官考察点：对内存分配、随机访问性能、插入删除效率的理解，以及是否考虑碎片和确定性。
回答框架：先对比两者优缺点，再根据场景（静态或动态数据、实时性、内存资源）给出选择依据，最后提一下嵌入式场景的优化手段（静态链表/内存池）。
简短示例回答：若数据量固定且需频繁随机访问，选数组；若需动态增删且数据量变化大，选链表。在MCU上优先用静态链表或内存池避免堆碎片。例如I2C设备列表用数组，任务控制块用双向链表。
可能追问：如何避免链表导致的内存碎片？环形缓冲区能否替代链表？
Q2：实时系统中排序算法如何选？需要考虑哪些因素？
面试官考察点：时间复杂度、空间复杂度、稳定性、原地排序、递归深度对栈的影响。
回答框架：先按数据量级分：小数据（<100）用插入/冒泡（常数小、稳定）；大数据且内存允许用归并或堆排序；若栈空间紧张避免递归快排。结合具体MCU的RAM和Flash说明。
简短示例回答：对于100个以内的采集数据排序，我用插入排序，代码简单且无需额外内存。对于上千条日志排序，我选用堆排序，O(nlogn)且原地排序，无递归栈风险。
可能追问：归并排序的额外空间如何解决？能否用非递归快排？
Q3：如何实现一个线程安全的环形缓冲区？
面试官考察点：队列实现细节、读写指针模运算、竞态条件处理、实时性保障。
回答框架：先定义数组和读写索引，写前检查是否满，读前检查是否空；多任务/中断场景需要关中断或使用原子操作（如CAS）。可扩展为无锁环形缓冲区（单生产者-单消费者）。
简短示例回答：定义uint8_t buffer[256]和uint8_t wr_idx, rd_idx；写时wr_idx = (wr_idx+1)&0xFF；判满条件是wr_idx+1==rd_idx。在中断中操作时，先关中断再更新指针，防止破坏一致性。
可能追问：如何优化成无锁版本？如何支持多生产者？
项目案例：智能家居多传感器数据采集系统
| 项目名称 | 基于STM32的多传感器数据汇聚与上传系统 |
|---|---|
| 业务背景 | 智能家居网关需实时采集温湿度、光照、PM2.5等10种传感器数据，通过UART上报云端。 |
| 规模指标 | 10个传感器节点，采样率100Hz，MCU RAM 16KB，Flash 64KB，单次上传数据包256字节。 |
| 技术栈 | C语言、FreeRTOS、STM32F103、HAL库、I2C/SPI传感器驱动、DMA+环形缓冲区 |
| 核心难点 | 1. 中断频繁导致数据丢失；2. 动态内存分配引发碎片；3. 不同传感器时序差异导致互锁。 |
| 面试高频追问 | 追问1：如何解决内存碎片？→ 改用静态环形缓冲区+内存池管理传感器状态链表。追问2：实时性如何保证？→ 使用FreeRTOS消息队列，高优先级任务处理传感器中断，低优先级任务打包上传。追问3：数据丢包如何排查？→ 添加序列号机制，通过环形缓冲区满标志统计丢包率。 |
| 可迁移回答话术 | “在项目中我采用静态分配的环形缓冲区避免动态内存碎片，利用DMA+双缓冲减少CPU干预；对于需要动态管理的传感器列表，我实现了一个固定大小的内存池来分配节点，确保分配时间确定且无碎片。这种思路也可以推广到其他需要数据缓存和任务调度的嵌入式场景。” |