数据结构
2021-09-02 00:14:02 209 举报AI智能生成
含有对应代码注解,考研和面试均可使用
作者其他创作
大纲/内容
树
基本概念
高度
结点高度
树的高度
层数/深度
结点深度
树的深度
祖先、子孙、兄弟、双亲；堂兄弟
度
结点的度
树的度
结点
分支结点
叶子结点
有序树与无序树
路径和路径长度
路径
路径长度
森林
性质
结点与度数
结点数(m)=非叶子结点数+叶子节点数
结点数 = Σ 度 x 个数 + 1【根】
结点个数
高度为 h 的 m 叉树至(最)多结点数
sp: 高 h 的二叉树结点至多为
偶数个结点的二叉树，其 度数为1 的结点个数必然为奇数
最小高度
n 个结点的 m阶树/m叉树/完全 m 叉树 的高度 【必背】
最大高度
n个结点，度为m的树最大高度
类型
二叉树
定义
如果某结点只有一个子结点，则必为左孩子
结点个数 ,含有左右子树的有序树
性质
个数相关
叶子结点个数
第k层最多结点数
高度为h至多结点个数
下标相关
左右孩子
i 结点的左孩子编号 = 2i
i 结点的右孩子编号 = 2i+1
深度相关
结点所在深度
完全二叉树】深度
严格二叉树的最大深度
(n+1)/2
指针个数
n个节点的二叉链存储节点空指针个数为 n+1
遍历访问序
次序合法性
访问序确定二叉树形状
左必在右的前面被访问
前中后序的访问序列，叶子结点序列不变
高度等于其结点数时，先序和后序遍历序列相反
类型
满二叉树
定义
完全二叉树
定义
层都是满的，同时第 层按照从左往右顺序填结点
每个结点都与高为 的满二叉树编号为 的结点位置一一对应
性质
若一个结点没有左孩子，则其必然是叶结点
叶子结点的双亲的左兄弟（若存在）则必然不是叶子结点
高度为 h 的完全二叉树，节点个数最小为
最后一个分支 (非叶) 结点序号为
若某完全二叉树有 个结点，则其叶子节点个数为
计算
第 x 层有 k 个叶子结点，
求结点个数max/min情况
求结点个数max/min情况
结点个数最少为：
结点个数最多为：
结点个数最多为：
存储结构
顺序存储
链式存储
遍历
先/前序(NLR)
中序(LNR)
后序(LRN)
树和森林
定义
度为m的树 m叉树
森林
存储结构
双亲表示法
顺序存储；存储地址=逻辑地址
孩子表示法
邻接表存储；有向图存储结构
孩子兄弟/二叉树表示法
森林结点数
已知森林边和结点数，求森林中包含的树的个数
森林和二叉树关系
右孩子指针为空的结点个数
森林左子树结点数=森林第一棵树结点树
遍历以及有序树
树：先根
森林：先序
二叉树：先序
树：后根
森林：后序
二叉树：中序
树、森林和二叉树转换
遍历
BFS广度优先搜索
复杂度分析
生成树与生成森林
DFS深度优先搜索
遍历与连通性
递归与非递规转换
递归 = 栈
层次遍历
辅助队列
遍历序列构造二叉树
中序(必须)+先序/后续
线索树遍历需要栈
后序遍历
求祖先到子孙的路径可以使用先/中序遍历
已知次序求二叉树异构个数
应用
哈夫曼树
带权路径长度
定义
带权路径长度(WPL)最小的二叉树；也称最优二叉树
度为 m 的哈夫曼树，为严格的 m 叉树
构造
贪心，每次取两个权值最小的结点作为新结点的左右子树
新结点权值为左右子树和，并放入到可选择的结点集合中
新结点权值为左右子树和，并放入到可选择的结点集合中
性质
初始结点均为叶子结点
权值越小到根节点路径越长
新建了n-1个结点，结点 总数 为 2n-1
度为m的哈夫曼树中，叶子结点为n，则其非叶子节点个数为
叶子结点个数即为不同符号的编码数
哈夫曼编码
固定长度编码
每个字符用相等长度二进制位表示
前缀编码
没有一个编码是另一个编码的前缀
线索二叉树
物理/存储结构
标志域含义
概念
线索
线索化
相关问题
线索化后的空链个数
仍需要栈支持的遍历为 后序线索树
不是每个结点都能通过线索查找其前驱后继
已知后序线索二叉树，求后序后继仍不能完全求解
二叉搜索树 BST
定义
操作
插入
查找
递归实现
非递归实现
删除
叶结点
直接删除
直接删除
x 只有一个左/右子树
子结点接上其父节点
子结点接上其父节点
x 有左右两棵子树
补前驱后继
补前驱后继
构造
性质
删除某节点后将其插入，则前后排序树有可能不同
题目计算
ASL(平均查找长度）
成功查找长度
失败查找长度
递增序列遍历=中序遍历
非法查找路径序列
平衡二叉树AVL
平衡机制
平衡因子
操作原理
插入/删除
旋转
旋转要点
调整最小不平衡子树
LL,RR 旋一次，LR,RL 旋两次（先内后外）
左重顺旋减轻左深，右重逆旋减轻右深
根连前驱后继【按照数值大小比较连接】
旋转方式
LL(左孩子左子树)
左子树旋转，降低一层就平衡
RR(右孩子右子树)
LR(左孩子右子树)
RL(右孩子左子树)
计算
构造一棵高为 h 的 AVL 所需要的最少结点数
已知共有 n 个结点的 AVL，求其最大深度
已知AVL的高度为 n,且所有非叶子结点的平衡因子为 1,求结点总数
并查集
操作
合并 Union
寻找祖先 Find(S,x)
初始化 Init(S)
图
相关概念
有向图
弧头(顶点)
弧尾(顶点)
无向图
简单图、多重图
简单图：无自环，无重复边
多重图：有自环，重复边
完全图
简单图的边数达到上限
子图
边和顶点均为子集且能够形成一张图
连通、连通图和连通分量
连通：u,v之间存在路径
连通图：图中任意两点均连通
连通分量：无向图中极大连通子图
强连通、强连通分量
强连通:有向图中的u,v互相可达
强连通图：有向图中任意两点互相可达
强连通分量：有向图中极大墙连通子图
生成树、生成森林
生成树：包含图中全部顶点的一个极小连通子图
生成森林：非连通图中连通分量的生成树构成了生成森林
极小连通子图：保持图的联通性，又使得边数尽可能少
顶点度，入度和出度
顶点度：无向图中顶点所连边数
边的权和网
网：带权图
稠密图、稀疏图
路径、路径长度和回路
路径：顶点序列【由顶点和相邻顶点序偶构成的边所形成的序列】
回路/环：路径中第一个和最后一个顶点相同
简单路径、简单回路
距离
有向树
无向图森林
n个顶点，e条边的无向图森林树的个数
存储结构
稀疏矩阵
十字链表
邻接表法
邻接多重表
稠密矩阵
邻接矩阵
有向图
无向图
性质
遍历
广搜bfs
深搜dfs
应用
最小生成树
Prim算法
Kruskal算法
最短路径
Dijkstra
Floyd
有向无环图表达式
拓扑排序
AOV网
有序序列个数
关键路径
AOE网
事件最早发生时间
事件最迟发生时间
活动最早开始事件
活动最晚开始时间
时间余量
排序
基本概念
关键字有序过程
稳定性
具体元素未知，至少比较次数
趟
排序过程中，对尚未确定最终位置的所有元素进行一遍处理
内部排序
常见类型
插入排序
直接插入
时间复杂度
稳定排序
特点
每一次排序完后，前i位有序，i位以后也可能存在使得原i位发生改变的值
折半插入
对已排好序列查找部分使用折半搜索
顺序存储
时间复杂度
稳定排序
希尔排序
算法描述
选定增量d，将原序列分成几个部分，然后对每个部分进行插入排序
选定增量d，将原序列分成几个部分，然后对每个部分进行插入排序
时间复杂度
空间复杂度
不稳定排序【分组原因】
交换排序
冒泡排序
算法描述【最大泡泡冒起来】
每一次排序将最小/最大的元素，通过依次遍历比较交换，放到序列末尾/队首最终位置
每一次排序将最小/最大的元素，通过依次遍历比较交换，放到序列末尾/队首最终位置
时间复杂度
空间复杂度
稳定排序
特点
前i位或者后i位(根据顺序或逆序)为最终有序排序
快速排序
基于分治思想【二分】
时间复杂度【与递归栈的深度有关】
空间复杂度【栈深】
特点
某个值的左边均为小于它的值，右边均为大于它的值
当序列基本有序或者逆序情况下，效率最低：受不平衡划分影响
真题
2014) 对 15 个元素进行快排，则比较元素次数最少是
选择排序
简单选择
算法描述
每趟找到后n-i个元素中，关键字最小的元素，并与第i个元素进行交换
每趟找到后n-i个元素中，关键字最小的元素，并与第i个元素进行交换
时间复杂度
空间复杂度
不稳定排序【多个最小取最后遍历位置】
特点
前i位或者后i位(根据顺序或逆序)为最终有序排序
堆排序
算法描述
二叉堆：完全二叉树，左右子树
均小于/大于根结点【小/大顶堆】
二叉堆：完全二叉树，左右子树
均小于/大于根结点【小/大顶堆】
时间复杂度
空间复杂度
建堆时间【计算补充】
特点
最后一个非叶子结点位置为len/2【根结点下标为1】
不稳定排序【调整时可能调节后面位置到根】
归并排序
算法描述
二路归并算法：初始每个子表长度为1，然后不断两两合并排序，最终合并成长为n的有序序列
二路归并算法：初始每个子表长度为1，然后不断两两合并排序，最终合并成长为n的有序序列
时间复杂度 【与序列初始状态无关】
空间复杂度
稳定排序
特点
当有足够大到内存装不下的文件进行排序时，采用分治的归并排序
基数排序
算法描述
基于关键字位上数字大小进行逐一排序
基于关键字位上数字大小进行逐一排序
时间复杂度
空间复杂度
常见关键字排序
最高位优先 MSD
最低位优先 LSD
稳定排序
排序比较
时间复杂度
有序情况下
直接插入、冒泡排序
快排
无序情况下【平均】
简单选择、直接插入、冒泡排序
堆排，快排、归并
空间复杂度
简单选择、插入、冒泡、希尔、堆排
快排
归并
算法稳定性
稳定排序
不稳定排序
存储结构影响
顺序存储
链式存储
算法过程特征
【每趟排序能够得到至少一个最终有序序】
堆排序，快速排序、简单选择、冒泡排序
【比较次数与初始序列】
无关
二路归并排序、简单选择排序、基数排序
二路归并排序、简单选择排序、基数排序
有关
快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
【排序趟数与初始序列】
无关
直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序
直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序
有关
冒泡排序、快速排序
冒泡排序、快速排序
外部排序
基本概念
一般方法
归并排序法
归并排序法
外部排序总时间 = 内存排序时间 + 外存信息读写时间 + 内部归并所需时间
归并躺数 = 树的高度 =
归并总比较次数 =
=
=
I/O 操作次数
读入归并段，写入归并段（以块为单位）
读入归并段，写入归并段（以块为单位）
图解
初始序列为12个无序数据
把内存数据划分为多个块，首先对块内进行排序，形成有序字串
将两个已经排序好的子块进行归并成一个更大的块【二路归并】
继续将小的归并段合并为更大的归并段
多路平衡归并与败者树
k 路平衡归并
最多只能有 k 个段归并为一个
每一趟中，若有m个块进行归并，则一趟处理得到个块
胜者树/败者树
胜者树
败者树
利用败者树加快排序
置换-选择排序
原理
初始段建立图解
每组划分6个元素，则初始组数至少划分4组
选择出第一个 MINIMAX 29
选择比初始段中更大的 MINIMAX 38
同理
直到无 MINIMAX 选出，此时认为初始段已经完成
败者树利用
最佳归并树
原理
附加虚短的最佳归并树
额外补充虚断数
C11语法
typedef 关键字
struct 结构体
语法
不带 typedef 标签
带 typedef 标签
错误语法
结构体嵌套
自引用
相互引用
C与C++中 struct 区别
指针 T *t
地址与值
& 取地址/引用(别名)
绪论
算法
算法定义
问题求解步骤描述
五个特性
有穷性
确定性
可行性
输入
输出
复杂度计算
时间复杂度
加法规则
乘法规则
常见渐进时间复杂度
等差等比公式
空间复杂度
定义
辅助空间大小与原数据量之间的关系
辅助空间大小与原数据量之间的关系
原地工作
求解问题
递归算法
递推公式
递归调用
递归公出口
列方程法
数据
数据对象
数据元素
(个体)基本单位
数据项
(个体)属性
数据类型
原子类型
结构类型
抽象数据类型(ADT)
数据结构
三要素
逻辑结构
线性结构
一般线性表
受限线性表
栈
队列
串
线性表推广
数组
非线性结构
树
二叉树
多叉树
森林
图/网
有向图
无向图
集合
存储结构
顺序存储
链式存储
索引存储
散列存储/哈希存储
数据运算(操作)
Linear List
线性表
线性表
定义/概念
有限个数据元素，相同数据类型，且有序
存储空间大小相同
表头元素；表尾元素；位序； 前驱；后继
操作
创建/销毁
静态分配
动态分配
C/C++
malloc , new[]
malloc , new[]
增删改查
属性获取
存储结构
sequential mapping
顺序存储
顺序存储
SqList
顺序表
顺序表
特性
随机存取[物理顺序和逻辑顺序相同]
删除和插入时间复杂度高
分配方式
静态
C语言数组方式分配
动态
C语言指针方式分配
操作
初始化
插入
实现逻辑
健壮性判断
移动
属性修改
返回函数状态
时间复杂度
最好
O(1)
O(1)
最坏
O(n)
O(n)
平均 = 概率 移动次数 = 期望
删除
实现逻辑
健壮性
移动
属性修改
返回函数状态
时间复杂度
最好
O(1)
O(1)
最坏
O(n)
O(n)
平均
按值查找
实现逻辑
顺序寻找
返回位序
时间复杂度
最好
O(1)
O(1)
最坏
O(n)
O(n)
平均
合并
真题
2010】408
整数数组循环左移
整数数组循环左移
2011】408
找出两个等长升序序列的中位数
找出两个等长升序序列的中位数
2013】408
找出序列中的主元素
主元素：个数 > 序列总个数/2
找出序列中的主元素
主元素：个数 > 序列总个数/2
2018】408
求最小未出现整数
求最小未出现整数
2020】408
求三元组最小距离
求三元组最小距离
链式存储
单链表
定义
操作
插入
头插法
尾插法
时间复杂度
O(n)
O(n)
删除
按值查找
判空
双链表
定义
操作
插入
实现逻辑
时间复杂度
删除
循环链表
单向循环链表
双向循环链表
静态链表
跳跃表
相关概念
头结点
头指针
链表头
首元结点
尾指针
真题
2009】408
查找只含头结点的单链表中倒数第k位置的结点值
查找只含头结点的单链表中倒数第k位置的结点值
2012】408
求出某两个链表共同后缀起始位置
求出某两个链表共同后缀起始位置
2015】408
单链表中保留所有绝对值相等节点中, 第一个出现位置的结点
单链表中保留所有绝对值相等节点中, 第一个出现位置的结点
2019】408
对单链表进行重排
对单链表进行重排
优缺点
顺序
随机访问，链式则只能顺序访问
链式
分配灵活，无需占用连续空间，插入删除时间复杂度低
逻辑结构
栈(Stack)
定义
栈顶(top)
栈低(Bottom)
空栈(Empty)
特性
LIFO 后进先出
LIFO 后进先出
数学性质 [ 卡特兰数 ]
n 个不同元素进栈，出栈元素不同的排列个数为
n 个不同元素进栈，出栈元素不同的排列个数为
操作
初始化
Init (&S)
Init (&S)
销毁
Destroy(&S)
Destroy(&S)
进栈(Push)
Push(&S,&e)
Push(&S,&e)
出栈
Pop(&S,&e)
Pop(&S,&e)
读取栈顶
GetTop(S,&e)
GetTop(S,&e)
判空
IsEmpty
IsEmpty
存储结构
顺序
顺序栈
共享栈
链式
链栈
操作
属性
表头结点
表尾结点
应用题型
括号匹配
表达式求值
前缀/波兰表达式
中缀
后缀/逆波兰表达式
转换方法
计算方法
表达式树
递归调用
时间复杂度计算
dfs广搜
出栈序列
不可能序列
序列种类数
卡特兰数:
可能序列
数值转换
栈的最小深度
函数局部变量存储
队列/Queue
基本操作
FIFO
初始化
销毁
判空
入队
出队
读取队头元素
概念
队头指针
队尾指针
头结点
存储结构
顺序
循环队列
顺序存储
链式
双端队列
链式存储
定义
操作
逻辑结构
应用
二叉树层次遍历
出队序列计算
做题时可标注左右进入的序列
FIFO性质
OS缓冲区
CPU资源分配
页面替换算法
数组矩阵
数组
定义
存储结构
行优先
列优先
特殊矩阵
对称矩阵
下标转换公式
三角矩阵
下标转换
三对角矩阵
下标转换
稀疏矩阵
三元组
十字链表
疏密矩阵
邻接矩阵
真题
矩阵元素下表与一位数组下标换算
地址求行长
串
基本概念
子串
主串
位置
存储结构
定长顺序存储
堆分配存储
块链存储
相关运算
模式匹配
暴力匹配
KMP算法
next数组
next手工算法
相等判断
求子串
连接
长度
查找
效率指标
平均查找长度
查找成功
查找失败
概念
查找表/查找结构
操作
查找特定元素
检查满足条件元素属性
插入元素
删除元素
静态查找表
顺序
折半
散列
动态查找表
二叉排序树
AVL平衡二叉树
B树
平均查找长度
冲突/碰撞
同义词之间冲突
不可能避免
聚集/堆积
同义词与非同义词发生冲突
主要与冲突探测方法有关
散列结构
散列函数
直接定址法
除留余数法
数字分析法
平方取中法
冲突处理
开放定址法
线性探测再散列
二次探测再散列
伪随机探测再散列
链地址法/拉链法
再哈希(散列)法
平均查找长度
查找成功
查找失败
装填因子
a= 表中记录数/散列表长度
线性结构
顺序查找(链式限制)
一般顺序表查找
有序表顺序查找
折半(二分)查找
适用于有序顺序存储结构
折半查找判定树
类型：平衡二叉树
n 个元素时的树高 h
判定树是否复合规则判断
最多查找次数
最少查找次数
分块(索引顺序)查找
理想块长
顺序分块查找
最优优化
索引结构/树表
B树
属性
B树的阶
非叶结点结构
所有结点平衡因子为 0 【高度平衡】
高度
最高
最低
关键字数
最多
最少
性质
非根结点关键字个数
非根结点子树个数
根节点为非终端结点时，至少有两个孩子.
严格平衡查找树，所有节点子树高度一致
叶子处于同一层且用NULL表示
叶子处于同一层且用NULL表示
非叶结点的结构
操作
查找
插入
分裂
删除
合并
图示
计算
已知阶、层数、某层关键字数，求最多结点数
B+树
图示
B与B+树区别
红黑树
定义
性质
应用
基本操作
变色
旋转
插入
插入调整
删除
删除调整
935考纲对比
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)
(九) 基数排序
(十) 【外部排序】
(十一) 各种排序算法的比较
(十二) 排序算法的应用
一、线性表
(一) 线性表的定义和基本操作
(二) 线性表的实现
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)
(九) 基数排序
(十) 【外部排序】
(十一) 各种排序算法的比较
(十二) 排序算法的应用
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)
(九) 基数排序
(十) 各种内部排序算法的比较
(十一) 内部排序算法的应用
一、线性表
(一) 线性表的定义和基本操作
(二) 线性表的实现
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)
(九) 基数排序
(十) 各种内部排序算法的比较
(十一) 内部排序算法的应用
0 条评论
下一页
