简介针对计算机专业《数据结构》期末复习与知识梳理的需求这份教学课件以浙江大学陈越老师课堂内容为基础整理共300页PPT覆盖课程开篇的核心内容与常见考点。全包为单个PPT文件.ppt格式压缩包大小14.59MB下载后可直接翻页学习适合考研、期末备考或教师备课选用。课件从“数据结构是计算机中存储、组织数据的方式”这一定义切入围绕图书摆放问题、PrintN循环与递归实现、多项式计算的直接法与秦九韶法、clock()效率测试等经典示例展开帮助理解算法效率与数据组织方式、空间利用率、算法巧妙程度的关系。同时系统梳理了数据对象、操作、算法、逻辑结构、物理结构、数据类型及抽象数据类型等基础术语并以矩阵ADT为例说明操作集与数据对象集的抽象描述方式。已有206人学习下载内容贴合理论课堂讲义适合快速回顾关键概念、整理复习笔记。1. 这份300页PPT为什么适合数据结构期末复习数据结构这门课很多人复习到一半就卡在“概念都懂题不会做”。我整理过不少课程资料浙江大学陈越老师的这份《数据结构》课件约300页属于少见的“用例子带概念”的PPT。第1章概论里就用“图书馆怎么摆书”“PrintN递归打印”“多项式求值”三个例子把数据组织方式、空间复杂度、时间复杂度讲透了。对期末复习和考研党来说它最好的地方不是概念罗列而是把“为什么这个方案更好”的推导过程完整保留下来了。如果你正在找一份能照着推导、能把算法复杂度落到纸面的课程资料这份PPT值得你从头到尾过一遍。2. 从三个经典例子读懂第1章代码、执行过程与效率对比第1章概论占了这份PPT约25页却包含了整个数据结构课程最重要的思维训练。这里我用PPT里的三个例子展开讲顺带把每段代码都跑一遍的思考过程写出来方便你复习时直接对照电脑操作。2.1 图书摆放问题逻辑结构的选择决定了查找与插入的成本课件开头抛出一个生活化的问题图书馆里有一堆书怎么摆才能让读者方便找到《数据结构》这本书PPT给了三种方法方法1随便放新书哪里有空插哪里。查找时只能一本一本翻效率极低。 方法2按书名拼音字母顺序排。查找变快了但插入新书时需要把后面的书全部挪动遇到中间插入会很痛苦。 方法3先分区域每类书内部再按拼音顺序排。查找和插入都相对可控代价是维护规则更复杂。这个问题看起来不像代码题但它本质上是“数据组织方式的选择要跟着操作来定”。如果查找频率远高于插入频率方法2是可行的如果插入也很频繁方法3的“分类局部有序”就是更折中的方案。对应到数据结构课程里这其实就是逻辑结构的选择方法1是散乱集合方法2是线性有序方法3是“先分成树状类别、每类内部再线性排列”。你学后面的线性表、树会发现所有结构都是为了在“查找”和“插入/删除”之间做权衡。这里没有代码但你可以做一个简单的实验来加深理解拿一组随机整数先存进数组再存进链表分别对比中间插入和查找的时间。课件后面讲线性表时也会回到这个主题。我在复习时会把这种例子贴在笔记开头提醒自己数据结构选型的本质是“操作成本”的博弈。2.2 PrintN循环与递归的空间复杂度对比PPT第二个例子是写一个函数PrintN传入正整数N顺序打印1到N。给了两个版本。循环版本void PrintN( int N ) { int i; for ( i 1; i N; i ) printf( %d\n, i ); return; }逻辑说明维护一个循环变量i从1递增到N每次打印当前值。整个过程只用一个固定大小的变量空间占用不随N变化。递归版本void PrintN( int N ) { if ( !N ) return; PrintN( N - 1 ); printf( %d\n, N ); return; }逻辑说明调用PrintN(N)时先把任务拆成PrintN(N-1)等子任务打印完再打印N。子任务没结束时当前函数调用不会返回系统调用栈上会保留一帧里面存着参数N和返回地址。N每减一次栈就多一层所以空间复杂度是S(n) c·nc是一个调用帧占用的固定空间。参数说明这里的N是正整数参数。循环版本对N大小没有额外敏感度递归版本则在N较大时可能直接耗尽栈空间。我在电脑上跑过N10万时递归版本直接崩换成循环版本瞬间打完。这不是编译器问题而是递归的隐式空间消耗。PPT后面还专门提到这个例子的意义在于说明“解决问题方法的效率跟空间的利用效率有关”。很多人只盯着时间复杂度和快慢忽略了递归的栈空间也是一笔账。复习时如果你要写递归代码先估算一下递归深度深度在万级以上的就要考虑改成显式栈或循环。2.3 多项式求值秦九韶法为什么比直接法快一个数量级第三个例子是多项式求值给定阶数n和系数数组a[]计算f(x) a0 a1x a2x² … anxⁿ在给定点x的值。PPT给了两种方法并指出秦九韶法的计算速度比直接法快了一个数量级。直接法double f( int n, double a[], double x ) { int i; double p a[0]; for ( i 1; i n; i ) p a[i] * pow( x, i ); return p; }逻辑说明从i1到n每一项用pow(x, i)计算x的i次幂再乘系数累加。每一项的幂运算是分开算的导致大量重复运算。按PPT后面的分析这个算法时间T2(n) c1·n² c2·n是平方级。秦九韶法double f( int n, double a[], double x ) { int i; double p a[n]; for ( i n; i 0; i-- ) p a[i-1] x * p; return p; }逻辑说明从最高次项开始p先等于an然后每轮p a[i-1] x * p。括号展开后正好是 a0 x(a1 x(a2 … x·an)…) 。整个循环只有n次加法和n次乘法时间复杂度T1(n) c·n线性级。参数说明系数数组a[]从下标0到nx是自变量。用秦九韶法时p的初值必须取a[n]循环从n递减到1最后p就是多项式值。如果写成从0开始就有问题。为什么快一个数量级核心在于避免了pow。pow(x, i)内部通过反复乘法实现算到x的n次幂时已经积累了n次乘法。直接法每一项都重新算幂总共约n²/2次乘法秦九韶法每次只做一次乘法。当n很大时这个差距非常明显。我在实际跑多项式拟合时n1000直接法慢得像蜗牛秦九韶法几乎是瞬时。这里可以做一张对比表复习时贴在笔记旁边对比项直接法秦九韶法核心运算每项独立pow(x,i)每轮一次乘法和一次加法乘法次数约12…n次n次时间复杂度O(n²)O(n)代码难度简单直观需要理解递推PPT还给出了一段用clock()测运行时间的框架值得单独拿出来练习。原文代码是#include stdio.h #include time.h clock_t start, stop; double duration; int main() { start clock(); function(); /* 被测函数 */ stop clock(); duration ((double)(stop - start)) / CLK_TCK; return 0; }逻辑说明start和stop记录被测函数前后的CPU时钟差值除以CLK_TCK得到秒数。注意被测函数执行时间太短时duration可能是0需要让函数重复跑很多次再除总数。参数说明CLK_TCK在不同平台上可能是每秒1000或每秒1000000即使不关心具体精度也能用于同一环境下的相对比较。我一般会加一个外层循环比如把被测函数跑1万次然后总耗时除以1万这样才测得准。这个框架在后续章节测试排序、查找算法时也会反复用。3. 抽象数据类型与算法复杂度把“黑匣子”翻译成能考试的结论第1章后半部分正式引入术语数据对象、操作、算法、逻辑结构、物理结构、数据类型、抽象数据类型。这些概念单独看很抽象但结合例子就顺理成章。我在这一章里帮你把这些名词串成“考试答题语言”。3.1 抽象数据类型只有“是什么”不谈“怎么做”课件里对抽象数据类型ADT的解释是描述数据类型的方法不依赖于具体实现数据对象集和操作集的描述与机器无关、与物理结构无关、与算法和语言无关。简单说ADT只回答“有哪些数据、支持哪些操作”不回答“怎么存、怎么算”。以PPT的矩阵ADT为例类型名称Matrix数据对象集是一个M×N矩阵操作集包括Create、GetMaxRow、GetMaxCol、GetEntry、Add、Multiply。定义操作时只写“返回矩阵总行数”“返回A和B相加的结果如果行列不一致返回错误标志”不写矩阵到底用二维数组还是用稀疏存储。这就是抽象矩阵。这里有个判断技巧考试里经常问“某某设计是不是抽象数据类型”关键看描述里有没有出现“数组”“链表”“指针”这类实现词汇。只要没提实现细节就是抽象一旦说“用一个二维数组存储”就落到物理结构了。计算机专业的学生常在这里犯迷糊复习时要把这个判断标准刻在脑子里。抽象数据类型的价值还在于它是后续所有结构的学习框架。线性表、栈、队列、树、图每一章都会先给出ADT定义再讨论具体实现。如果你在第1章理解了“定义与实现分离”后面学顺序表和链表时就不会被“表”和“链”的物理结构绕晕。3.2 复杂度的渐进表示法O/Ω/Θ怎么用PPT用数学定义引入渐进符号。T(n) O(f(n))表示存在常数c0和n00当n≥n0时T(n)≤c·f(n)T(n) Ω(g(n))表示存在常数c0和n00当n≥n0时T(n)≥c·g(n)T(n) Θ(h(n))表示既有O又有Ω。翻译成人话O是上界Ω是下界Θ是精确阶。这套符号是在帮我们忽略低阶项和常数。PPT专门讨论了一个问题程序A执行3n4步程序B执行2n2步A一定比B慢吗答案是No。因为渐进分析只关心n充分大时的增长趋势3n和2n都是线性增长差别是常数倍。真正决定“数量级”的是n的次方不是系数。厚度体现在这里很多人从“快慢”角度理解复杂度但考试要你证明或比较时必须写出定义。我复习时会把O、Ω、Θ三个定义抄在一张卡上然后给自己出一道题证明2n²3n O(n²)。步骤是先找c和n0比如c5n01当n≥1时2n²3n≤5n²成立。这类题在考研里出现过基础但重要。判断符号时还有一个细节如果只有O说明说的是上界如果说“平均时间复杂度”那是在讨论Tavg(n)。PPT里指出Tavg(n)≤Tworst(n)而且最坏情况分析通常更容易。考试中没特别说明时默认说的是最坏情况复杂度。3.3 复杂度分析的小窍门串行、嵌套、分支怎么算PPT总结了几个复杂度计算规则我按自己的理解整理成下面这张表复习时可以直接参考代码结构复杂度计算例子两段算法串联T1 T2 max(O(f1), O(f2))先做O(n)再做O(1)整体O(n)两段算法嵌套T1 × T2 O(f1 × f2)两层循环各n次整体O(n²)if-else分支max(条件判断, 两个分支)无论走哪个分支取最贵的单层循环循环次数 × 循环体复杂度for(i0;iN;i){xy*xz;}是O(N)这些规则本质上是“取最大头”。实际刷题时嵌套循环看层数循环体内有函数调用要看函数本身的复杂度。考研里常考的是递归函数的复杂度递推式比如T(n)T(n-1)1是O(n)T(n)2T(n/2)n是O(n log n)。PPT没有展开递归式求解但你可以把第1章这些基础规则作为起点后续学归并排序时再补递推树的推导。这里特别提醒一点串联复杂度取max的前提是两段代码确实按顺序执行。如果第二段代码依赖第一段的结果并且每个结果都要遍历那可能变成乘积而不是max。判断方法就是看外层是否多套了一层循环。3.4 从函数增长表看复杂度差距log n 到 n!PPT给了一张常用函数增长表输入规模n从8、16、32逐步翻倍各函数值的变化非常直观。这里我整理出一份简化版复习时用来训练“一眼看出数量级”的能力nlog2 nnn log2 nn²n³2ⁿ83824645122561641664256409665536325321601024327684294967296看这张表n32时2ⁿ已经超过42亿而n²才1024。这就是为什么说“指数级算法在较大规模下根本不可用”。很多初学者容易低估O(n²)和O(n log n)的差距等到处理实际数据量就能体会到。考研里经常会问“某算法优化前后从O(n²)降到O(n log n)数据量扩大10倍运行时间大概怎么变”这时候用这张表的趋势心算就够。理解这张表还有一个重要应用判断一个算法是不是“好算法”。PPT里的结论是好的算法通常让复杂度保持在n log n或更低。超过n²就需要注意超过2ⁿ基本只适合论文或极小规模场景。复习数据结构时每学一个新算法都去“查一次表”把这个算法的复杂度放到这几个档位里比背结论更直观。4. 把PPT读成自己的复习资料三步整理法很多人下载课件后只是从头翻到尾合上PPT还是记不住。这份PPT的好处是信息密度高、案例集中但需要主动加工。下面是我自己比较实用的三步整理法适合期末复习和考研二轮复习。4.1 第一步按“定义-例子-复杂度”给每页PPT打标签不要按页码顺序死记而是按知识类型给每页打标签。我的做法是准备一张A4纸把PPT的章节拆成三类标签“定义类”记录术语的准确表述比如数据结构定义、抽象数据类型、逻辑结构、物理结构。 “例子类”记录PPT里出现的每一个例子的输入、输出和关键代码比如图书摆放、PrintN、多项式求值。 “复杂度类”记录每个算法的时间复杂度和空间复杂度以及推导依据。以这份PPT第1章为例你可以做成这样的清单数据结构的定义计算机中存储、组织数据的方式精心选择可带来最优效率算法。 逻辑结构线性、树、图。 物理结构顺序存储、链式存储。 抽象数据类型只描述“是什么”不涉及“怎么做”。 算法五要求输入、输出、确定性、有限性、可行性。 复杂度最坏Tworst(n)、平均Tavg(n)。做完这张清单第1章的骨架就到手了。后面每一章线性表、栈、队列、树、图、排序都用同样方法整理考前只需要看自己的清单不用重翻300页。4.2 第二步把例子的C代码变成自己的跑一遍并记录时间PPT里所有代码都是C语言片段不能直接复制运行因为缺少main函数和头文件。我建议每看到一个算法先自己补全成完整程序再编译运行。具体步骤新建一个c文件比如poly.c写出多项式直接法和秦九韶法的完整代码#include stdio.h #include math.h double direct( int n, double a[], double x ) { double p a[0]; int i; for ( i 1; i n; i ) p a[i] * pow( x, i ); return p; } double qinjiushao( int n, double a[], double x ) { double p a[n]; int i; for ( i n; i 0; i-- ) p a[i-1] x * p; return p; } int main() { double a[4] {1, 2, 3, 4}; printf( direct %f\n, direct( 3, a, 2 ) ); printf( qinjiushao %f\n, qinjiushao( 3, a, 2 ) ); return 0; }逻辑说明这里a[4]存了从0次到3次的系数x2。直接法和秦九韶法结果应该一致如果一致说明实现正确。参数说明把n改成更大的值比如100循环次数增加可以更明显感受到时间差异。编译命令gcc -o poly poly.c -lm ./poly逻辑说明-lm用来链接数学库因为用了pow函数。如果直接法输出和秦九韶法不同多半是循环边界或初始值写错。跑通之后再用clock()框架计算耗时把被测函数放到循环里跑10000次时间就出来了。这一步的价值是把PPT里的被动阅读变成主动实验。我复习树结构时也把PPT里的遍历代码改成完整二叉树程序用同一棵树的输出验证前序、中序、后序关系。这样比背代码有效得多。4.3 第三步用“一句话笔记”对抗遗忘整理完标签和代码后再做一件事每个小节用一句话笔记。不要写长句子只写“这个问题在解决什么”。比如图书摆放插入频繁用“分区局部有序”查找频繁用“全局有序”。 PrintN循环省空间递归费空间递归深度大会爆栈。 多项式求值秦九韶法把O(n²)降成O(n)核心是避免重复计算幂。 抽象数据类型只关心能做什么不关心怎么做。这句话既是索引也是记忆锚点。考前脑子里快速过一遍这些句子比重新翻PPT快得多。我通常会在A4纸的背面写这些一句话笔记配合前面打标签的清单形成一份只有3页纸的“数据结构急救包”。期末复习时这套东西比厚厚的课本更实用。4.4 用教材补全细节参考书怎么选这份PPT是教学课件页数再多也不可能把所有推导细节都写在上面。如果你发现某个概念只记住了定义但不会应用我建议找一本C语言描述的数据结构教材做对照。常见的是严蔚敏的《数据结构C语言版》或者Mark Allen Weiss的《数据结构与算法分析C语言描述》。陈越老师课件的章节安排和这类经典教材对应度很高先讲概念再讲线性表、栈队列、树、图、排序最后是散列和文件。把PPT当提纲把教材当详解复习效率会高很多。具体做法是每学完PPT的一章去教材里找一道对应的例题手推一遍。比如看完第1章立刻做“最大子列和问题”的四种算法复杂度分析。这个题在很多教材里反复出现正好用上你刚学的O、Ω、Θ和复杂度计算规则。做完再回到PPT看老师的讲解思路会有“原来如此”的感觉。5. 避坑与排查用这份PPT复习时最常见的5个坑下面这几条都是实际复习时会遇到的翻车现场我按“现象→原因→解决”的顺序写出来你可以对照排查。5.1 递归PrintN在N很大时崩溃不是编译器坏了现象写递归版PrintN传N100000程序一闪而过或直接报错退出改成循环版就好。原因递归版每次调用都在系统栈上压入一帧空间复杂度S(n)c·n。N很大时栈空间被耗尽程序被操作系统终止。解决先估算递归深度超过万级就不要用递归。改用循环或者用显式栈模拟递归。学习时这个例子本身是为了提醒你空间复杂度所以不要纠结“为什么别人的递归没崩”而是要把这个场景记成“递归的空间开销是真实的”。如果你用的是Linux可以在终端里执行ulimit -s查看默认栈大小再去估算能压多少层。这样能把“要背的概念”变成手上能算的数字。5.2 clock()测出0秒不代表算法快现象用课件里的clock()框架测多项式求值两种方法耗时全是0无法看出差别。原因被测函数执行时间远小于系统计时精度clock()的返回值变化量不足以体现差异。解决把被测函数放进一个大循环里比如循环10万次再除以循环次数start clock(); for ( i 0; i 100000; i ) f( 100, a, 2 ); stop clock(); duration ((double)(stop - start)) / CLK_TCK / 100000;这样可以测出单次平均耗时。如果你在Linux下也可以改用clock_gettime但对于这份PPT的教学场景clock()配合循环已经够用。注意别把循环次数设得太离谱否则测一次要等很久又是一个时间黑洞。5.3 把常数差异当成复杂度差异现象看到程序A执行3n4步程序B执行2n2步就认为B一定更快或者看到系数大就认定复杂度高。原因渐进分析法刻意忽略常数和低阶项只关注n充分大时的增长趋势。3n和2n都是O(n)常数差异不改变数量级。解决比较复杂度时只看O、Ω、Θ级别。只有在同一个级别内部比如两个都O(n)才谈常数优化。考试答题时先写数量级再写常数不要混在一起。考研选择题常在这里埋坑。我在复习时给自己立了一个规矩凡是看到“哪个更快”的问题先把两个算法在n10、100、1000下的增长趋势写出来再决定是否值得谈常数。这个习惯帮我避开了很多直觉错误。5.4 分不清逻辑结构和物理结构现象把“书本按类别分区摆放”当成物理存储方式认为这就是链式存储或顺序存储。原因把抽象的组织关系和内存中的实际存储方式混为一谈。逻辑结构描述的是数据元素之间的逻辑关系线性、树、图物理结构描述的是这些数据在内存里的表示方式顺序、链式。图书按类别分区域属于逻辑上的树状组织至于书架上的书是连续排列还是通过索引关联是另一回事。解决判断时问自己一个问题描述里能看出“内存地址”或“指针”吗如果没有就是逻辑层面的东西。复习到链表时把“链式存储”想成“每个节点里存着下一个节点的地址”就不会和逻辑结构混淆。5.5 秦九韶法循环边界写错现象实现秦九韶法时结果和直接法不一致或者对高位系数出错。原因循环边界和p的初值没配对。正确的写法是pa[n]然后从in倒着做到i1每轮pa[i-1]x*p。有人从in-1开始或者把p初值设为0都会漏掉最高次项。解决写完后用一个小例子验证比如n2系数{1,2,3}x2。手算结果应是12·23·417。代码里设断点或者打印中间p值检查第一轮是不是pa[1]xa[2] 22·38第二轮pa[0]x811617。这个验证过程还能帮你理解秦九韶法的递推结构不只是背代码。6. 进阶与验证把这套课件变成考研/期末的答题框架当你把第1章真正吃透后可以继续用同样的方法处理后序章节。这里分享一个进阶用法把课件里的每个结构/算法做成一张“选型决策卡”用来对付期末大题和考研设计题。决策卡正面写四行适用场景、核心操作、时间/空间复杂度、一句话代码模板。比如线性表查找频繁用顺序表插入删除频繁用链表顺序表支持O(1)随机访问链表插入O(1)但查找O(n)。 栈递归、表达式求值、括号匹配入栈出栈O(1)栈满要注意。 队列BFS、缓冲区循环队列判满条件要背。 树层次关系、排序树、堆遍历复杂度O(n)查找树平均O(log n)。 图路径搜索、最小生成树邻接矩阵适合稠密图邻接表适合稀疏图。每张卡都回到第1章那个核心问题“这个结构到底在哪个操作上付出了什么代价”比如数组随机访问代价低插入要搬移链表反过来。考试时遇到设计题先在纸上列出可选结构再按“操作频率”排除最后得到答案。我自己的血泪经验是复杂度背不下来时不要硬背而是把课件里每个算法的代码在脑子里走一遍数一数循环层数和递归层数。比如快排递归树高度log n每层总扫描n所以平均O(n log n)。PPT第1章的复杂度分析技巧后面所有章节都在反复用。验证方式也很简单找一套期末或考研真题把每个选择题的复杂度选项用你的决策卡过一遍填空题里的概念用第4章做的“一句话笔记”回答。如果正确率超过80%说明课件内容已经内化成自己的东西。从那以后我每次复习数据结构都会强制走一遍“打标签-跑代码-做决策卡”三步效率比单纯翻PPT高很多。希望帮到你。本文还有配套的精品资源点击获取
数据结构期末复习：从三个经典例子吃透复杂度分析
简介针对计算机专业《数据结构》期末复习与知识梳理的需求这份教学课件以浙江大学陈越老师课堂内容为基础整理共300页PPT覆盖课程开篇的核心内容与常见考点。全包为单个PPT文件.ppt格式压缩包大小14.59MB下载后可直接翻页学习适合考研、期末备考或教师备课选用。课件从“数据结构是计算机中存储、组织数据的方式”这一定义切入围绕图书摆放问题、PrintN循环与递归实现、多项式计算的直接法与秦九韶法、clock()效率测试等经典示例展开帮助理解算法效率与数据组织方式、空间利用率、算法巧妙程度的关系。同时系统梳理了数据对象、操作、算法、逻辑结构、物理结构、数据类型及抽象数据类型等基础术语并以矩阵ADT为例说明操作集与数据对象集的抽象描述方式。已有206人学习下载内容贴合理论课堂讲义适合快速回顾关键概念、整理复习笔记。1. 这份300页PPT为什么适合数据结构期末复习数据结构这门课很多人复习到一半就卡在“概念都懂题不会做”。我整理过不少课程资料浙江大学陈越老师的这份《数据结构》课件约300页属于少见的“用例子带概念”的PPT。第1章概论里就用“图书馆怎么摆书”“PrintN递归打印”“多项式求值”三个例子把数据组织方式、空间复杂度、时间复杂度讲透了。对期末复习和考研党来说它最好的地方不是概念罗列而是把“为什么这个方案更好”的推导过程完整保留下来了。如果你正在找一份能照着推导、能把算法复杂度落到纸面的课程资料这份PPT值得你从头到尾过一遍。2. 从三个经典例子读懂第1章代码、执行过程与效率对比第1章概论占了这份PPT约25页却包含了整个数据结构课程最重要的思维训练。这里我用PPT里的三个例子展开讲顺带把每段代码都跑一遍的思考过程写出来方便你复习时直接对照电脑操作。2.1 图书摆放问题逻辑结构的选择决定了查找与插入的成本课件开头抛出一个生活化的问题图书馆里有一堆书怎么摆才能让读者方便找到《数据结构》这本书PPT给了三种方法方法1随便放新书哪里有空插哪里。查找时只能一本一本翻效率极低。 方法2按书名拼音字母顺序排。查找变快了但插入新书时需要把后面的书全部挪动遇到中间插入会很痛苦。 方法3先分区域每类书内部再按拼音顺序排。查找和插入都相对可控代价是维护规则更复杂。这个问题看起来不像代码题但它本质上是“数据组织方式的选择要跟着操作来定”。如果查找频率远高于插入频率方法2是可行的如果插入也很频繁方法3的“分类局部有序”就是更折中的方案。对应到数据结构课程里这其实就是逻辑结构的选择方法1是散乱集合方法2是线性有序方法3是“先分成树状类别、每类内部再线性排列”。你学后面的线性表、树会发现所有结构都是为了在“查找”和“插入/删除”之间做权衡。这里没有代码但你可以做一个简单的实验来加深理解拿一组随机整数先存进数组再存进链表分别对比中间插入和查找的时间。课件后面讲线性表时也会回到这个主题。我在复习时会把这种例子贴在笔记开头提醒自己数据结构选型的本质是“操作成本”的博弈。2.2 PrintN循环与递归的空间复杂度对比PPT第二个例子是写一个函数PrintN传入正整数N顺序打印1到N。给了两个版本。循环版本void PrintN( int N ) { int i; for ( i 1; i N; i ) printf( %d\n, i ); return; }逻辑说明维护一个循环变量i从1递增到N每次打印当前值。整个过程只用一个固定大小的变量空间占用不随N变化。递归版本void PrintN( int N ) { if ( !N ) return; PrintN( N - 1 ); printf( %d\n, N ); return; }逻辑说明调用PrintN(N)时先把任务拆成PrintN(N-1)等子任务打印完再打印N。子任务没结束时当前函数调用不会返回系统调用栈上会保留一帧里面存着参数N和返回地址。N每减一次栈就多一层所以空间复杂度是S(n) c·nc是一个调用帧占用的固定空间。参数说明这里的N是正整数参数。循环版本对N大小没有额外敏感度递归版本则在N较大时可能直接耗尽栈空间。我在电脑上跑过N10万时递归版本直接崩换成循环版本瞬间打完。这不是编译器问题而是递归的隐式空间消耗。PPT后面还专门提到这个例子的意义在于说明“解决问题方法的效率跟空间的利用效率有关”。很多人只盯着时间复杂度和快慢忽略了递归的栈空间也是一笔账。复习时如果你要写递归代码先估算一下递归深度深度在万级以上的就要考虑改成显式栈或循环。2.3 多项式求值秦九韶法为什么比直接法快一个数量级第三个例子是多项式求值给定阶数n和系数数组a[]计算f(x) a0 a1x a2x² … anxⁿ在给定点x的值。PPT给了两种方法并指出秦九韶法的计算速度比直接法快了一个数量级。直接法double f( int n, double a[], double x ) { int i; double p a[0]; for ( i 1; i n; i ) p a[i] * pow( x, i ); return p; }逻辑说明从i1到n每一项用pow(x, i)计算x的i次幂再乘系数累加。每一项的幂运算是分开算的导致大量重复运算。按PPT后面的分析这个算法时间T2(n) c1·n² c2·n是平方级。秦九韶法double f( int n, double a[], double x ) { int i; double p a[n]; for ( i n; i 0; i-- ) p a[i-1] x * p; return p; }逻辑说明从最高次项开始p先等于an然后每轮p a[i-1] x * p。括号展开后正好是 a0 x(a1 x(a2 … x·an)…) 。整个循环只有n次加法和n次乘法时间复杂度T1(n) c·n线性级。参数说明系数数组a[]从下标0到nx是自变量。用秦九韶法时p的初值必须取a[n]循环从n递减到1最后p就是多项式值。如果写成从0开始就有问题。为什么快一个数量级核心在于避免了pow。pow(x, i)内部通过反复乘法实现算到x的n次幂时已经积累了n次乘法。直接法每一项都重新算幂总共约n²/2次乘法秦九韶法每次只做一次乘法。当n很大时这个差距非常明显。我在实际跑多项式拟合时n1000直接法慢得像蜗牛秦九韶法几乎是瞬时。这里可以做一张对比表复习时贴在笔记旁边对比项直接法秦九韶法核心运算每项独立pow(x,i)每轮一次乘法和一次加法乘法次数约12…n次n次时间复杂度O(n²)O(n)代码难度简单直观需要理解递推PPT还给出了一段用clock()测运行时间的框架值得单独拿出来练习。原文代码是#include stdio.h #include time.h clock_t start, stop; double duration; int main() { start clock(); function(); /* 被测函数 */ stop clock(); duration ((double)(stop - start)) / CLK_TCK; return 0; }逻辑说明start和stop记录被测函数前后的CPU时钟差值除以CLK_TCK得到秒数。注意被测函数执行时间太短时duration可能是0需要让函数重复跑很多次再除总数。参数说明CLK_TCK在不同平台上可能是每秒1000或每秒1000000即使不关心具体精度也能用于同一环境下的相对比较。我一般会加一个外层循环比如把被测函数跑1万次然后总耗时除以1万这样才测得准。这个框架在后续章节测试排序、查找算法时也会反复用。3. 抽象数据类型与算法复杂度把“黑匣子”翻译成能考试的结论第1章后半部分正式引入术语数据对象、操作、算法、逻辑结构、物理结构、数据类型、抽象数据类型。这些概念单独看很抽象但结合例子就顺理成章。我在这一章里帮你把这些名词串成“考试答题语言”。3.1 抽象数据类型只有“是什么”不谈“怎么做”课件里对抽象数据类型ADT的解释是描述数据类型的方法不依赖于具体实现数据对象集和操作集的描述与机器无关、与物理结构无关、与算法和语言无关。简单说ADT只回答“有哪些数据、支持哪些操作”不回答“怎么存、怎么算”。以PPT的矩阵ADT为例类型名称Matrix数据对象集是一个M×N矩阵操作集包括Create、GetMaxRow、GetMaxCol、GetEntry、Add、Multiply。定义操作时只写“返回矩阵总行数”“返回A和B相加的结果如果行列不一致返回错误标志”不写矩阵到底用二维数组还是用稀疏存储。这就是抽象矩阵。这里有个判断技巧考试里经常问“某某设计是不是抽象数据类型”关键看描述里有没有出现“数组”“链表”“指针”这类实现词汇。只要没提实现细节就是抽象一旦说“用一个二维数组存储”就落到物理结构了。计算机专业的学生常在这里犯迷糊复习时要把这个判断标准刻在脑子里。抽象数据类型的价值还在于它是后续所有结构的学习框架。线性表、栈、队列、树、图每一章都会先给出ADT定义再讨论具体实现。如果你在第1章理解了“定义与实现分离”后面学顺序表和链表时就不会被“表”和“链”的物理结构绕晕。3.2 复杂度的渐进表示法O/Ω/Θ怎么用PPT用数学定义引入渐进符号。T(n) O(f(n))表示存在常数c0和n00当n≥n0时T(n)≤c·f(n)T(n) Ω(g(n))表示存在常数c0和n00当n≥n0时T(n)≥c·g(n)T(n) Θ(h(n))表示既有O又有Ω。翻译成人话O是上界Ω是下界Θ是精确阶。这套符号是在帮我们忽略低阶项和常数。PPT专门讨论了一个问题程序A执行3n4步程序B执行2n2步A一定比B慢吗答案是No。因为渐进分析只关心n充分大时的增长趋势3n和2n都是线性增长差别是常数倍。真正决定“数量级”的是n的次方不是系数。厚度体现在这里很多人从“快慢”角度理解复杂度但考试要你证明或比较时必须写出定义。我复习时会把O、Ω、Θ三个定义抄在一张卡上然后给自己出一道题证明2n²3n O(n²)。步骤是先找c和n0比如c5n01当n≥1时2n²3n≤5n²成立。这类题在考研里出现过基础但重要。判断符号时还有一个细节如果只有O说明说的是上界如果说“平均时间复杂度”那是在讨论Tavg(n)。PPT里指出Tavg(n)≤Tworst(n)而且最坏情况分析通常更容易。考试中没特别说明时默认说的是最坏情况复杂度。3.3 复杂度分析的小窍门串行、嵌套、分支怎么算PPT总结了几个复杂度计算规则我按自己的理解整理成下面这张表复习时可以直接参考代码结构复杂度计算例子两段算法串联T1 T2 max(O(f1), O(f2))先做O(n)再做O(1)整体O(n)两段算法嵌套T1 × T2 O(f1 × f2)两层循环各n次整体O(n²)if-else分支max(条件判断, 两个分支)无论走哪个分支取最贵的单层循环循环次数 × 循环体复杂度for(i0;iN;i){xy*xz;}是O(N)这些规则本质上是“取最大头”。实际刷题时嵌套循环看层数循环体内有函数调用要看函数本身的复杂度。考研里常考的是递归函数的复杂度递推式比如T(n)T(n-1)1是O(n)T(n)2T(n/2)n是O(n log n)。PPT没有展开递归式求解但你可以把第1章这些基础规则作为起点后续学归并排序时再补递推树的推导。这里特别提醒一点串联复杂度取max的前提是两段代码确实按顺序执行。如果第二段代码依赖第一段的结果并且每个结果都要遍历那可能变成乘积而不是max。判断方法就是看外层是否多套了一层循环。3.4 从函数增长表看复杂度差距log n 到 n!PPT给了一张常用函数增长表输入规模n从8、16、32逐步翻倍各函数值的变化非常直观。这里我整理出一份简化版复习时用来训练“一眼看出数量级”的能力nlog2 nnn log2 nn²n³2ⁿ83824645122561641664256409665536325321601024327684294967296看这张表n32时2ⁿ已经超过42亿而n²才1024。这就是为什么说“指数级算法在较大规模下根本不可用”。很多初学者容易低估O(n²)和O(n log n)的差距等到处理实际数据量就能体会到。考研里经常会问“某算法优化前后从O(n²)降到O(n log n)数据量扩大10倍运行时间大概怎么变”这时候用这张表的趋势心算就够。理解这张表还有一个重要应用判断一个算法是不是“好算法”。PPT里的结论是好的算法通常让复杂度保持在n log n或更低。超过n²就需要注意超过2ⁿ基本只适合论文或极小规模场景。复习数据结构时每学一个新算法都去“查一次表”把这个算法的复杂度放到这几个档位里比背结论更直观。4. 把PPT读成自己的复习资料三步整理法很多人下载课件后只是从头翻到尾合上PPT还是记不住。这份PPT的好处是信息密度高、案例集中但需要主动加工。下面是我自己比较实用的三步整理法适合期末复习和考研二轮复习。4.1 第一步按“定义-例子-复杂度”给每页PPT打标签不要按页码顺序死记而是按知识类型给每页打标签。我的做法是准备一张A4纸把PPT的章节拆成三类标签“定义类”记录术语的准确表述比如数据结构定义、抽象数据类型、逻辑结构、物理结构。 “例子类”记录PPT里出现的每一个例子的输入、输出和关键代码比如图书摆放、PrintN、多项式求值。 “复杂度类”记录每个算法的时间复杂度和空间复杂度以及推导依据。以这份PPT第1章为例你可以做成这样的清单数据结构的定义计算机中存储、组织数据的方式精心选择可带来最优效率算法。 逻辑结构线性、树、图。 物理结构顺序存储、链式存储。 抽象数据类型只描述“是什么”不涉及“怎么做”。 算法五要求输入、输出、确定性、有限性、可行性。 复杂度最坏Tworst(n)、平均Tavg(n)。做完这张清单第1章的骨架就到手了。后面每一章线性表、栈、队列、树、图、排序都用同样方法整理考前只需要看自己的清单不用重翻300页。4.2 第二步把例子的C代码变成自己的跑一遍并记录时间PPT里所有代码都是C语言片段不能直接复制运行因为缺少main函数和头文件。我建议每看到一个算法先自己补全成完整程序再编译运行。具体步骤新建一个c文件比如poly.c写出多项式直接法和秦九韶法的完整代码#include stdio.h #include math.h double direct( int n, double a[], double x ) { double p a[0]; int i; for ( i 1; i n; i ) p a[i] * pow( x, i ); return p; } double qinjiushao( int n, double a[], double x ) { double p a[n]; int i; for ( i n; i 0; i-- ) p a[i-1] x * p; return p; } int main() { double a[4] {1, 2, 3, 4}; printf( direct %f\n, direct( 3, a, 2 ) ); printf( qinjiushao %f\n, qinjiushao( 3, a, 2 ) ); return 0; }逻辑说明这里a[4]存了从0次到3次的系数x2。直接法和秦九韶法结果应该一致如果一致说明实现正确。参数说明把n改成更大的值比如100循环次数增加可以更明显感受到时间差异。编译命令gcc -o poly poly.c -lm ./poly逻辑说明-lm用来链接数学库因为用了pow函数。如果直接法输出和秦九韶法不同多半是循环边界或初始值写错。跑通之后再用clock()框架计算耗时把被测函数放到循环里跑10000次时间就出来了。这一步的价值是把PPT里的被动阅读变成主动实验。我复习树结构时也把PPT里的遍历代码改成完整二叉树程序用同一棵树的输出验证前序、中序、后序关系。这样比背代码有效得多。4.3 第三步用“一句话笔记”对抗遗忘整理完标签和代码后再做一件事每个小节用一句话笔记。不要写长句子只写“这个问题在解决什么”。比如图书摆放插入频繁用“分区局部有序”查找频繁用“全局有序”。 PrintN循环省空间递归费空间递归深度大会爆栈。 多项式求值秦九韶法把O(n²)降成O(n)核心是避免重复计算幂。 抽象数据类型只关心能做什么不关心怎么做。这句话既是索引也是记忆锚点。考前脑子里快速过一遍这些句子比重新翻PPT快得多。我通常会在A4纸的背面写这些一句话笔记配合前面打标签的清单形成一份只有3页纸的“数据结构急救包”。期末复习时这套东西比厚厚的课本更实用。4.4 用教材补全细节参考书怎么选这份PPT是教学课件页数再多也不可能把所有推导细节都写在上面。如果你发现某个概念只记住了定义但不会应用我建议找一本C语言描述的数据结构教材做对照。常见的是严蔚敏的《数据结构C语言版》或者Mark Allen Weiss的《数据结构与算法分析C语言描述》。陈越老师课件的章节安排和这类经典教材对应度很高先讲概念再讲线性表、栈队列、树、图、排序最后是散列和文件。把PPT当提纲把教材当详解复习效率会高很多。具体做法是每学完PPT的一章去教材里找一道对应的例题手推一遍。比如看完第1章立刻做“最大子列和问题”的四种算法复杂度分析。这个题在很多教材里反复出现正好用上你刚学的O、Ω、Θ和复杂度计算规则。做完再回到PPT看老师的讲解思路会有“原来如此”的感觉。5. 避坑与排查用这份PPT复习时最常见的5个坑下面这几条都是实际复习时会遇到的翻车现场我按“现象→原因→解决”的顺序写出来你可以对照排查。5.1 递归PrintN在N很大时崩溃不是编译器坏了现象写递归版PrintN传N100000程序一闪而过或直接报错退出改成循环版就好。原因递归版每次调用都在系统栈上压入一帧空间复杂度S(n)c·n。N很大时栈空间被耗尽程序被操作系统终止。解决先估算递归深度超过万级就不要用递归。改用循环或者用显式栈模拟递归。学习时这个例子本身是为了提醒你空间复杂度所以不要纠结“为什么别人的递归没崩”而是要把这个场景记成“递归的空间开销是真实的”。如果你用的是Linux可以在终端里执行ulimit -s查看默认栈大小再去估算能压多少层。这样能把“要背的概念”变成手上能算的数字。5.2 clock()测出0秒不代表算法快现象用课件里的clock()框架测多项式求值两种方法耗时全是0无法看出差别。原因被测函数执行时间远小于系统计时精度clock()的返回值变化量不足以体现差异。解决把被测函数放进一个大循环里比如循环10万次再除以循环次数start clock(); for ( i 0; i 100000; i ) f( 100, a, 2 ); stop clock(); duration ((double)(stop - start)) / CLK_TCK / 100000;这样可以测出单次平均耗时。如果你在Linux下也可以改用clock_gettime但对于这份PPT的教学场景clock()配合循环已经够用。注意别把循环次数设得太离谱否则测一次要等很久又是一个时间黑洞。5.3 把常数差异当成复杂度差异现象看到程序A执行3n4步程序B执行2n2步就认为B一定更快或者看到系数大就认定复杂度高。原因渐进分析法刻意忽略常数和低阶项只关注n充分大时的增长趋势。3n和2n都是O(n)常数差异不改变数量级。解决比较复杂度时只看O、Ω、Θ级别。只有在同一个级别内部比如两个都O(n)才谈常数优化。考试答题时先写数量级再写常数不要混在一起。考研选择题常在这里埋坑。我在复习时给自己立了一个规矩凡是看到“哪个更快”的问题先把两个算法在n10、100、1000下的增长趋势写出来再决定是否值得谈常数。这个习惯帮我避开了很多直觉错误。5.4 分不清逻辑结构和物理结构现象把“书本按类别分区摆放”当成物理存储方式认为这就是链式存储或顺序存储。原因把抽象的组织关系和内存中的实际存储方式混为一谈。逻辑结构描述的是数据元素之间的逻辑关系线性、树、图物理结构描述的是这些数据在内存里的表示方式顺序、链式。图书按类别分区域属于逻辑上的树状组织至于书架上的书是连续排列还是通过索引关联是另一回事。解决判断时问自己一个问题描述里能看出“内存地址”或“指针”吗如果没有就是逻辑层面的东西。复习到链表时把“链式存储”想成“每个节点里存着下一个节点的地址”就不会和逻辑结构混淆。5.5 秦九韶法循环边界写错现象实现秦九韶法时结果和直接法不一致或者对高位系数出错。原因循环边界和p的初值没配对。正确的写法是pa[n]然后从in倒着做到i1每轮pa[i-1]x*p。有人从in-1开始或者把p初值设为0都会漏掉最高次项。解决写完后用一个小例子验证比如n2系数{1,2,3}x2。手算结果应是12·23·417。代码里设断点或者打印中间p值检查第一轮是不是pa[1]xa[2] 22·38第二轮pa[0]x811617。这个验证过程还能帮你理解秦九韶法的递推结构不只是背代码。6. 进阶与验证把这套课件变成考研/期末的答题框架当你把第1章真正吃透后可以继续用同样的方法处理后序章节。这里分享一个进阶用法把课件里的每个结构/算法做成一张“选型决策卡”用来对付期末大题和考研设计题。决策卡正面写四行适用场景、核心操作、时间/空间复杂度、一句话代码模板。比如线性表查找频繁用顺序表插入删除频繁用链表顺序表支持O(1)随机访问链表插入O(1)但查找O(n)。 栈递归、表达式求值、括号匹配入栈出栈O(1)栈满要注意。 队列BFS、缓冲区循环队列判满条件要背。 树层次关系、排序树、堆遍历复杂度O(n)查找树平均O(log n)。 图路径搜索、最小生成树邻接矩阵适合稠密图邻接表适合稀疏图。每张卡都回到第1章那个核心问题“这个结构到底在哪个操作上付出了什么代价”比如数组随机访问代价低插入要搬移链表反过来。考试时遇到设计题先在纸上列出可选结构再按“操作频率”排除最后得到答案。我自己的血泪经验是复杂度背不下来时不要硬背而是把课件里每个算法的代码在脑子里走一遍数一数循环层数和递归层数。比如快排递归树高度log n每层总扫描n所以平均O(n log n)。PPT第1章的复杂度分析技巧后面所有章节都在反复用。验证方式也很简单找一套期末或考研真题把每个选择题的复杂度选项用你的决策卡过一遍填空题里的概念用第4章做的“一句话笔记”回答。如果正确率超过80%说明课件内容已经内化成自己的东西。从那以后我每次复习数据结构都会强制走一遍“打标签-跑代码-做决策卡”三步效率比单纯翻PPT高很多。希望帮到你。本文还有配套的精品资源点击获取