这是我跟着教材一路读下来的笔记原稿。内容按章节排列：绪论 → 线性表 → 栈与队列 → 串/数组/广义表 → 树 → 图。 因为笔记里夹了大量 Typora 本地截图（AppData/Roaming/Typora/...），无法在博客直接渲染；如需带图阅读，请到仓库查看原文。

• 仓库原文（带截图）：notes.md

下方是笔记里纯文字部分的摘录，按章节整理，便于检索。

整体感知

重点	你要避免的误区	正确做法
先学「结构选择」再学「代码细节」	一上来死记代码模板	每学一个结构都问自己：它适合什么场景？和别的结构相比 trade-off 是什么？
每章都做「小实现」	只看概念，不写代码	每章至少写 1–2 个核心操作（链表插删、栈队列、树遍历、图遍历、排序）
把「复杂度分析」贯穿全程	只关心能跑出来	每次实现后写一句：时间/空间复杂度、为什么这样选

绪论 · 复杂度

时间复杂度 = 输入变大时，程序会慢多少的「增长规律说明书」：

• O(1)：东西再多，工作量基本不变
• O(n)：东西翻倍，工作量大约也翻倍
• O(n²)：东西翻倍，工作量约 4 倍
• O(log n)：东西翻倍，只多做一点点

不是「只看执行次数最多的那一条语句」，而是看总成本里增长最快的那一类项（主导项）。

空间复杂度同理 —— 通常说的是额外空间（辅助空间），关注「增长趋势」而不是精确字节数。

线性表

• 位序从 1 开始，注意与 0-indexed 的转换。
• 顺序 vs 链式：前者随机访问 O(1) 但插删 O(n)；后者插删 O(1) 但访问 O(n)。
• 带头结点 vs 不带：带头结点时空表的判定统一为 head->next == NULL，简化边界处理。

栈与队列

• 栈：后进先出，栈顶指针通常指向「下一个空位」，弹出时先 top-- 再取值。
• 队列：先进先出，front 指数据，rear 指数据之后一格。
• 循环队列：用 (i + 1) % MAX 解决「假溢出」；牺牲一格区分「空 / 满」是最常见做法。
• 链队列天然灵活，没有循环 / 假溢出问题。

串 / 数组 / 广义表

• 数据结构意义的「串」是封装过的结构体，不是裸 char[]。
• 二维数组按行优先存：addr(a[i][j]) = base + (i*n + j) * sizeof(T)。注意 i*n+j 要用 long 防溢出。
• 广义表：原子 + 子表，递归结构 → 用递归算法处理（求长度、深度、复制都一样）。

树

三种遍历对应三个访问时机（站在节点上的第几次经过）：

• 第一次经过即访问 → 先序
• 第二次经过才访问 → 中序
• 第三次经过才访问 → 后序

非递归后序需要双栈或带 visited 标记，因为要等左右子树都处理完再访问根。

由「先序 + 中序」或「后序 + 中序」可唯一确定一棵二叉树。

图

• 邻接矩阵 vs 邻接表：稠密图用矩阵，稀疏图用表。
• DFS = 尽可能深入，体现栈思想；BFS = 一层一层，体现队列思想。
• 度的统计可以反推边数（无向图 Σdeg = 2E）。

---

完整 488 行原始笔记（含教材截图、灵感速记）请到仓库阅读 notes.md。