适用于备考数据结构期末考试日常学习理解面试复习考研辅助理解写在前面想象一个场景。你走进一个图书馆。书架上所有的书按类别排列文学在一层科技在一层历史在一层。每本书有编号有位置。你找一本书不会迷路。现在想象另一个场景。同样是这个图书馆书被随意堆在地上没有分类没有编号。你想找一本《C Primer》——只能一本一本翻。哪个图书馆你愿意去数据结构就是第一种图书馆。它研究的是数据怎么组织、怎么存放、怎么高效地存取也就是对数据的整理归纳。一、数据结构是什么1.1 定义数据结构相互之间存在一种或多种特定关系的数据元素的集合。拆开看数据程序处理的对象数字、文字、图片、音频…结构这些对象之间的关系你写一个学生管理系统。每个学生有学号、姓名、成绩。多个学生放在一起你怎么存用一个数组→ 顺序结构用一个链表→ 链式结构用一张树形表格→ 树形结构不同的存法就是不同的数据结构。1.2 两个维度逻辑结构 vs 物理结构这两个词很重要搞混了后面全乱。维度意思比喻逻辑结构数据之间是什么关系从你的角度看家庭关系你知道谁是爸爸、谁是儿子物理结构数据在内存里怎么存放从计算机的角度房子地址爸爸住101儿子住102还是住隔壁楼同一套逻辑关系可以用不同的物理方式存放。二、四种基本逻辑结构2.1 集合结构关系数据元素之间没有关系。就像一麻袋土豆每个土豆是独立的。应用哈希表。2.2 线性结构关系一对一。每个元素有一个前驱、一个后继除了第一个和最后一个。应用数组、链表、栈、队列第二章和第三章的内容。2.3 树形结构关系一对多。一个节点有多个子节点但每个子节点只有一个父节点。应用文件系统、HTML的DOM树、二叉搜索树第六章。2.4 图形结构关系多对多。任意两个节点之间都可能连接。应用地图导航地铁线路、社交网络好友关系、网络路由第七章。三、算法是什么有了数据你要操作它们——查找、插入、删除、排序。算法解决特定问题的步骤描述。做一道菜需要菜谱。解一道题需要算法。3.1 算法的五个特性特性含义有穷性必须能在有限步内结束不能死循环确定性每一步没有歧义同一种输入得到同一种输出可行性每一步都能在有限时间内执行完输入有0个或多个输入输出至少有1个输出3.2 好算法的标准正确能解决问题可读别人或三个月后的你看得懂健壮输入非法数据不会崩溃高效跑得快、占内存少后面两个快和少就是复杂度分析要解决的问题。四、时间复杂度你的算法跑得有多快4.1 为什么要分析时间复杂度写两个算法解决同一个问题。一个跑1秒一个跑1小时。区别在哪里不是看代码长短是看操作次数随输入规模增长的速度。4.2 大O表示法我们不看具体的执行时间跟机器、语言有关。我们看操作次数随n增长的趋势。用大O表示忽略常数项、忽略低次项。代码示例执行次数时间复杂度int a 10;1次O(1)for(int i0;in;i){ sumi; }n次O(n)for(int i0;in;i){ for(int j0;jn;j){ sum; } }n²次O(n²)4.3 常见复杂度曲线最重要的一张图O(1)水平线O(log n)平缓上升越来越平O(n)斜线O(n log n)比斜线稍陡O(n²)快速上升的抛物线O(2^n)像跳楼一样垂直上升]看到这张图你就能理解为什么O(2^n)的算法在n100时宇宙毁灭了都跑不完。4.4 最好、最坏、平均情况以顺序查找为例在一个数组里找一个数最好情况第一个就是 → O(1)最坏情况最后一个才是或者没有 → O(n)平均情况大概在中间 → O(n)我们一般关心最坏情况。因为写程序要保证任何时候都不会崩。4.5 计算复杂度的小技巧// 例子1O(1)intsum0;sumab;// 例子2O(n)for(inti0;in;i){sumi;}// 例子3O(n²)for(inti0;in;i){for(intj0;jn;j){sum;}}// 例子4O(log n)inti1;while(in){ii*2;// i每次翻倍循环次数是log₂n}口诀看循环嵌套层数一层O(n)两层O(n²)看循环变量变化每次乘2 → O(log n)顺序执行取量级最大的五、空间复杂度你的算法占多少内存时间复杂度的兄弟空间复杂度。也是用大O表示分析额外占用的内存随n增长的趋势。// O(1) 空间只用了几个变量跟n无关intsum0;for(inti0;in;i){sumi;}// O(n) 空间申请了一个大小为n的数组int*arrnewint[n];for(inti0;in;i){arr[i]i;}delete[]arr;时间换空间 / 空间换时间用一个额外数组记录中间结果可以少循环几次 → 空间换时间不申请新数组直接在原数组上操作 → 时间换空间没有绝对的好坏。内存够大时优先优化时间。嵌入式系统内存紧张时优先优化空间。六、本章总结背下来概念一句话解释数据结构数据怎么组织算法问题怎么解决逻辑结构数据之间是什么关系集合/线性/树/图物理结构数据在内存里怎么放顺序/链式时间复杂度跑多快大O表示空间复杂度占多少内存大O表示 本章必考必背知识点清单一、核心概念背定义术语定义考法数据所有能输入计算机并能被程序处理的符号总称选择题下列哪个属于数据数据元素数据的基本单位通常作为一个整体考虑填空题数据的基本单位是____数据项数据元素的最小组成单位不可再分选择题数据项vs数据元素的关系数据对象性质相同的数据元素的集合判断题数据对象是数据的一个子集数据结构相互之间存在特定关系的数据元素的集合简答题数据结构的定义数据元素、数据项、数据对象的关系图必考举例学生表数据对象→ 每个学生记录数据元素→ 学号、姓名、成绩数据项二、逻辑结构与物理结构对比必背对比维度逻辑结构物理结构存储结构定义数据元素之间的逻辑关系数据在内存中的存放方式与计算机无关✅ 是抽象层面❌ 否硬件层面分类集合、线性、树形、图形顺序存储、链式存储考法判断题逻辑结构是面向问题的选择题数组对应哪种物理结构四种逻辑结构速记表结构关系举例考法集合无关系哈希表选哪个是无关系结构线性一对一数组、链表选排队属于哪种树形一对多文件目录、家族树选文件夹结构图形多对多地铁图、社交网络选好友关系属于哪种三、算法相关必背术语定义考法算法解决特定问题的步骤描述简答题算法的定义有穷性算法必须在有限步内结束判断题死循环是否满足有穷性确定性相同输入得到相同输出选择题确定性含义可行性每一步都能在有限时间内完成判断题正确性算法能解决问题简答题好算法的标准健壮性输入非法数据不会崩溃简答题高效性时间少、空间少简答题四、时间复杂度计算期末必考大题时间复杂度 基本操作执行次数 与 n 的函数关系可以这么理解在i次循环内n从0-nin在i次循环内n从1-2的i次方ilog2n所以时间复杂度其实就是i和n的关系4.1 大O表示法规则规则说明例子常数项忽略O(1) 就是 O(1)10 → O(1)只保留最高次项去掉低次项n² n → O(n²)忽略系数去掉常数乘数2n → O(n)4.2 常见复杂度大小关系必背顺序O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) O(n!)4.3 复杂度计算模板背下来代码模式复杂度判断方法int a 0;O(1)没有循环for(i0;in;i){...}O(n)一层循环for(i0;in;i){ for(j0;jn;j){...} }O(n²)两层循环次数独立for(i0;in;i){ for(j0;ji;j){...} }O(n²)两层循环求和 12…n n(n1)/2while(in){ ii*2; }O(log n)循环变量乘2除2for(i0;in;i){ while(jn){ j; } }O(n)j不重置总共n次二分查找O(log n)每次砍一半递归斐波那契无记忆O(2ⁿ)递归树节点数4.4 典型例题背解法例题1intsum0;for(inti0;in;i){for(intj0;ji;j){sum;}}答案O(n²) —— 因为 12…n-1 n(n-1)/2例题2inti1;while(in){ii*2;}答案O(log n) —— 2^k n → k log₂n例题3for(inti0;in;i){for(intj0;j100;j){sum;}}答案O(n) —— 内层固定100次常数忽略例题4for(inti0;in;i){for(intji;jn;j){sum;}}答案O(n²) —— n (n-1) … 1 n(n1)/2五、空间复杂度常考代码空间复杂度原因int a;O(1)单个变量int arr[100];O(1)固定大小与n无关int* p new int[n];O(n)大小随n增长int arr[n][n];O(n²)二维数组空间换时间用额外数组换速度时间换空间不用额外数组慢一点下一章预告第二章线性表。我们会讲数组和链表的爱恨情仇包括它们怎么插入、删除、查找以及什么时候用数组、什么时候用链表。思考题检验你有没有读懂以下代码的时间复杂度是多少for(inti0;in;i){for(intj0;ji;j){cout*;}}逻辑结构和物理结构的区别是什么能不能给一个“逻辑上是线性结构物理上是链式结构”的例子为什么我们通常分析最坏情况复杂度而不是最好情况答案在评论区公布