4. 数据结构与算法在嵌入式中的运用
嵌入式环境资源受限（RAM/Flash小、算力低、实时性要求高），数据结构与算法的选择直接影响系统稳定性与性能。面试中常考察：基础数据结构选型、手写实现、复杂度分析、极端场景处理。本章聚焦高频考点与面试表达框架。
📊 常见嵌入式数据结构对比
| 数据结构 | 优点 | 缺点 | 典型嵌入式场景 | 时间复杂度（插入/删除/访问） |
|---|---|---|---|---|
| 静态数组 | 连续内存、随机访问O(1) | 大小固定、插入删除O(n) | ADC采样缓冲区、环形FIFO | O(1)/O(n)/O(1) |
| 单向链表 | 动态大小、插入删除O(1) | 随机访问O(n)、额外指针内存 | 任务管理链表、内存池空闲块 | O(1)/O(n)/O(n) |
| 循环队列 | 内存复用、FIFO定长 | 需要维护读写指针 | UART接收缓冲区、按键消息队列 | O(1)/O(1)/O(1) |
| 栈 | LIFO、中断嵌套自动保存 | 只能访问栈顶 | 函数调用栈、RTOS任务栈 | O(1)/O(1)/O(1) |
| 哈希表 | 查找O(1)平均 | 可能冲突、内存不可预测 | 命令解析表、参数快速索引 | O(1)/O(1)/O(1)均摊 |
🔹 面试问题 1
问题：在嵌入式系统中，你会如何选择使用链表还是数组？
考察点：数据结构选型能力、嵌入式资源意识、时间复杂度理解。
回答框架：
① 明确场景：内存动态性要求、实时性、访问模式。
② 对比优缺点：数组 O(1) 随机访问但大小固定；链表 O(1) 插入删除但额外指针开销。
③ 给出结论：若元素个数固定且随机访问多，选数组；若频繁增删且大小动态，选链表。
示例回答：我会优先判断数据规模是否固定。例如传感器采样点固定 64 个，用数组更高效；而任务控制块链表因创建/删除频繁，用双向链表。同时注意嵌入式下链表节点分配需用静态内存池避免碎片。
可能追问：如何实现一个静态内存池来管理链表节点？
🔹 面试问题 2
问题：请用 C 语言实现一个循环队列，并说明在嵌入式中的使用场景。
考察点：编码规范、边界处理、嵌入式应用知识。
回答框架：
① 定义结构体：数组、头/尾指针、容量。
② 核心函数：初始化、入队、出队、判空/满。
③ 常用判满方式：浪费一个元素或使用 size 计数。
④ 场景举例：UART 缓冲区，用中断入队、主循环出队。
示例回答：我选择浪费一个元素判满。入队时先检查是否满，未满则放入数据并更新尾指针；出队类似。常用在通信 FIFO 中，例如串口接收中断只入队，主循环出队解析，避免中断处理耗时过长。
可能追问：如果队列满时再收到数据，你会怎么处理？
🔹 面试问题 3
问题：嵌入式系统中，哈希表有什么优缺点？如何解决哈希冲突？
考察点：哈希表原理、嵌入式内存限制、冲突处理方案。
回答框架：
① 优点：平均 O(1) 查找，适合命令/参数快速索引。
② 缺点：哈希计算耗时、冲突退化到 O(n)、内存不可控。
③ 解决冲突：链地址法（需动态链表，不适合 ISR）、开放地址法（线性探测、二次探测，需注意聚集）。
④ 嵌入式推荐：预先计算完美哈希或使用小规模线性探测。
示例回答：在命令解析中我会用开放地址法中的线性探测：先对字符串做简单哈希，若冲突则向下探测直到空位置。由于命令表通常固定且不会频繁增删，这种方案无动态内存开销，查找性能可接受。
可能追问：如何设计一个针对嵌入式 MCU 的轻量级哈希函数？