数据结构基础：从概念到复杂度分析

大家好，我是你们的老朋友。今天咱们来聊聊数据结构的基础知识。说实话，我刚开始学嵌入式那会儿，觉得数据结构就是一堆理论，跟写代码没啥关系。直到有一次，我在一个实时控制项目里，因为用了不合适的队列实现，导致系统响应延迟了整整200毫秒——嗯，从那以后，我再也不敢小看数据结构了。

什么是数据结构？

数据结构，说白了就是计算机存储、组织数据的方式。你想想看，我们写程序，本质上就是在处理数据。数据怎么放、怎么取、怎么找，这些就是数据结构要解决的问题。

我个人习惯把数据结构理解成"数据的容器"。就像你家里有衣柜、书架、工具箱一样，不同的东西要放在不同的容器里。代码里的数据也一样——整数、字符串、结构体，各有各的存放方式。

逻辑结构与物理结构

这里有个容易混淆的概念，我当年也踩过坑——逻辑结构和物理结构。

逻辑结构

逻辑结构是数据元素之间的抽象关系，跟计算机怎么存没关系。它分为四类：

• 集合结构：数据元素之间"同属一个集合"，没别的联系。就像一筐苹果，彼此独立。
• 线性结构：数据元素是一对一的关系。比如排队买饭，前面一个人，后面一个人。队列、栈都属于线性结构。
• 树形结构：一对多的关系。比如公司的组织架构，一个经理管好几个员工。
• 图形结构：多对多的关系。比如地铁线路图，一个站可以连接多个站。

我在项目中遇到过最典型的例子：用队列管理串口接收的数据包。数据包一个接一个来，先进先出，这就是线性结构。如果换成树形结构去管理，那就乱套了。

物理结构

物理结构是数据在内存中实际怎么存的。就两种：

物理结构	特点	典型应用
顺序存储	用连续的内存空间，像数组	数组实现的栈、队列
链式存储	用不连续的内存，靠指针连接	链表实现的栈、队列

举个例子：你有一排连续的座位，大家挨着坐——这是顺序存储。如果座位不连续，但每个人都知道下一个人坐哪儿——这就是链式存储。

算法复杂度分析（大O表示法）

好，接下来是重头戏——大O表示法。很多初学者觉得这玩意儿抽象，其实没那么复杂。

大O表示法，说白了就是衡量算法效率的"尺子"。它不关心具体执行了多少条指令，只关心当数据量 n 变大时，算法执行时间（或占用空间）的增长趋势。

常见的时间复杂度

大O表示	名称	例子	我的评价
O(1)	常数阶	数组随机访问	理想状态，跟数据量无关
O(log n)	对数阶	二分查找	非常优秀，数据量翻倍，时间只加一点点
O(n)	线性阶	遍历数组	可以接受，数据量翻倍时间也翻倍
O(n log n)	线性对数阶	快速排序	常见排序算法的天花板
O(n²)	平方阶	冒泡排序	数据量一大就崩，慎用
O(2ⁿ)	指数阶	递归斐波那契	能不用就别用

为什么会这样？我举个例子。假设你有一个数组，要找某个元素：

• 如果数组无序，你得从头到尾遍历——O(n)。
• 如果数组有序，用二分查找——O(log n)。

n=1000时，O(n)要查1000次，O(log n)只要查10次。差距就这么大。

空间复杂度

除了时间，我们还得关心内存。嵌入式系统内存有限，空间复杂度同样重要。

空间复杂度也是用大O表示。比如：

• O(1)：只用了几个临时变量，跟数据量无关。
• O(n)：需要额外申请一个跟数据量等长的数组。

我建议你在写代码时，养成一个习惯：先想清楚时间复杂度和空间复杂度，再动手写代码。这能帮你避免很多后期优化的大坑。

知识体系总览

下面这张图，是我自己整理的本章知识结构。你可以把它当成一个"地图"，学完一章回头看看，心里更有底。

小结

这一章我们聊了三个核心概念：

• 数据结构：数据怎么组织、怎么存、怎么操作。
• 逻辑结构与物理结构：逻辑结构是"关系"，物理结构是"实现"。
• 算法复杂度：用大O表示法衡量时间和空间效率。

嗯，这些概念看起来简单，但它们是后面所有内容的基础。你想想看，队列和栈本身就是线性结构，它们的物理实现可以是数组（顺序存储）也可以是链表（链式存储）。而你在选择用哪种实现时，本质上就是在做复杂度分析的权衡。

下一章，我们会正式进入队列的世界。到时候我会带着你手写代码，从底层实现一个完整的队列。准备好了吗？

---

公众号:蓝海资料掘金营，微信deep3321