0. 课程视角：为什么需要数据结构

章节导引

本页从《FDS 数据结构基础讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标

理解数据结构不是接口清单，而是用不变量和组织方式换取更好的时间/空间表现。

前置知识

基础编程、数组、循环、函数和简单数学符号。

建议用时

建议 1–2 小时：重点理解结构选择和复杂度压力。

练习建议

找 3 个实际场景，说明为什么朴素存储会慢，以及可能换成什么结构。

参考资料与引用边界

• 整理者：Lumner。
• 课程来源：根据 FDS/ 目录下的课件整理；本章对应课件：FDS/DS00-2026.pdf。
• 原始讲义文件：note/FDS_数据结构基础讲义.md。
• 引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

数据结构是组织、处理、检索和存储数据的专门格式。程序当然可以“直接写”，但当数据规模变大、操作频率变高、约束变复杂时，朴素写法往往会被时间复杂度击穿。

一个常见例子是区间求和：

• 如果每次查询 [L, R] 都从 L 加到 R，一次查询是 \(O(N)\)。
• 如果查询非常频繁，先花时间建立结构，例如前缀和或线段树，就能把查询降低到 \(O(1)\) 或 \(O(\log N)\)。
• 选择哪种结构，取决于是否需要修改数组：静态数组适合前缀和；频繁修改适合线段树。

因此，这门课的重点不是“某个结构长什么样”，而是“结构如何把操作变快”。每一种数据结构都可以从下面四个角度学习：

角度	要问的问题	例子
对象	存的是什么	表存序列，堆存带优先级的元素，图存顶点和边
操作	用户需要什么动作	插入、删除、查找、合并、区间查询
不变量	结构必须维持什么性质	BST 左小右大，堆父节点不大于孩子，并查集根节点代表集合
复杂度	每个操作要花多少代价	链表插入 \(O(1)\)，查找第 k 个元素 \(O(N)\)