数据结构基础

这篇笔记只回答三件事：数据怎么组织、操作怎么定义、效率怎么判断。读完后，脑子里应该留下一个清晰框架：数据结构管组织方式，算法管操作方法，复杂度管效率上界。

什么是数据结构？

数据结构是带有结构特性的数据元素集合。它研究的是数据的逻辑结构、物理结构以及它们之间的关系，并为这种结构定义相适应的运算。

常见分类可以先按逻辑结构来记：

• 线性结构：结点之间是一对一的线性关系，通常只有一个开始结点和一个终端结点。
• 非线性结构：结点之间存在多个对应关系，一个结点可能有多个前驱或多个后继。

常见入门结构

• 栈 Stack
  • 只允许在一端插入和删除，这一端叫栈顶 Top，另一端叫栈底 Bottom
  • 特点：先进后出 LIFO
• 队列 Queue
  • 一端插入、另一端删除，删除端叫队头 front，插入端叫队尾 rear
  • 特点：先进先出 FIFO
• 数组 Array
  • 同类型元素按顺序存放在连续空间里
  • 特点：支持下标访问，定位快
• 链表 Linked List
  • 元素通过指针串起来，物理地址不一定连续
  • 特点：插删灵活，但随机访问不如数组快

进阶一点的结构

• 散列表 / 哈希表
  • 根据关键码 key 直接定位记录，靠的是散列函数
  • 适合“查找优先”的场景
• 链式哈希表
  • 每个桶里挂一条链表
  • 发生冲突时，把不同元素放进同一个桶里
  • 当桶不够用时，需要扩容并重新散列

为什么学数据结构和算法？

• 提高程序运行效率
• 提高空间利用效率
• 提高解决问题的能力

很多时候，程序慢不一定是语言慢，而是数据组织方式不合适。

如何描述数据结构？

最常用的方法是 抽象数据类型 ADT。

ADT 只描述两件事：

• 数据对象集
• 相关的操作集

它关心的是“是什么”，不关心“如何实现”。

也就是说：

• 与机器无关
• 与物理存储结构无关
• 与具体算法和编程语言无关

一个矩阵 ADT 的例子

以 m x n 的矩阵为例，可以把它看成由若干三元组 <a, i, j> 组成的数据对象，其中：

• a 是元素值
• i 是行号
• j 是列号

操作集

• Create(m, n)：创建一个空矩阵
• GetMaxRow()：返回总行数
• GetMaxCol()：返回总列数
• GetEntry(i, j)：返回第 i 行第 j 列的元素
• Add(A, B)：矩阵加法
• Multiply(A, B)：矩阵乘法

这类定义的重点不是代码，而是先把“对象和操作”讲清楚。

什么是算法？

算法 Algorithm 是一个有限指令集。它至少要满足这些特性：

• 输入：接受若干输入，有些问题也可以没有输入
• 输出：产生结果
• 有穷性：在有限步后结束
• 确定性：每一步都明确无歧义
• 可行性：每一步都能在有限时间内完成

什么是好的算法？

评价算法，最常看的就是两件事：

• 时间复杂度：程序运行要花多久
• 空间复杂度：程序执行要占多少额外内存

一般来说，真正拉开差距的，往往不是“能不能做”，而是“做得快不快、省不省”。

复杂度的渐进表示法

分析复杂度时，通常只关心增长趋势，不纠结常数和低阶项。

• O(g(n))：上界，表示最坏情况常用
• Ω(g(n))：下界，表示最好情况常用
• Θ(g(n))：紧界，表示上下界同阶

常见增长阶

函数	n=1	n=2	n=4	n=8	n=16	n=32
1	1	1	1	1	1	1
log n	0	1	2	3	4	5
n	1	2	4	8	16	32
n log n	0	2	8	24	64	160
n^2	1	4	16	64	256	1024
n^3	1	8	64	512	4096	32768
2^n	2	4	16	256	65536	4294967296
n!	1	2	24	40326	2092278988000	26313 * 10^33

两个小结论

• 先看最高阶项，再看系数和常数，最后再做比较
• T1 + T2 取两者中较大的阶
• T1 * T2 约等于两个阶相乘

复杂度分析小窍门

• for 循环的时间复杂度 = 循环次数 × 循环体复杂度
• if-else 的复杂度，取条件判断和各分支里最大的那个
• 递归要先看“每次做了几次递归调用”，再看“每次调用额外做了什么”
• 如果一个算法的主导项是 n^k，通常就可以记成 O(n^k)

应用实例：最大子列和

问题：给定整数序列 {A1, A2, ..., An}，求连续子列的最大和。

常见思路可以这样记：

1. 暴力枚举：把所有子序列都算一遍
2. 优化枚举：减少重复计算
3. 分而治之：把问题拆成左右两半
4. 在线处理：每读入一个数就即时更新答案

这个问题最值得记住的不是答案本身，而是“不同算法，复杂度差很多”。

应用实例：多项式求值

题目：计算

f(x) = a0 + a1x + a2x^2 + ... + anx^n

一种直接写法是逐项乘方，思路简单，但通常不够省。

更好的写法是霍纳法则：

public static double f1(int n, double[] a, double x) {
    double res = a[n];
    for (int i = n - 1; i >= 0; i--) {
        res = res * x + a[i];
    }
    return res;
}

它的优点很直接：

• 只做一层循环
• 时间复杂度是 O(n)
• 实现短，效率高

最后记一句

数据结构决定“怎么放”，算法决定“怎么做”，复杂度决定“做得值不值”。

这三个词串起来，基本就是计算机基础里最核心的那条线。