《数据结构》课程回顾
8.31 | 9.4 | 9.9 | 9.11 |
9.18 | 9.23 | 9.25 | 9.27 |
9.30 | 10.9 | 10.14 | 10.21 |
10.23 | 10.28 | 10.30 | 11.4|
11.6 | 11.11 | 11.13 | 11.18 |
11.20 | 11.25 | 11.27 | 12.2 |
12.9 | 12.11 | 12.16 | 12.18
- 哈希表
- 处理冲突的方法
- 开放定址法：二次聚集
- 链地址法：不会引起非同义词之间的冲突
- 再哈希法
- 建立一个公共溢出区
- 哈希表的查找及其分析：算法、平均查找长度、装填因子
- 哈希表的插入、删除
- 动态存储管理
- 动态存储管理的需求和主要问题
- 可利用空间表及分配方法
- 可利用空间表的结构:目录表 vs. 链表
- 可变分区的分配方法:首次拟合、最佳拟合、最差拟合
- 边界标识法
- 可利用空间表的结构：可利用存储块组成一个双向循环链表
每个存储块：有头部标识（空闲标识，块的大小，双向循环链）和尾部标识（头部的起始地址，空闲标识）
- 分配算法：空闲块的大小比申请的大，则拆分成2块
- 回收算法：利用被回收空间的前后标识来快速检查左邻和右邻的存储块是否是空闲的，若空闲则合并
- 伙伴系统
- 可利用空间表的结构：额外的索引表(表长m＋1)，
每个索引项包括大小（i）以及指向由该大小（2i）的可利用存储块组成的链表
- 分配算法: 对分，从1块中对分成的2个小块被称为互为伙伴。
- 回收算法: 两空闲块互为伙伴才被归并
[顶层]
- 动态查找表
- m阶B-树
- m阶B-树的定义; 2-3树
- 查找算法：纵向、横向交叉进行
- 插入算法思想：注意结点的关键字是否达到m，达到m则要“分裂”
- 删除算法思想：注意结点的关键字是否低于B-树的限制，若低于则先“向兄弟借”,借不到则与一个兄弟及双亲关联的关键字“合并”
- B-树的查找分析: 结点数与高度的关系
- B+树
- 键树
- 定义
- 键树的双链树表示
- 键树的多重链表表示－－Trie树
- 哈希表
[顶层]
- 动态查找表
- 二叉排序树
- 定义与性质
- 查找算法及性能分析
- 插入算法：作为叶子插入
- 删除算法：分三种情况；针对待删的结点有左右孩子的情况，有四种删除方法，两两对称
- 查找的时空性能分析
- 平衡二叉树
- 平衡二叉树的定义:平衡因子
- 平衡化的四个规律：LL型(向右旋转)、RR型(向左旋转)、LR型(先向左旋再向右旋)、RL型(先向右旋再向左旋)
- 平衡的二叉排序树上的插入算法
- 查找的性能分析: 结点数与高度的关系
- m阶B-树
[顶层]
- 查找
- 顺序查找：思想、数据结构、算法、性能分析(平均查找长度ASL)
- 折半查找：思想、数据结构、算法、性能分析(平均查找长度ASL)
- Fibonacci查找：思想
- 插值查找：思想
- 静态树表的查找：定义(PH值：树的带权内路径长度)、次优查找树的构造、查找算法
- 索引顺序表的查找：起因、思想、查找算法、性能分析
注意：在计算ASL时，要注意是针对查找成功，还是查找不成功，还是两者都考虑！
你需要为每一种情况的发生概率作假设，然后给出ASL!
- 动态查找表
[顶层]
- 广义表
- 存储结构：头尾链表示、扩展线性链表示
- m元多项式的表示
- 广义表的递归算法
- 基本项和归纳项
- 广义表的递归算法：基于头尾链表示或扩展线性链表示，重点要理解广义表的存储结构
- 查找
- 一些概念：查找表(静态、动态)，关键字，查找(不)成功
- 静态查找表:查找的目的只是为了检索和查询！
[顶层]
以下问题及算法，需要从问题的应用背景、算法思想、算法在具体图上的应用、算法及其复杂性分析等方面逐步深入理解和消化！
- 有向无环图及其应用
- 拓扑排序（AOV-网）
- 对于DAG，拓扑有序序列不一定唯一
- 选择入度为0的输出----可用于检测有向图是否有环
- 若已知图为DAG，则利用DFS可以得到逆拓扑有序序列
- 算法：保存当前入度为0的顶点编号的数据结构没有限制，可以是栈、队列等; 采用邻接表存储图时，T(n,e)=O(n+e)
- 关键路径（AOE-网）
- 事件的最早(迟)发生时间、活动的最早(迟)开始时间、关键活动
- 算法：基于拓扑排序求事件的最早发生时间，基于逆拓扑序列求事件的最迟发生时间，求活动的最早(迟)开始时间并判断是否为关键活动; 采用邻接表存储图时，T(n,e)=O(n+e)
- 最短路径
- 无权图的最短路径：广度优先搜索
- 单源最短路径：Dijkstra算法（依路径中弧的数目递增的次序）
- 每一对顶点之间的最短路径
- 调用Dijkstra算法
- Floyd算法(中间顶点的次序号不大于k, k逐步增加)
- 广义表: 元素类型可以是原子，也可以是子表; 广义表的表头，表尾
[顶层]
- 图的连通性
- 有向图的强连通分量：DFS和逆向DFS
- 最小生成树
- 最小生成树的定义和MST性质
- 普里姆算法：最小生成树不断壮大的过程，适于稠密图，T(n)=O(n2)
算法的关键：如何表示当前生成树的顶点集U、如何表示V-U中各顶点到U中各边的最小权值和关联的顶点
- 克鲁斯卡尔算法：连通分量不断合并的过程，适于稀疏图,T(n,e)=O(elog2e)
算法的关键：排序、多个连通分量的表示（利用第6章的MFSet）
- 关节点和重连通分量
- 定义：关节点、重连通图、连通度
- 关节点在深度优先生成树中的特点
算法的关键：顶点的深度优先访问序号visited[v]，理解low[v]的含义；如何根据visited和low确定关节点
- 有向无环图及其应用
- 应用举例：用有向无环图表示表达式->公共子表达式的共享
- 如何判断一个无向图/有向图是否有环？
- 拓扑排序（AOV-网）
[顶层]
- 非递归的DFS遍历算法
- 遍历算法的应用
- 基于DFS的算法设计
- 基于BFS的算法设计
- 求距顶点v0的各顶点中最短路径长度最长的一个顶点
- ...
- 要求：
- 分析时间、空间复杂度
- 对上面的题目从以下角度扩展，如何求解呢？
- 要实现的功能：存在性/统计/找一个/找全部/输出路径...
- 使用图的哪种存储结构：邻接矩阵/邻接表/...
- 图的种类：有向图/无向图/有向网/无向网
- 结果的表现方式：全局变量/参数/返回值
- 无向图的连通分量和生成树：基于孩子-兄弟链的BFS(DFS)生成树(森林)的创建算法
[顶层]
- 布置综合实验
- 图的深(广)度优先遍历算法
- 深度优先搜索(DFS): 深度优先遍历序列、生成树/森林
- 广度优先搜索(BFS): 广度优先遍历序列、生成树/森林
- 基于抽象数据类型ADT Graph 的算法设计
- DFS:
栈／递归；BFS: 队列
- 需要使用顶点的访问标志数组：visited
- 基于某种存储类型的算法设计
- 注意FirstAdjVex,
NextAdjVex的实现
- 时间复杂度：邻接矩阵T(n)=O(n2),邻接表T(n)=O(n＋e)
- 空间复杂度：DFS－跟生成树的深度有关，BFS－跟生成树的宽度有关
- 给定一个图，其深度(广度)优先遍历序列不一定唯一。
- 给定一个图的存储表示，其深度(广度)优先遍历序列一定唯一。
[顶层]
- 图的定义和术语
- 子图、连通分量、生成树/森林
- 边(弧)数与顶点数间的关系：(有向)完全图、稀疏图、稠密图
- 网：边(弧)上附加有权值
- 图的存储结构: 邻接矩阵、
邻接表、十字链表(有向图)、邻接多重表(无向图)
注意：
1) 存储结构中保存的是顶点间的邻接关系，不是连通关系。
2) 十字链表是针对邻接表存储有向图(网)中的不足（邻接表只反映指定顶点的出边）而提出的。
搜索指定顶点的入边：从该顶点结点的firstin开始，顺着弧结点的hlink进行搜索；
若是搜索出边，则从顶点结点的firstout出发，顺着弧结点的tlink来搜索
3) 邻接多重表是针对邻接表存储无向图(网)中的不足（邻接表包含2e个结点，e为边数）而提出的。
- 图的创建：图的种类->顶点数和边(弧)数->顶点信息->边(弧)信息
- 图的遍历
[顶层]
- 树与等价问题
- 问题的描述：给定一个集合和作用在该集合上的一个等价关系，需要求该集合的一个等价类划分。
- 涉及集合的3个基本操作:由多个元素初始化多个集合、查找某元素所在的集合、两个集合的并集
- 集合的表示----双亲表示法表示的树
- 查找和并集操作的算法和时间复杂度
- 改进一：含成员少的子集树根结点指向含成员多的子集的根。
- 改进二：压缩路径
- 回溯法与树的遍历
- 回溯问题与树的先序遍历：n皇后问题
搜索过程是对某棵状态树的先序遍历，但是无须创建这棵树
- 求含n个元素的集合的幂集
----依次对集合中的元素“取”或“舍”
- 树的计数
- 概念: 树的相似、相等，树的计数问题
- 二叉树的计数问题:
从两种角度来解决这个问题：
1)按二叉树的结点数归纳来确定形态数；
2)转变为求先序序列均为12...n的二叉树所能得到的中序序列的数目＝>考虑入栈和出栈操作的合法序列的数目
- 树的计数问题:可以转化为对应的二叉树的计数问题
- 图的定义和术语：图的种类，邻接，路径与连通性
[顶层]
- 树和森林
- 树的存储结构: 孩子兄弟表示法
- 森林与二叉树的相互转换: 二叉链(孩子兄弟链～左右孩子链)
- 树和森林的遍历:
先根遍历(对应二叉树的先序遍历)，后根遍历(对应二叉树的中序遍历)
- 基于二叉链(孩子-兄弟链)的算法设计与应用
- 赫夫曼树及其应用
- 概念：树的路径长度、
树的带权路径长度、最优二叉树（赫夫曼树）
- 赫夫曼树的应用及构造算法
- 赫夫曼树的性质：结点的度(0或2)，结点数与高度的关系
- 赫夫曼编码——前缀编码
- 赫夫曼编码与译码的思想与实现：赫夫曼树用三叉静态链表存储，赫夫曼编码用动态分配的串存储
1) 给定一组符号及其权值，构造赫夫曼编码；
2) 编码：给定一个符号流和赫夫曼树以及赫夫曼编码，得到对应的编码串；
3) 译码：给定一个编码串和赫夫曼树以及赫夫曼编码，得到对应的符号流；
[顶层]
- 线索二叉树
- 概念:首先明确按什么次序进行线性化!
线索(指向结点前驱或后继的指针)、
线索链表(包含线索信息的链表)、
线索二叉树(加上线索的二叉树)、
线索化(对二叉树以某种次序遍历使其变成线索二叉树的过程)
- 几种线索二叉树: 注意其表示方法(利用二叉链中的空链域放线索，对二叉链进行结构扩展)
- 中序线索二叉树：结构对称
- 后序线索二叉树 vs. 先序线索二叉树：互为对称
- 与线索二叉树有关的算法
- 如何在线索二叉树中找指定结点的直接前驱/后继？
- 如何对二叉树进行线索化？
- 在线索二叉树上如何遍历？
- 如何快速找到二叉树在某种遍历次序下的第一个结点和最后一个结点？
- 树和森林
- 树的存储结构: 双亲表示法,孩子表示法,双亲-孩子表示法,孩子兄弟表示法
[顶层]
- 先序/中序/后序遍历二叉树的非递归算法: 辅助数据结构是栈
- 层次遍历算法: 辅助数据结构是队列
- 层次遍历算法的应用
- 如何判断一棵二叉树是否是完全二叉树?
- 如何找距指定结点最近或最远的叶子子孙？---问题延伸及解决
- 几种创建二叉树的方法（输入什么样的序列能唯一确定一棵二叉树？）
1)通过加虚结点，将二叉树补成完全二叉树，以所得完全二叉树的层次遍历序列为输入；
2)为二叉树中实际存在的结点补齐孩子，以所得的二叉树的层次遍历序列为输入；
3)为二叉树中实际存在的结点补齐孩子，以所得的二叉树的先序遍历序列为输入；
4)以二叉树的中序遍历序列和先序遍历为输入（假设二叉树中结点的值互不相同）；
5)以二叉树的中序遍历序列和后序遍历为输入（假设二叉树中结点的值互不相同）。
[顶层]
- 基于二叉树先/中/后序遍历算法的应用
- 遍历算法应用的特点：访问结点->结合具体问题利用结点的信息进行求解；
- 应用举例1：基于先序序列创建一棵二叉链表示的二叉树
- 应用举例2：统计二叉树中叶子结点的数目
展示结果的各种表示形式：返回值、变参、全局变量
- 应用举例3：释放二叉树的所有结点空间
- 应用举例4：删除并释放二叉树中以元素值为x的结点作为根的各子树
展示遍历次序对问题求解的影响
- 应用举例5：求位于二叉树先序序列中第k个位置的结点的值
展示如何处理多个输出结果和传递需要使用的中间结果
- 基于递归的算法设计中需要注意的问题
- (递归)调用函数时，要强调对函数调用结果的使用；
- 定义函数时，要保证从各个出口返回前都已经对结果进行了设置；
- 遍历次序对问题求解的影响；
- 如何处理多个结果?
- 如何传递中间结果?
- 注意分析时间复杂度和空间复杂度
[顶层]
- 树的定义和基本术语
注意：1) 终端结点为叶子结点；2) 非终端结点为分支结点，
包括根结点；3) 内部结点为除去根结点的分支结点
- 二叉树: 二叉树 vs. 度小于等于2的有序树
- 二叉树的定义和性质: 理解５个性质并拓展
注意: 各种树的递归定义
一棵具有n个结点(n>=0)XX树是指：
- 基本步：当n==0时，这是空的XX树；
- 归纳步：当n>0时，
- 有且仅有一个根结点root;
- 剩余的n-1个结点划分成m棵互不相交的子集（非空?），每个子集形成一棵XX树，这些树是否有次序？
- 针对每一个非空的子集形成的XX树，其根结点与root形成孩子和双亲之间的关系。
- 特殊的二叉树：满二叉树、完全二叉树
- 二叉树的存储结构：顺序存储、链式存储(二叉链、三叉链)
- 二叉树的遍历：先序、后序、中序、层次遍历
- 先/中/后序三种遍历的定义与特点
- 先/中/后序遍历算法的递归实现：时间、空间复杂度
假设二叉树中结点个数为n，高度为h，则T(n)=O(n), S(n,h)=O(h)
- 递归的注意点：递归处理的规律、递归的终止条件
- 递归函数的编写：从函数定义(求解,设置结果)和函数使用(使用函数调用的结果)两个角度考虑
[顶层]
- 线性表、栈、队列的总结
- 串
- 串是一种特殊的线性表
- 数据元素的类型是字符类型
- 操作的对象：数据元素(字符)—个体、数据元素的集合(子串)—整体
注意：空串(长度为0的串) vs. 空格串（空白串）
- 串的表示与实现：
- 定长顺序存储表示--串的顺序映像
- 堆分配存储表示--串的顺序映像，建立串名与串值的映像
- 块链存储表示--串的链式映像，存储密度
- 简单的串的模式匹配算法
- 串的应用(文本编辑、词索引表)
- 树和二叉树
[顶层]
- 离散事件模拟
- 银行排队叫号系统的设计与实现
- 本章小结
[顶层]
- 队列:定义、ADT
- 链队列：存储结构、基本操作的实现
- 循环队列：存储结构、基本操作的实现
重点：区分队空和队满的方法
- 布置第二次基本实验：
[顶层]
- 递归的定义：递归、递推、递归与递推的关系
- 递归的应用：递归函数求解、Hanoi塔求解
- 递归工作栈
- 递归与回溯：N皇后问题
[顶层]
- 栈：定义，ADT
- 顺序栈
- 栈的应用：数值转换、括号匹配、表达式求值
[顶层]
- 基于链表的算法设计（续）
- 一元多项式的表示及相加
- 本章内容回顾
[顶层]
- 动态链表与静态链表应用对比
- 双向链表的定义和基本操作实现（算法思想）
- 基于链表的算法设计
[顶层]
- 单链表的定义和基本操作
- 定义及基本操作的实现
- 在有头结点和无头结点的单链表上操作的区别
- 链表操作的算法设计小结
- 循环链表
- 静态链表
- 布置基础实验一
[顶层]
- C中的动态内存分配与释放函数
- 顺序表的基本操作的实现：基本操作的算法，时（空）间复杂度。
- 基于顺序表的算法设计：基于顺序表实现例2.1和2.2
- 顺序表的不足
[顶层]
- 伪C语言中的引用参数，C语言中标识符的辨别规则
- 线性表的类型定义：逻辑特征、ADT List、基于ADT List的算法设计
- 线性表的顺序表示：顺序表定义的两种方案
- 补充知识：可编程内存的几大部分：静态存储区、堆区和栈区。
[顶层]
- 伪C语言的简介
- 算法和算法分析
- 算法的定义、特点
- 算法的评价标准
- 时间复杂度、空间复杂度、（渐进）时间/空间复杂度
- 常见函数的增长率
[顶层]