跳转至
跳转到正文

FDS 数据结构基础讲义

拆分状态

这页保留原来的 /zh/notes/fds-data-structures-lecture/ 地址，作为 FDS 数据结构基础讲义总览和旧链接兼容层。章节正文已经拆分到稳定子路径；如果旧链接带有 #note-sec-... 锚点，可在本页的“旧锚点跳转表”找到对应新位置。

阅读导引

这门课的主线是：用合适的数据组织方式，让算法能在可接受的时间和空间内完成任务。阅读时不要只背接口名称，而要追问结构维护了什么不变量、操作如何保持不变量、复杂度来自哪里。

课程目标

  • 掌握算法分析、ADT、线性结构、树、堆、并查集、线段树和图的核心结构。
  • 能根据操作频率和不变量选择合适的数据结构。
  • 能解释关键操作的时间复杂度和常见边界错误。

前置知识

  • 基础 C/伪代码、数组、指针或引用、递归和简单数学符号。
  • 能阅读 \(O(N)\)、\(O(\log N)\)、\(O(N\log N)\) 等复杂度记号。

总体建议用时

建议按 10 个主体章节分 5–8 周学习；如果只做复习，可先读第 1、2、3、4、6、7、8、9 章，再查附录。

总体练习建议

  • 每章至少写一张“结构卡”：存储方式、不变量、关键操作、复杂度、易错点。
  • 对算法过程，手算一个小样例，再写伪代码。
  • 对复杂度，说明瓶颈来自循环、递归深度、树高还是边数。

课程来源与引用边界

  • 整理者：Lumner。
  • 内容来源：根据 FDS/ 目录下现有数据结构课件与 note/FDS_数据结构基础讲义.md 整理。
  • 站内用途：作为公开学习笔记和碧影可读取的公共知识来源。
  • 引用边界：这不是课程官方教材，也不替代教师课件、课堂说明或考试要求；外部引用时请注明来自本网站整理版。

章节入口

  • 0. 课程视角：为什么需要数据结构：数据组织方式、操作频率、规模增长和结构选择的基本问题。（建议 1–2 小时）
  • 1. 算法分析：算法与程序、分析对象、渐进记号、最大子列和、二分查找和复杂度检查。（建议 4–5 小时）
  • 2. 抽象数据类型与线性表：ADT、数组表、链表、双向循环链表、多项式 ADT、多重链表和游标实现。（建议 5–6 小时）
  • 3. 栈与队列：栈 ADT、括号匹配、表达式求值、中缀转后缀、系统栈、队列和循环队列。（建议 4–5 小时）
  • 4. 树与二叉树：树术语、树的表示、二叉树、表达式树、遍历、非递归遍历和线索二叉树。（建议 5–6 小时）
  • 5. 二叉搜索树：二叉搜索树定义、查找、最值、插入、删除、懒惰删除和平均/退化情况。（建议 3–4 小时）
  • 6. 优先队列与二叉堆：优先队列 ADT、实现对比、堆序性、插入、删除最小值、建堆、应用和 d-堆。（建议 4–5 小时）
  • 7. 并查集：等价关系、动态等价问题、基本表示、按大小/高度合并、路径压缩和典型应用。（建议 3–4 小时）
  • 8. 线段树：区间结构动机、适用算子、建树、区间查询、点更新、区间更新和懒标记。（建议 5–6 小时）
  • 9. 图与拓扑排序：图定义、图存储、AOV 网络、拓扑序、朴素拓扑排序和队列优化拓扑排序。（建议 4–5 小时）
  • 附录：复杂度速查与结构选择：复杂度表、选结构模板、后续扩展记录。

章节与课件对应表

章节 覆盖内容 对应课件
0. 课程视角：为什么需要数据结构 数据组织方式、操作频率、规模增长和结构选择的基本问题。 FDS/DS00-2026.pdf
1. 算法分析 算法与程序、分析对象、渐进记号、最大子列和、二分查找和复杂度检查。 FDS/DS01_Ch02_Algorithm Analysis(a)-2026.pdf, FDS/DS02_Ch02_Algorithm Analysis(b).ppt
2. 抽象数据类型与线性表 ADT、数组表、链表、双向循环链表、多项式 ADT、多重链表和游标实现。 FDS/DS02_Ch03_List.ppt
3. 栈与队列 栈 ADT、括号匹配、表达式求值、中缀转后缀、系统栈、队列和循环队列。 FDS/DS03_Ch03_Stack and Queue.ppt
4. 树与二叉树 树术语、树的表示、二叉树、表达式树、遍历、非递归遍历和线索二叉树。 FDS/DS04_Ch04_Binary Trees.ppt
5. 二叉搜索树 二叉搜索树定义、查找、最值、插入、删除、懒惰删除和平均/退化情况。 FDS/DS05_Ch04_Search Tree.pdf
6. 优先队列与二叉堆 优先队列 ADT、实现对比、堆序性、插入、删除最小值、建堆、应用和 d-堆。 FDS/DS06_Ch05_Priority Queues.ppt
7. 并查集 等价关系、动态等价问题、基本表示、按大小/高度合并、路径压缩和典型应用。 FDS/DS07_Ch08_Union and Find.ppt
8. 线段树 区间结构动机、适用算子、建树、区间查询、点更新、区间更新和懒标记。 FDS/DS07_Segment Tree.pdf
9. 图与拓扑排序 图定义、图存储、AOV 网络、拓扑序、朴素拓扑排序和队列优化拓扑排序。 FDS/DS08_Ch09_Graph Definition_Topological Sort.ppt

旧锚点跳转表

下面的条目用于兼容旧版长页面的 #note-sec-... 锚点。锚点本身保留在本页；点击条目会进入新的章节子页面或附录页。