数据结构知识点总结PDF：从ADT到复杂度，复习底稿全解析

简介这份《数据结构知识点总结.pdf》面向计算机专业学生、考研备考者及刚入门编程的开发者用于系统梳理数据结构核心概念与算法分析基础。内容从数据、数据元素、数据项等基本术语切入依次讲解逻辑结构与存储结构的区别涵盖顺序存储、链式存储、索引存储与散列存储并展开线性表、栈、队列等典型结构涉及顺序表与链表的插入删除复杂度对比、单链表与双链表的指针操作、循环队列的判空判满方法以及时间复杂度和空间复杂度的渐近分析。资源包内共1个pdf文件大小约205KB篇幅精炼适合作为课堂笔记补充或考前快速回顾的提纲。目前已有437人学习下载读者可借助它建立清晰的知识框架理解抽象数据类型与信息隐藏思想掌握常见操作的复杂度推导为后续算法学习与编程实践打下基础。1. 一份被低估的复习底稿数据结构知识点总结.pdf 能解决什么如果你正在准备数据结构期末、考研 408 或者面试八股大概率经历过这种场景教材翻了三章笔记记了两本合上书还是说不清「顺序表和链表到底什么时候选哪个」。这份《数据结构知识点总结.pdf》就是冲着这个痛点来的——它不是教材而是一份把十章的骨架、公式、复杂度、算法代码全部压缩到可检索密度的复习底稿。覆盖范围从概论里的 ADT、时间复杂度数量级一路到线性表、栈队列、串、多维数组、树、图、排序、查找基本对齐严蔚敏《数据结构 C 语言版》的章节结构。适合三类人考前两周需要快速回捞知识点的学生、面试前想系统过一遍复杂度分析的求职者、以及需要一份可打印速查表的在职开发者。它不教你从零推导但能让你在最短时间内把散落的概念重新串成一条线。2. 从 ADT 到复杂度这份 PDF 的知识骨架怎么读2.1 逻辑结构与存储结构的分离是理解全书的钥匙这份资料第一章就把「逻辑结构」和「存储结构」拆开讲这个分法看着基础但后面每一章都在用它。逻辑结构描述数据之间的关系——线性结构是一对一树是一对多图是多对多存储结构则是逻辑结构在计算机里的落地方式顺序存储用连续地址数组链式存储用指针串起来链表索引存储分稠密和稀疏散列存储直接算地址。很多人复习到后面章节会卡住根源就是没把这两层分开。比如「栈」是逻辑结构层面的概念它限制只能在一端插入删除而「顺序栈」和「链栈」是存储结构层面的选择。PDF 里把栈的基本运算列了六种InitStack、StackEmpty、StackFull、Push、Pop、StackTop然后分别讲顺序栈和链栈的实现差异。顺序栈有上溢和下溢链栈没有上溢限制进栈不需要判满。这种「先逻辑后存储」的写法贯穿全书读的时候建议每章都先问自己这一章的数据结构在逻辑上是什么关系它有哪些存储实现抽象数据类型 ADT 是另一个容易被跳过的点。PDF 里明确写了 ADT 是把数据和操作封装在一起、实现信息隐藏。这个概念在后面学 BST、堆、散列表的时候会反复用到——你不需要知道堆内部数组怎么排只需要知道它能 O(log n) 插入和删除最值。复习时把 ADT 当成「接口」来理解后面的算法实现就是「实现类」。2.2 时间复杂度数量级必须背到条件反射PDF 里把时间复杂度按数量级递增排列O(1) O(log₂n) O(n) O(nlog₂n) O(n²) O(n³) O(n^k) O(2^n)。这个序列不是让你背的是让你在看到算法时能立刻定位它的性能档位。比如看到「二分查找」直接反应 O(log₂n)看到「冒泡排序」直接反应 O(n²)看到「归并排序」直接反应 O(nlog₂n)。资料里特别强调了一点算法中语句的频度不仅与问题规模有关还与输入实例中各元素的取值相关。这句话对应的是最好情况、最坏情况和平均情况的分析。直接插入排序在数据已经有序时是 O(n)基本反序时是 O(n²)这就是输入实例影响的典型例子。复习时不要只记一个复杂度要记清楚它在什么条件下取最好、什么条件下取最坏。空间复杂度同理。PDF 里把空间复杂度和时间复杂度合称算法复杂度并且指出空间复杂度主要看辅助存储空间。直接插入排序只占一个缓冲单元空间复杂度 O(1)归并排序需要额外数组空间复杂度 O(n)。这个区分在面试里经常被追问建议对着 PDF 里的排序章节把每个算法的时空复杂度列成一张表。2.3 用一张对照表把线性表和链表的选型锁死线性表这一章的核心不是代码是选型。PDF 里给了明确的判断依据基于空间顺序表存储密度为 1适合事先确定大小的场景链表存储密度小于 1适合长度变化大的场景。基于时间顺序表是随机存储查找为主时选它插入删除为主时选链表如果插入删除集中在首尾两端选尾指针表示的单循环链表。维度顺序表链表存储分配静态需预判大小动态按需申请存储密度1 1含指针域随机访问支持O(1)不支持O(n)插入/删除平均移动 n/2 个元素修改指针O(1)已知位置适用场景查找为主、大小已知频繁增删、长度变化大这张表建议直接抄在笔记第一页。PDF 里还给了顺序表插入和删除的平均移动次数插入是 n/2删除是 (n-1)/2平均时间复杂度都是 O(n)。链表部分重点讲了头插法和尾插法的区别——头插法生成的顺序与输入顺序相反尾插法保持一致。加头结点的算法统一了空表和非空表的处理这个技巧在写代码时能省掉大量边界判断。提示复习线性表时不要只背「链表插入是 O(1)」要区分「已知前驱结点」和「需要查找前驱结点」两种情况。PDF 里给的插入运算pGetNode(L,i-1); s-nextp-next; p-nexts;前面那步 GetNode 本身就是 O(n)。3. 栈、队列、串与多维数组把零散考点串成一条线3.1 循环队列的三种判空判满方法考试必考栈和队列这一章PDF 把重点放在了顺序栈的上溢下溢、循环队列的假上溢、以及链队列的出队边界处理上。循环队列的判空判满有三种方法另设布尔变量、少用一个元素空间、用计数器记录元素总数。第二种方法在考试里出现频率最高入队前先测试(rear1)%m front相等则满否则空。用代码表达循环队列的入队和出队逻辑#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; // 队头指针 int rear; // 队尾指针 } SqQueue; // 入队先判满再移动 rear int EnQueue(SqQueue *Q, int x) { if ((Q-rear 1) % MAXSIZE Q-front) { return 0; // 队满少用一个元素空间的判满条件 } Q-data[Q-rear] x; Q-rear (Q-rear 1) % MAXSIZE; return 1; } // 出队先判空再移动 front int DeQueue(SqQueue *Q, int *x) { if (Q-front Q-rear) { return 0; // 队空 } *x Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }这段代码的关键在取模运算% MAXSIZE它把线性的数组空间变成了逻辑上的环。判满条件用(rear1)%m front而不是rear front因为后者和判空条件冲突。少用一个元素空间的代价是队列实际容量变成 MAXSIZE-1但换来了判空判满的逻辑统一。链队列部分PDF 特别提醒了一个坑出队时如果原队列只有一个结点出队后要同时修改头尾指针并使队列变空。这个边界在写代码时极容易漏掉漏掉之后尾指针会变成野指针后续入队直接崩溃。3.2 串的模式匹配从 O(n²) 到 KMP 的跳跃点串这一章PDF 把模式匹配的最坏时间复杂度写清楚了O((n-m1)×m)当 m 和 n 同阶时就是 O(n²)。这个复杂度对应的是朴素匹配算法——主串指针每次失配后回退到下一个位置重新开始。KMP 算法的改进点就在于让主串指针不回退利用模式串自身的部分匹配信息决定模式串指针回退到哪。PDF 里没有展开 KMP 的 next 数组推导但给出了串的基本运算和存储结构。顺序串分静态存储分配和动态存储分配静态用定长字符数组涉及串长的操作快但不适合插入链接动态在定义时不分配空间使用时按需分配。链串的结点数据域是单个字符存储密度低解决办法是一个结点存多个字符。复习串这一章建议把朴素匹配的代码手写一遍然后对照 KMP 的改进思路理解「主串不回退」这个核心优化。很多 408 真题会在 next 数组的计算上出题PDF 虽然没给完整推导但理解了「前缀和后缀的最长公共部分」这个定义手算 next 数组并不难。3.3 多维数组的地址计算与稀疏矩阵压缩多维数组这一章的核心是地址计算和压缩存储。PDF 给了行优先和列优先两套公式行优先C/PASCALLOCa(ij) LOCa(11) ((i-1)*n (j-1)) * d列优先FORTRANLOCa(ij) LOCa(11) ((j-1)*n (i-1)) * d这两个公式的区别在于哪个下标先变化。行优先是先把一行走完再走下一行列优先是先把一列走完再走下一列。考试里经常给一个二维数组和起始地址让你算某个元素的地址套公式时注意n是列数行优先还是行数列优先别搞反。特殊矩阵的压缩存储PDF 覆盖了对称矩阵、三角矩阵和对角矩阵。对称矩阵只存下三角元素总数从 n² 降到 n(n1)/2地址公式用Imax(i,j)、Jmin(i,j)把上三角元素映射到下三角。三角矩阵分上三角和下三角对角矩阵的地址公式是k2ij。稀疏矩阵用三元组表存储每个非零元素存行号、列号、值但会失去随机存储功能加行表记录每行起始位置可以部分恢复。注意三元组表的「失去随机存储」指的是不能像二维数组那样 O(1) 定位任意元素但按行遍历仍然高效。如果题目要求频繁按行列访问三元组表不是好选择。4. 树与图递归结构的两大重头戏4.1 二叉树的四个性质与三种遍历必须手推一遍树这一章PDF 把二叉树的四个重要性质列得很清楚第 i 层最多 2^(i-1) 个结点深度为 k 的二叉树最多 2^k - 1 个结点终端结点数 n0 n2 1具有 n 个结点的完全二叉树深度为 int(log₂n) 1。这四个性质在选择题里出现频率极高尤其是 n0 n2 1 这个关系几乎每年都考。三种遍历——先序、中序、后序——PDF 写了时间复杂度 O(n)但没有给完整的递归代码。补一份可以直接跑的class BinTNode: def __init__(self, data): self.data data self.lchild None self.rchild None def preorder(root): 先序遍历根 - 左 - 右 if root: print(root.data, end ) preorder(root.lchild) preorder(root.rchild) def inorder(root): 中序遍历左 - 根 - 右 if root: inorder(root.lchild) print(root.data, end ) inorder(root.rchild) def postorder(root): 后序遍历左 - 右 - 根 if root: postorder(root.lchild) postorder(root.rchild) print(root.data, end )这三种遍历的递归写法差异只在print的位置。先序在进入左右子树前打印中序在左子树返回后打印后序在右子树返回后打印。理解了这个位置差异就能理解为什么中序遍历二叉排序树能得到有序序列。线索二叉树是另一个高频考点。PDF 里写了利用 n1 个空指针域存放前驱和后继指针线索使得查找中序前趋和中序后继变得简单但对前序前趋和后序后继没什么作用。这个「没什么作用」的原因在于线索的指向依赖于遍历次序中序线索化后前驱后继关系最自然。哈夫曼树部分PDF 给了构造方法和编码规则n 个叶结点共有 2n-1 个结点没有度为 1 的结点左分支写 0 右分支写 1从根到叶的路径就是编码。哈夫曼编码是前缀码任一字符的编码不是其他字符编码的前缀这保证了解码无二义性。4.2 图的存储选型邻接矩阵还是邻接表图这一章PDF 把邻接矩阵和邻接表的选型讲得很直接邻接矩阵适合稠密图时间复杂度 O(n²)邻接表适合稀疏图时间复杂度 O(ne)。无向图的邻接矩阵是对称的有向图的行是出度、列是入度。邻接表的顶点表结构是vertex | firstedge无向图称边表有向图分出边表和逆邻接表。存储方式适用场景空间复杂度判断两点是否相邻遍历某点所有邻接点邻接矩阵稠密图O(n²)O(1)O(n)邻接表稀疏图O(ne)O(度)O(度)遍历部分深度优先用栈保存已访问结点广度优先用队列保存已访问结点。PDF 里写「深度优先借助于邻接矩阵的列广度优先借助于邻接矩阵的行」这个说法对应的是有向图里出度和入度的方向理解时结合具体图的例子更清楚。最小生成树两个算法Prim 时间复杂度 O(n²)与边数无关适合稠密图Kruskal 时间复杂度 O(e log e)取决于边数适合稀疏图。最短路径的 Dijkstra 算法时间复杂度 O(n²)思路类似 Prim。拓扑排序两种方法无前趋顶点优先得到拓扑序列无后继结点优先得到逆拓扑序列。4.3 树和森林的转换记住三句话PDF 里给了树、森林和二叉树转换的方法总结起来三句话树变二叉树兄弟相连保留长子的连线二叉树变树结点的右孩子与其双亲连森林变二叉树树变二叉树后各个树的根相连。这三句话建议默写考试里画图题经常考。树的存储结构有四种双亲链表表示法求双亲方便求孩子不方便、孩子链表表示法、双亲孩子链表表示法、孩子兄弟链表表示法。孩子兄弟链表的结构是leftmostchild | data | rightsibling分别指向最左孩子和右邻兄弟。这个结构在树变二叉树的转换里直接对应左指针指向长子右指针指向兄弟。提示树的前序遍历对应二叉树的前序遍历树的后序遍历对应二叉树的中序遍历。这个对应关系在考试里经常用来出题记住「树的前序 二叉树的前序树的后序 二叉树的中序」就不会搞混。5. 排序与查找复杂度、稳定性与选型决策5.1 八大排序算法的时空复杂度与稳定性对照排序这一章是 PDF 里篇幅最大的部分之一覆盖了插入排序直接插入、希尔、交换排序冒泡、快速、选择排序直接选择、堆、归并排序、分配排序箱排序、基数排序。每种排序都给了基本思想、时间复杂度和稳定性。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景直接插入O(n²)O(n²)O(1)稳定数据基本有序希尔排序O(n^1.25)O(n²)O(1)不稳定中等规模冒泡排序O(n²)O(n²)O(1)稳定教学用快速排序O(nlog₂n)O(n²)O(log₂n)不稳定大规模、随机数据直接选择O(n²)O(n²)O(1)不稳定移动次数少堆排序O(nlog₂n)O(nlog₂n)O(1)不稳定记录数大归并排序O(nlog₂n)O(nlog₂n)O(n)稳定链表、外排序基数排序O(d(nrd))O(d(nrd))O(nrd)稳定关键字可分解这张表建议打印出来贴在显示器旁边。PDF 里特别强调了直接插入排序的哨兵作用一是作为临时变量存放 R[i]二是在查找循环中监视下标 j 是否越界。这个技巧在写代码时能省掉一个边界判断。快速排序的基准选择PDF 里写的是「以第一个元素为参考基准」这是最基础的版本。实际应用中如果数据已经有序以第一个元素为基准会退化成 O(n²)常见做法是随机选基准或三数取中。堆排序部分PDF 给了建堆的调整函数和初始化建堆的循环从(n-1-1)/2开始往前调整这个起始下标对应的是最后一个非叶子结点。5.2 查找算法ASL 计算与散列冲突处理查找这一章PDF 覆盖了顺序查找、二分查找、分块查找、二叉排序树、B-树和散列技术。顺序查找的 ASL 是 (n1)/2二分查找用二叉判定树计算 ASL分块查找要求「分块有序」并建立索引表。二叉排序树的插入、建立、删除平均时间性能是 O(nlog₂n)。删除分三种情况叶子直接删只有一个孩子用孩子替代有两个孩子用中序后继替代。第三种情况最容易写错PDF 里写的是「先将 *p 结点的中序后继结点的数据到 *p删除中序后继结点」注意是复制数据然后删除后继结点不是直接改指针。散列技术部分PDF 给了四种散列函数构造方法平方取中法、除余法、相乘取整法、随机数法。处理冲突有开放定址法和拉链法。开放定址法的一般形式是hi (h(key) di) % m线性探查di i二次探查di i²双重散列di i * hash(y)。拉链法把所有同义词结点链接在同一个单链表中优点是处理冲突简单、无堆积现象、删除容易实现缺点是结点规模小时指针域占用额外空间。# 拉链法散列表的简单实现 class HashTable: def __init__(self, size): self.size size self.table [[] for _ in range(size)] # 每个槽位一个链表 def _hash(self, key): return key % self.size # 除余法 def insert(self, key): idx self._hash(key) if key not in self.table[idx]: # 避免重复插入 self.table[idx].append(key) def search(self, key): idx self._hash(key) return key in self.table[idx] def delete(self, key): idx self._hash(key) if key in self.table[idx]: self.table[idx].remove(key) return True return False这段代码用 Python 的列表模拟链表每个槽位是一个列表。_hash用除余法insert时先检查是否已存在delete直接从列表中移除。拉链法的装填因子 α 可以大于 1因为链表可以无限延伸但 α 越大查找效率越低。一般建议 α 控制在 0.75 左右。注意开放定址法的装填因子 α 必须 ≤ 1因为所有元素都存在散列表数组内部。拉链法没有这个限制但 α 过大时链表过长查找退化成线性。6. 把 PDF 用出复利我的三遍复习法和一个自检脚本这份 PDF 最大的价值不是「读一遍」而是「反复检索」。我的习惯是三遍走第一遍按章节顺序通读在每一章开头写下这一章的核心数据结构和它的复杂度第二遍只读每章的公式和代码手推一遍地址计算、遍历序列、排序过程第三遍对着目录回忆每章内容回忆不出来的地方标记出来重点补。为了检验复习效果我写了一个简单的自检脚本把 PDF 里的关键复杂度做成题库随机抽题import random # 从 PDF 中提取的关键知识点题库 quiz_bank [ (顺序表插入的平均移动次数, n/2), (顺序表删除的平均移动次数, (n-1)/2), (单链表按值查找的平均时间复杂度, O(n)), (循环队列判满条件少用一个空间, (rear1)%m front), (二叉树终端结点与度为2结点的关系, n0 n2 1), (具有n个结点的完全二叉树深度, int(log2n) 1), (Prim算法的时间复杂度, O(n^2)), (Kruskal算法的时间复杂度, O(e log e)), (快速排序平均时间复杂度, O(nlog2n)), (归并排序的空间复杂度, O(n)), (二分查找的ASL, log2(n1) - 1), (拉链法装填因子的取值范围, 可以大于1), ] def run_quiz(n5): 随机抽取 n 道题进行自测 selected random.sample(quiz_bank, min(n, len(quiz_bank))) score 0 for i, (question, answer) in enumerate(selected, 1): print(f第{i}题{question}) user_input input(你的答案).strip() if user_input.lower() answer.lower(): print( 正确) score 1 else: print(f 错误正确答案{answer}) print(f\n得分{score}/{len(selected)}) if __name__ __main__: run_quiz()这个脚本的逻辑很简单从题库里随机抽题对比用户输入和标准答案最后给一个得分。题库里的每一条都对应 PDF 里的一个知识点答错的题回去翻对应章节。我一般会在考前一周每天跑一次错题超过三道就重点补那一章。从那以后我每次复习这类知识点总结类的资料都强制走一遍「通读 → 手推 → 自检」的流程不再只是用眼睛扫一遍就觉得自己会了。希望帮到你。本文还有配套的精品资源点击获取