数据结构
2023-03-10 15:22:09 1 举报AI智能生成
数据结构考研【408、821】 知识点覆盖全面
作者其他创作
大纲/内容
有序序列L-L(i)-无序序列L若用数组保存，插入一个元素后，插入位置之后的元素要移动，所以移动的次数可能会较多
思想
O(n^2)
最坏
时间
O(1)
空间
是
稳定性
效率
顺序存储
基本有序
适用场景
直接插入
无关
与待排序表初始状态
O(n*log 2 n)
比较次数
O（n^2)
移动次数
数据量不大的排序表
折半插入
直接插入与折半插入图解
增量排序
追求表中元素基本有序，再逼近全局有序
O(n^1.3)
平均
否
仅用于顺序表，不用于链表
图解
希尔排序（shell sort
插入排序
顺序表、链表均可
冒泡排序
取一个pivot，采用分治思想
O(log 2 n)
需要调用递归工作栈
log 2 n
递归层数
每趟排序都可以确定一个元素的最终位置（左边的数都比它小，右边的数都比它大）
特性
内部排序算法中性能最优
优点
快速排序
交换排序
与序列初始状态
每一趟在待排序元素中选取关键字最小地元素，加入有序子序列，（交换两个数据位置）
简单选择
4*n
对比一次
上升
对比两次或一次
下坠
调整根堆
最多关键字比较次数
先排成完全二叉树
从最后一个孩子结点的父节点开始，（n/2向下取整），依次向前处理每个结点，注意处理完之后的结点的子树是否符合根堆
初始堆
构造
插入、删除
适合关键字较多的情况
堆排序
选择排序
归并树（倒立的二叉树
O(n)
与原始序列
效率（二路归并）
多用2路归并
内部排序
多用多路归并
外部排序
归并排序
基于关键字各位的大小
分配，收集……
最高位优先法
MSD
排列数字，升序
最低位优先法
LSD
方法
O(d*（n+r）)
O(r)
与序列的初始状态
可以方便拆分为d组，且d较小
必须为整数或者小数位已知
关键字的取值范围不大，即r较小
数据元素个数n较大
基数排序
关注如何使读/写磁盘次数更少
关注
在排序过程中，需要进行多次内存和外存之间的交换
概念
内部排序时间+外存读写时间+内部归并需要时间
外部排序总时间
减少内部归并的比较次数，从而减小内部归并的时间
log 2 r 向上取整*（n-1）*（k-1)/log 2 k向上取整
未优化之前
log 2 r 向上取整*（n-1）
优化之后
内部归并比较次数与k无关
内存空间满足条件下，增大归并的路数，减少I/O次数，提高外部排序速度
特点
败者树
减少归并段个数
生成初始归并段
作用
置换-选择排序
组织长度不等的初始归并段归并顺序
记录数最小的最先归并
记录数多的最晚归并
哈夫曼树推广到m叉树
减少I/O次数
=读磁盘次数=写磁盘次数
归并树WPL
=归并树WPL*2
归并过程中磁盘I/O次数
需要增加长度为0的虚段
n=n0+nk
k*nk=n-1
虚段个数
若不满足
须构造一棵严格二叉树
注
最佳归并树
优化
排序
对比关键字的次数
查找成功
查找失败
平均查找长度
ASL
查找长度
查找成功ASL：（n+1）/2
不成功ASL：n+1
性能
一般线性表
可用二叉判定树
自身结点所在层数
成功结点查找长度
查找长度为关键字对比次数
父节点所在层数
n个结点，对应n+1个失败结点
n/2+n/(n+1)
失败结点查找长度
有序线性表
顺序、链式均可
存储结构
顺序查找
但二叉判定树不限制为二叉平衡树
折半查找的二叉判定树为平衡二叉树
log[(n+1)/2]向上取整【树高不包括失败结点】
树高
查找过程可用二叉判定树描述
log2n
时间复杂度
n+1个=成功结点的空链域个数
失败结点
仅适合顺序存储结构
不适合链表存储结构
要求元素有序
局限性
树高即关键字比较最多的次数
折半查找
块内无序，块间有序
综合顺序、折半查找优点，既有动态结构，又快速查找
索引表每个元素含各块最大关键字、各块第一个元素地址
长度n，均匀的分为b块，s个记录/块
=(s^2+2*s+n)/2*s
（b+1）/2+（s+1)/2
log2（b+1）向上取整+（s+1）/2
对索引表折半
若s=n^(1/2)，ASL有最小值n^(1/2)+1
查找效率
分块查找（顺序索引查找）
线性结构
一定是从叶节点插入
插入
叶结点
左（右）子树为空
两颗子树均不空
删除（三种情况）
取决于
二叉排序树
n
单支树
若为
二分查找判定树唯一
二叉排序树查找不唯一（受关键字插入顺序影响
若为静态查找，宜选用顺序存储结构，二分查找实现查找；若为动态查找，宜选用二叉排序树作为逻辑结构
二叉排序（查找）树（BST，Binary Search Tree）
查找效率分析
查为主也是一棵二叉排序树，左<根<右
LL
RL
RR
LR
平衡旋转
删除
插入、删除，树高、查找
2012
找到最小的不平衡树开始调整
二叉平衡树（AVL
适用频繁插入、删除
左根右，根叶黑，不红红，黑路同
左右高度差<=2倍
树黑高最少2^（h/2） -1
n个内部结点，h<=2*log2（n+1）
红黑树（RBT，Red-Black Tree）【非重点】
方便查找
平衡因子为0的多路平衡查找树
每个结点至多有m颗子树，即m-1个关键字
除根节点，非叶结点至少有m/2向上取整，颗子树，即m/2向上取整-1个关键字
左根右依次增大
所有叶结点（失败结点）均出现在同一层
总叶结点=总关键字数+1
高度（磁盘存取次数）
m/2向上取整
分裂位置
前驱后继替代
不在终端结点
直接删除关键字
兄弟够借
合并
兄弟不够借
在终端结点
终端结点，最底层非叶结点
叶节点（外部结点）
名词
B树（多路平衡查找树）
数据库
应用
支持顺序查找
B+树
B树、B+树区分
B树、B+树
树形结构
表中关键字映射到对应地址的函数
散列函数
实际数据数/可放数据数
装填因子
尽量减少冲突，分布均匀
构造思想
直接定址法
H(key)=key%p
p为<=m的最大质数（m为散列表长）
除留余数法
选择数码分布均匀的若干位数作为散列地址
数字分析法
平方取中法
构造方法
Hi=（H（key）+di）%m
线性探测法
散列表长度m为可以表示为4*j+3的素数
平方探测法
伪随机序列法
双散列法
开放定址法
经常插入删除
适用
处理冲突
开放定址法的空位置也算作一次比较
拉链法，有的学校空指针算作一次判定比较
查找、性能分析
408-2010-线性探测再散列
散列表（哈希表，Hash Table）
散列结构
查找
G（V，E），顶点集V，边集E
线性表可以是空表，树可以是空树，但图不可以是空图（至少有一个顶点，可以没有边）
所有顶点入度之和=出度之和=E
入度，ID（v）；出度，OD（v）
有向图
一条边连接两个顶点
所有顶点度之和：2*E
无向图
n*(n-1)/2
边数
完全图（无向图）
n*(n-1)
有向完全图
完全图
包含原图的所有顶点
条件
生成子图
子图
图
任意两个顶点相连
n-1条边
n个顶点，最少有
C（上标2，下标n-1）条边
图在任何情况下都是连通的C（上标2，下标n-1）+1条边
n个顶点，最多有
非连通图
连通图
子图连通，同时尽可能保留多的边
极大连通子图
无向图的极大连通子图
大陆公路网（极大连通子图）
海南公路网（极大连通子图）
台湾公路网（极大连通子图）
中国公路网（图）
例
连通分量
连通、连通图、连通分量
针对有向图
图中任何一对顶点均是强连通的
821-2020
最少需要n条边，形成回路
强连通图
极大强连通子图
强连通分量
强连通图、强连通分量
连通
边尽可能少，但要保持连通
包含图中所有顶点的极小连通子图
n个顶点，含有n-1条边
生成树不唯一
减去一条边，变成非连通图
加上一条边，形成回路
生成树
生成森林
生成树、生成森林
稠密图，稀疏图
一个顶点入度为0，其余顶点入度为1的有向图
有向树
树、森林、有向树
几种特殊形态的树
度为依附该顶点的边数
顶点的度，入度，出度
边的权、网
顶点和相邻顶点序偶构成的边的序列
路径
第一个顶点和最后一个顶点重合
回路
序列中顶点不重复出现
简单路径
路径、路径长度、回路（2011-408）
其他
基本概念
定义（无权）
定义（带权）
是用数组实现的顺序存储、空间复杂度较高
定义
求顶点度、入度、出度
性质
邻接矩阵法
邻接表示并不唯一
邻接表广度优先遍历，借助队列实现
邻接表法
只针对
含义
O(V+E)
空间复杂度
十字链表法
邻接多重表
四种方式对比
图的存储
广度优先搜索
层次遍历
需要借助辅助队列
相当于
O(V)
O(V^2)
邻接矩阵存储
邻接表存储
性能分析
每次选择自己邻近的最短的边
单源最短路径问题
生成树唯一
邻接矩阵
邻接表
广度优先生成树
调用BFS函数的次数=连通分量数
对于无向图
BFS
深度优先搜索
先根树
借助递归工作栈
O(E+V)
DFS
上述两个函数调用BFS和DFS的次数等于该图的连通分量数
图的遍历可用来判断连通性
任取顶点，再选取离顶点最近的点相连
边稠密的图
适合
Prim算法
每次选取权值最小的两个顶点
O(E*log E))
边稀疏，顶点较多
Kruskal算法
最小生成树
求单源最短路径，针对无权图
求解单源最短路径问题
标记各顶点是否找到最短路径
final[ ]
最短路径长度
dist[ ]
最短路径前驱
path[ ]
构造过程中使用辅助数组
带负权值时不适用
可以带回路，也可以任意两个顶点的最短路径
适用情况
Dijkstra算法
求解各顶点最短路径问题
动态规划思想
带负权值时适用
不适用带负权值的边组成的回路
O(V^3)
复杂度
Floyd
区分
最短路径
2019-6
有向无环图
用来描述表达式
AOV，AOE网均是有向无环图
化简DAG图
DAG图
DAG图表示一个工程
顶点表事件
有向边表关系
功能描述
逆拓扑排序
DFS实现拓扑排序和逆拓扑排序
理解
AOV网
拓扑排序
边表活动
ve(k)
vl(k)
e(i)
l(i)
AOE网
关键路径（2011-408）
图的应用
图的遍历
线性表
一对一关系
关系
一对多
多对多
图状结构/网状结构
非线性结构
外框
逻辑结构
数据的运算
链式存储
索引存储
哈希存储
别名
散列存储
非顺序存储
存储结构（物理结构）
数据结构三要素
定义一个ADT（抽象数据类型）就是在定义一种数据结构
确定ADT存储结构，才可以实现存储
相同性质元素集合
数据对象
原子类型
结构类型
数据类型
描述数据逻辑结构、抽象运算【用数据对象、数据关系、基本操作集来表示】
ADT
抽象数据类型
描述数据元素之间的关系
数据结构
程序=数据结构+算法
对特定问题求解步骤的一种描述
有穷性
确定性
可行性
输入
输出
正确性
可读性
健壮性
效率与低存储量需求
“好”算法
函数递归调用带来内存开销
效率度量
算法
绪论
相同数据类型的n个数据元素的有限序列
基本操作
随机访问
存储密度高
扩容、插入删除操作不方便
逻辑、物理均相邻
插入，删除，查找均为
顺序表
头插法
需要添加一个表尾指针，用来始终指向表尾结点
尾插法
单链表
节点中含两个指针prior、next，分别指向前驱结点和后继结点
双链表
表尾结点指针不指向NULL，指向头结点
区别于单链表
循环单链表
循环双链表
循环链表
分配一整片连续的内存空间，各个结点集中安置
数组方式实现的链表
next==-1
结束标志
静态链表
n个不同元素进栈，出栈元素不同的排列数为C(上标n，下标2n）/（n+1）
卡特兰数
只允许一段插入、删除的线性表
代码
初始栈顶指针为-1【进栈指针先加1，再进栈；出栈，先出栈，指针再减1】初始栈顶指针为0【……】
顺序栈
共享栈
带头结点
推荐使用
不带头节点
两种实现方式
链栈
栈类别
栈
只允许在一端进行插入，在另一端进行删除的线性表
实现思想
循环队列
链式队列
两端插入，两端删除的线性表
双端队列
队列
遇到左括号就入栈，遇到右括号就出栈
括号匹配
”左优先“原则
中缀转后缀
先弹出的是右操作数
计算
后缀表达式
右优先原则
中缀转前缀
先弹出的是左操作数
前缀表达式
表达式求值
递归工作栈
递归中的应用
层次遍历中的应用
进程抢占，先来先服务
操作系统中
计算机系统中的应用
栈、队列的应用
行优先
列优先
一维数组
对称矩阵
三角矩阵
三对角矩阵
压缩存储
稀疏矩阵
多维数组
数组
顺序存储：三元组；链式存储：十字链表
特殊矩阵压缩存储
栈、队列、数组
定长顺序存储
堆分配存储
块链存储
暴力匹配法
值为前缀和后缀最长的共有元素的长度
next数组
KMP算法
nextval数组
KMP算法优化
模式匹配算法
串
分支结点：度>0的结点
树的性质
常考性质
树
是一颗有序树
n个结点的二叉链表共有n+1个空链域（可用于构造线索二叉树）
非空二叉树叶子结点等于度为2结点数+1，n0=n2+1
满二叉树
位置关系（初始结点从1开始）
完全二叉树
树中若存在相同关键字结点，则插入失败
二叉排序树（BST）
联系第七章，查找
平衡二叉树（AVL树）
特殊二叉树
第一次路过访问的结点
先序遍历
第二次路过访问的结点
中序遍历
第三次路过访问的结点
后序遍历
若队列非空，则队头结点出队，访问该结点，然后将左右孩子插入队尾
根结点入队
需要借助一个辅助队列
未考虑层与层之间的关系
先序序列和中序序列
后序和中序
层序和中序
确定一棵二叉树
遍历序列构造二叉树
遍历
将没有左孩子，右孩子的结点线索化
中序
后序线索树的遍历仍需要栈的支持
知识结构
线索化
找前驱、后继
线索二叉树
用于数据压缩
前缀编码-没有一个编码是另一个编码的前缀
每个字符都用相等长度的二进制位表示
固定长度编码
允许对不同字符用不等长的二进制位表示
可变长度编码
编码
哈夫曼编码
只存在度为0和度为m的结点
n个结点新建n-1个结点
即树的带权路径长度WPL，最小
所有叶结点的带权路径长度之和，最小
每次选择两个最小的结点合并
哈夫曼树并不唯一
经典例题：2012-41-408
哈夫曼树（最优二叉树）
二叉树
双亲表示法
顺序+链式存储
孩子表示法
孩子兄弟表示法
左孩子右兄弟
用二叉链表存储森林
本质
森林和二叉树的转换
定义，存储结构
树，先根遍历【深度优先遍历】=森林先序遍历=二叉先序遍历
树，中根（后根）遍历【深度优先遍历】=森林中序遍历=二叉中序遍历
树层次遍历【广度优先遍历】（用队列实现）
树、森林
判断连通性，判断环
kruskal算法=排序+并查集
并，查
初始化并查集
代码实现
find
union
P185-9
模拟操作
操作
双亲表示法的树
逻辑
存储
存储方式
优化前O(n)
用根节点绝对值表示一棵树的结点总数
优化后O(logn)
find，先找到根节点，再进行压缩路径
union操作合并两棵树，小树并大树
终极优化
优化图解
O（1）
o(n^2)
优化前
o（n）
优化后
总复杂度
O(nlogn)
kruskal时间复杂度
并查集
树与二叉树
收藏
收藏
0 条评论
下一页
