第一章 绪论
- 数据的逻辑结构独立于其存储结构
- 可以用抽象数据类型定义一个完整的数据结构
- 数据的运算也是数据结构的一个重要方面：
- 二叉树和二叉排序树的逻辑结构和物理结构完全相同，但运算效率大不相同；如查找，二叉树O(n)，二叉排序树O(logn)
- 一个算法是问题求解步骤的描述，五个基本特征：可行性、确定性、有穷性、输入、输出
- 好的算法：正确性、可读性、健壮性、效率与低存储需求
- 判断一个有向图是否存在回路的方法：拓扑排序和深度优先遍历算法
第二章 线性表
- 线性表是具有n个数据元素的有限序列
- 链式存储结构比顺序存储结构能更方便的表示出各种逻辑结构（画个图嘛就是）
- 顺序存储方式能用于存储线性表、树、图（邻接矩阵）
- 静态链表需要分配较大的连续空间，插入和删除不需要移动元素（和OS中的FAT即显示链接非常类似）
- 单链表中，增加一个头节点的目的是方便运算的实现
- 为了方便插入和删除数据 可以使用双链表存放数据
第三章 栈 队列 数组
- 普通顺序队列的“上溢出”是一种“假溢出” 即 Q.rear==Maxsize 于是引出循环队列的概念 逻辑上看作一个环
- 队列长度的计算 (rear-front+MaxSize)%MaxSize
- 用单链表实现队列时 队头必须设置在链头（为了出队） 队尾可以设置在任何地方
- 链式存储方式的队列进行删除操作时 可能头尾指针都要修改
- 链队中 入队操作为 rear->next=x;x->next=NULL;rear=x;
- 栈的应用：递归 进制转换 迷宫求解 括号匹配
- 执行函数时 其局部变量一般采用栈进行存储
- 广度优先搜索需要用队列
- 消除递归不一定需要栈
- 栈是运算受限的线性表 只允许在单端操作
- 队列是运算受限的线性表 只允许在双端操作
- 适用于压缩存储稀疏矩阵的是：三元组表 十字链表
- 对特殊矩阵采用压缩存储的主要目的是减少不必要的存储空间
第四章 串和KMP（很简单）
- KMP算法匹配时 next数组后跳到的位置也需要先比一次
第五章 树
- 树的路径长度是 从树根到每个节点的路径长度的总和
- 完全二叉树就是从满二叉树里摘出来的 把大序号的叶子结点去掉
- 度为n的树和n叉树是不一样的两种概念！！！
- 在完全二叉树中 若一个节点没有左孩子 则它必是叶结点
- 在完全二叉树中 叶子结点的双亲的左兄弟(若存在) 一定不是叶结点
- 完全二叉树和满二叉树都适合顺序存储
- 二叉树是逻辑结构 线索二叉树的物理结构
- n个节点线索二叉树中有n+1个线索
- 讲个笑话 后序线索二叉树求不出后序后继 前序线索二叉树求不出前序前驱 所以后序线索二叉树的遍历需要栈的支持
- 森林中 结点数-边数=树的个数
- 将森林转换为对应的二叉树 森林中的叶结点的个数等于二叉树中左孩子指针为空的结点个数
- 结点数＝度数＋1
- 在完全二叉树中，已知节点总数就可以确定其形状。已知其先序序列，便可知其节点总数，再根据先序序列确定每个节点的位置。实际上，只要已知完全二叉树的任一种遍历序列都可以唯一确定该二叉树。
- 在先序遍历二叉树的序列中，任何节点其子树的所有节点都是直接跟在该节点之后的
- 红黑树 左根右 根叶黑 不红红 黑路同 黑叔转 再染色 红叔染 爷变新（王道给的口诀很好用） n个节点的红黑树高度≤2logn+1
- 快排递归次数与每次划分后得到的分区处理顺序无关（排序怎么乱入？）
- 前缀编码 任何一个字符的编码都不是另一个字符编码的前缀
- B树和B+树的根节点不受最小关键字数的限制
- 后根遍历与对应二叉树的中序遍历序列相同
- 并查集是双亲表示法存储的树
第六章 图
- 图的路径 由顶点和相邻顶点序偶构成的边所形成的序列
- 若从无向图任意顶点出发进行一次深度优先搜索即可访问所有顶点 则该图一定是 连通图
- 无向图中的连通分量是指 无向图中的极大连通子图
- 有向完全图一定是强连通有向图
- 生成树是极小连通子图 连通分量是极大连通子图
- 回路不是简单路径(回路怎么可能是路径！！！气抖冷)气抖冷!!!!!
- 邻接矩阵 行是出度 列是入度
- 十字链表只用于有向图 邻接多重表只用于无向图
- 判断图中是否有回路 拓扑排序和深度优先遍历
- 注意拓扑排序和逆拓扑排序
- 各边权值相等时 广度优先遍历可以解决单元路径最短问题
- BFS DFS 时间复杂度一样 同拓扑排序 主要看邻接矩阵还是邻接表
- AOV网和DAG图(有向无环图)
- 最短路径一定就是简单路径
- 一个有向图具有有序的拓扑排序序列 则他的邻接矩阵必定为三角阵
- 图的所有生成树的边数是相同的，其中数值之和最小的生成树为最小生成树。
- 简单图 不存在重复边 不存在顶点到自身的边
- 无向完全图 任意两个顶点直接都存在边 有向完全图 任意两个顶点之间都存在方向相反的弧
- 生成子图包括母图的所有顶点
- 连通图 任意两个顶点都是连通的
- 无向图中的极大连通子图称为连通分量 有向图的极大强连通子图称为有向图的强连通分量 一个单独的点是强连通图
- 图可以只有顶点没有边 树也可以
- 在无向图中讨论连通性 有向图中讨论强连通性
- 连通图的生成树是包括图中全部顶点的一个极小连通子图 非连通图的连通分量的生成树构成了连通森林
- 简单路径 顶点不重复出现的路径 简单回路 除第一个顶点 不出现重复的回路
- 有向无环图拓扑序列唯一 不能唯一确定图
第七章 查找
- 折半查找的判定树是平衡二叉树 所以和二叉排序树的性能有时不相同
- 红黑树 左根右 根叶黑 不红红 黑路同
- AVL平衡二叉树查找效率优于红黑树 红黑树的目的是为了插入 删除等操作
- 红黑树不是平衡二叉树 平衡二叉树是二叉排序树
- 如果红黑树的所有叶结点都是黑色的 那么他一定是一颗满二叉树
- 折半查找只能在顺序结构上进行
- 聚集现象是线性探测法所独有的
- B树的查找长度 n个关键字 m阶
- 对于n阶B树来说 首先得满足至少有一个节点有5个孩子 才能考虑其他
- 红黑树的内部节点中 红色节点可能超过一半 但加上叶节点就不会超过一半 查找路径上也不会超过一半 左右高度之差不超过两倍
- 黑高为h时 最少有2h-1个内部节点 最多22h-1个内部节点 注意黑高不会算自己（即当前根）
第八章 排序
- 拓扑排序不是排序算法
- 算法的稳定性与优劣无关
- 对同一线性表使用不同的排序方法 得到的排序结果可能不同 这与稳定性有关
- 希尔排序属于插入排序 在子表中使用直接插入排序 而非折半插入排序
- 折半插入排序的时间复杂度是O(n2) 就只是在查找的时候用了折半查找罢了 稍微优化了一下
- 堆中的次大值或次小值一定在第二层
- 快排堆排都不稳定 只有归并排序稳定 nlogn
数据结构算是几天之内重新过了一遍知识点，个人觉得数据结构的内容比较通俗易懂，学会了没那么容易忘记，与之相比，剩下的三本书可以说是折磨了。加油！文章来源地址https://www.toymoban.com/news/detail-721209.html
文章来源：https://www.toymoban.com/news/detail-721209.html
到了这里，关于【考研易忘知识点】数据结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
