第一章 数据结构导论

📖 ⏱️ 预计阅读时长

---

1. 为什么要学习数据结构

数据结构不是单纯记忆“数组、链表、树、图”这些名词，而是研究“数据应当如何组织，程序才能更高效、更稳定、更容易维护”的一门基础课程。对于计算机专业学习而言，数据结构连接着程序设计、算法分析、数据库、操作系统、编译原理以及软件工程，是理解软件世界内部运行规律的重要桥梁。

在实际程序设计中，问题往往并不在于“能不能把功能写出来”，而在于“能不能在合理时间和合理空间内把功能写出来”。例如，同样是保存一批学生成绩，若采用不同组织方式，后续的查找、插入、统计和排序成本会有明显差异。数据结构正是研究这种差异产生原因的课程。

上图体现了学习数据结构时应当建立的完整链条：现实问题不会直接变成代码，中间必须经过抽象、组织和分析。如果缺少“结构”这一环节，程序往往只能停留在能运行但不高效的水平。

2. 什么是数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，以及定义在该集合上的一组操作。简言之，数据结构研究两个问题：第一，数据怎样组织；第二，组织好的数据怎样高效地被访问、插入、删除、修改和统计。

例如，学生成绩数据如果采用无序线性存放，那么查找某个学生可能需要逐个比对；如果按照学号建立有序结构或索引结构，则查找效率会显著提高。由此可见，数据结构并不是数据的“外形描述”，而是与处理效率直接相关的组织方式。

3. 数据结构研究的三个层面

在大学课程中，通常从以下三个层面理解数据结构。

3.1 逻辑结构

逻辑结构研究数据元素之间“在概念上”的关系，与具体存储无关。例如元素之间是前后相连、层次依赖，还是复杂网状关联，都属于逻辑结构问题。

3.2 存储结构

存储结构研究数据在计算机内存中的实际存放方式。相同的逻辑关系，可以用连续存储实现，也可以用链式方式实现。不同存储结构会直接影响访问效率和空间使用。

3.3 运算结构

运算结构研究在某种结构上适合执行哪些操作，以及这些操作的时间和空间代价。离开操作谈结构没有意义，因为结构的价值最终要通过操作效率体现出来。

逻辑结构回答“它们之间是什么关系”，存储结构回答“它们在内存里怎么放”，运算结构回答“这样放以后，哪些操作快，哪些操作慢”。

4. 逻辑结构分类

4.1 集合结构

集合中的元素除了“同属一个集合”之外，彼此之间没有明显的顺序关系或层次关系。例如一组城市名称、一组考试科目、一组用户标签等。

4.2 线性结构

线性结构中的元素通常具有一对一的前驱和后继关系，形成单线条排列。例如线性表、栈、队列、串等都属于线性结构。

4.3 树形结构

树形结构中的元素之间存在一对多的层次关系，适合描述组织架构、目录系统、表达式结构、数据库索引等场景。

4.4 图结构

图结构中的元素之间可以存在多对多关系，适合描述交通网络、社交关系、课程先修关系、通信网络等复杂关联。

5. 存储结构分类

5.1 顺序存储

把逻辑上相邻的元素尽量存放在物理地址也相邻的存储单元中。其典型代表是数组和顺序表。优点是支持快速随机访问，缺点是插入删除时往往需要移动大量元素。

5.2 链式存储

元素存储位置不必连续，通过指针或引用记录逻辑关系。链表是最典型的链式存储结构。优点是插入删除较灵活，缺点是访问某个中间位置时通常不能直接跳转。

5.3 索引存储

在存储数据的同时建立附加索引，通过索引定位目标元素。数据库索引、查找表等都体现了这种思想。

5.4 散列存储

通过哈希函数把关键字映射到某个地址或桶中，以期在平均意义上快速完成查找、插入和删除。哈希表是此类结构的代表。

6. 抽象数据类型与具体实现

抽象数据类型强调“从用户角度看，结构应该提供哪些功能”，而不强调“底层具体怎样实现”。例如栈的核心特征是后进先出，用户只关心 push、pop、top 等操作，不必首先关心它是用数组实现还是用链表实现。

这一区分非常重要。因为同一个抽象数据类型往往可以有多种实现方式，而不同实现方式的性能会不同。例如：

1. 栈可以用顺序表实现，也可以用链表实现。
2. 队列可以用数组实现，也可以用链表实现。
3. 映射表可以用平衡树实现，也可以用哈希表实现。

理解 ADT 的意义，在于避免把“功能”和“实现”混为一谈。学习数据结构时，应当先把结构的行为规则理解清楚，再讨论它的具体编码方式。

7. 算法效率与复杂度

评价数据结构是否“好用”，不能只看能不能完成操作，还要看完成操作的代价。常用评价指标包括：

1. 时间复杂度：衡量算法执行时间随数据规模增长的变化趋势。
2. 空间复杂度：衡量算法在执行过程中额外占用存储空间的变化趋势。

7.1 常见渐进记号

记号	含义	常见理解
O(f(n))	上界	最常见，用于描述最坏情况下的增长量级
Ω(f(n))	下界	描述至少需要达到的增长量级
Θ(f(n))	紧确界	同时给出上下界

7.2 常见复杂度层次

1. O(1)：常数时间，例如数组按下标访问。
2. O(log n)：对数时间，例如平衡搜索树查找。
3. O(n)：线性时间，例如顺序查找。
4. O(n log n)：典型高效排序复杂度。
5. O(n^2)：常见于简单双重循环算法。

需要注意，复杂度分析关注的是“数量级”，不是某一次运行的绝对秒数。实际程序性能还会受到常数因子、内存局部性、语言运行时和硬件环境的影响。

7.3 为什么复杂度分析离不开数据结构

很多初学者会把复杂度分析理解为算法课的内容，而把数据结构理解为“存东西的方法”。这种认识并不完整。实际上，任何复杂度都离不开底层结构。例如：

1. 数组按下标访问之所以是 O(1)，依赖的是顺序存储。
2. 链表按位置访问之所以是 O(n)，根源在于节点分散，只能沿指针逐步前进。
3. 二叉搜索树平均查找较快，依赖的是左小右大的结构约束。
4. 哈希表平均查找很快，依赖的是哈希函数与桶分布。

因此，复杂度不是附着在算法外部的标签，而是结构特征在操作层面的直接表现。

8. 本章小结

本章解决的是学习数据结构之前必须先想清楚的几个问题：数据结构研究什么、数据结构有哪些基本分类、逻辑结构与存储结构有何区别、为什么必须重视复杂度分析。只有把这些基础观念建立起来，后续学习线性表、树、图、哈希表时，才能真正理解每种结构的价值所在。