数据结构：从存储到抽象

本篇要点

本篇是 C 语言数据结构学习的总导航。在正式进入具体的数据结构之前，先回答三个根本问题：

数据结构到底是什么？为什么需要多种数据结构？如何衡量一个数据结构的好坏？

具体涵盖：

• 程序 = 数据结构 + 算法：这句经典名言的真正含义
• 什么是数据结构：数据怎么“摆“、怎么“取“——核心框架：物理存储 × 逻辑规则
• 为什么需要不同的数据结构：数组的三大优势与三大短板，没有万能结构
• 时间复杂度：大 O 记号、三种循环模式、常见复杂度对比表
• 空间复杂度：衡量内存开销的工具
• 本篇学习路线：从数据存储结构（第十八章）到通用抽象数据结构（第十九章）

一、程序 = 数据结构 + 算法

计算机科学界有一句广为流传的名言：

程序 = 数据结构 + 算法

—— 尼克劳斯·维尔特（Niklaus Wirth），Pascal 语言之父，图灵奖得主

这句话揭示了写程序的本质——只做两件事：

同一个问题，选择不同的数据组织方式，算法的难度和效率天差地别：

• 数组查第 5 号同学：scores[4]，一步搞定。
• 数组中间插入转学生：后面 45 人全部往后挪一格。
• 链表插入：改一个指针就好，但找第 5 号又得从头数起。

核心结论：数据结构就是研究“数据怎么组织“的学问。学好它，才能在面对具体问题时做出正确的选择。

二、什么是数据结构

2.1 一句话定义

数据结构 = 数据怎么“摆“、怎么“取“。

2.2 三个生活例子

三者的共同问题：数据多了，怎么放才能又快又准地找到、添加、删除？ 答案不同，因为场景需求不同。

2.3 核心框架：物理存储 + 逻辑规则

深入一层——数据最终都在内存里。针对本篇讨论的线性结构，可以先用两类常见存储方式建立分析框架：

链式存储的本质：每个节点除了存数据，还携带“其他节点在哪“的信息。单链表（只记后继）和双链表（记前驱+后继）只是这种思想最常用的两种实现形式——记录几个指针、指向谁，都是可以根据需求自由组合的。本教程后续链表代码统一采用带头节点写法：头节点不保存有效数据，真实数据从 head->next 开始。

物理存储之上，才是逻辑规则。 抛开底层细节，给数据“加规则“：

核心公式：数据结构 = 物理存储方式 + 逻辑组织规则

• 物理层决定效率上限：能不能 O(1) 随机访问？修改要不要搬移数据？记录几个关系指针？
• 逻辑层决定行为：LIFO 还是 FIFO？单向还是双向？

整个数据结构的学习，就是在反复体会这两层如何相互作用。

三、为什么需要不同的数据结构

3.1 数组的三大优势

在“数据量确定、主要操作为读取和遍历“的场景下，数组几乎是最优解。

3.2 数组的三大短板

考虑这个需求：维护一份待办事项列表，随时添加和删除。

核心认知：数组的短板不是设计缺陷，而是结构特性决定的——连续存放带来 O(1) 随机访问，也带来搬移代价。鱼和熊掌不可兼得。

3.3 数据结构的分类全景

放眼全局，数据结构种类繁多，但追根溯源：

数组和链表是实现数据结构时最常见的两类基础存储方式。栈、队列、树和图等抽象结构，可以根据需求用数组、链式节点或二者组合实现。

数组（连续存储）
  ├── 加规则"只能一端进出"           → 栈
  ├── 加规则"一端进一端出 + 取模绕回" → 环形队列
  └── 排序 + 二分查找                → O(log n) 查找

链表（链式存储）
  ├── 节点只记后继                    → 单链表
  ├── 节点记前驱+后继                 → 双链表
  ├── 加规则"一端进一端出"            → 链式队列
  ├── 节点记录子节点关系              → 树的一种实现
  └── 节点记录任意邻接关系            → 图的一种实现

链式存储的本质不在“几个指针“，而在“记录节点之间的关系信息“。单链表和双链表只是两种实现——向上扩展为树（一对多），再扩展为图（多对多）。这正是数据结构从线性到非线性的演进脉络。

四、时间复杂度

4.1 一句话定义

时间复杂度 = 随着数据量变大，操作耗时怎么增长。不关心具体秒数，只关心增长趋势。用大 O 记号表示。

4.2 大 O 记号四个要点

4.3 从 C 语言循环看三种复杂度模式

⚠️ 关键区分：并列是 O(n) + O(n) = O(n)，嵌套是 O(n) × O(n) = O(n²)。不要混淆！

代码示例：

// 单层循环 → O(n)
for (int i = 0; i < n; i++)
    printf("%d\n", i);

// 嵌套循环 → O(n²)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        printf("%d, %d\n", i, j);   // n × n 次

// 并列循环 → 仍为 O(n)，不是 O(2n)
for (int i = 0; i < n; i++)        // O(n)
    printf("%d\n", i);
for (int i = 0; i < n; i++)        // O(n)
    printf("%d\n", i * 2);
// 总复杂度：O(n)

4.4 常见复杂度速查表

n 越大，差距越悬殊。n=10000 时，O(n²) 是 1 亿步，O(log n) 只需约 13 步。选对结构，效率可以相差几个数量级。

4.5 复杂度分析三步法

拿到一段代码，按顺序问自己：

五、空间复杂度

空间复杂度 = 额外占用多少内存。同样用大 O 记号。

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

// 空间复杂度 O(1)：只用一个临时变量
int sum(const int arr[], size_t n) {
    int temp = 0;
    for (size_t i = 0; i < n; i++) temp += arr[i];
    return temp;
}

// 空间复杂度 O(n)：创建了和输入同等大小的新数组
int *copy_array(const int arr[], size_t n) {
    if (n > SIZE_MAX / sizeof(int)) return NULL;
    int *new_arr = malloc(n * sizeof(int));
    if (new_arr == NULL && n != 0) return NULL;
    for (size_t i = 0; i < n; i++) new_arr[i] = arr[i];
    return new_arr;
}

实际意义：空间复杂度常用来回答“算法除输入和输出外，还需要多少辅助内存”；讨论数据结构本身时，也会单独比较其存储开销。例如链表每节点多存 1~2 个指针，数组栈和环形队列预分配空间，链式队列按需分配节点。

六、本篇学习路线

理解了“数据结构 = 物理存储 + 逻辑规则“这个核心框架之后，本篇分两个章节展开：

路线图

数据结构总览（本篇）
    │  建立全局认知：物理存储 × 逻辑规则、时间复杂度
    │
    ├── 第十八章：数据存储结构
    │       │  聚焦物理存储层——连续存储 vs 链式存储
    │       │
    │       ├── 连续存储——数组的增删改查（查/改/增/删 × 复杂度分析）
    │       ├── 链式存储——链表
    │       │     ├── 单链表（只记后继）
    │       │     ├── 双链表（记前驱+后继）
    │       │     └── 发散思维：链式存储的本质（指针记录关系，自由组合）
    │
    └── 第十九章：通用抽象数据结构
            │  聚焦逻辑规则层——给存储加规则
            │
            ├── 线性 vs 非线性数据结构（概念引入）
            ├── 栈（基于数组，LIFO）
            ├── 链式队列（基于链表，FIFO）
            ├── 环形队列（基于数组，取模绕回）
            └── 总结与对比（全部结构效率总表 + 选型指南）

各章要点

第十八章 —— 数据存储结构：回答“数据在内存中怎么放“。

链式存储的本质：记录节点之间的关系信息，几个指针、指向谁，自由组合。单/双只是两种常用实现。

第十九章 —— 通用抽象数据结构：回答“加上什么规则、产生什么行为“。

💡 建议的学习顺序：

1. 先通读本篇，建立“物理存储 × 逻辑规则“的全局认知
2. 按顺序学习第十八章（数据存储结构）和第十九章（通用抽象数据结构）
3. 每学完一种结构，回到本章对照它属于哪一层——这样能帮你建立起系统化的数据结构知识框架

入门阶段结束后，进阶篇将继续深入非线性数据结构（树、图等），它们大多数也建立在数组和链表的基础之上。