首页  思维导图  详情

数据结构

2021-09-02 00:14:02   194  举报





AI智能生成

为你推荐

查看更多



数据结构

数据库，数据结构 - mysql, mongodb, redis, es

含有对应代码注解,考研和面试均可使用

作者其他创作

大纲/内容

结点高度

树的高度

高度

结点深度

树的深度

层数/深度

祖先、子孙、兄弟、双亲；堂兄弟

结点的度

树的度

度

分支结点

叶子结点

结点

有序树与无序树

路径

路径长度

路径和路径长度

森林

基本概念

结点数(m)=非叶子结点数+叶子节点数

结点数 = Σ 度 x 个数 + 1【根】

结点与度数

sp: 高 h 的二叉树结点至多为

高度为 h 的 m 叉树至(最)多结点数

偶数个结点的二叉树，其度数为1 的结点个数必然为奇数

结点个数

n 个结点的 m阶树/m叉树/完全 m 叉树的高度【必背】

最小高度

n个结点，度为m的树最大高度

最大高度

性质

如果某结点只有一个子结点，则必为左孩子

结点个数 span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"n\\geq 0\

定义

叶子结点个数

第k层最多结点数

高度为h至多结点个数

个数相关

i 结点的左孩子编号 = 2i

i 结点的右孩子编号 = 2i+1

左右孩子

下标相关

结点所在深度

完全二叉树】深度

(n+1)/2

严格二叉树的最大深度

深度相关

n个节点的二叉链存储节点空指针个数为 n+1

指针个数

次序合法性

访问序确定二叉树形状

左必在右的前面被访问

前中后序的访问序列，叶子结点序列不变

高度等于其结点数时，先序和后序遍历序列相反

遍历访问序

定义span class=\"equation-text\" data-index=\"0\" data-equation=\

满二叉树

层都是满的，同时第层按照从左往右顺序填结点

每个结点都与高为的满二叉树编号为的结点位置一一对应

若一个结点没有左孩子，则其必然是叶结点

叶子结点的双亲的左兄弟（若存在）则必然不是叶子结点

高度为 h 的完全二叉树，节点个数最小为

最后一个分支 (非叶) 结点序号为

若某完全二叉树有个结点，则其叶子节点个数为

结点个数最少为：结点个数最多为：

第 x 层有 k 个叶子结点，求结点个数max/min情况

计算

完全二叉树

类型

顺序存储

链式存储

存储结构

先/前序(NLR)

中序(LNR)

后序(LRN)

遍历

二叉树

度为m的树 m叉树

顺序存储；存储地址=逻辑地址

双亲表示法

邻接表存储；有向图存储结构

孩子表示法

孩子兄弟/二叉树表示法

已知森林边和结点数，求森林中包含的树的个数

森林结点数

右孩子指针为空的结点个数

森林左子树结点数=森林第一棵树结点树

森林和二叉树关系

二叉树：先序

森林：先序

树：先根

二叉树：中序

森林：后序

树：后根

遍历以及有序树

树、森林和二叉树转换

树和森林

复杂度分析

生成树与生成森林

BFS广度优先搜索

遍历与连通性

DFS深度优先搜索

递归 = 栈

递归与非递规转换

辅助队列

层次遍历

中序(必须)+先序/后续

遍历序列构造二叉树

后序遍历

线索树遍历需要栈

求祖先到子孙的路径可以使用先/中序遍历

已知次序求二叉树异构个数

带权路径长度

带权路径长度(WPL)最小的二叉树；也称最优二叉树

度为 m 的哈夫曼树，为严格的 m 叉树

贪心，每次取两个权值最小的结点作为新结点的左右子树新结点权值为左右子树和，并放入到可选择的结点集合中

构造

初始结点均为叶子结点

权值越小到根节点路径越长

新建了n-1个结点，结点总数为 2n-1

度为m的哈夫曼树中，叶子结点为n，则其非叶子节点个数为

叶子结点个数即为不同符号的编码数

哈夫曼树

每个字符用相等长度二进制位表示

固定长度编码

没有一个编码是另一个编码的前缀

前缀编码

哈夫曼编码

物理/存储结构

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

标志域含义

线索

线索化

概念

线索化后的空链个数

仍需要栈支持的遍历为后序线索树

不是每个结点都能通过线索查找其前驱后继

已知后序线索二叉树，求后序后继仍不能完全求解

相关运算

Linear List线性表

查找成功

查找失败

平均查找长度

效率指标

查找特定元素

检查满足条件元素属性

插入元素

删除元素

查找表/查找结构

折半

散列

静态查找表

二叉排序树

AVL平衡二叉树

B树

动态查找表

同义词之间冲突

不可能避免

冲突/碰撞

同义词与非同义词发生冲突

主要与冲突探测方法有关

聚集/堆积

直接定址法

除留余数法

数字分析法

平方取中法

散列函数

线性探测再散列

二次探测再散列

伪随机探测再散列

开放定址法

链地址法/拉链法

再哈希(散列)法

冲突处理

a= 表中记录数/散列表长度

装填因子

散列结构

一般顺序表查找

有序表顺序查找

顺序查找(链式限制)

适用于有序顺序存储结构

类型：平衡二叉树

n 个元素时的树高 h

判定树是否复合规则判断

折半查找判定树

最多查找次数

最少查找次数

折半(二分)查找

理想块长

顺序分块查找

最优优化

分块(索引顺序)查找

B树的阶

span class=\"equation-text\" data-index=\"0\" data-equation=\

非叶结点结构

所有结点平衡因子为 0 【高度平衡】

最高

最低

最多

最少

关键字数

非根结点关键字个数

根节点为非终端结点时，至少有两个孩子.

非根结点子树个数

严格平衡查找树，所有节点子树高度一致叶子处于同一层且用NULL表示

非叶结点的结构

分裂

图示

已知阶、层数、某层关键字数，求最多结点数

B与B+树区别

B+树

变色

插入调整

删除调整

红黑树

索引结构/树表

2021】一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 (三) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉排序树 2. 平衡二叉树 3. 哈夫曼(Huffman)树和哈夫曼编码三、图 (一) 图的概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. 深度优先搜索 2. 广度优先搜索(四) 图的基本应用 1. 最小(代价)生成树 2. 最短路径 3. 拓扑排序 4. 关键路径四、查找 (一) 查找的基本概念 (二) 顺序查找法 (三) 折半查找法 (四) B-树及其基本操作、B+树的基本概念(五) 散列(Hash)表 (六) 查找算法的分析及应用五、内部排序 (一) 排序的基本概念 (二) 插入排序 1. 直接插入排序 2. 折半插入排序 (三) 冒泡排序(bubble sort) (四) 简单选择排序 (五) 希尔排序(shell sort) (六) 快速排序 (七) 堆排序 (八) 二路归并排序(merge sort) (九) 基数排序 (十) 各种内部排序算法的比较 (十一) 内部排序算法的应用

2022】一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 【多维数组的存储】和特殊矩阵的压缩存储三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 (三) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉搜索树 2. 平衡二叉树3. 哈夫曼(Huffman)树和哈夫曼编码4. 【并查集】三、图 (一) 图的概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. 深度优先搜索 2. 广度优先搜索(四) 图的基本应用 1. 最小(代价)生成树 2. 最短路径 3. 拓扑排序 4. 关键路径四、查找 (一) 查找的基本概念 (二) 顺序查找法(三) 【分块查找法】(四) 折半查找法 (五) B-树及其基本操作、B+树的基本概念(六) 散列(Hash)表 (七) 查找算法的分析及应用五、排序 (一) 排序的基本概念 (二) 插入排序 1. 直接插入排序 2. 折半插入排序 (三) 冒泡排序(bubble sort) (四) 简单选择排序 (五) 希尔排序(shell sort) (六) 快速排序 (七) 堆排序 (八) 二路归并排序(merge sort)(九) 基数排序(十) 【外部排序】 (十一) 各种排序算法的比较 (十二) 排序算法的应用

935考纲对比