椰程信奥 · 教案
vector / priority_queue / deque · 教案（课件 21 页）
一、教学目标
| 维度 | 具体目标 |
|---|
| 知识与技能 | ① 说出三种容器的代价表与适用面；② 独立完成论坛帖子、哈夫曼 WPL、
龙的追踪、公交换乘四题的代码；③ 掌握小顶堆的两种写法。 |
| 过程与方法 | 通过 8 个可单步动画，把内存动作外显化；建立"先问三句再选容器"的流程。 |
| 情感态度价值观 | 建立复杂度意识与代价意识；养成"先估复杂度再动手"的工程习惯。 |
二、重点难点
| 类别 | 内容 | 突破方式 |
|---|
| 重点 | 三种容器的代价表与选型三问 | 第 14 页对比表 + 三个场景卡 |
| 重点 | 哈夫曼 WPL = 合并代价和 | 第 11 页动画逐步累加，学生手算验证 |
| 难点 | 扩容的均摊 O(1) | 第 4 页动画：多数插入不搬，偶尔搬一次 |
| 难点 | 公交换乘"票价不够的票不能删" | 第 16 页反例：这张票后面还能用 |
三、教学过程
| 环节 | 教师活动 | 学生活动 | 设计意图 |
|---|
| ① 引入 4′ | 数组三宗罪提问 | 举例自己踩过的坑 | 建立动机 |
| ② vector 8′ | 第 4–6 页动画 + 板书代价表 | 预测 capacity 与移动次数 | 代价可视化 |
| ③ 例题1 6′ | 第 7–8 页逐条执行指令 | 说出 QUERY 前的判断 | 越界风险前置 |
| ④ 优先队列 8′ | 第 9–10 页上浮下沉单步 + 小顶堆三写法 | 报交换下标 | 把 log n 具体化 |
| ⑤ 例题2 6′ | 第 11–12 页合并动画 | 手算验证 WPL | 发现不用建树 |
| ⑥ deque 5′ | 第 13–14 页对比与选型三问 | 判断场景选容器 | 形成规则 |
| ⑦ 例题3/4 5′ | 第 15–17 页动画 + 三个坑 | 完成检测 | 形成性评价 |
| ⑧ 小结 3′ | 第 19 页检测 + 椰程锦囊 | 自评 | 收口 |
四、当堂检测标准
| 题号 | 正确答案 | 达标说明 |
|---|
| ① | -1 | 能说出"必须先比 size 再取下标" |
| ② | while(堆中元素 > 1) | 能说出写成 !empty() 会取不到第二个元素 |
| ③ | 留在队列里 | 能举出"后面更便宜的公交"的反例 |
五、板书设计
vector：连续 翻倍扩容 v[i] O(1) 头插 O(n) ★ reserve 免搬家
priority_queue：默认大顶堆 top O(1) 增删 O(log n) greater / 存负数 → 小顶堆
deque：两端 O(1) at(i) O(1) → 两头动 + 查中间
选型三问：长度不定 → vector｜每次取最值 → 优先队列｜两头动+查中间 → deque
六、易错预警清单
① v.end() 是"尾后一位"，解引用 RE；② pop_back() 不返回值；
③ v.size() 无符号，size()-1 在空容器时会溢出；
④ priority_queue 默认大顶堆、没有 clear()、不能遍历；
⑤ 哈夫曼 n=1 时输出 0，且答案需 long long；
⑥ 公交换乘 t - t_sub > 45 才过期（端点含 45），票价不够的票不能删。