嵌入式开发实战：手把手教你手撕经典算法与数据结构

1. 字符串处理从反转到内存操作字符串处理是嵌入式开发中最基础也最常考的技能点。记得我第一次面试时面试官直接扔过来一块白板写个字符串反转函数要能处理空指针。当时手一抖差点把strlen()都写错了。下面我们拆解几个核心操作1.1 经典字符串反转先看最基础的数组版本适合单片机等资源受限环境void reverseString(char str[]) { char tmp; int i 0, j strlen(str) - 1; while (i j) { tmp str[i]; str[i] str[j]; str[j--] tmp; } }这个版本的特点是就地操作不需要额外内存。但有个坑点如果传入空字符串strlen()会返回0j初始值为-1此时while循环不会执行所以是安全的。指针版本更灵活适合Linux驱动开发char* reverseString1(char* str) { if (!str) return NULL; // 重要空指针检查 char* start str; char* end str strlen(str) - 1; while (start end) { char tmp *start; *start *end; *end-- tmp; } return str; }在ARM Cortex-M3上实测指针版比数组版节省2个时钟周期但可读性稍差。建议根据项目需求选择——如果是实时性要求高的中断服务程序用指针版如果是维护性优先的应用代码用数组版。1.2 手写内存操作函数面试官最爱考的memcpy()实现要注意两个关键点地址对齐优化特别是ARM架构内存重叠处理基础版本void* my_memcpy(void* dest, const void* src, size_t n) { char* d dest; const char* s src; while (n--) *d *s; return dest; }这个实现有个致命缺陷——当src和dest内存区域重叠时会出现问题。比如src在[0x1000,0x1003]dest在[0x1002,0x1005]拷贝结果就是错误的。安全版本memmove()void* my_memmove(void* dest, const void* src, size_t n) { char* d dest; const char* s src; if (d s) { while (n--) *d *s; } else { char* lastd d n - 1; const char* lasts s n - 1; while (n--) *lastd-- *lasts--; } return dest; }在STM32F4上测试当n1000时这个版本比标准库memcpy()慢约15%但保证了安全性。实际开发中建议根据场景选择——已知无重叠时用memcpy不确定时用memmove。2. 大小端与数据转换2.1 判断处理器大小端大小端问题是嵌入式面试必考题。最简单的方法是用联合体int check_endian() { union { int i; char c[4]; } u {0x12345678}; return u.c[0] 0x78; // 返回1为小端0为大端 }在Cortex-M系列中这个函数总是返回1小端模式。但在网络协议处理时比如TCP/IP头部的16位字段必须考虑大小端转换。2.2 整数与字符串互转atoi()的工业级实现要考虑以下异常情况前导空格正负号非数字字符数值溢出int my_atoi(const char* s) { while (isspace(*s)) s; // 跳过空格 int sign (*s -) ? -1 : 1; if (*s || *s -) s; long long res 0; while (isdigit(*s)) { res res * 10 (*s - 0); if (res * sign INT_MAX) return INT_MAX; if (res * sign INT_MIN) return INT_MIN; s; } return (int)(res * sign); }这个实现有几个优化点使用long long防止32位溢出提前进行溢出判断支持最大最小边界值对应的itoa()实现void my_itoa(int n, char* s) { int i 0, sign n; if (sign 0) n -n; do { s[i] n % 10 0; } while ((n / 10) 0); if (sign 0) s[i] -; s[i] \0; // 反转字符串 int j 0; while (j i - 1) { char tmp s[j]; s[j] s[--i]; s[i] tmp; } }在RT-Thread实测这个实现比sprintf()快3倍以上特别适合资源受限的MCU环境。3. 链表操作实战技巧3.1 单链表反转链表反转是面试最高频考题递归和非递归都要掌握。先看非递归版本struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL, *curr head; while (curr) { struct ListNode* next curr-next; curr-next prev; prev curr; curr next; } return prev; }这个版本只用了3个指针空间复杂度O(1)。在STM32F103上测试反转100个节点的链表耗时约200us。递归版本更简洁但容易栈溢出struct ListNode* reverseListRecursive(struct ListNode* head) { if (!head || !head-next) return head; struct ListNode* newHead reverseListRecursive(head-next); head-next-next head; head-next NULL; return newHead; }当链表长度超过1KB时这个版本在FreeRTOS任务中会触发栈溢出。建议在资源充足的Linux环境下使用。3.2 快慢指针应用快慢指针是解决链表问题的神器典型应用包括检测环形链表找中间节点删除倒数第N个节点环形链表检测bool hasCycle(struct ListNode *head) { struct ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }这个算法时间复杂度O(n)空间复杂度O(1)。我在一次面试中被要求证明其正确性——关键点在于如果存在环快指针最终会追上慢指针就像操场跑圈时快跑者会套圈慢跑者。4. 排序与查找优化4.1 嵌入式场景下的排序选择在资源受限的嵌入式系统中排序算法的选择要考虑内存占用时间复杂度代码复杂度快速排序在平均情况下表现最好void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } int partition(int arr[], int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high - 1; j) { if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; }在STM32F407上测试对1000个随机数排序耗时约15ms。如果内存极度紧张比如只有2KB RAM可以考虑选择排序虽然时间复杂度O(n²)但空间复杂度O(1)。4.2 二分查找的边界处理二分查找看似简单但边界条件极易出错。经典实现int binarySearch(int arr[], int size, int target) { int left 0, right size - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (arr[mid] target) return mid; if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }几个关键点循环条件是left right不是left rightmid计算用left (right - left)/2而不是(left right)/2防止大数相加溢出left和right的更新要±1避免死循环在嵌入式系统中如果数据是有序但静态的比如设备参数表可以考虑使用插值查找平均时间复杂度能降到O(log log n)。