数据结构并不是一份需要死记硬背的名词表，而是一套解决问题的方法：先确认数据之间的关系，再选择合适的存储方式，最后围绕这些数据设计高效、可靠的操作。本文从数据结构与算法的基本概念出发，建立后续学习顺序表、链表、栈、队列、树和图所需要的整体框架。

1. 什么是数据结构

数据结构（Data Structure）是具有一种或多种特定关系的数据元素的集合，以及这些元素在计算机中的组织方式。

理解一个数据结构时，应同时观察三个层面：

1. 逻辑结构：元素之间是什么关系；
2. 存储结构：这种关系如何放进内存；
3. 数据运算：允许执行哪些操作，以及操作应满足什么约束。

例如，一个班级的学生名单在逻辑上是线性的；它既可以连续存放在数组中，也可以分散存放并用指针连接成链表。逻辑结构相同，不代表物理存储方式相同。

2. 数据的逻辑结构

按元素之间的关系，常见逻辑结构可以分为四类：

逻辑结构描述的是问题本身，而不是某种编程语言中的类型。数组是存储工具，线性表才是逻辑模型；二者不能简单画等号。

3. 数据的存储结构

3.1 顺序存储

顺序存储把元素放在一段连续内存中。数组是最典型的实现：

1

int scores[5] = {90, 82, 95, 76, 88};

已知下标即可通过“首地址 + 下标 × 元素大小”定位元素，因此随机访问通常为 $O(1)$。代价是中间插入和删除可能需要移动大量元素，动态扩容也可能触发整体搬迁。

3.2 链式存储

链式存储允许节点分散在内存中，通过指针表达逻辑关系：

1
2
3
4

typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

如果已经拿到插入位置附近的节点，修改链接通常只需 $O(1)$；但按序号查找第 $i$ 个元素需要从头沿指针遍历，复杂度为 $O(n)$。链表还要承担指针字段、动态分配和较差缓存局部性的成本。

3.3 索引存储与散列存储

• 索引存储：额外建立索引项，用空间换取更快的定位能力，数据库索引就是典型例子；
• 散列存储：通过散列函数把键映射到桶，理想情况下查找、插入和删除的平均复杂度可达 $O(1)$，但最坏情况仍可能退化到 $O(n)$。

一种数据结构可以组合多种存储方式。例如哈希表的桶数组采用顺序存储，处理冲突的链表则采用链式存储。

4. 什么是算法

算法（Algorithm）是一个定义明确、能够在有限步骤内把输入转换成输出的计算过程。一个合格算法通常具有以下特征：

• 有穷性：执行有限步后结束；
• 确定性：每一步含义明确；
• 可行性：每一步都能由基本操作实现；
• 输入与输出：可以没有显式输入，但至少产生一个结果；
• 正确性：对约定范围内的合法输入给出正确输出。

下面的线性查找体现了最小而完整的算法结构：

1
2
3
4
5
6
7
8
9
10
11

#include <stddef.h>

int linear_search(const int a[], size_t n, int target)
{
    for (size_t i = 0; i < n; ++i) {
        if (a[i] == target) {
            return (int)i;
        }
    }
    return -1;
}

它对无序数组也适用，但最坏情况下要检查全部 $n$ 个元素，因此时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

5. 抽象数据类型：把“做什么”与“怎么做”分开

抽象数据类型（Abstract Data Type，ADT）只规定数据对象、操作集合和语义，不限定具体实现。

以栈为例，它的抽象接口可以写成：

1
2
3
4
5

Stack:
    push(x)   将 x 放到栈顶
    pop()     删除栈顶元素
    top()     读取栈顶元素
    empty()   判断栈是否为空

栈可以用动态数组实现，也可以用链表实现。调用者依赖的是“后进先出”的行为，而不是内部到底使用数组还是节点。这种分层思维能降低耦合，也方便在不改变上层代码的前提下替换实现。

6. 如何评价一种实现

不能只问“它快不快”，而应明确以下条件：

例如，“链表插入是 $O(1)$”必须附带前提：已经获得合法插入位置。如果需要先查找位置，总成本仍可能是 $O(n)$。同样，“动态数组尾插是 $O(1)$”通常指均摊复杂度；触发扩容的单次操作仍为 $O(n)$。

7. 数据结构中的不变量

不变量是每次公开操作前后都必须成立的条件。设计实现时先写出不变量，往往比直接写代码更可靠。

一些典型不变量如下：

• 动态顺序表满足 size <= capacity；
• 非空链式队列的 rear->next == NULL；
• 空队列满足 front == NULL && rear == NULL；
• 二叉搜索树左子树的键小于根，右子树的键大于根（具体还要约定重复键策略）；
• 小根堆中任意父节点的值不大于孩子节点。

每个插入、删除和扩容操作，都应在结束时恢复这些不变量。

8. 一套可执行的学习方法

8.1 先画逻辑，再写代码

链表反转、树的递归遍历、循环队列下标变化都适合先画图。图中应标出操作前后的节点、指针和边界，而不是只画一个静态结构。

8.2 每个结构都回答五个问题

1. 它解决什么问题？
2. 核心不变量是什么？
3. 增、删、查、改的复杂度如何？
4. 最容易出错的边界是什么？
5. 有哪些可替代结构，取舍是什么？

8.3 自己实现，但不要停在“能运行”

实现后至少测试：

• 空结构上的查询和删除；
• 第一次插入、删除最后一个元素；
• 连续扩容；
• 头部、中间、尾部操作；
• 重复值、负数和大规模输入；
• 释放后是否存在泄漏、悬空指针或重复释放。

编译时建议开启严格警告，并结合 AddressSanitizer、UndefinedBehaviorSanitizer 等工具检查内存错误与未定义行为。

9. 学习路线

建议按依赖关系推进：

1. 时间复杂度与空间复杂度；
2. 顺序表与链表；
3. 栈与队列；
4. 树、二叉树与堆；
5. 排序与查找；
6. 哈希表、二叉搜索树和图；
7. 在真实问题中练习递归、回溯、分治、贪心和动态规划。

数据结构的核心不是记住多少接口，而是能够根据访问模式、数据规模和边界条件做出选择。先建立模型，再分析复杂度，最后用代码维护不变量，这三步会贯穿整个学习过程。