椰程信奥 · 说课稿

vector / priority_queue / deque · 说课稿（对应视频 41′56″，课件 21 页）

一、教材与学情

本讲对应视频《CSP复赛专题10-数据结构2》（41′56″），聚焦 C++ STL 中最常用的三个容器： vector、priority_queue、deque。学生在专题 9 已经掌握了栈与队列的"手动实现 + STL"两遍走法，本讲是在此基础上的横向扩张：从"固定操作"走向"按需选型"。

学情上的典型困难不是记不住接口，而是做题时不知道该用哪个——看到"第 k 个"还在用数组，看到"每次取最小"还在写双重循环，看到"两头都要动"还在用 vector 头插。所以本讲把教学目标定位在选型判断力，而不是接口记忆量。

二、教学目标

知识与技能：能说出 vector（连续内存 / 翻倍扩容 / 随机访问 O(1)）、priority_queue （完全二叉树 / 大顶堆默认 / top O(1)、增删 O(log n)）、deque（分段缓冲 / 两端 O(1) / 随机访问 O(1)）各自的代价与适用面；能独立完成四道真题的代码。
过程与方法：通过 8 个可单步的动画，把"扩容搬家""上浮下沉""合并累加""两端增删" 这些不可见的内存动作变成可观察、可预测的过程；建立"先问三句再选容器"的思维流程。
情感态度：体会"代价意识"——同样是插入，位置不同代价差一个数量级；养成写代码前先估复杂度的习惯。

三、重点难点

重点

① 三种容器的代价表；② 扩容的均摊 O(1)； ③ 哈夫曼"WPL = 合并代价和"；④ 公交换乘的票队列建模。

难点

① 均摊分析为什么成立；② 小顶堆 greater 与"取负数"两种写法的转换； ③ 公交换乘里"票价不够的票不能删"。

四、教学过程（45 分钟）

环节	时间	教师活动	学生活动	设计意图
① 动机引入	4′	课件第 3 页：数组三宗罪（长度写死 / 删中间痛 / 两端不能动），让学生各举一个自己踩过的坑	回忆并举例	用真实痛点锚定新知识的必要性
② vector 内存模型	8′	第 4–5 页动画：连点 push_back 直到扩容，追问"这一次插入搬了几个元素？"；再对比头插的移动次数	预测下次 capacity 变成几、搬几个	把"均摊 O(1)"从结论变成观察
③ vector 进阶	3′	第 6 页：二维 / 结构体 / 邻接表三种形态，重点讲邻接表为什么用 `vector<int> g[N]`	跟着写一遍初始化	为后续图论铺垫
④ 例题1 论坛帖子	6′	第 7–8 页动画逐条执行指令，重点停在"回复数不足 → -1"那一条	说出 QUERY 前必须先比什么	把越界风险前置暴露
⑤ 优先队列与堆	8′	第 9 页动画：push → 单步上浮；pop → 单步下沉。第 10 页讲小顶堆三写法，重点敲默认是大顶堆	口头报每一步交换的下标	把 log n 变成"只走一条链"的直观事实
⑥ 例题2 哈夫曼	6′	第 11–12 页动画：每步取最小两个合并，盯着 WPL 累加；讲清"WPL = 合并代价和"为什么成立	手算验证一组	让学生自己发现不用建树
⑦ deque	5′	第 13–14 页：对比 vector 头插的移动次数，给出选型三问与代价表	判断给定场景该选哪个	形成可迁移的选型规则
⑧ 例题3 / 4	5′	第 15–17 页：龙的追踪（两头动 + 查中间）、公交换乘（票队列 + 有效期），重点讲三个坑	完成当堂检测	当堂形成性评价

五、板书设计

vector：连续内存　size / capacity　扩容翻倍（均摊 O(1)）　v[i] O(1)　头插 O(n) ★

priority_queue：完全二叉树　父 (i-1)/2　子 2i+1 / 2i+2　默认大顶堆　top O(1)　增删 O(log n)

小顶堆：greater<T>　或　存负数取反　（自定义 cmp 返回 true = 优先级更低）

deque：分段缓冲　两端增删 O(1)　at(i) O(1)　→ 两端都要动 + 查中间

选型三问：① 长度不定？→ vector　② 每次取最值？→ 优先队列　③ 两头动 + 查中间？→ deque

六、教学亮点与反思

亮点一：把"代价"可视化。每个操作动画都显示"搬了多少个元素"，学生不再是背 O(n)/O(1)，而是亲眼看到头插时后面元素一个个后移。
亮点二：堆的每一步都可预测。上浮/下沉做成单步，学生先猜交换哪两个下标再揭示，把被动观看变成主动推演。
亮点三：哈夫曼不建树。用动画让学生自己发现"WPL 就是合并代价之和"，把一道看似要建树的题降维成几行堆操作。
反思：公交换乘的三个坑（端点含 45、票不能删、不能用 vector 模拟队列）信息量偏大，时间紧时可只讲前两个，第三个留作课后自查。

七、答辩预设

问：为什么不直接讲 STL 用法表，要花时间讲扩容和堆的内部？
答：用法表学生查得到，但代价判断力查不到。不知道 vector 会翻倍扩容，就不会想到 reserve；不知道堆只沿一条链移动，就不会相信它比排序快。讲原理是为了让"选型"有依据，而不是靠试。