1525 字
8 分钟
课程地图
这套课是什么
| 项 | 内容 |
|---|---|
| 课程 | 数据结构 |
| 讲师 | Harsha Suryanarayana（mycodeschool），中文配音：外影译坊 |
| 地址 | BV1Jr4RemEHY |
| 规模 | 42 集 / 约 564 分钟（9.4 小时）/ 平均 13 分钟一集 |
| 先修 | C 语言指针 + 动态内存分配 |
| 定位 | 用 C/C++ 手写实现每一种数据结构，不是调库 |
这套课的特点
讲课方式是「边画图边写代码」，每一集基本都是：先画结构图讲清思路 → 再一行行写 C/C++ 代码 → 最后讲复杂度和边界情况。
几个贯穿全课的约定：
| 约定 | 内容 |
|---|---|
| 高度定义 | 用「边数」定义：空树高度 = −1，叶节点高度 = 0 |
| 深度定义 | 根节点深度 = 0 |
| 数组下标 | 0-based |
| 链表位置 | 1-based（长度为 n 的链表最大合法插入位置是 n+1） |
| head 是什么 | 指向头节点的指针，不是头节点本身 |
| NULL | 就是地址 0，用来标记链表末尾 |
| 「路径」 | 默认指简单路径；允许重复叫「漫步」 |
这套课的字幕是 AI 识别的，同音字错极多（「店主」=电阻、「试播器」=示波器这类）。本笔记已按上下文还原，凡是识别不清或口误自相矛盾的地方，都用 [待确认] 标出来了。
全目录与章节对照
| 集 | 时长(分) | 标题 | 对应章节 |
|---|---|---|---|
| p1 | 6.3 | 1.数据结构：课程导论 | 导论与抽象数据类型 |
| p2 | 12.6 | 2.抽象数据类型：ADT | 导论与抽象数据类型 |
| p3 | 16.6 | 3.链表：基本介绍 | 链表（一）基础与数组对比 |
| p4 | 11.8 | 4.数组 vs 链表 | 链表（一）基础与数组对比 |
| p5 | 13.4 | 5.链表：C_C++实现 | 链表（二）C 实现与头部插入 |
| p6 | 12.3 | 6.链表：头部插入一个节点 | 链表（二）C 实现与头部插入 |
| p7 | 14.7 | 7.链表：任意位置插入一个节点 | 链表（三）任意位置插入与删除 |
| p8 | 12.0 | 8.链表：任意位置删除一个节点 | 链表（三）任意位置插入与删除 |
| p9 | 13.3 | 9.链表：反转一个链表 ( 迭代方式实现 ) | 链表（四）反转与递归 |
| p10 | 13.8 | 10.链表：打印一个链表 ( 递归方式实现 ) | 链表（四）反转与递归 |
| p11 | 8.6 | 11.链表：反转一个链表 ( 递归方式实现 ) | 链表（四）反转与递归 |
| p12 | 6.9 | 12.链表：双向链表的介绍 | 双向链表 |
| p13 | 14.8 | 13.链表：双向链表的实现 | 双向链表 |
| p14 | 8.1 | 14.栈：基本介绍 | 栈 |
| p15 | 12.7 | 15.栈：使用数组实现一个栈 | 栈 |
| p16 | 10.6 | 16.栈：使用链表实现一个栈 | 栈 |
| p17 | 15.8 | 17.栈：反转一个字符串或者反转一个链表 ( 使用栈来实现 ) | 栈 |
| p18 | 13.7 | 18.栈：检查括号的匹配性 ( 使用栈来实现 ) | 栈 |
| p19 | 13.1 | 19.栈：中缀, 前缀, 后缀的基本概念 | 栈的应用 前缀 中缀 后缀 |
| p20 | 13.6 | 20.栈：前缀, 后缀表达式求值 ( 使用栈来实现 ) | 栈的应用 前缀 中缀 后缀 |
| p21 | 17.6 | 21.栈：中缀到后缀表达式的转换 ( 使用栈来实现 ) | 栈的应用 前缀 中缀 后缀 |
| p22 | 9.0 | 22.队列：基本介绍 | 队列 |
| p23 | 14.4 | 23.队列：使用数组实现一个队列 | 队列 |
| p24 | 13.7 | 24.队列：使用链表实现一个队列 | 队列 |
| p25 | 15.2 | 25.树：基本介绍 | 树与二叉树 |
| p26 | 15.7 | 26.树：二叉树 | 树与二叉树 |
| p27 | 18.7 | 27.树：二叉搜索树 | 二叉搜索树 |
| p28 | 17.9 | 28.树：二叉搜索树 (C_C++实现) | 二叉搜索树 |
| p29 | 12.6 | 29.树：二叉搜索树 (C_C++实现) - 内存中的栈与堆详解 | 内存中的栈与堆 |
| p30 | 5.6 | 30.树：二叉搜索树 - 查找最小值和最大值 | BST 查找最值与二叉树的高度 |
| p31 | 6.9 | 31.树：二叉树的高度 | BST 查找最值与二叉树的高度 |
| p32 | 11.4 | 32.树：二叉树的遍历 - 广度优先 vs 深度优先 | 二叉树的遍历 |
| p33 | 10.9 | 33.树：二叉树的层次遍历 | 二叉树的遍历 |
| p34 | 13.9 | 34.树：二叉树的前序, 中序, 后序遍历 | 二叉树的遍历 |
| p35 | 15.9 | 35.树：判断是否为二叉搜索树 | 判断 BST 与删除节点 |
| p36 | 17.8 | 36.树：二叉搜索树中删除一个节点 | 判断 BST 与删除节点 |
| p37 | 17.3 | 37.树：二叉搜索树的中序后继节点 | 判断 BST 与删除节点 |
| p38 | 16.1 | 38.图：基本介绍 | 图 |
| p39 | 14.7 | 39.图：图的一些基本属性 | 图 |
| p40 | 13.2 | 40.图：图的表示法（第1部分：边列表） | 图 |
| p41 | 14.2 | 41.图：图的表示法（第2部分：邻接矩阵） | 图 |
| p42 | 26.8 | 42.图：图的表示法（第3部分：邻接表） | 图 |
数据结构全貌
线性结构├── 数组 连续内存，随机访问 O(1)，插入删除 O(n)├── 链表 离散内存 + 指针，插入删除 O(1)（已知位置时），访问 O(n)│ └── 双向链表 多一个 prev 指针，能反向走，单指针即可删除├── 栈 单侧开口，LIFO，push/pop 都是 O(1)└── 队列 两侧开口，FIFO，enqueue/dequeue 都是 O(1)
非线性结构├── 树 层级结构，N 个节点恰好 N−1 条边│ └── 二叉搜索树 平均 O(log N)，最坏 O(N)（退化成链表）└── 图 没有支配连接的规则，树只是图的特例 ├── 边列表 O(|V|+|E|) 空间，但找邻居 O(|E|) ├── 邻接矩阵 O(V²) 空间，判断相连 O(1)，适合密集图 └── 邻接表 O(|V|+|E|) 空间，适合稀疏图复杂度总表
| 数据结构 | 访问 | 查找 | 插入 | 删除 | 空间 |
|---|---|---|---|---|---|
| 数组（有序 + 二分） | O(1) | O(log N) | O(N) | O(N) | O(N) |
| 链表 | O(N) | O(N) | O(1)（头部） | O(1)（已知前驱） | O(N) |
| 双向链表 | O(N) | O(N) | O(1) | O(1)（单指针即可） | O(N) |
| 栈 | O(1)（栈顶） | — | O(1) | O(1) | O(N) |
| 队列 | O(1)（队头） | — | O(1) | O(1) | O(N) |
| BST（平衡） | O(log N) | O(log N) | O(log N) | O(log N) | O(N) |
| BST（最坏） | O(N) | O(N) | O(N) | O(N) | O(N) |
怎么用这份笔记
每一章对应视频里的一段。每章结构：核心概念 → 代码/算法 → 复杂度 → 坑。
这套课的笔记里「坑」那部分特别值得看。边界情况本来就容易错，连课上写的代码也会漏（比如删除函数忘了 return），这些都是真实会犯的错。
建议动手顺序：
① 链表三章（p3-p13）—— 把指针彻底搞明白，后面全靠这个② 栈和队列（p14-p24）—— 实现简单，但边界条件最容易错③ 树（p25-p37）—— 重点是递归，尤其是插入为什么必须接住返回值④ 图（p38-p42）—— 重点理解三种表示法的取舍请输入编辑凭据，只有站点所有者可以修改文章。