空
front==rear&&tag==0
满
front==rear&&tag==1
链队列
概念 用链式存储方式存储队列
带头结点
不带头结点
基本操作
初始化
入队 注意第一个元素入队
出队 注意最后一个元素出队
获取队头元素
双端队列
概念 只允许从两端插入、两端删除的线性表
分类
双端队列
输入受限的双端队列
输出受限的双端队列
题型 判断输出队列的合法性
队列的应用
树的层次遍历
图的广度优先遍历
在操作系统中应用
数组和特殊矩阵
数组的存储结构
一维数组
二维数组
行优先存储 b[i][j]存储位置:LOC+(i*N+j)*sizeof(ElemType)
列优先存储 b[i][j]存储位置:LOC+(j*M+i)*sizeof(ElemType)
特殊矩阵压缩存储
对称矩阵
策略:只存储主对角线+下三角区;(或主对角线+上三角区)
存储(以下三角为例)
行优先
k=
i(i-1)/2+j-1, i>=j(下三角区和主对角元素)
j(j-1)/2+i-1, i<j(上三角区元素)
列优先
三角矩阵
策略 存储主对角线+三角区元素
存储
行优先
k=
(i-1)(2n-i+2)/2+(j-i) i<=j(上三角区和主对角线)
n(n+1)/2 i>j(下三角区元素)
列优先
三对角矩阵
策略 只存储带状部分
存储
行优先
k=
i(i-1)/2+(j-1) i>=j(下三角区和主对角线)
n(n+1)/2 i<j(上三角区元素)
列优先
稀疏矩阵
策略 只存储非零元素
存储
顺序存储--三元组<行,列,值>
链式存储--十字链表法
串
基本概念
定义 串、串名、串长度、空串、子串、主串、字符在主串中的位置、子串在主串中的位置
存储结构
顺序存储
方案一:数组最后一位元素存放长度变量
方案二:首位置存放长度变量
方案三:以字符“ ”表示结尾
方案四:首元素空着 ,数组最后一位元素存放长度变量
链式存储
方案一:每个字符附带一个指针
方案二:一组字符附带一个指针
基本操作
求子串 SubString
字符串比较 StrCompare
定位操作 Index
模式匹配
定义 在主串中找到与模式串相同的子串,并返回其所在位置
朴素模式匹配算法
概念
时间复杂度:O(nm)
KMP算法
优化思路
next数组
作用
求法
next[1]:0
next[2]:1
其他next
前后缀法
模式后退法
最坏时间复杂度:O(m+n)
KMP算法优化
优化思路
nextval数组 先求出next数组
树与二叉树
树
基本概念术语
概念
空树
非空树
根结点
分支结点
叶子结点
边
子树
有序树
无序树
森林
结点
关系
祖先结点
子孙结点
双亲结点(父结点)
孩子结点
兄弟结点
堂兄弟结点
路径、路径长度
属性
结点深度
结点高度
结点的度
树的度
性质
结点数=总度数+1
度为m的树、m叉树区别
度为m的树第i层至多有m^(i−1)个结点
m叉树第i层至多有m^i-1个结点
高度为h的m叉树至多有(m^h-1)/(m-1)个结点
高度为h的m叉树至少有h个节点
高度为h、度为m的树至少有h+m-1个结点
具有n个结点的m叉树的最小高度是[log_𝑚 (𝑛(𝑚−1)+1)]
存储结构
双亲表示法
每个结点保存指向双亲的“指针”
顺序表示
孩子表示法
顺序存储各个结点,每个结点中保存孩子链表头指针
顺序+链式存储
孩子兄弟表示法
每个结点两个指针,一个指向左孩子,一个指向右兄弟
链式存储
二叉树
概念特点
每个结点至多只有两颗子树
左右子树不能颠倒
几种特殊二叉树
满二叉树
概念 高度为h,结点数为2^h-1的二叉树
特点
只有最后一层有叶子结点
不存在度为1的结点
按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1;结点i的父结点为[i/2]向下取整
完全二叉树
定义 每个结点都与高度为h的满二叉树中编号为1-n的结点一一对应
特点
只有最后两层可能有叶子结点
最多只有一个度为1的结点
按层序从1开始编号,结点i的左孩子为2i,右孩子为2i+1;结点i的父结点为[i/2]向下取整
i<=[n/2](下取整)为分支结点,i>[n/2](下取整)为叶子结点
二叉排序树
左子树上所有结点关键字小于根结点
右子树上所有结点关键字大于跟结点
左右子树各是一颗二叉排序树
平衡二叉树 树上任一结点的左子树和右子树的深度之差不超过1
性质
n0=n2+1
第i层最多有2^(i-1)个结点
高度为h的二叉树最多有2^h-1个结点
完全二叉树
具有n个结点的完全二叉树的高度为[log_2(n+1)](向上取整)或[log_2(n)](向下取整)+1
可以由结点数n推出度为0、1和2的结点个数n0、n1、n2
n个结点的完全二叉树高度log_2(n)+1取下界
存储结构
顺序存储
元素按层次存储
结点编号反映结点之间关系
注意:一定要把结点编号与完全二叉树对应
链式存储 左、右孩子指针存储法
问题一:产生大量空指针域 解决方法:线索二叉树
线索:指向前驱、后继的指针
二叉树的线索化
中序线索化
先序线索化
后序线索化
找前驱、后继
问题二:无法找到父结点 解决方法:三叉链表
二叉树的遍历
遍历方式
层次遍历 借助辅助队列
先序遍历
中序遍历
后序遍历
由遍历序列构造二叉树
前序+中序
后序+中序
层序+中序
树、森林与二叉树的转换
原则:树-左孩子、右兄弟;二叉树:左孩子、右孩子
森林与二叉树之间的转换
树、森林的遍历
树的遍历
先根遍历 对应二叉树先序遍历
后根遍历 对应二叉树中序遍历
层序遍历
森林的遍历
先序遍历 依次对各个树进行先根遍历
中序遍历 依次对各个树进行后根遍历
哈夫曼树
带权路径长度WPL
定义 在含有n个带权叶结点的二叉树中,其带权路径长度最小的二叉树
哈夫曼树构造
哈夫曼编码 由哈夫曼树得到的编码
图
基本概念
定义 非空、无向图、有向图、顶点的度、出度、入度、边的权、带权图
点之间关系
路径、回路、简单路径、简单回路
路径长度
点到点的距离、最短路径
无向图顶点的连通性、连通图
有向图顶点的连通性、强连通图
局部图
子图
连通分量 极大连通子图
强连通分量 极大强连通子图
连通无向图的生成树 包含全部顶点的极小连通子图
非联通无向图的生成森林 各连通分量的生成树
几种特殊的图
完全图
稠密图、稀疏图
树、森林、有向树
图的存储
邻接矩阵
空间复杂度
适用情况
入度、出度
邻接表
空间复杂度
适用情况
表示方式
出度、入度
十字链表
顶点结点
弧结点
适用于:有向图
邻接多重表
顶点结点
边结点
适用于:无向图
空间复杂度
基本操作 图的遍历
广度优先遍历BFS
概念
性能分析
空间复杂度:O(|V|)
时间复杂度
邻接表:O(|V|+|E|)
邻接矩阵:O(|V|^2)
非连通
广度优先遍历序列
广度优先生成树
深度优先遍历DFS
概念
性能分析
空间复杂度:O(|V|)
时间复杂度
邻接表:O(|V|+|E|)
邻接矩阵:O(|V|^2)
深度优先遍历序列
深度优先生成树
图的应用
最小生成树MST
概念
两种算法
Prim算法(普里姆)
思想
特点
时间复杂度:O(|V|^2),不依赖|E|
适用:稠密图
Kruskal算法(克鲁斯卡尔)
思想
时间复杂度:O(|E|log_2(|E|))
适用:稀疏图
最短路径
单源最短路径
BFS算法 适用情况
Dijkstra算法
思想
辅助变量
特点
各顶点间最短路径 Floyd算法
思想
特点
局限 不能解决“负”权值的图
拓扑排序
有向无环图DAG 描述表达式
顶点表示网络AOV网
拓扑排序
定义
实现
特点
注意
关键路径
用边表示活动的网AOE网
几个概念
几个参量
关键路径
查找
基本概念
查找表
静态查找表 顺序查找、折半查找、散列查找
动态查找表 二叉排序树、B树、散列查找
平均查找长度ASL
查找成功
查找失败
顺序查找
一般线性表顺序查找
算法特点
优缺点
优点 数据存储、记录有序性无要求
缺点 n较大时,查找长度大
性能
ASL成功 (n+1)/2
ASL失败
n+1
有序表的顺序查找
特点
性能
查找成功
查找失败
n/2+n/(n+1)
折半查找
特点 仅适用于有序的顺序表
思想
时间复杂度
O(log_2(n))
性能 构建二叉查找树
分块查找
思想
块内无序,块间有序
索引表:存放块中最大关键字与各块中第一个元素地址
平均查找长度
L1+Ls
树形查找
二叉排序树
基本操作
查找
插入
构造
删除
查找效率分析
最好情况
O(log_2(n))
最坏情况
O(n)
平衡二叉树
插入
LL
右单旋转
RR
左单旋转
LR
先左后右双旋转
RL
先右后左双旋转
删除
按照二叉排序树方式删除
找最小不平衡子树下个头最高儿子、孙子
孙子LL
孙子RR
孙子LR
孙子RL
不平衡向上传递
查找
高度为h的平衡二叉树最小结点数
n0=0
n1=1
n(h)=n(h-1)+n(h-2)+1
时间复杂度O(log_2(n))
B树、B+树
B树
概念
基于二叉查找树
特性(m阶B树)
根节点子树数[2,m],关键字数[1,m-1]
其他结点的子树数[m/2,m],关键字数[(m/2)-1,m-1]
对任一结点,所有子树高度相同
关键字的值:子树0<关键字1<子树1<关键字2<子树2……
查找
插入
只能插入终端结点
两个原则
除根节点外,结点关键字个数[m/2-1,m-1]
关键字的值:子树0<关键字1<子树1<关键字2<子树2……
方法
删除
删除结点为终端结点
关键字个数不低于下限 直接删除
关键字个数低于下限
兄弟够借
兄弟不够借 合并
删除结点非终端结点
用直接前驱或直接后继代替
直接前驱
直接后继
B+树 概念
基于分块查找 “索引表”保存每个分块的最大关键字和分块的存储空间
特性
每个分支结点最多有M棵子树
非叶根结点至少有两颗子树,其他分支结点至少有[m/2]棵子树
结点的子树个数与关键字个数相等
所有叶结点包含全部关键字及指向相应记录的指针,叶结点关键字按大小排序,并且相邻叶结点按大小顺序相互链接起来
所有分支结点仅包含它的各个子结点中关键字的最大值及指向子结点的指针
查找 无论查找成功与否,都走到最下面一层结点
B树与B+树比较
不同点一
B+树:结点中n个关键字对应n棵子树;非叶根结点至少有两颗子树,其他分支结点至少有[m/2]棵子树
B树:除根结点其他结点的子树数[m/2,m],关键字数[(m/2)-1,m-1]
不同点二
B+树:叶结点包含全部关键字,关键字有重复
B树:各结点包含关键字不重复
不同点三
B+树:叶结点包含信息,非叶结点仅仅起到索引作用;索引项只包含对应子树最大关键字和指向该子树指针,不包含该关键字存储地址
B树:结点中包含关键字对应的记录存储地址
不同点四
B+树:支持顺序查找
B树:不支持顺序查找
相同点
除根点外,最少[m/2]个分叉
任何一结点子树一样高
散列表
概念
数据元素关键字与存储地址直接相关
同义词、冲突
散列函数
除留余数法
直接定址法
数字分析法
平房取中法
冲突
拉链法
把“同义词”存储在一个链表中
装填因子 表中记录数/散列表长度
开放定址法
增量序列
线性探测法 查找效率分析
平方探测法
伪随机序列法
注意删除操作 做删除标记
再散列法
排序
基本概念 评价指标
稳定性
时间复杂度
空间复杂度
插入排序
直接插入排序
代码实现 哨兵
性能
稳定
时间复杂度
最好时间复杂度
O(n)
最坏时间复杂度
O(n^2)
空间复杂度
O(1)
折半插入排序
代码实现
性能
稳定
时间复杂度
O(n^2)
空间复杂度
O(1)
希尔排序
思想
适用 仅适用于顺序表
算法实现
性能
不稳定
时间复杂度 不确定
最坏
O(n^2)
可达
O(n^1.3)
空间复杂度
O(1)
交换排序
冒泡排序
思想
提前结束 在某一趟排序未发生交换
适用 顺序表、链表
性能
稳定
时间复杂度
最好情况(有序)
O(n)
最坏情况(逆序)
O(n^2)
空间复杂度
O(1)
快速排序
思想
代码实现
性能
不稳定
空间复杂度 O(递归层数)
最好情况
O(log_2(n))
划分平均
最坏情况
O(n)
正序或逆序
时间复杂度 O(n*递归层数)
最好情况
O(n*log_2(n))
最坏情况
O(n^2)
平均时间复杂度
O(n*log_2(n))
选择排序
简单选择排序
思想
代码实现
适用性 顺序表、链表
性能
不稳定
空间复杂度
O(1)
时间复杂度
O(n*2)
堆排序
堆的分类
大根堆
小根堆
思想
建立大根堆 自低向上调整各分支结点
将堆顶元素加入有序子序列
将待排序元素调整为大根堆
性能
空间复杂度
O(1)
时间复杂度
O(n*log_2(n))
不稳定
插入
小根堆 新元素不断“上升”
大根堆 新元素不断上升
删除 最后一位元素补空缺 不断下坠
归并排序
思想
分类
二路归并
多路归并
代码实现
性能
空间复杂度
O(n)
时间复杂度
O(nlog_2(n))
稳定
基数排序
思想
性能
空间复杂度
O(r)
时间复杂度
O(d(n+r))
稳定
适用情况