简介这是一份适用于高校计算机及相关专业的《数据结构》课程教案由山东科技大学泰山科技学院教师编写内容与严蔚敏《数据结构C语言版》教材配套可作为任课教师备课、出课和信管类专业学生预习复习的参考资料。教案采用课时授课计划形式包含教学目的与要求、教学重点与难点、课堂类型、教学过程设计、例题讲解与课后作业等完整环节覆盖数据结构绪论、数据类型、抽象数据类型、算法设计、数据结构的实现等章节并对逻辑结构中的线性结构、树形结构、图状结构网状结构及抽象数据类型的三元组表示展开说明。资源为单个doc文档压缩包大小522KB便于直接打印或编辑修改。目前已有420人浏览学习适合需要快速组织课堂教学或系统梳理数据结构知识框架的师生使用。1. 数据结构教案的第一页把教学目标写成人可执行的闭环很多刚站讲台的助教交上来的数据结构教案打开看其实是课程目录数组、链表、栈、队列、树、图、排序各占几页每页写着定义、代码和复杂度表。这份目录只回答了今天讲到哪回答不了学生上完这节课能不能独立写出可运行的结构。可执行的教案应该是一个闭环先说明教学目标对应哪种实际操作再给出接口与存储结构的选择理由随后落到一段能编译或能运行的代码最后用复杂度分析和测试用例收口。换句话说教案的每一节都要让学生完成从抽象到实物的转换。这篇内容适合三类人第一次主持习题课的数据结构助教考研复试前想把知识点串起来的本科生以及用算法题带新人的工程师。下面按线性结构、树与图、排序与哈希三段拆解每一段都给出可以直接抄进课堂的代码和边界参数。2. 线性结构教案顺序表与链表的选型对照2.1 教案先讲 ADT 接口还是先写存储结构从签名推导复杂度课堂的第一个分歧是顺序。一些讲师喜欢用 struct node 开场先把链表节点写出来很快学生就在指针上晕掉我倾向先用函数签名把“要做什么”固定下来再问“用什么做”。课堂上先给学生三个空实现签名让每个人说出自己预期的复杂度def push_back(container, value): 尾部插入顺序表连续写链表要看是否维护了尾指针 pass def pop_front(container): 头部删除顺序表要把后面所有元素前移链表只需移动头指针 pass def get_at(container, idx): 按下标访问顺序表基址加偏移链表要遍历 idx 步 pass这几个签名支撑一整节课。讲法是这样的先把三个接口贴在黑板上让学生各自填预期的复杂度再在实现完后回看答案是否成立。顺序表按下标访问是 O(1)因为数组的基址和下标在内存里直接可计算链表要逐个节点跳过去因此是 O(n)。尾部插入对数组是常数时间但数组满时要复制迁移链表如果额外维护一个尾指针插入也是 O(1)否则要遍历到最后又回到 O(n)。课堂结论不用背诵这个推导过程走一遍比任何口诀都牢固。这个设计让“先定义接口再讨论实现”成为这门课的默认纪律。教案里还要预留一条反问如果学生把接口写成“既支持频繁头插又支持按下标定位”该选什么——答案不是立刻给而是留到第 2.3 节末尾让复杂度表说话。2.2 循环队列手写代码用 size 字段把“空”和“满”分开顺序表这一节里我很少留“再写一个顺序表”的作业因为学生已经会了我更愿意安排手写循环队列。普通数组队列的队头删除会在数组前部留下空洞初学者最容易想到的做法是每次删除都把后续元素整体前移得到一个 O(n) 的“假删除”。循环队列用取模绕回让空间在逻辑上首尾相接教学重心在“front、rear、size 三个参数如何协同”。下面是可以在习题课上直接演示的 C 代码重点在注释标出的边界#define MAX 5 typedef struct { int data[MAX]; int front; /* 队头下标 */ int rear; /* 下一个可写位置 */ int size; /* 当前元素个数 */ } CQueue; void init_cq(CQueue *q) { q-front q-rear q-size 0; } int cq_push(CQueue *q, int v) { /* 满则返回 0 */ if (q-size MAX) return 0; q-data[q-rear] v; q-rear (q-rear 1) % MAX; /* 最后一个下标回到 0 */ q-size; return 1; } int cq_pop(CQueue *q, int *out) { /* 空则返回 0 */ if (q-size 0) return 0; *out q-data[q-front]; q-front (q-front 1) % MAX; q-size--; return 1; }代码逻辑front 指向队头元素rear 指向下一个可写空位两者下标重合时队列既可能空也可能满所以加 size 字段区分。如果不用 size常见做法是把数组开成 MAX1让 rear 追上前面的一个空闲槽表示满语义上稍微绕一点我一般先用 size 版本因为它把“满”的判断明确写成一次整数比较。取模运算(i 1) % MAX是循环结构唯一的新知识点跟前一节链表完全无关适合作为课堂演练的入口。给学生安排的两个必测用例是队列容量刚好为 MAX 时继续入队不应覆盖数据以及 pop 到 size 为 0 后继续 pop 不能访问未初始化内存。2.3 链表教案的五个必讲参数与易错点跳出语法本身链表教案比结构定义更需要讲的是五个实现参数。第一是头结点的角色带头结点可以让空表和非空表的插入删除逻辑归一不必每次都要处理“head 是否为空”的分支。第二是哨兵指针也就是 dummy node它在头插和尾插时统一了“前驱”的存在避免删除头节点时单独写一段。第三是游标更新删除时要用 prev 记住当前节点的前驱否则只能从链表头重新定位。第四是尾指针的维护状态带尾指针的链表尾插为 O(1)不带则退化为 O(n)这个差异在实验报告里很容易被观察到。第五是节点释放后的悬空引用C 语言里 free 不会自动把指针置空这是习题里最常见的隐蔽错误。放一张对照表把这一节与顺序表的对比固定下来操作顺序表数组单链表按下标取元素O(1)O(n)尾部插入O(1)扩容均摊有尾指针 O(1)否则 O(n)头部插入O(n)O(1)已知前驱的中间删除O(n)O(1)额外空间几乎无每个节点一个 next 指针表里的“尾部插入”那行最值得展开数组扩容时要把旧数据复制到新数组但如果按倍增扩容均摊后仍是 O(1)所以不能简单地说数组尾插慢链表的 O(1) 建立在尾指针存在且插入位置已知两个前提上。到这里再回头看 2.1 末尾留的问题就可以回答了频繁头插加按下标定位的组合单链表能解决头插却救不了按下标访问真要兼顾这两个要求通常需要换一层索引结构。这一句话就把教案选型从背结论变成了用复杂度倒推结构。3. 树与图教案用遍历统一递归与迭代3.1 二叉树教案把前中后序遍历讲成“访问时机”前序、中序、后序在课堂上最常见的讲法是三句口诀根左右、左根右、左右根。口诀只能应付两天后的考试放不进去。我的做法是换一个切入点每个节点都会被递归路径经过很多次遍历的结果差异只在于我们选择哪一次“发出处理动作”。用一段递归模板把三种遍历挤进同一个函数只有一个 print 的位置不同class BinaryNode: def __init__(self, v): self.v v self.left None self.right None def traverse(node, order): if node is None: return if order pre: print(node.v) # 第一次经过该节点时输出 traverse(node.left) if order in: print(node.v) # 左子树完全处理完回到当前节点 traverse(node.right) if order post: print(node.v) # 左右子树都处理完最后一次经过代码逻辑说明递归对每个节点总是“先到当前节点、进左子树、回到当前节点、进右子树、再回到当前节点”走上这么几回print 放在不同位置就得到三种顺序。参数 changeorder 文件三种文字传 pre/in/post 即可切换没有改变递归结构学生能看到遍历的本质不是三种口诀。复杂度同样不因顺序改变每个节点访问一次O(n)递归栈深度等于树高最坏情况下退化成单链二叉树时 O(n) 的空间。给这个教案配一张适用范围表把“什么时候用哪种序”落到具体场景遍历输出时机典型场景前序第一次到达节点树序列化、拷贝二叉树中序左子树返回后二叉搜索树读取有序序列后序右子树返回后子树统计、释放节点、树形DP这里各栏的数据反复强调后序不算“奇凑第三”因为它需要先拿到左子树的结果才能计算当前节点比如求树高、求路径和这种“先子后父”的顺序是递归计算的基础尤其在动态规划里几乎都是后序形态。常见见习是让 learner 从“一棵索引树”改成“前序遍历用数组存储完全二叉树的父子下标”连接从一般二叉树到堆的课文。3.2 BFS 和 DFS 教案一个状态机适配两种策略图的遍历教案如果只是分开给出 bfs 和 dfs 两段代码学生背得下来却不知道为什么这样判定访问。我常用的教学设计是三色状态机白色表示还没进入容器灰色表示已经被放入待处理集合黑色表示它的邻接边都已经展开完毕。BFS 和 DFS 的差异只剩从容器里取下一个节点时用队列还是栈。给出一版能跑无向图的有向图三色搜索代码from collections import deque def search(graph, start): WHITE, GRAY, BLACK 0, 1, 2 color {v: WHITE for v in graph} container deque([start]) # 换容器换遍历性质 color[start] GRAY result [] while container: v container.popleft() # 改成 pop() 则变为 DFS result.append(v) for w in graph[v]: if color[w] WHITE: color[w] GRAY # 入容器时立刻标记避免重复入 container.append(w) color[v] BLACK # 邻接都处理完 return result代码观察入队时就置灰而不是出队时再判重这样同一个节点不会被塞进容器多次出队时只处理当前顶点处理完的所有邻边都一次性扩展进去变黑。需要切换 DFS 时把popleft()改成pop()就是栈先出后进三色状态机的语义一行不用改。课堂问题适合放两个一个是连通分量个数——对外层 for 循环每个未访问顶点调用 search调用次数就是连通分量个数另一个是路径输出——如果在边w被置灰时记录parent[w] v等结束从目标反向回溯 parent 就能还原一条路径。这两个题把状态机用熟了比再背十个图算法更有用。用一个表列出两个版本在手写代码中的差异方便教案排版和复习版本取出策略空间增长典型感知BFS队首按层最短路径层数先出DFS栈顶往深处路径存在回溯顺序固定3.3 拓扑排序教案利用完成时间反推依赖顺序讲完三色状态机后拓扑排序可以在二十分钟内顺出来没必要换成另一套哲学。要点只有一句DFS 完全展开一个节点的所有子节点后再把该节点追加进结果栈得到的序列整体逆序就是拓扑序。上面search里把结点变黑的位置写一个order.append(v)所有结点结束后返回order[::-1]。代码可以整段放进教案def topo_sort(graph: dict): WHITE, GRAY, BLACK 0, 1, 2 state {v: WHITE for v in graph} def dfs(v, order): state[v] GRAY for w in graph[v]: if state[w] GRAY: raise RuntimeError(cycle detected: %s - %s % (v, w)) if state[w] WHITE: dfs(w, order) state[v] BLACK order.append(v) # 结束时间顺序 order [] for v in graph: if state[v] WHITE: dfs(v, order) return order[::-1]逻辑说明图中如果存在环DFS 在递归过程中会遇到一条指向灰色节点的边那个灰色节点还在当前递归栈里没有被处理完所以能立刻报错这在教案里比“Kahn 算法数入度”更显眼。时间复杂度和 BFS/DFS 一样是 O(VE)其中 E 是边数因为每条边在遍历时最多访问一次。参数可改项实际上是方向order存储了完成顺序反转它排出的序列才是依赖方向正确的顺序如果用了不反转的写法结果会变成反向依赖单测里用一个三节点依赖链马上就能暴露坏出来。教案课后的扩展提问如果把 result 从栈的逆序改成每次在头部插入order.insert(0, v)会导致结果是 O(V^2)因为插入头部的线性开销累积这个坑值得让学生自己复现一遍。4. 排序与哈希教案把背代码改成读参数4.1 排序算法教案的顺序选择从冒泡到归并为什么不能跳排序教案的首要决定是教学顺序而不是代码。我见过的几份数据结构教案都按冒泡、选择、插入、快排、归并把算法逐个排开实际上前三个的定位完全不同。冒泡排在最前的价值不在效率而在于它能引出“逆序对”“交换次数”“一趟无交换提前结束”三个概念当输入已升序时冒泡可以做到 O(n)这个特例让“最好/最坏复杂度”第一次变得可见。插入排序则承接“排序前缀”概念在几乎有序的序列上同样能接近 O(n)所以工程上常把它放在快排分区规模较小时收底。选择排序几乎被实用代码遗弃但它是“每趟固定选最值”的直观模型用来和冒泡对比稳定性时效果很好。快排和归并才是复杂度教学的主战场。快排强调的是划分点选择、逆序退化、以及“基准等于重复元素时会不会无限递归”而归并强调固定折半的稳定分治代价是额外 O(n) 空间且原地归并的写法过于复杂教案不必展开。我把四者的对比浓缩为一句话从冒泡到归并参数的变化是“交换驱动、插值驱动、分治与是否稳定”复杂度只是结果不是教学顺序本身。4.2 用 key 参数把快排写成参数化教案工程里的排序函数真正的接口不是“如何比较两个数字”而是“如何从对象提取排序键”。课堂上学生手写的快排返回值硬邦邦而 Python 的sorted支持key与reverse这个差别正好可以当作参数化教学的入口。给一份可运行、可改参数的快排实现def quick_sort(items, keylambda x: x): if len(items) 1: return list(items) pivot items[len(items) // 2] left [x for x in items if key(x) key(pivot)] same [x for x in items if key(x) key(pivot)] right [x for x in items if key(x) key(pivot)] return quick_sort(left, key) same quick_sort(right, key) # 按字符串长度升序逆序可把 key 换成 lambda x: -len(x) words [binary, tree, graph, queue] print(quick_sort(words, keylen))逻辑说明key是提取排序依据的可调用对象比较动作全由它驱动len 作为 key 时排序比较的是各字符串的长度而不是字符串本身。这种设计比在函数内部写死if a b更容易让学生理解 Python 标准库里key与cmp的差别——现代接口大都保留 key返回的是“排序依据位置”。参数可改项是稳定性本实现用left same right分组相同键的元素全被收进 same天然稳定而经典 Lomuto 划分交换相同的元素时稳定性会丢正好用来解释为什么工程排序宁愿用插排收底快排后半段。复杂度pivot 选择每次取中间下标对随机分布接近 O(n log n)对逆序数据则会退化到 O(n^2)所以教案第二问通常是“如何选 pivot 避免退化”往往就引出随机基准或三数取中。一个练习能检验学生理解数据是一批字典对象如items [{name: a, age: 3}, {name: b, age: 2}]用keylambda d: d[age]快排一遍就能确认结构是否成熟。这种在教案代码里做泛化的做法完胜让学生按教材默写一个只处理 int 的程序。4.3 哈希教案装载因子、哈希链与冲突解决策略哈希表的教案重点在“哈希函数”“装载因子”“冲突解决”三个参数而不是具体到某一种哈希函数。课堂从链地址法入手最直观将桶设为链表冲突的键挂在同一桶后面桶的链表在课里就叫哈希链它可以借用第 2.3 节讲的链表操作。给一份可跑的极简实现并让capacity与load_factor成为显式字段class ChainHash: def __init__(self, capacity16, load_factor0.75): self.capacity capacity self.load_factor load_factor self.table [[] for _ in range(capacity)] self.length 0 def _index(self, key): return hash(key) % self.capacity def put(self, key, value): bucket self.table[self._index(key)] for i, (k, v) in enumerate(bucket): if k key: # 键已存在更新 bucket[i] (key, value) return bucket.append((key, value)) # 新键挂到哈希链 self.length 1 if self.length / self.capacity self.load_factor: self._resize(self.capacity * 2) # 扩容这里只保留入口 def get(self, key): bucket self.table[self._index(key)] for k, v in bucket: if k key: return v return None代码把哈希链实现成 Python 的 list也就是当好结点数组的链表化方案hash(key) % capacity是把任意键映射到下标取模运算让桶号分布。装载因子在这里是触发扩容的阈值不调它只调 capacity 的常见错误是桶数翻倍、冲突概率却没按期望下降因为装载因子才是有效控制冲突的那个比值。复杂度上理想哈希链的查找是 O(1 链长)链长受装载因子约束所以把 load_factor 从 0.75 改成 1.0 测同一组冲突键感知差异会很直观。下表把三种冲突解法放到同一张对比里用于课堂结尾的提问冲突解法平均查找复杂度删除代价关键限制线性探测依赖探测步长需要删除标记墓碑容易在连续区块堆积二次探测好于线性探测同样要墓碑标记必须保证覆盖整个表链地址法O(1链长)直接删链表节点每个桶多了指针开销表格下面的课堂练习容量 8、装载因子 0.75连续插入哈希值对 8 取模相等的 6 个键手画出哈希链变长过程并指出扩容发生的那一刻。这样哈希不再是“先有函数再填表”的死记而是一个由参数控制的动态过程。5. 把教案回收成实验报告与面试验证题数据结构教案在课堂上讲完并不能算收工它最后应该在实验报告和面试题两种场景里被回收验证。一份我认可的实验报告包含五个部分实验目标、设计说明、关键代码、测试用例、性能记录恰好对应教案的闭环——目标对应“这节课解决什么现实操作”设计对应接口与存储结构选择关键代码对应可运行实现测试用例覆盖空表、满表、重复键、最大规模四种边界性能记录让复杂度从纸面变成曲线。用这个模板反向检查教案质量比听课更有用。教案如果连测试用例和复杂度都讲清楚了学生写完报告后会余裕地发现期末考试已经不需要临时翻书因为报告本身就是按考点组织的材料。面试角度最常见的是三个串联测试哈希表装载因子定在多少、为什么经验值选 0.75单链表按已知前驱删除节点能否做到 O(1)实现一个支持 O(1) 取最小值的栈。这三个题分别对应第 4.3、2.3、以及线性结构教案里的附加题前两题考参数理解第三题考“用辅助结构换时间”的迁移。把这三题回传教案哪个版面学生只背了答案、哪个版面能用自己的话复述立刻可见。最后一个可以落地的技巧是给教案附加一道收尾验证题用后序遍历求二叉树高度并给出三个不同形态只有左子树、只有右子树、完全二叉树用来对照计算过程。这道题把递归终止、返回值传递和复杂度一次全查出来还能呼应前序中序遍历之外的第三种形态。教案的任务不是穷尽知识点而是把每个知识点压成可迁移的接口学生在接口和实现之间来回收放时课程才算真正落地。本文还有配套的精品资源点击获取
数据结构教案设计的可执行闭环：从线性结构到哈希的选型与实操
简介这是一份适用于高校计算机及相关专业的《数据结构》课程教案由山东科技大学泰山科技学院教师编写内容与严蔚敏《数据结构C语言版》教材配套可作为任课教师备课、出课和信管类专业学生预习复习的参考资料。教案采用课时授课计划形式包含教学目的与要求、教学重点与难点、课堂类型、教学过程设计、例题讲解与课后作业等完整环节覆盖数据结构绪论、数据类型、抽象数据类型、算法设计、数据结构的实现等章节并对逻辑结构中的线性结构、树形结构、图状结构网状结构及抽象数据类型的三元组表示展开说明。资源为单个doc文档压缩包大小522KB便于直接打印或编辑修改。目前已有420人浏览学习适合需要快速组织课堂教学或系统梳理数据结构知识框架的师生使用。1. 数据结构教案的第一页把教学目标写成人可执行的闭环很多刚站讲台的助教交上来的数据结构教案打开看其实是课程目录数组、链表、栈、队列、树、图、排序各占几页每页写着定义、代码和复杂度表。这份目录只回答了今天讲到哪回答不了学生上完这节课能不能独立写出可运行的结构。可执行的教案应该是一个闭环先说明教学目标对应哪种实际操作再给出接口与存储结构的选择理由随后落到一段能编译或能运行的代码最后用复杂度分析和测试用例收口。换句话说教案的每一节都要让学生完成从抽象到实物的转换。这篇内容适合三类人第一次主持习题课的数据结构助教考研复试前想把知识点串起来的本科生以及用算法题带新人的工程师。下面按线性结构、树与图、排序与哈希三段拆解每一段都给出可以直接抄进课堂的代码和边界参数。2. 线性结构教案顺序表与链表的选型对照2.1 教案先讲 ADT 接口还是先写存储结构从签名推导复杂度课堂的第一个分歧是顺序。一些讲师喜欢用 struct node 开场先把链表节点写出来很快学生就在指针上晕掉我倾向先用函数签名把“要做什么”固定下来再问“用什么做”。课堂上先给学生三个空实现签名让每个人说出自己预期的复杂度def push_back(container, value): 尾部插入顺序表连续写链表要看是否维护了尾指针 pass def pop_front(container): 头部删除顺序表要把后面所有元素前移链表只需移动头指针 pass def get_at(container, idx): 按下标访问顺序表基址加偏移链表要遍历 idx 步 pass这几个签名支撑一整节课。讲法是这样的先把三个接口贴在黑板上让学生各自填预期的复杂度再在实现完后回看答案是否成立。顺序表按下标访问是 O(1)因为数组的基址和下标在内存里直接可计算链表要逐个节点跳过去因此是 O(n)。尾部插入对数组是常数时间但数组满时要复制迁移链表如果额外维护一个尾指针插入也是 O(1)否则要遍历到最后又回到 O(n)。课堂结论不用背诵这个推导过程走一遍比任何口诀都牢固。这个设计让“先定义接口再讨论实现”成为这门课的默认纪律。教案里还要预留一条反问如果学生把接口写成“既支持频繁头插又支持按下标定位”该选什么——答案不是立刻给而是留到第 2.3 节末尾让复杂度表说话。2.2 循环队列手写代码用 size 字段把“空”和“满”分开顺序表这一节里我很少留“再写一个顺序表”的作业因为学生已经会了我更愿意安排手写循环队列。普通数组队列的队头删除会在数组前部留下空洞初学者最容易想到的做法是每次删除都把后续元素整体前移得到一个 O(n) 的“假删除”。循环队列用取模绕回让空间在逻辑上首尾相接教学重心在“front、rear、size 三个参数如何协同”。下面是可以在习题课上直接演示的 C 代码重点在注释标出的边界#define MAX 5 typedef struct { int data[MAX]; int front; /* 队头下标 */ int rear; /* 下一个可写位置 */ int size; /* 当前元素个数 */ } CQueue; void init_cq(CQueue *q) { q-front q-rear q-size 0; } int cq_push(CQueue *q, int v) { /* 满则返回 0 */ if (q-size MAX) return 0; q-data[q-rear] v; q-rear (q-rear 1) % MAX; /* 最后一个下标回到 0 */ q-size; return 1; } int cq_pop(CQueue *q, int *out) { /* 空则返回 0 */ if (q-size 0) return 0; *out q-data[q-front]; q-front (q-front 1) % MAX; q-size--; return 1; }代码逻辑front 指向队头元素rear 指向下一个可写空位两者下标重合时队列既可能空也可能满所以加 size 字段区分。如果不用 size常见做法是把数组开成 MAX1让 rear 追上前面的一个空闲槽表示满语义上稍微绕一点我一般先用 size 版本因为它把“满”的判断明确写成一次整数比较。取模运算(i 1) % MAX是循环结构唯一的新知识点跟前一节链表完全无关适合作为课堂演练的入口。给学生安排的两个必测用例是队列容量刚好为 MAX 时继续入队不应覆盖数据以及 pop 到 size 为 0 后继续 pop 不能访问未初始化内存。2.3 链表教案的五个必讲参数与易错点跳出语法本身链表教案比结构定义更需要讲的是五个实现参数。第一是头结点的角色带头结点可以让空表和非空表的插入删除逻辑归一不必每次都要处理“head 是否为空”的分支。第二是哨兵指针也就是 dummy node它在头插和尾插时统一了“前驱”的存在避免删除头节点时单独写一段。第三是游标更新删除时要用 prev 记住当前节点的前驱否则只能从链表头重新定位。第四是尾指针的维护状态带尾指针的链表尾插为 O(1)不带则退化为 O(n)这个差异在实验报告里很容易被观察到。第五是节点释放后的悬空引用C 语言里 free 不会自动把指针置空这是习题里最常见的隐蔽错误。放一张对照表把这一节与顺序表的对比固定下来操作顺序表数组单链表按下标取元素O(1)O(n)尾部插入O(1)扩容均摊有尾指针 O(1)否则 O(n)头部插入O(n)O(1)已知前驱的中间删除O(n)O(1)额外空间几乎无每个节点一个 next 指针表里的“尾部插入”那行最值得展开数组扩容时要把旧数据复制到新数组但如果按倍增扩容均摊后仍是 O(1)所以不能简单地说数组尾插慢链表的 O(1) 建立在尾指针存在且插入位置已知两个前提上。到这里再回头看 2.1 末尾留的问题就可以回答了频繁头插加按下标定位的组合单链表能解决头插却救不了按下标访问真要兼顾这两个要求通常需要换一层索引结构。这一句话就把教案选型从背结论变成了用复杂度倒推结构。3. 树与图教案用遍历统一递归与迭代3.1 二叉树教案把前中后序遍历讲成“访问时机”前序、中序、后序在课堂上最常见的讲法是三句口诀根左右、左根右、左右根。口诀只能应付两天后的考试放不进去。我的做法是换一个切入点每个节点都会被递归路径经过很多次遍历的结果差异只在于我们选择哪一次“发出处理动作”。用一段递归模板把三种遍历挤进同一个函数只有一个 print 的位置不同class BinaryNode: def __init__(self, v): self.v v self.left None self.right None def traverse(node, order): if node is None: return if order pre: print(node.v) # 第一次经过该节点时输出 traverse(node.left) if order in: print(node.v) # 左子树完全处理完回到当前节点 traverse(node.right) if order post: print(node.v) # 左右子树都处理完最后一次经过代码逻辑说明递归对每个节点总是“先到当前节点、进左子树、回到当前节点、进右子树、再回到当前节点”走上这么几回print 放在不同位置就得到三种顺序。参数 changeorder 文件三种文字传 pre/in/post 即可切换没有改变递归结构学生能看到遍历的本质不是三种口诀。复杂度同样不因顺序改变每个节点访问一次O(n)递归栈深度等于树高最坏情况下退化成单链二叉树时 O(n) 的空间。给这个教案配一张适用范围表把“什么时候用哪种序”落到具体场景遍历输出时机典型场景前序第一次到达节点树序列化、拷贝二叉树中序左子树返回后二叉搜索树读取有序序列后序右子树返回后子树统计、释放节点、树形DP这里各栏的数据反复强调后序不算“奇凑第三”因为它需要先拿到左子树的结果才能计算当前节点比如求树高、求路径和这种“先子后父”的顺序是递归计算的基础尤其在动态规划里几乎都是后序形态。常见见习是让 learner 从“一棵索引树”改成“前序遍历用数组存储完全二叉树的父子下标”连接从一般二叉树到堆的课文。3.2 BFS 和 DFS 教案一个状态机适配两种策略图的遍历教案如果只是分开给出 bfs 和 dfs 两段代码学生背得下来却不知道为什么这样判定访问。我常用的教学设计是三色状态机白色表示还没进入容器灰色表示已经被放入待处理集合黑色表示它的邻接边都已经展开完毕。BFS 和 DFS 的差异只剩从容器里取下一个节点时用队列还是栈。给出一版能跑无向图的有向图三色搜索代码from collections import deque def search(graph, start): WHITE, GRAY, BLACK 0, 1, 2 color {v: WHITE for v in graph} container deque([start]) # 换容器换遍历性质 color[start] GRAY result [] while container: v container.popleft() # 改成 pop() 则变为 DFS result.append(v) for w in graph[v]: if color[w] WHITE: color[w] GRAY # 入容器时立刻标记避免重复入 container.append(w) color[v] BLACK # 邻接都处理完 return result代码观察入队时就置灰而不是出队时再判重这样同一个节点不会被塞进容器多次出队时只处理当前顶点处理完的所有邻边都一次性扩展进去变黑。需要切换 DFS 时把popleft()改成pop()就是栈先出后进三色状态机的语义一行不用改。课堂问题适合放两个一个是连通分量个数——对外层 for 循环每个未访问顶点调用 search调用次数就是连通分量个数另一个是路径输出——如果在边w被置灰时记录parent[w] v等结束从目标反向回溯 parent 就能还原一条路径。这两个题把状态机用熟了比再背十个图算法更有用。用一个表列出两个版本在手写代码中的差异方便教案排版和复习版本取出策略空间增长典型感知BFS队首按层最短路径层数先出DFS栈顶往深处路径存在回溯顺序固定3.3 拓扑排序教案利用完成时间反推依赖顺序讲完三色状态机后拓扑排序可以在二十分钟内顺出来没必要换成另一套哲学。要点只有一句DFS 完全展开一个节点的所有子节点后再把该节点追加进结果栈得到的序列整体逆序就是拓扑序。上面search里把结点变黑的位置写一个order.append(v)所有结点结束后返回order[::-1]。代码可以整段放进教案def topo_sort(graph: dict): WHITE, GRAY, BLACK 0, 1, 2 state {v: WHITE for v in graph} def dfs(v, order): state[v] GRAY for w in graph[v]: if state[w] GRAY: raise RuntimeError(cycle detected: %s - %s % (v, w)) if state[w] WHITE: dfs(w, order) state[v] BLACK order.append(v) # 结束时间顺序 order [] for v in graph: if state[v] WHITE: dfs(v, order) return order[::-1]逻辑说明图中如果存在环DFS 在递归过程中会遇到一条指向灰色节点的边那个灰色节点还在当前递归栈里没有被处理完所以能立刻报错这在教案里比“Kahn 算法数入度”更显眼。时间复杂度和 BFS/DFS 一样是 O(VE)其中 E 是边数因为每条边在遍历时最多访问一次。参数可改项实际上是方向order存储了完成顺序反转它排出的序列才是依赖方向正确的顺序如果用了不反转的写法结果会变成反向依赖单测里用一个三节点依赖链马上就能暴露坏出来。教案课后的扩展提问如果把 result 从栈的逆序改成每次在头部插入order.insert(0, v)会导致结果是 O(V^2)因为插入头部的线性开销累积这个坑值得让学生自己复现一遍。4. 排序与哈希教案把背代码改成读参数4.1 排序算法教案的顺序选择从冒泡到归并为什么不能跳排序教案的首要决定是教学顺序而不是代码。我见过的几份数据结构教案都按冒泡、选择、插入、快排、归并把算法逐个排开实际上前三个的定位完全不同。冒泡排在最前的价值不在效率而在于它能引出“逆序对”“交换次数”“一趟无交换提前结束”三个概念当输入已升序时冒泡可以做到 O(n)这个特例让“最好/最坏复杂度”第一次变得可见。插入排序则承接“排序前缀”概念在几乎有序的序列上同样能接近 O(n)所以工程上常把它放在快排分区规模较小时收底。选择排序几乎被实用代码遗弃但它是“每趟固定选最值”的直观模型用来和冒泡对比稳定性时效果很好。快排和归并才是复杂度教学的主战场。快排强调的是划分点选择、逆序退化、以及“基准等于重复元素时会不会无限递归”而归并强调固定折半的稳定分治代价是额外 O(n) 空间且原地归并的写法过于复杂教案不必展开。我把四者的对比浓缩为一句话从冒泡到归并参数的变化是“交换驱动、插值驱动、分治与是否稳定”复杂度只是结果不是教学顺序本身。4.2 用 key 参数把快排写成参数化教案工程里的排序函数真正的接口不是“如何比较两个数字”而是“如何从对象提取排序键”。课堂上学生手写的快排返回值硬邦邦而 Python 的sorted支持key与reverse这个差别正好可以当作参数化教学的入口。给一份可运行、可改参数的快排实现def quick_sort(items, keylambda x: x): if len(items) 1: return list(items) pivot items[len(items) // 2] left [x for x in items if key(x) key(pivot)] same [x for x in items if key(x) key(pivot)] right [x for x in items if key(x) key(pivot)] return quick_sort(left, key) same quick_sort(right, key) # 按字符串长度升序逆序可把 key 换成 lambda x: -len(x) words [binary, tree, graph, queue] print(quick_sort(words, keylen))逻辑说明key是提取排序依据的可调用对象比较动作全由它驱动len 作为 key 时排序比较的是各字符串的长度而不是字符串本身。这种设计比在函数内部写死if a b更容易让学生理解 Python 标准库里key与cmp的差别——现代接口大都保留 key返回的是“排序依据位置”。参数可改项是稳定性本实现用left same right分组相同键的元素全被收进 same天然稳定而经典 Lomuto 划分交换相同的元素时稳定性会丢正好用来解释为什么工程排序宁愿用插排收底快排后半段。复杂度pivot 选择每次取中间下标对随机分布接近 O(n log n)对逆序数据则会退化到 O(n^2)所以教案第二问通常是“如何选 pivot 避免退化”往往就引出随机基准或三数取中。一个练习能检验学生理解数据是一批字典对象如items [{name: a, age: 3}, {name: b, age: 2}]用keylambda d: d[age]快排一遍就能确认结构是否成熟。这种在教案代码里做泛化的做法完胜让学生按教材默写一个只处理 int 的程序。4.3 哈希教案装载因子、哈希链与冲突解决策略哈希表的教案重点在“哈希函数”“装载因子”“冲突解决”三个参数而不是具体到某一种哈希函数。课堂从链地址法入手最直观将桶设为链表冲突的键挂在同一桶后面桶的链表在课里就叫哈希链它可以借用第 2.3 节讲的链表操作。给一份可跑的极简实现并让capacity与load_factor成为显式字段class ChainHash: def __init__(self, capacity16, load_factor0.75): self.capacity capacity self.load_factor load_factor self.table [[] for _ in range(capacity)] self.length 0 def _index(self, key): return hash(key) % self.capacity def put(self, key, value): bucket self.table[self._index(key)] for i, (k, v) in enumerate(bucket): if k key: # 键已存在更新 bucket[i] (key, value) return bucket.append((key, value)) # 新键挂到哈希链 self.length 1 if self.length / self.capacity self.load_factor: self._resize(self.capacity * 2) # 扩容这里只保留入口 def get(self, key): bucket self.table[self._index(key)] for k, v in bucket: if k key: return v return None代码把哈希链实现成 Python 的 list也就是当好结点数组的链表化方案hash(key) % capacity是把任意键映射到下标取模运算让桶号分布。装载因子在这里是触发扩容的阈值不调它只调 capacity 的常见错误是桶数翻倍、冲突概率却没按期望下降因为装载因子才是有效控制冲突的那个比值。复杂度上理想哈希链的查找是 O(1 链长)链长受装载因子约束所以把 load_factor 从 0.75 改成 1.0 测同一组冲突键感知差异会很直观。下表把三种冲突解法放到同一张对比里用于课堂结尾的提问冲突解法平均查找复杂度删除代价关键限制线性探测依赖探测步长需要删除标记墓碑容易在连续区块堆积二次探测好于线性探测同样要墓碑标记必须保证覆盖整个表链地址法O(1链长)直接删链表节点每个桶多了指针开销表格下面的课堂练习容量 8、装载因子 0.75连续插入哈希值对 8 取模相等的 6 个键手画出哈希链变长过程并指出扩容发生的那一刻。这样哈希不再是“先有函数再填表”的死记而是一个由参数控制的动态过程。5. 把教案回收成实验报告与面试验证题数据结构教案在课堂上讲完并不能算收工它最后应该在实验报告和面试题两种场景里被回收验证。一份我认可的实验报告包含五个部分实验目标、设计说明、关键代码、测试用例、性能记录恰好对应教案的闭环——目标对应“这节课解决什么现实操作”设计对应接口与存储结构选择关键代码对应可运行实现测试用例覆盖空表、满表、重复键、最大规模四种边界性能记录让复杂度从纸面变成曲线。用这个模板反向检查教案质量比听课更有用。教案如果连测试用例和复杂度都讲清楚了学生写完报告后会余裕地发现期末考试已经不需要临时翻书因为报告本身就是按考点组织的材料。面试角度最常见的是三个串联测试哈希表装载因子定在多少、为什么经验值选 0.75单链表按已知前驱删除节点能否做到 O(1)实现一个支持 O(1) 取最小值的栈。这三个题分别对应第 4.3、2.3、以及线性结构教案里的附加题前两题考参数理解第三题考“用辅助结构换时间”的迁移。把这三题回传教案哪个版面学生只背了答案、哪个版面能用自己的话复述立刻可见。最后一个可以落地的技巧是给教案附加一道收尾验证题用后序遍历求二叉树高度并给出三个不同形态只有左子树、只有右子树、完全二叉树用来对照计算过程。这道题把递归终止、返回值传递和复杂度一次全查出来还能呼应前序中序遍历之外的第三种形态。教案的任务不是穷尽知识点而是把每个知识点压成可迁移的接口学生在接口和实现之间来回收放时课程才算真正落地。本文还有配套的精品资源点击获取