一、数据结构概述
各位同学，欢迎来到《C语言数据结构实战》的第一章。我是你们的老朋友，一个在嵌入式领域摸爬滚打了十几年的工程师。今天咱们要聊的，是数据结构的“开场白”——看似基础，但说实话，很多人在这个阶段就埋下了坑。
数据结构是什么？我习惯用一个比喻：你想想看，程序就像一座工厂，数据就是原材料。而数据结构，就是这些原材料怎么堆放、怎么流转的规则。没有好的规则，工厂再大也是乱糟糟的。
1.1 数据结构的概念
数据结构，说白了就是计算机存储、组织数据的方式。它包含三个要素：
- 逻辑结构：数据元素之间的逻辑关系。比如你手机里的联系人列表，谁在前谁在后，这就是逻辑关系。
- 存储结构：数据在内存里怎么放的。是挨着放（顺序存储），还是东一个西一个用指针串起来（链式存储）。
- 运算：对数据能做什么操作。增、删、改、查，就这四样。
核心要点：逻辑结构是“怎么看”，存储结构是“怎么存”。同一个逻辑结构，可以用不同的存储结构实现。我在项目中见过有人把链表硬写成数组，结果插入删除时痛苦不堪——这就是没分清逻辑和存储的区别。
1.2 逻辑结构与物理结构
逻辑结构分四种：
- 集合结构：元素之间“没关系”，就是一堆东西放一起。比如一篮子鸡蛋。
- 线性结构：元素一对一的关系。像排队买奶茶，一个接一个。
- 树形结构：一对多的关系。比如公司的组织架构，一个老板管好几个经理。
- 图形结构：多对多的关系。比如地铁线路图，一个站可以连多个站。
物理结构就两种：
- 顺序存储：用数组实现。优点是随机访问快，缺点是插入删除要挪动大量元素。
- 链式存储：用指针实现。优点是插入删除快，缺点是不能随机访问。
我的经验：在嵌入式开发中，内存往往很金贵。我建议你优先考虑顺序存储，除非你确定要频繁插入删除。我曾经在一个传感器数据采集项目里，因为用了链表导致内存碎片化严重，最后不得不改成环形缓冲区——嗯，这就是教训。
1.3 抽象数据类型（ADT）
抽象数据类型，英文叫 Abstract Data Type，简称 ADT。这个概念听起来高大上，其实很简单：它只关心“能干什么”，不关心“怎么干”。
举个例子：栈（Stack）。你只需要知道它能 push（压入）和 pop（弹出），至于底层是用数组还是链表实现的，ADT 不管。这就是“抽象”的含义——把实现细节藏起来。
在C语言里，我们通常用结构体加函数指针来实现ADT。比如：
// 定义一个栈的ADT
typedef struct {
int *data; // 数据存储区
int top; // 栈顶指针
int capacity; // 容量
void (*push)(struct Stack*, int);
int (*pop)(struct Stack*);
} Stack;注意：ADT 不是具体的代码，而是一种设计思想。我见过很多新手一上来就写具体实现，结果后面想换存储结构，代码改得面目全非。先定义 ADT，再写实现，这是专业做法。
1.4 算法效率度量
算法效率，说白了就是“快不快”和“省不省”。我们通常用两个指标来衡量：
时间复杂度
时间复杂度不是代码跑了几秒，而是操作次数随数据规模增长的趋势。我们用大O表示法：
| 大O表示 | 含义 | 例子 |
|---|---|---|
| O(1) | 常数时间 | 数组随机访问 |
| O(log n) | 对数时间 | 二分查找 |
| O(n) | 线性时间 | 遍历数组 |
| O(n log n) | 线性对数时间 | 快速排序 |
| O(n²) | 平方时间 | 冒泡排序 |
为什么会这样？因为当数据量翻倍时，不同复杂度的操作次数增长完全不同。O(1) 的算法，数据量翻倍，操作次数不变。O(n²) 的算法，数据量翻倍，操作次数变成4倍。你想想看，如果数据量是100万，O(n²) 的算法基本就跑不动了。
空间复杂度
空间复杂度衡量的是算法运行时占用的内存大小。同样用大O表示：
- O(1)：只用了固定几个变量。比如交换两个数的值。
- O(n)：需要额外申请一个数组。比如归并排序的临时数组。
- O(n²)：需要二维数组。比如图的邻接矩阵。
避坑指南：我曾经在一个内存只有64KB的MCU上做项目，用了递归算法。递归每次调用都会压栈，结果栈空间爆了，程序直接跑飞。从那以后，我在嵌入式项目里尽量不用递归，或者严格控制递归深度。空间复杂度不是闹着玩的。
知识体系总览
下面这张图，是我画的数据结构第一章的知识脉络。你可以把它当作一张地图，后面每学一个知识点，都能在这张图上找到位置。
学习建议：这一章的内容，我建议你反复看三遍。第一遍通读，第二遍对照代码理解，第三遍合上书自己画一遍知识图谱。数据结构不是背出来的，是“用”出来的。后面每一章我都会带着你写代码，但前提是这一章的概念你得吃透。
好了，第一章的内容就到这里。记住：数据结构是程序的骨架，算法是灵魂。骨架歪了，后面再漂亮的代码也站不住。咱们下一章见。