一、数据结构与算法概述
各位同学好，我是老林。在嵌入式这行摸爬滚打了十几年，今天咱们来聊聊数据结构和算法。说实话，我刚入行时也觉得这东西太理论，不如直接写代码来得实在。直到有一次，我负责一个车载导航项目，地图数据加载慢得像蜗牛爬……嗯，从那以后我才真正明白——数据结构选不对，算法写不好，再牛的硬件也白搭。
1.1 数据结构的概念
数据结构，说白了就是计算机存储、组织数据的方式。你想想看，数据就像一堆散落的零件，数据结构就是你的工具箱——怎么放、怎么拿、怎么归类，全看你怎么设计。
我个人习惯把数据结构分成两类：
- 逻辑结构：数据元素之间的逻辑关系。比如线性结构（数组、链表）、树形结构（二叉树）、图形结构（图）等。
- 存储结构：数据在内存里实际怎么放的。常见的有顺序存储（数组）和链式存储（链表）。
举个例子，你在嵌入式开发里经常要处理传感器数据流。用数组存，访问快但插入删除麻烦；用链表存，灵活但指针开销大。选哪个？得看你的实时性要求。
核心要点：数据结构 = 数据 + 数据之间的关系 + 对数据的操作。三者缺一不可。
1.2 算法的概念
算法是什么？就是解决问题的步骤和方法。我经常跟团队说：算法不是数学题，而是你写代码时的思路。
一个合格的算法，得满足这几点：
- 有穷性：不能无限循环下去，得有个头
- 确定性：每一步做什么，清清楚楚，不含糊
- 可行性：用现有的工具和资源能实现
- 输入输出：有数据进来，有结果出去
我在项目中遇到过最典型的例子——冒泡排序。刚毕业那会儿觉得它简单好用，后来发现处理几千个数据时，CPU占用率直接飙到90%。这才意识到：算法选不对，性能就是灾难。
1.3 时间复杂度
时间复杂度，衡量的是算法执行时间随数据规模增长的变化趋势。注意，不是具体跑了多少秒，而是「趋势」。
为什么这么说？因为同样的算法，在不同硬件上跑的时间不一样。但趋势是固定的——数据量翻倍，时间翻几倍？这个才是关键。
来看个简单的例子：
// 计算1到n的和
int sum(int n) {
int result = 0;
for (int i = 1; i <= n; i++) {
result += i;
}
return result;
}这个循环执行了n次，时间复杂度就是O(n)。如果改成嵌套循环：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 操作
}
}那就是O(n²)。数据量一大，性能直接崩。
我的经验：在嵌入式开发中，O(n)和O(n²)的差距，可能就是系统能不能跑起来的区别。我曾经在一个实时控制项目里，就因为一个O(n²)的查找算法，导致中断响应超时……后来改成哈希表，问题秒解。
1.4 空间复杂度
空间复杂度，衡量的是算法运行时占用的内存空间。嵌入式开发尤其要关注这个——单片机内存就那么几KB，你一个算法吃掉一半，别的功能还怎么跑？
空间复杂度的计算和时间复杂度类似，也是看趋势。比如：
// 创建一个n个元素的数组
int* arr = (int*)malloc(n * sizeof(int));这个空间复杂度就是O(n)。如果只是几个临时变量，那就是O(1)。
注意：空间复杂度和时间复杂度往往需要权衡。用空间换时间（比如查表法），或者用时间换空间（比如压缩算法）。具体怎么选，得看你的资源瓶颈在哪里。
1.5 大O表示法
大O表示法，就是用来描述算法效率的「速记符号」。它关注的是最坏情况下的增长趋势。
常见的几种复杂度：
| 大O表示 | 名称 | 例子 |
|---|---|---|
| O(1) | 常数阶 | 数组随机访问 |
| O(log n) | 对数阶 | 二分查找 |
| O(n) | 线性阶 | 遍历数组 |
| O(n log n) | 线性对数阶 | 快速排序 |
| O(n²) | 平方阶 | 冒泡排序 |
| O(2ⁿ) | 指数阶 | 递归斐波那契 |
你想想看，n=1000时，O(n)只要1000步，O(n²)要100万步。差距就是这么明显。
记住：大O表示法忽略常数和低阶项。比如3n²+5n+2，大O就是O(n²)。因为当n足够大时，低阶项的影响可以忽略不计。
1.6 本章知识体系
下面这张图，是我自己梳理的本章知识结构。你看一遍，心里就有谱了。
这张图把本章的核心内容串起来了。数据结构是基础，算法是方法，复杂度分析是工具，大O表示法是语言。四者结合，你才能写出高效、可靠的代码。
避坑指南：我曾经在一个项目里，用链表实现了FIFO队列，结果每次插入都要遍历找尾节点，时间复杂度O(n)。后来改成循环链表+尾指针，直接O(1)。你看，数据结构选对了，性能提升立竿见影。
好了，第一章就到这里。记住：数据结构与算法不是纸上谈兵，而是你每天写代码时都要面对的现实问题。多思考、多实践，慢慢你就能找到感觉。
公众号:蓝海资料掘金营，微信deep3321